Mean estimation when you have the source code; or, quantum Monte Carlo methods
share
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.
READ FULL TEXT