On the quantum complexity of approximating median of continuous distribution

Abstract

We consider approximating of the median of absolutely continuous distribution given by a probability density function $f$. We assume that $f$ has $r$ continuous derivatives, with derivative of order $r$ being Hölder continuous with the exponent $\rho$. We study the $\epsilon$-complexity of this problem in the quantum setting. We show that the $\epsilon$-complexity up to logarithmic factor is of order ${\epsilon }^{-1/((r+\rho +1))}$.

17 pages

References in corpus (1)

• A Quantum Algorithm for Finding the Minimum