116
Part Three · B · Algorithms

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 A\mathcal A prepares a ∣good⟩+1−a ∣bad⟩\sqrt a\,|\text{good}\rangle + \sqrt{1-a}\,|\text{bad}\rangle, where aa is the quantity you want, such as an expected payoff rescaled to lie between 0 and 1. Classically you would run A\mathcal A and measure MM times, estimating aa with error about a(1−a)/M\sqrt{a(1-a)/M}. Gilles Brassard, Peter Høyer, Michele Mosca and Alain Tapp showed in 2002 that phase estimation (Chapter 113) on the Grover operator built from A\mathcal A (Chapter 115) gives error about π/M\pi/M after MM uses of A\mathcal A. Established

Quadratically fewer samples

Set the target error to 3.0 (as 10−x10^{-x}). Classical sampling needs about 1/ε21/\varepsilon^2 runs, a million for 10−310^{-3}; amplitude estimation about π/ε\pi/\varepsilon, 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 0,1,2,4,…0, 1, 2, 4, \dots, 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 10x10^x), 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 1/ε1/\varepsilon versus 1/ε21/\varepsilon^2 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.

How does classical Monte Carlo error scale with samples?tap
As 1/√M.
How does amplitude estimation scale?tap
As 1/M, a quadratic improvement.
Why might it not help in practice?tap
Each quantum sample costs many orders of magnitude more time than a classical one.

And one to work out. For error ε=10−3\varepsilon = 10^{-3}, about how many uses of A\mathcal A does amplitude estimation need, π/ε\pi/\varepsilon?

M ≈

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⁻³.

Next · Chapter 117
Quantum walks and element distinctness

A quantum walker spreads quadratically faster than a random one, and on special graphs exponentially faster.

Turn the page