On the quantum complexity of approximating median of continuous distribution
arXiv:1811.10017h-index: 1
Originality Incremental advance
AI Analysis
Provides a complexity bound for quantum algorithms approximating medians, relevant for quantum computing and numerical analysis.
The paper studies the quantum complexity of approximating the median of a continuous distribution with smooth density, showing that the ε-complexity scales as ε^{-1/((r+ρ+1))} up to logarithmic factors.
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 $ρ$. We study the $ε$-complexity of this problem in the quantum setting. We show that the $ε$-complexity up to logarithmic factor is of order $ε^{-1/((r+ρ+1))}$.