Amplitude estimation and quantum Monte Carlo
Monte Carlo methods estimate an average by sampling: the price of an option, the dose a tumour receives in radiotherapy planning, the probability a protein folds a certain way. The error shrinks as one over the square root of the number of samples, so ten times more accuracy costs a hundred times more work. Quantum amplitude estimation shrinks the error as one over the number of samples. On paper, that is a quadratic speedup for one of the most widely used computational methods there is.
On the plate: error against number of samples, classical and quantum, on a log–log scale.
The problem
Suppose a quantum circuit prepares , where is the quantity you want, such as an expected payoff rescaled to lie between 0 and 1. Classically you would run and measure times, estimating with error about . Gilles Brassard, Peter Høyer, Michele Mosca and Alain Tapp showed in 2002 that phase estimation (Chapter 113) on the Grover operator built from (Chapter 115) gives error about after uses of . Established
Quadratically fewer samples
Set the target error to 3.0 (as ). Classical sampling needs about runs, a million for ; amplitude estimation about , about three thousand. Ashley Montanaro showed in 2015 how to extend this to general Monte Carlo with bounded variance.
Phase estimation needs deep circuits. Yohichi Suzuki and colleagues showed in 2020 that the same scaling can be reached without it: run Grover powers , measure each a few times, and combine all the results by maximum likelihood. That version is what current experiments run.
The crossover
Each quantum sample is far more expensive than a classical one: it is a whole fault-tolerant circuit, including state preparation and the payoff calculation done reversibly. Shouvanik Chakrabarti and colleagues estimated in 2021 what pricing a realistic financial derivative would need: about 8,000 logical qubits and a sequence of tens of millions of T gates, and logical gate speeds far faster than current projections to beat a classical cluster in useful time. Set the cost of one quantum sample relative to a classical one, 6.0 (as ), and see where the curves cross. Debated when, if ever, it pays.
What you now have
Amplitude estimation as phase estimation of a Grover operator, the versus scaling, maximum-likelihood amplitude estimation without phase estimation, and why the crossover with classical Monte Carlo depends on the overhead of each quantum sample.
· · ·
Three questions to carry with you.
And one to work out. For error , about how many uses of does amplitude estimation need, ?
Sources: G. Brassard, P. Høyer, M. Mosca and A. Tapp, Contemp. Math. 305, 53 (2002). A. Montanaro, Proc. R. Soc. A 471, 20150301 (2015). Y. Suzuki et al., Quantum Inf. Process. 19, 75 (2020). S. Chakrabarti et al., Quantum 5, 463 (2021). Checked by code: 1/ε² = 10⁶ and π/ε = 3142 at ε = 10⁻³.