Near-Optimal Quantum Algorithms for Multivariate Mean Estimation
arXiv:2111.09787 · doi:10.1145/3519935.3520045
Abstract
We propose the first near-optimal quantum algorithm for estimating in Euclidean norm the mean of a vector-valued random variable with finite mean and covariance. Our result aims at extending the theory of multivariate sub-Gaussian estimators to the quantum setting. Unlike classically, where any univariate estimator can be turned into a multivariate estimator with at most a logarithmic overhead in the dimension, no similar result can be proved in the quantum setting. Indeed, Heinrich ruled out the existence of a quantum advantage for the mean estimation problem when the sample complexity is smaller than the dimension. Our main result is to show that, outside this low-precision regime, there is a quantum estimator that outperforms any classical estimator. Our approach is substantially more involved than in the univariate setting, where most quantum estimators rely only on phase estimation. We exploit a variety of additional algorithmic techniques such as amplitude amplification, the Bernstein-Vazirani algorithm, and quantum singular value transformation. Our analysis also uses concentration inequalities for multivariate truncated statistics. We develop our quantum estimators in two different input models that showed up in the literature before. The first one provides coherent access to the binary representation of the random variable and it encompasses the classical setting. In the second model, the random variable is directly encoded into the phases of quantum registers. This model arises naturally in many quantum algorithms but it is often incomparable to having classical samples. We adapt our techniques to these two settings and we show that the second model is strictly weaker for solving the mean estimation problem. Finally, we describe several applications of our algorithms, notably in measuring the expectation values of commuting observables and in the field of machine learning.
arXiv comment35 pages, 1 figure; v2: minor changes
References in corpus (26)
- Quantum Circuit Learning
- Quantum Amplitude Amplification and Estimation
- Predicting Many Properties of a Quantum System from Very Few Measurements
- Parameterized quantum circuits as machine learning models
- Tight bounds on quantum searching
- Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
- Quantum measurements and the Abelian Stabilizer Problem
- A Quantum Algorithm for Finding the Minimum
- Quantum speedup of Monte Carlo methods
- Optimal Quantum Measurements of Expectation Values of Observables
- Quantum agents in the Gym: a variational quantum algorithm for deep Q-learning
- Tomography and Generative Data Modeling via Quantum Boltzmann Training
- Quantum query complexity of state conversion
- Fast quantum algorithm for numerical gradient estimation
- Optimizing quantum optimization algorithms via faster quantum gradient computation
- Quantum Speed-up for Approximating Partition Functions
- Quantum Sub-Gaussian Mean Estimator
- Fast quantum algorithms for numerical integrals and stochastic processes
- Quantum enhancements for deep reinforcement learning in large spaces
- Quantum algorithms for testing properties of distributions
- Generative training of quantum Boltzmann machines with hidden units
- How many functions can be distinguished with k quantum queries?
- An optimal quantum algorithm to approximate the mean and its application for approximating the median of a set of points over an arbitrary distance
- Near-Optimal Quantum Algorithms for Multivariate Mean Estimation
- Variations on Quantum Adversary
- Quantum algorithms for multivariate Monte Carlo estimation
Cited by in corpus (6)
- Quantum computing for finance
- Challenges and Opportunities in Quantum Optimization
- Fault-tolerant quantum computation of molecular observables
- Near-Optimal Quantum Algorithms for Multivariate Mean Estimation
- A Sublinear-Time Quantum Algorithm for Approximating Partition Functions
- On Quantum Perceptron Learning via Quantum Search