mlsanityData to 7 Oct 2026

Quantum Sub-Gaussian Mean Estimator

arXiv 2108.12172 ↗First posted 27 Aug 2021quant-ph cs.CC cs.DScited by 15

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 15 papers in the map (data through 7 Oct 2026). Builds on 6 of its 43 references that are in the map. First posted on arXiv 27 Aug 2021.

Builds on

6 of 43 references.

References · 6

  1. 2019Mean estimation and regression under heavy-tailed distributions--a surveycited by 133
  2. 2018Mean Estimation with Sub-Gaussian Rates in Polynomial Timecited by 33
  3. 2016Optimal Quantum Sample Complexity of Learning Algorithmscited by 32
  4. 2017Quantum SDP-Solvers: Better upper and lower boundscited by 27
  5. 2017Quantum query complexity of entropy estimationcited by 11
  6. 2018Quantum Chebyshev's Inequality and Applicationscited by 10

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 3; 2023: 4; 2024: 1; 2025: 4; 2026: 1.

15 papers.

Sort:

By area:

  1. 2021Quantum Algorithms for Reinforcement Learning with a Generative Modelcited by 24
  2. 2021Near-Optimal Quantum Algorithms for Multivariate Mean Estimationcited by 16
  3. 2022Quantum policy gradient algorithmscited by 15
  4. 2022Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Banditscited by 11
  5. 2023Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regretcited by 9
  6. 2023Quantum Heavy-tailed Banditscited by 7
  7. 2023Quantum Computing Provides Exponential Regret Improvement in Episodic Reinforcement Learningcited by 6
  8. 2022A Sublinear-Time Quantum Algorithm for Approximating Partition Functionscited by 5
  9. 2025Accelerating Quantum Reinforcement Learning with a Quantum Natural Policy Gradient Based Approachcited by 4
  10. 2023Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward Markov Decision Processescited by 3
  11. 2024Quantum Algorithms and Lower Bounds for Finite-Sum Optimizationcited by 3
  12. 2025Wavefunction Flows: Efficient Quantum Simulation of Continuous Flow Modelscited by 3
3 more
  1. 2025A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Modelcited by 1
  2. 2025Quantum speedup of non-linear Monte Carlo problemscited by 0
  3. 2026Improved Quantum Algorithms for Reinforcement Learning Under a Generative Modelcited by 0