Amplitude Estimation & Quantum Counting
Quadratic speedups for Monte Carlo.
Monte Carlo estimates converge like : a hundred times more work for one more digit. Run phase estimation on the Grover iterate instead and the error falls like . That is amplitude estimation, a quadratic speedup for estimating probabilities, counts and averages.
What you’ll learn
- Explain why sampling needs repetitions and how the amplification iterate's eigenphases encode an amplitude.
- Derive amplitude estimation and its error bound .
- Apply it to quantum counting and to Monte Carlo mean estimation, with the right caveats.
- Describe phase-estimation-free variants and the optimality of the scaling.
From sampling to phases
Let , with good outcomes flagged. Classically, run and measure times: the observed frequency has standard deviation , so additive error costs samples, and no method that only sees samples does better.
The quantum route: the amplification iterate rotates the plane by , where and . Its eigenvalues there are , and (see The Geometry of Grover & Optimal Iterations). So is written into an eigenphase, and phase estimation reads eigenphases.
You estimate by classical sampling until the standard error reaches . How many samples does that take, in thousands?
Show the answer
210 thousand
. Amplitude estimation reaches error about with applications of , succeeding with probability at least .
The algorithm and its error bound
Prepare control qubits in uniform superposition and run on the main register.
Controlled powers , controlled by bit , kick the eigenphase back onto the control register, separately for each eigenvector: applications of in total.
The inverse QFT turns each phase ramp into a peak, as in phase estimation with eigenphases .
Both peaks give the same estimate, because .
You double the number of oracle evaluations in amplitude estimation. The error bound
- is unchanged
- shrinks by about
- shrinks by about
- shrinks by about
Show the answer
C. shrinks by about
The leading term is inversely proportional to . Doubling classical samples shrinks the standard error only by : that is the quadratic speedup.
Quantum counting
Run amplitude estimation with and the search oracle. Then , where is the number of marked items (we write because now counts queries). Multiplying the error bound by :
With queries the error is at most . An estimate within relative error needs queries, even when is unknown (increase geometrically until the estimate stabilizes), and Nayak and Wu (1999) proved such query counts optimal. Knowing roughly fixes the Grover schedule , and deciding versus is search itself.
Monte Carlo, and avoiding phase estimation
Bounded outputs. Write a randomized algorithm as a unitary that prepares its random coins in superposition and computes its output into a register. Append a controlled rotation . The probability of reading is exactly , so amplitude estimation returns using applications of and , versus classical runs.
Without phase estimation. The controlled- ladder and the inverse QFT are expensive. Alternatives measure directly, which reads "good" with probability , for a schedule of values, and infer classically: maximum-likelihood amplitude estimation (Suzuki et al. 2020), iterative amplitude estimation (Grinko et al. 2021), and the simplified approximate counting of Aaronson and Rall (2020). They keep the scaling, up to logarithmic factors, with no extra control register.
Key takeaways
- The amplification iterate has eigenphases with ; phase estimation reads and returns .
- The error is at most with probability at least : queries versus samples, and this is optimal.
- Quantum counting estimates the number of marked items to with queries; mean estimation achieves .
- Phase-estimation-free variants keep the scaling with simpler circuits; practical advantage hinges on depth and error-correction overhead.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
To halve the error, classical sampling needs about ___ times more samples, and amplitude estimation about ___ times more oracle evaluations.
- ;
- ;
- ;
- ;
Show the answer
B. ;
Sampling error scales like , so halving it takes the samples. Amplitude-estimation error scales like , so halving it takes the queries.
Amplitude estimation sometimes returns and sometimes . Why do both give the same estimate ?
- The QFT always produces outcomes in symmetric pairs
- Measurement noise flips the bits of
- Because in every application
- is an equal superposition of two eigenvectors of with eigenphases , and cannot tell them apart
Show the answer
D. is an equal superposition of two eigenvectors of with eigenphases , and cannot tell them apart
The two eigenvectors carry phases . Phase estimation finds or , and maps both to the same .
Quantum counting with queries estimates the number of marked items to within
- , independently of
Show the answer
A.
The bound with gives .
Which statement about the quantum speedup for Monte Carlo is accurate?
- It is exponential in the number of samples
- It needs only one qubit of quantum memory
- Each "sample" is a coherent run of the whole randomized algorithm, and the runs are sequential, so depth grows like
- It applies only to Gaussian distributions
Show the answer
C. Each "sample" is a coherent run of the whole randomized algorithm, and the runs are sequential, so depth grows like
The speedup is quadratic, versus , and it requires running the sampler reversibly in superposition, inside a deep sequential circuit.
Further reading
- G. Brassard, P. Høyer, M. Mosca & A. Tapp, "Quantum amplitude amplification and estimation", Contemporary Mathematics 305, 53–74 (2002); arXiv:quant-ph/0005055.
- G. Brassard, P. Høyer & A. Tapp, "Quantum counting", Proc. ICALP 1998, Lecture Notes in Computer Science 1443 (1998).
- A. Montanaro, "Quantum speedup of Monte Carlo methods", Proc. R. Soc. A 471, 20150301 (2015).
- Y. Suzuki, S. Uno, R. Raymond, T. Tanaka, T. Onodera & N. Yamamoto, "Amplitude estimation without phase estimation", Quantum Information Processing 19, 75 (2020).
- D. Grinko, J. Gacon, C. Zoufal & S. Woerner, "Iterative quantum amplitude estimation", npj Quantum Information 7, 52 (2021).