Amplitude Amplification
The general procedure behind Grover search: boosting the amplitude of a marked subspace by iterated reflections.
Generalizing Grover
Grover search is the special case of amplitude amplification where the initial state is the uniform superposition. The general procedure works for any state-preparation unitary A and any way of marking good states. If A|0> has amplitude sqrt(a) on the good subspace, amplitude amplification raises the probability of measuring a good state from a to near one using O(1/sqrt(a)) applications of A, a quadratic improvement over the 1/a repetitions naive sampling would need.
The two reflections
Define S_chi, which flips the phase of good states, and S_0, which flips the phase of the |0> state. The amplification operator is Q = -A S_0 A^dagger S_chi. Geometrically, Q is a product of two reflections and therefore a rotation, by angle 2*theta, in the two-dimensional plane spanned by the good and bad components, where sin^2(theta) = a. Iterating Q rotates the state toward the good subspace.
The recipe
- Prepare the state A|0>.
- Apply Q about (pi/4)/sqrt(a) times.
- Measure; the good subspace now dominates the outcome probability.
- Amplitude estimation instead reads theta to learn a itself.
Why it is central
Amplitude amplification is a master primitive. Grover search, amplitude estimation, counting, and the success-probability boosting inside larger algorithms (such as post-selection in HHL) are all instances or applications of it. Any subroutine that produces the right answer with small probability p can be amplified to near-certainty with a quadratic saving in repetitions.
Variants
Oblivious amplitude amplification handles cases where the initial amplitude is unknown or where A must be applied to arbitrary inputs, important in linear-combination-of-unitaries constructions. Phase-engineered variants give fixed-point convergence. In the modern framework, amplitude amplification is the polynomial that approximates a step function under the quantum singular value transformation.