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 |µ'-µ| = s/n, where s = stddev[y]. This dependence on n is optimal for quantum algorithms. One may compare with classical algorithms, which can only achieve the quadratically worse |µ'-µ| = s/vn. Our method improves upon previous works, which either made additional assumptions about y, and/or assumed the algorithm knew an a priori bound on s, and/or used additional logarithmic factors beyond O(n). The central subroutine for our result is essentially Grover’s algorithm but with complex phases. This is joint work with Ryan O'Donnell and can be found at https://arxiv.org/abs/2208.07544.
Copyright. All Rights Reserved.