Algorithm Zoo · Primitives
Amplitude Estimation
Also known as: QAE
First described: Brassard, Høyer, Mosca, Tapp, 2002
The problem
Estimate the probability p that a quantum algorithm A outputs 'success'.
Combines amplitude amplification with phase estimation: estimate p = sin²(θ) by extracting θ from the Grover-like rotation operator. Achieves O(1/ε) queries to A to reach ε precision — quadratic improvement over classical O(1/ε²) Monte Carlo.
Best classical
O(1/ε²) Monte Carlo sampling.
Quantum complexity
O(1/ε) queries to A.
Our verdict
The quadratic-speedup primitive that finance vendors love to cite. The asymptotic is real — quadratic for Monte Carlo is genuinely valuable. The constants are merciless in practice, and the crossover problem-size for derivatives-pricing or risk-VAR estimation is still beyond NISQ. Watch for iterative-QAE variants that drop QPE and improve hardware fit.
When to use it
- Monte Carlo replacement when classical sampling is the bottleneck — option pricing, risk estimation, integration.
- Inside QML algorithms that need expectation values to high precision.
When not to use it
- When ε is large (low-precision regimes). The quadratic speedup is in 1/ε; for ε = 0.01 it's only a 10× win in queries, and constants kill that.
- When classical Monte Carlo is already fast enough.
Classical baseline
Modern Monte Carlo with variance reduction (importance sampling, antithetic variates, quasi-MC sequences) is extraordinarily strong. Crossover problem sizes for QAE to win are large.
Hardware cost
Same as amplitude amplification + phase estimation. Without QFT (iterative QAE, Suzuki et al. 2020), more NISQ-friendly but slower constants.
Key papers
- Quantum Amplitude Amplification and Estimation ↗
Brassard, Høyer, Mosca, Tapp · 2002 · Contemp. Math.
- Amplitude Estimation without Phase Estimation ↗
Suzuki et al. · 2020 · Quantum Information Processing
Deep-dive tutorials
Last verified: 2026-05-24