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

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.