Algorithm Zoo · Search
Amplitude Amplification
Also known as: Generalized Grover
First described: Brassard, Høyer (later Mosca, Tapp), 1997
The problem
Boost the success probability of a randomized quantum procedure from p to ≈1 in O(1/√p) iterations.
Generalizes Grover's diffusion step to any state-preparation circuit A: given |ψ⟩ = A|0⟩ = sin(θ)|good⟩ + cos(θ)|bad⟩, AA prepares a state close to |good⟩ in O(1/sin θ) = O(1/√p) calls to A and its inverse.
Best classical
O(1/p) repetitions
Quantum complexity
O(1/√p) calls to A and A†
Our verdict
The quadratic speedup primitive everyone actually uses. Grover is one application; QML training, Monte Carlo, and counting are others. Constants are what kill it on hardware — the asymptotic is real but the crossover problem-size is enormous.
When to use it
- Inside amplitude estimation (the QFT-free version of phase estimation).
- When you have a state-preparation circuit whose success probability you can verify.
- Inside Monte Carlo-style algorithms — quadratic speedup in the number of samples.
When not to use it
- When you can't unitarily reflect about the |bad⟩ subspace (you need a clean oracle).
- When the speedup is eaten by oracle cost or by needing exponentially many qubits.
Classical baseline
Naive repetition O(1/p). For Monte Carlo integration this is the dominant cost; amplitude estimation's quadratic improvement matters in principle but the constants are punishing in practice.
Hardware cost
Needs controlled-A and controlled-A† plus the reflection circuits. T-count grows linearly with iterations and quadratically (in some constructions) with the bit-precision of θ.
Key papers
- Quantum Amplitude Amplification and Estimation ↗
Brassard, Høyer, Mosca, Tapp · 2002 · Contemp. Math.
Deep-dive tutorials
Last verified: 2026-05-24