Quantum Sub-Gaussian Mean Estimator

08/27/2021
by   Yassine Hamoudi, et al.
0

We present a new quantum algorithm for estimating the mean of a real-valued random variable obtained as the output of a quantum computation. Our estimator achieves a nearly-optimal quadratic speedup over the number of classical i.i.d. samples needed to estimate the mean of a heavy-tailed distribution with a sub-Gaussian error rate. This result subsumes (up to logarithmic factors) earlier works on the mean estimation problem that were not optimal for heavy-tailed distributions [BHMT02,BDGT11], or that require prior information on the variance [Hein02,Mon15,HM19]. As an application, we obtain new quantum algorithms for the (ϵ,δ)-approximation problem with an optimal dependence on the coefficient of variation of the input random variable.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset