Mean Estimation When You Have the Source Code; or, Quantum Monte Carlo Methods

Explore a quantum procedure for mean estimation in random variables presented by Robin Kothari of Google at IPAM's Quantum Algorithms for Scientific Computation Workshop. Delve into an innovative approach that achieves optimal dependence on n for quantum algorithms, outperforming classical methods. Discover how this technique improves upon previous works by eliminating additional assumptions and logarithmic factors. Examine the central subroutine, which adapts Grover's algorithm with complex phases, and understand its application in estimating the mean of a real random variable given access to its generating code. Learn about the procedure's ability to achieve high-probability estimates with significantly better precision than classical algorithms. Gain insights into the implications of this research for quantum Monte Carlo methods and its potential impact on scientific computation.