Near-Optimal Quantum Algorithms for Multivariate Mean Estimation
The topic of the next session:
Topic
- Title: Near-Optimal Quantum Algorithms for Multivariate Mean Estimation
- Presenter: Jakab Csatári
- Language: Hungarian
- Paper: https://arxiv.org/abs/2111.09787
Coordinates
- Time: 2024 April 11, Thursday 16:15 (1 hour + questions)
- Place: BME Building I, IB134 (inside the SZIT department)
Abstract
Based on the article of Arjan Cornelissen, Yassine Hamoudi and Sofiene Jerbi, we will look into the problem of estimating in Euclidean norm the mean of a vector-valued random variable with finite mean and covariance. 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. Previously S. Heinrich ruled out the existence of a quantum advantage for the mean estimation problem when the sample complexity is smaller than the dimension. [https://doi.org/10.1006/jcom.2001.0629] The main result of the authors is to show that, outside this low-precision regime, there is a quantum estimator that outperforms any classical estimator. Their approach is substantially more involved than in the univariate setting, where most quantum estimators rely only on phase estimation, exploiting a variety of additional algorithmic techniques such as amplitude amplification, the Bernstein-Vazirani algorithm, and quantum singular value transformation.