Near-Optimal Quantum Algorithms for Multivariate Mean Estimation

Understand

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.