  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.
