Abstract
Suppose y 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 y). We give a quantum procedure that runs the code O(n) times and returns an estimate μ for μ = E[y] that with high probability satisfies |μ - μ| ≤ σ/n, where σ = stddev[y]. This dependence on n is optimal for quantum algorithms. One may compare with classical algorithms, which can only achieve the quadratically worse |μ - μ| ≤ σ/√n. Our method improves upon previous works, which either made additional assumptions about y, 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.