ON THE QUANTUM COMPLEXITY OF COMPUTING THE MEDIAN OF CONTINUOUS DISTRIBUTIONS

We study the approximation of the median of an absolutely continuous distribution with respect to the Lebesgue measure given by a probability density function f. We assume that f has r continuous derivatives, with derivative of order r being Holder continuous with the exponent rho. We study the quantum query complexity of this problem. We show that the epsilon-complexity up to a logarithmic factor is of order epsilon(-1/ (r+rho+1)). We also extend the results to the problem of computing the vector of quantiles of an absolutely continuous distribution.