# Mean estimation when you have the source code; or, quantum Monte Carlo methods

arXiv: https://arxiv.org/abs/2208.07544 · HTML: https://mlsanity.com/paper/2208.07544/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Aug 2022.

## Built on by (most cited first, 6 of 6)

- [Quantum Algorithms and Lower Bounds for Finite-Sum Optimization](https://mlsanity.com/paper/2406.03006/) (2024)
- [Wavefunction Flows: Efficient Quantum Simulation of Continuous Flow Models](https://mlsanity.com/paper/2510.08462/) (2025)
- [Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexities](https://mlsanity.com/paper/2507.04438/) (2025)
- [A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model](https://mlsanity.com/paper/2507.22854/) (2025)
- [Quantum speedup of non-linear Monte Carlo problems](https://mlsanity.com/paper/2502.05094/) (2025)
- [Improved Quantum Algorithms for Reinforcement Learning Under a Generative Model](https://mlsanity.com/paper/2608.02826/) (2026)

## Abstract (arXiv)

Suppose boldsymboly is a real random variable, and one is given access to ``the code'' that generates it (for example, a randomized or quantum circuit whose output is boldsymboly). We give a quantum procedure that runs the code O(n) times and returns an estimate widehatboldsymbolμ for μ = E[boldsymboly] that with high probability satisfies |widehatboldsymbolμ - μ| ≤ σ/n, where σ = stddev[boldsymboly]. This dependence on n is optimal for quantum algorithms. One may compare with classical algorithms, which can only achieve the quadratically worse |widehatboldsymbolμ - μ| ≤ σ/√n. Our method improves upon previous works, which either made additional assumptions about boldsymboly, and/or assumed the algorithm knew an a priori bound on σ, and/or used additional logarithmic factors beyond O(n). The central subroutine for our result is essentially Grover's algorithm but with complex phases.ally Grover's algorithm but with complex phases.