Amplitude amplification

Amplitude amplification (Brassard, Høyer, Mosca, Tapp, 2000) generalizes Grover's algorithm from the specific case where the initial state is prepared by Hadamards to an arbitrary state-preparation operator $A$.

Setup. Suppose $A|0\rangle = \sin\theta\,|\text{good}\rangle + \cos\theta\,|\text{bad}\rangle$, so the initial success probability is $a=\sin^2\theta$. Define the amplification operator

$$Q = A\,S_0\,A^{-1}\,S_\chi,$$

where $S_\chi$ flips the phase of good states and $S_0$ flips the phase of everything except $|0\rangle$. Geometrically, $Q$ is a rotation by $2\theta$ in the 2-dimensional real span of $|\text{good}\rangle$ and $|\text{bad}\rangle$, so after $k$ applications the success probability is

$$P_k = \sin^2\big((2k+1)\theta\big).$$

Choosing $k\approx \frac{\pi}{4\theta}-\frac12$ drives $P_k$ close to 1, needing $O(1/\sqrt a)$ iterations versus the $O(1/a)$ classical repetitions needed to hit a probability-$a$ event with matching confidence — the same quadratic gain that Grover's algorithm gets as the special case $A=H^{\otimes n}$.

Exactly solvable small instance. Take a single qubit with $A=R_y(2\theta)$, $\theta=\pi/6$, so $a=\sin^2(\pi/6)=1/4$ — the initial success ("good" = $|1\rangle$) probability is exactly $1/4$. One iteration gives

$$P_1 = \sin^2(3\theta) = \sin^2\!\left(\frac{\pi}{2}\right) = 1,$$

i.e. a single amplitude-amplification step turns a 25%-success preparation into a certain one — the same numeric case that underlies the classic "Grover on $N=4$, $M=1$" result, here derived directly from the rotation-angle formula rather than from an oracle over a register.

Where it is used. Amplitude amplification is the mechanism inside quantum counting, amplitude estimation, and any algorithm that needs to boost the probability of a rare event once a coherent way to recognize "success" (a reflection oracle) is available.