= Amplitude amplification
{wiki}
= Amplitude amplification theorem
{synonym}
<Amplitude amplification> increases the <probability> of obtaining an answer accepted by a specified <Boolean function>. It requires a coherent preparation $A$, its inverse, and a <marked-state phase oracle> that negates accepted components. Alternating that sign change with a <reflection operator> about the prepared state directs <interference> toward the accepted subspace. Brassard, Høyer, Mosca, and Tapp developed the general framework, extending <Grover's algorithm> beyond a <uniform quantum superposition>. https://arxiv.org/abs/quant-ph/0005055[Brassard et al., Quantum Amplitude Amplification and Estimation, 2000, §2]{ref}.
If a normalized <quantum state> has good amplitude $\sin\theta$, the product of the reflection in the bad axis and the reflection in the state line rotates its good-bad plane by $2\theta$. After $k$ iterations the good <probability> is
$$
\sin^2((2k+1)\theta),
$$
so $O(1/\sin\theta)$ iterations raise a small good amplitude close to one. Success subsequently oscillates, making the stopping time part of the algorithm.
Compute the <exact Grover search on four entries> directly. Order the <computational basis> as $00,01,10,11$ and mark $11$. The <Hadamard transform> prepares amplitudes $(1/2,1/2,1/2,1/2)$. The <marked-state phase oracle> changes these to $(1/2,1/2,1/2,-1/2)$, whose <arithmetic mean> is $\overline a=1/4$. The <Grover diffusion operator> performs <inversion about the mean>:
$$
a_x\longmapsto2\overline a-a_x,\qquad
\left(\tfrac12,\tfrac12,\tfrac12,-\tfrac12\right)\longmapsto(0,0,0,1).
$$
The three unmarked amplitudes become $1/2-1/2=0$, while the marked amplitude becomes $1/2-(-1/2)=1$. All three stages have squared <norm> one. Here $\sin\theta=1/2$, so $\theta=\pi/6$ and one iteration gives $\sin^2(3\theta)=1$, agreeing with the explicit calculation.
\Image[/four-state-amplitude-amplification.png]
{title=One Grover iteration on four states: a phase flip followed by reflection about the mean concentrates all amplitude on the marked state}
Grover's original search paper was submitted on 29 May 1996; its algorithm combines selective sign changes with <inversion about the mean>. The example exposes the beauty of that construction: a change initially invisible to <computational-basis measurement> becomes complete cancellation of every wrong answer. https://arxiv.org/abs/quant-ph/9605043[Grover, A fast quantum mechanical algorithm for database search, 1996, §§3–4]{ref}.
The <marked-state phase oracle> is an assumed operation, whose implementation cost must be counted. <Computational-basis measurement> yields a candidate label, here $11$; using it to retrieve a record requires the relevant data access. Preparing a <quantum superposition> does not make all its entries available as classical outputs. The improvement concerns the number of oracle queries needed to obtain an accepted label.
Back to article page
