Quantum Sub-Gaussian Mean Estimator

Abstract

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 $(\epsilon ,\delta )$-approximation problem with an optimal dependence on the coefficient of variation of the input random variable.

20 pages

Cited by in corpus (13)

• Prospects and challenges of quantum finance
• Long-range coupling and scalable architecture for superconducting flux qubits
• Quantum Computing for Fusion Energy Science Applications
• Quantum algorithm for credit valuation adjustments
• Near-Optimal Quantum Algorithms for Multivariate Mean Estimation
• Towards Large-Scale Quantum Computation
• A Sublinear-Time Quantum Algorithm for Approximating Partition Functions
• Approximation of Various Quantum Query Types
• Theoretical Analyses of Quantum Counting against Decoherence Errors
• Basic quantum subroutines: finding multiple marked elements and summing numbers
• Cosine series quantum sampling method with applications in signal and image processing
• Voronoi Diagrams for Quantum States and Its Application to a Numerical Estimation of a Quantum Channel Capacity
• A mass-energy-conserving discontinuous Galerkin scheme for the isotropic multispecies Rosenbluth--Fokker--Planck equation