Suppose $\boldsymbol{ 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 $\boldsymbol{ y}$). We give a quantum procedure that runs the code $O(n)$ times and returns an estimate $\widehat{ \boldsymbol{ \mu}}$ for $\mu = \mathrm{ E}[\boldsymbol{ y}]$ that with high probability satisfies $|\widehat{ \boldsymbol{ \mu}} - \mu| \leq \sigma/n$, where $\sigma = \mathrm{ stddev}[\boldsymbol{ y}]$. This dependence on $n$ is optimal for quantum algorithms. One may compare with classical algorithms, which can only achieve the quadratically worse $|\widehat{ \boldsymbol{ \mu}} - \mu| \leq \sigma/\sqrt{ n}$. Our method improves upon previous works, which either made additional assumptions about $\boldsymbol{ y}$, and/or assumed the algorithm knew an a priori bound on $\sigma$, 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.
Categories: quant-ph cs.CC cs.DS math.PR math.ST stat.TH