Computing Library › Quantum Algorithms
Quantum Algorithms
Amplitude Amplification
Amplitude amplification is the generalization of Grover — it boosts the probability of any 'good' subspace quadratically, wrapping many algorithms in a speedup.
- Speedup
- quadratic
- Generalizes
- Grover search
- Pattern
- reflect–reflect (oracle + about-mean)
What it does
Given any procedure that produces a good outcome with probability p, amplitude amplification finds it in O(1/√p) repetitions instead of O(1/p), by alternating reflections about the good subspace and about the initial state.
Where it's used
A meta-algorithm: speeds up Monte-Carlo estimation, search-within-search, and many quantum ML subroutines.
In code (Qiskit)
python
# generalized Grover: Q = -A S_0 A^{-1} S_f applied ~1/sqrt(p) times