Amplitude amplification

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. ^[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 isso $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: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.

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. ^[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.

For known initial success probability $p\in (0,1)$, this choice of iteration count ensures $|(2r+1)\theta -\pi /2|\le \theta$. Hence the success probability after amplitude amplification is at least ${\cos }^2\theta =1-p$. Counting initial state preparation and the forward and inverse preparation in each iterate gives $2r+1$ preparation-unitary applications, asymptotic to $\pi /(2\sqrt{p})$ as $p\to 0$.

If the state-preparation unitary sends $|0⟩$ to $|\psi ⟩=\sin \chi |g⟩+\cos \chi |b⟩$, use the orthonormal good/bad basis. The marked-space phase is diagonal there, and conjugating a phase on $|0⟩$ gives the rank-one phase in the displayed formula. Their product is unitary. An arbitrary preparation unitary not sending zero to this state need not preserve this particular two-dimensional subspace. Matrices in unnormalized good/bad vectors must not be described as unitary in the ordinary Euclidean inner product.

If the initial good amplitude $p=\sin \theta$ is known, an ancillary qubit can reduce it to $\sin {\theta }^{\prime }=pc$ with ${\theta }^{\prime }=\pi /(4k+2)$ and $0<c\le 1$. After $k$ ordinary amplitude-amplification iterations the good amplitude is $\sin ((2k+1){\theta }^{\prime })=1$, so the target state is prepared exactly.

Start from $|s⟩=N^{-1/2}{\sum }_x|x⟩$, negate amplitudes at marked indices, and apply $2|s⟩⟨s|-I$. If the marked fraction is $r$, the oracle-state mean amplitude is $(1-2r)/\sqrt{N}$. Inversion about the mean therefore gives amplitudes $(1-4r)/\sqrt{N}$ on unmarked indices and $(3-4r)/\sqrt{N}$ on marked ones. The marked success probability is $r(3-4r{)}^2$. At $r=1/4$ it is exactly one: unmarked amplitudes vanish and each marked amplitude is $2/\sqrt{N}$. The output is uniform among the $N/4$ marked indices. This is an exact special case of Grover's algorithm, using one phase oracle call under the stated promise.

For known good probability $p={\sin }^2\theta$, choose $j=\lceil \pi /(4\theta )-1/2\rceil$. A known reversible preparation of one state with good probability $p_{\ast }$ permits $j$ ordinary amplitude amplification iterations to reach the good subspace exactly. With ancillary marking access, prepare a flag with one-probability $q=p_{\ast }/p$ and define joint success as good data and flag one. Reflection about the prepared product state is known, while the joint phase test requires a controlled marking oracle or a computed Boolean output. This changes the success projector and enlarges the state space; it does not evade the obstruction to uniform probability lowering by a unitary. Query costs of preparation, its inverse and marking must all be counted.

Phase-matched amplitude amplification replaces the two sign-flip reflections by selective phase rotations. Choosing their phases from the known initial overlap can rotate the state exactly onto the target even when an integer number of ordinary Grover rotations would overshoot it.

A geometric amplitude-amplification schedule tries iteration counts $1,2,4,8,\dots$ when the initial good amplitude is unknown. It reaches the unknown optimal scale with only a geometric-series overhead.