Quantum Mean Estimation

Overview

Estimating the average value of a random quantity is one of the most common tasks in statistics. You draw samples, add them up, and divide. The classical error shrinks like the standard deviation divided by the square root of the number of samples, so halving the error costs four times as many samples. Quantum mean estimation reaches the same accuracy with a number of quantum samples proportional only to the standard deviation divided by the target error, which is a quadratic saving.

This page focuses on the statistical side of the problem: what assumptions are needed, what happens for random variables with heavy tails or unknown spread, and how close the best quantum algorithms come to the proven lower bound. The companion pages on amplitude estimation and Monte Carlo integration describe the circuits and the finance applications.

The problem it solves

Classically, estimating a mean to precision ε requires O(1/ε²) samples. Quantum mean estimation achieves this with O(1/ε) quantum samples.

History and background

Early work on quantum approaches to estimating means and medians came from Grover in 1998 and from Heinrich's study of quantum summation in 2002, which analyzed how the quantum cost of integration scales for different function classes. Nayak and Wu proved in 1999 that approximating the mean of a bounded quantity to precision epsilon needs at least about 1 over epsilon quantum queries, so the quadratic improvement cannot be beaten in general.

Montanaro's 2015 paper, Quantum Speedup of Monte Carlo Methods, gave a general algorithm for random variables whose variance is bounded, achieving a cost of about sigma over epsilon up to logarithmic factors. Hamoudi and Magniez extended the approach to relative error in 2019, Hamoudi gave a sub-Gaussian-style estimator in 2021, Cornelissen, Hamoudi, and Jerbi gave near-optimal multivariate estimators in 2022, and Kothari and O'Donnell removed the logarithmic factors in a 2023 paper that treats the random variable as an algorithm whose source code is available to the quantum computer.

How it works

Uses quantum amplitude estimation (which itself uses amplitude amplification and phase estimation) to encode the mean as a quantum amplitude and estimate it with quadratic fewer queries.

A random variable can be thought of as the output of a procedure that uses randomness. Suppose we can run that procedure coherently, so that all possible random choices are held in superposition together with the output. This is the access model in which quantum speedups are proved. It is natural for quantum simulations and for random variables defined by simple formulas, but it is a restriction compared with having only a black-box sampler.

If the variable takes values between 0 and 1, the mean is just the probability of a good outcome after a rotation, and amplitude estimation gives it to error epsilon with about 1 over epsilon runs. The harder case is when values are unbounded. Then a few rare, large values can dominate the mean, and a naive scaling would make the problem look harder than it is.

Montanaro's idea is to split the values into scales, such as values near 1, values near 2, 4, 8, and so on. Each scale is bounded, so amplitude estimation applies. The variance bound limits how much weight the large scales can carry, so only a few scales need accurate estimates. Combining them gives the mean with a cost that depends on the standard deviation rather than the maximum value.

Step by step

1. Specify the random variable as a quantum procedure A that prepares a superposition over random inputs and writes the output value into a register.
2. Obtain or assume a bound on the variance, or a bound on the second moment, as the algorithm needs a scale for the estimation.
3. Remove the mean's dominant part by estimating a rough value first, using a coarse quantum estimate with a small number of samples.
4. Split the shifted values into dyadic scales, and for each scale build a bounded variable by truncating and rescaling.
5. Run amplitude estimation on each bounded variable, with accuracy chosen so that the total error across scales stays below epsilon.
6. Add the scaled estimates to obtain the mean, and repeat the whole procedure a few times with a median to boost the confidence.

A worked example

Suppose a random variable has standard deviation 10 and you want the mean to within 0.01. A classical estimator needs about 10 squared over 0.01 squared samples, which is one million samples. The quantum estimator needs about 10 over 0.01, which is one thousand coherent uses of the sampling procedure, up to logarithmic factors.

If a few rare outcomes are huge, a plain average would have a heavy tail, and classical methods need tricks such as median of means to get reliable estimates. The quantum algorithm handles the same variable by treating the huge outcomes in their own scales, where they have small probabilities and are cheap to estimate.

Complexity and resources

What hardware it needs

• Fault-tolerant hardware capable of running the sampling circuit and its inverse many times coherently.
• Efficient implementations of the random variable as a reversible circuit.
• Classical post-processing to combine scales and compute medians.

Applications

• Estimating expected payoffs, risk measures, and moments in finance.
• Estimating expectation values of observables in quantum simulation.
• Statistical estimation in physics and engineering where the random variable is defined by a simulation.
• Subroutine inside quantum algorithms for optimization and machine learning that need averages.

Limitations and caveats

• The advantage is quadratic, and the coherent access model can be expensive to realize.
• Classical methods such as median of means and quasi-Monte Carlo already do well on many problems.
• Black-box sampling access without coherent control gives no speedup.
• Logarithmic factors and constants matter in practice.

Common misconceptions

• Quantum mean estimation does not apply to data given as a list of classical samples. It needs a coherent procedure that generates the random variable.
• It does not beat the lower bound. A quadratic speedup is the best possible in general.
• It is not specific to finance. It is a general statistical primitive.

How it compares

• The sample mean needs one over epsilon squared samples and works for any access model.
• Median of means gives reliable estimates for heavy-tailed variables classically, with sub-Gaussian error bounds.
• Quantum amplitude estimation is the building block for bounded variables, and mean estimation extends it to unbounded ones.

Real-world impact

Directly relevant to financial derivatives pricing and risk analysis — one of the most credible near-term quantum speedups for finance, actively piloted by Goldman Sachs, JPMorgan, and others.

Why it matters

Because so many tasks reduce to estimating averages, mean estimation is the cleanest statement of the quadratic speedup that quantum computers can offer for sampling-based computation. The matching lower bound shows exactly how much can be gained.

The recent work on multivariate and heavy-tailed cases also moves quantum Monte Carlo from textbook examples toward practical statistics, where the properties of real random variables matter.

Frequently asked questions

Keep learning

• Related algorithm: Quantum Amplitude Estimation
• Related algorithm: Quantum Monte Carlo Integration
• Related algorithm: Quantum Approximate Counting
• Related algorithm: Quantum Counting

This page is written for educational purposes. Complexity statements describe the best known results at the time of review (September 30, 2026), and research in this area moves quickly, so check recent papers before relying on a specific bound.

← Back to Algorithms Database