Simple Algorithm
Quantum Computing · Rydberg State · 30 min

Amplitude Estimation & Quantum Counting

Quadratic speedups for Monte Carlo.

Monte Carlo estimates converge like 1/samples1/\sqrt{\text{samples}}: a hundred times more work for one more digit. Run phase estimation on the Grover iterate instead and the error falls like 1/queries1/\text{queries}. That is amplitude estimation, a quadratic speedup for estimating probabilities, counts and averages.

What you’ll learn

  • Explain why sampling needs Θ(1/ε2)\Theta(1/\varepsilon^2) repetitions and how the amplification iterate's eigenphases encode an amplitude.
  • Derive amplitude estimation and its error bound 2πa(1−a)/M+π2/M22\pi\sqrt{a(1-a)}/M+\pi^2/M^2.
  • 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 1/ε1/\varepsilon scaling.

From sampling to phases

Let A∣0⟩=a ∣good⟩+1−a ∣bad⟩\mathcal A\ket0=\sqrt a\,\ket{\text{good}}+\sqrt{1-a}\,\ket{\text{bad}}, with good outcomes flagged. Classically, run A\mathcal A and measure nn times: the observed frequency has standard deviation a(1−a)/n\sqrt{a(1-a)/n}, so additive error ε\varepsilon costs n=Θ(a(1−a)/ε2)n=\Theta(a(1-a)/\varepsilon^2) samples, and no method that only sees samples does better.

The quantum route: the amplification iterate Q=−AS0A−1SχQ=-\mathcal AS_0\mathcal A^{-1}S_\chi rotates the plane span{∣good⟩,∣bad⟩}\mathrm{span}\{\ket{\text{good}},\ket{\text{bad}}\} by 2θa2\theta_a, where sin⁡2θa=a\sin^2\theta_a=a and 0≤θa≤π20\le\theta_a\le\frac\pi2. Its eigenvalues there are e±2iθae^{\pm2i\theta_a}, and A∣0⟩=12(eiθa∣ψ+⟩+e−iθa∣ψ−⟩)\mathcal A\ket0=\frac{1}{\sqrt2}\big(e^{i\theta_a}\ket{\psi_+}+e^{-i\theta_a}\ket{\psi_-}\big) (see The Geometry of Grover & Optimal Iterations). So aa is written into an eigenphase, and phase estimation reads eigenphases.

Predict before you look

You estimate a≈0.3a\approx0.3 by classical sampling until the standard error a(1−a)/n\sqrt{a(1-a)/n} reaches 0.0010.001. How many samples does that take, in thousands?

Show the answer

210 thousand

n=a(1−a)/ε2=0.21/10−6=210,000n=a(1-a)/\varepsilon^2=0.21/10^{-6}=210{,}000. Amplitude estimation reaches error about 2πa(1−a)/M≈0.0012\pi\sqrt{a(1-a)}/M\approx0.001 with M≈2,900M\approx2{,}900 applications of QQ, succeeding with probability at least 8/π2≈81%8/\pi^2\approx81\%.

The algorithm and its error bound

DerivationAmplitude estimation
  1. 1M∑j=0M−1∣j⟩⊗A∣0⟩\frac{1}{\sqrt M}\sum_{j=0}^{M-1}\ket{j}\otimes\mathcal A\ket0

    Prepare log⁡2M\log_2M control qubits in uniform superposition and run A\mathcal A on the main register.

  2. → ∑j∣j⟩ ⁣⟨j∣⊗Qj  12∑±e±iθa(1M∑j=0M−1e±2ijθa∣j⟩)⊗∣ψ±⟩\xrightarrow{\ \sum_j\dyad{j}\otimes Q^j\ }\ \frac{1}{\sqrt2}\sum_\pm e^{\pm i\theta_a}\Big(\frac{1}{\sqrt M}\sum_{j=0}^{M-1}e^{\pm2ij\theta_a}\ket{j}\Big)\otimes\ket{\psi_\pm}

    Controlled powers Q2lQ^{2^l}, controlled by bit ll, kick the eigenphase back onto the control register, separately for each eigenvector: M−1M-1 applications of QQ in total.

  3. → QFTM−1  peaks at y≈M θaπ  and  y≈M(1−θaπ)\xrightarrow{\ \mathrm{QFT}_M^{-1}\ }\ \text{peaks at } y\approx M\,\frac{\theta_a}{\pi}\ \text{ and }\ y\approx M\Big(1-\frac{\theta_a}{\pi}\Big)

    The inverse QFT turns each phase ramp into a peak, as in phase estimation with eigenphases ±θa/π(mod1)\pm\theta_a/\pi \pmod 1.

  4. a~=sin⁡2(πyM)\tilde a=\sin^2\Big(\frac{\pi y}{M}\Big)

    Both peaks give the same estimate, because sin⁡2(π−ϕ)=sin⁡2ϕ\sin^2(\pi-\phi)=\sin^2\phi.

Check your understanding

You double the number MM of oracle evaluations in amplitude estimation. The error bound

  1. is unchanged
  2. shrinks by about 2\sqrt2
  3. shrinks by about 22
  4. shrinks by about 44
Show the answer

C. shrinks by about 22

The leading term 2πa(1−a)/M2\pi\sqrt{a(1-a)}/M is inversely proportional to MM. Doubling classical samples shrinks the standard error only by 2\sqrt2: that is the quadratic speedup.

Quantum counting

Run amplitude estimation with A=H⊗n\mathcal A=H^{\otimes n} and the search oracle. Then a=K/Na=K/N, where KK is the number of marked items (we write KK because MM now counts queries). Multiplying the error bound by NN:

∣K~−K∣ ≤ 2πK(N−K)M+π2NM2with probability at least 8π2.\abs{\tilde K-K}\ \le\ \frac{2\pi\sqrt{K(N-K)}}{M}+\frac{\pi^2N}{M^2}\qquad\text{with probability at least }\frac{8}{\pi^2}.
Quantum counting (Brassard, Høyer & Tapp 1998).

With M=cNM=c\sqrt N queries the error is at most 2πcK+π2c2=O(K)\frac{2\pi}{c}\sqrt K+\frac{\pi^2}{c^2}=O(\sqrt K). An estimate within relative error ε\varepsilon needs O(1εN/K)O\big(\frac1\varepsilon\sqrt{N/K}\big) queries, even when KK is unknown (increase MM geometrically until the estimate stabilizes), and Nayak and Wu (1999) proved such query counts optimal. Knowing KK roughly fixes the Grover schedule k≈π4N/Kk\approx\frac\pi4\sqrt{N/K}, and deciding K=0K=0 versus K≥1K\ge1 is search itself.

Monte Carlo, and avoiding phase estimation

Bounded outputs. Write a randomized algorithm as a unitary R\mathcal R that prepares its random coins in superposition and computes its output v∈[0,1]v\in[0,1] into a register. Append a controlled rotation ∣v⟩∣0⟩↦∣v⟩(1−v ∣0⟩+v ∣1⟩)\ket{v}\ket0\mapsto\ket{v}\big(\sqrt{1-v}\,\ket0+\sqrt v\,\ket1\big). The probability of reading 11 is exactly E[v]\mathbb E[v], so amplitude estimation returns E[v]±ε\mathbb E[v]\pm\varepsilon using O(1/ε)O(1/\varepsilon) applications of R\mathcal R and R−1\mathcal R^{-1}, versus Θ(1/ε2)\Theta(1/\varepsilon^2) classical runs.

Without phase estimation. The controlled-QjQ^j ladder and the inverse QFT are expensive. Alternatives measure QkA∣0⟩Q^k\mathcal A\ket0 directly, which reads "good" with probability sin⁡2((2k+1)θa)\sin^2((2k+1)\theta_a), for a schedule of kk values, and infer θa\theta_a 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 O(1/ε)O(1/\varepsilon) scaling, up to logarithmic factors, with no extra control register.

Key takeaways

  • The amplification iterate has eigenphases ±2θa\pm2\theta_a with sin⁡2θa=a\sin^2\theta_a=a; phase estimation reads θa\theta_a and returns a~=sin⁡2(πy/M)\tilde a=\sin^2(\pi y/M).
  • The error is at most 2πa(1−a)/M+π2/M22\pi\sqrt{a(1-a)}/M+\pi^2/M^2 with probability at least 8/π28/\pi^2: O(1/ε)O(1/\varepsilon) queries versus Θ(1/ε2)\Theta(1/\varepsilon^2) samples, and this is optimal.
  • Quantum counting estimates the number of marked items to O(K)O(\sqrt K) with O(N)O(\sqrt N) queries; mean estimation achieves O~(σ/ε)\tilde O(\sigma/\varepsilon).
  • 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.

Question 1

To halve the error, classical sampling needs about ___ times more samples, and amplitude estimation about ___ times more oracle evaluations.

  1. 22; 22
  2. 44; 22
  3. 44; 44
  4. 22; 44
Show the answer

B. 44; 22

Sampling error scales like 1/n1/\sqrt n, so halving it takes 4×4\times the samples. Amplitude-estimation error scales like 1/M1/M, so halving it takes 2×2\times the queries.

Question 2

Amplitude estimation sometimes returns yy and sometimes M−yM-y. Why do both give the same estimate a~\tilde a?

  1. The QFT always produces outcomes in symmetric pairs
  2. Measurement noise flips the bits of yy
  3. Because a=1−aa=1-a in every application
  4. A∣0⟩\mathcal A\ket0 is an equal superposition of two eigenvectors of QQ with eigenphases ±θa/π\pm\theta_a/\pi, and sin⁡2(πy/M)\sin^2(\pi y/M) cannot tell them apart
Show the answer

D. A∣0⟩\mathcal A\ket0 is an equal superposition of two eigenvectors of QQ with eigenphases ±θa/π\pm\theta_a/\pi, and sin⁡2(πy/M)\sin^2(\pi y/M) cannot tell them apart

The two eigenvectors ∣ψ±⟩\ket{\psi_\pm} carry phases e±2iθae^{\pm2i\theta_a}. Phase estimation finds θa/π\theta_a/\pi or 1−θa/π1-\theta_a/\pi, and sin⁡2(π−ϕ)=sin⁡2ϕ\sin^2(\pi-\phi)=\sin^2\phi maps both to the same a~\tilde a.

Question 3

Quantum counting with Θ(N)\Theta(\sqrt N) queries estimates the number K≪NK\ll N of marked items to within

  1. O(K)O(\sqrt K)
  2. O(1)O(1)
  3. O(K)O(K)
  4. O(N)O(\sqrt N), independently of KK
Show the answer

A. O(K)O(\sqrt K)

The bound 2πK(N−K)M+π2NM2\frac{2\pi\sqrt{K(N-K)}}{M}+\frac{\pi^2N}{M^2} with M=cNM=c\sqrt N gives O(K)O(\sqrt K).

Question 4

Which statement about the quantum speedup for Monte Carlo is accurate?

  1. It is exponential in the number of samples
  2. It needs only one qubit of quantum memory
  3. Each "sample" is a coherent run of the whole randomized algorithm, and the runs are sequential, so depth grows like 1/ε1/\varepsilon
  4. 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 1/ε1/\varepsilon

The speedup is quadratic, O~(σ/ε)\tilde O(\sigma/\varepsilon) versus Θ(σ2/ε2)\Theta(\sigma^2/\varepsilon^2), 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).