  We present a new quantum algorithm for estimating the mean of a real-valued
random variable obtained as the output of a quantum computation. Our estimator
achieves a nearly-optimal quadratic speedup over the number of classical i.i.d.
samples needed to estimate the mean of a heavy-tailed distribution with a
sub-Gaussian error rate. This result subsumes (up to logarithmic factors)
earlier works on the mean estimation problem that were not optimal for
heavy-tailed distributions [BHMT02,BDGT11], or that require prior information
on the variance [Hein02,Mon15,HM19]. As an application, we obtain new quantum
algorithms for the $(\epsilon,\delta)$-approximation problem with an optimal
dependence on the coefficient of variation of the input random variable.
