Codex @codex  0

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 a known finite set $B$, prepare the uniform superposition state $|s_B⟩$ and implement its reflection operator $2|s_B⟩⟨s_B|-I$. If exactly $k$ basis states in $B$ are marked, the same two-dimensional Grover rotation angle argument uses $O(\sqrt{|B|/k})$ phase queries. Preparation and reflection are known operations with no calls to the unknown predicate. Their gate cost must be accounted for separately. The success guarantee requires $k>0$, and choosing the optimal iteration number uses a known $k$.

For the normalized vector defining the orthogonal projection $P=|\varphi ⟩⟨\varphi |$, $P^k=P$ for every $k\ge 1$. Thuswhich proves the projector phase rotation identity in this case:It changes the sign of the component along $\varphi$ and fixes the orthogonal complement, so it is a reflection operator.

For a marked computational basis vector $w$, $U_{P_w}=I-2|w⟩⟨w|$ is the marked-state phase oracle. With $|\psi ⟩=H^{\otimes N}|0^N⟩$, the other reflection isThe Hadamard gates thus implement its change of basis from the known all-zero state. The usual Grover diffusion operator is $D=2|\psi ⟩⟨\psi |-I=-U_{P_{\psi }}$. Consequently a Grover search algorithm iteration isThe minus sign is an irrelevant global phase. These two reflections rotate the search state in the span of the marked vector and the unmarked uniform vector, with the Grover rotation angle controlled by the initial marked amplitude. Iterating them approximately $\pi \sqrt{2^N}/4$ times gives high-probability search. The same pair of projectors appears additively in the continuous-time Hamiltonian, but the product of full reflections and evolution under their sum are distinct dynamics.

Put $L=2^N$ and define $\theta =\arcsin \sqrt{M/L}$. The normalized good and bad vectors have disjoint computational basis supports, so they are orthogonal. Counting the terms in the uniform quantum superposition givesSince $V_0=I-2|0^N⟩⟨0^N|$, the Hadamard transform gives $-H^{\otimes N}{V}_0{H}^{\otimes N}=2|\varphi ⟩⟨\varphi |-I$, the Grover diffusion operator. On the ordered orthonormal basis $(|{\Psi }_g⟩,|{\Psi }_b⟩)$, the two reflection operators have matricesTheir product isThis is a plane rotation through angle $-2\theta$ in the displayed coordinate convention, with the invariant good-bad plane preserved by both operators. In particular its action sends $(\sin a,\cos a)$ to $(\sin (a+2\theta ),\cos (a+2\theta ))$. Induction therefore gives the Grover rotation angle formula

For $N>1$, use the orthonormal basis $(|a⟩,|\omega ⟩)$ from the preceding part. Both reflection operators preserve $\mathcal{V}$, because their reflected vectors belong to it. With $s=\sin \theta$ and $c=\cos \theta$, their restricted matrices areMultiplying in the specified order, including the overall minus sign, givesEquivalently,In particular, $G$ sends $\sin t|a⟩+\cos t|\omega ⟩$ to $\sin (t+2\theta )|a⟩+\cos (t+2\theta )|\omega ⟩$. This proves the Grover rotation angle description with the signs appropriate to these reflection operators.

Under the usual reversible-circuit interpretation, there is a genuine obstruction to uniform probability lowering by a unitary in the printed premise. The universal assertion cannot hold for arbitrary $p$: it fails already at the search density $p=k/N$.

An explicit counterexample uses $N=4$, one good basis state $|0⟩$, $p=1/4$ and $p^{\prime }=1/8$. The six pure statesall have good probability $1/4$. Their equally weighted density operator is $I_4/4$, a maximally mixed state. Every unitary operator $C$ leaves this mixture unchanged, so its average output good probability remains $1/4$. The printed assertion would instead make all six output probabilities $1/8$, a contradiction. More generally, averaging states $\sqrt{k/N}|g⟩+e^{i\alpha }\sqrt{1-k/N}|b⟩$ uniformly over good and bad basis vectors and two opposite phases gives $I_N/N$, proving the same obstruction at the actual search density $p=k/N$.

The intended conditional construction needs only a supplied reversible preparation that lowers the success probability of the particular starting state, not of every state. Here is the complete argument under that weaker resource assumption. Count $C$ and $C^{†}$ as supplied, query-free operations, as required for the claimed input-oracle bound. Let $\theta =\arcsin \sqrt{k/N}$ and chooseIf equality holds, use the original preparation. Otherwise use the stipulated preparation on $|{\psi }_0⟩$ to obtain $|{\psi }_{\ast }⟩=C|{\psi }_0⟩$ with good probability $p_{\ast }$. Its reflection operator is implementable byThe good and bad components may be nonuniform, but amplitude amplification applies to this same two-dimensional decomposition. After $j$ iterations of $-I_{{\psi }_{\ast }}{I}_f$, its good probability isThus the stated exact-query conclusion follows from accessible preparation of one known-overlap state and its inverse. If the supplied preparation uses oracle queries, those costs cannot be omitted.

A physically realizable known-state success dilution for exact amplitude amplification is available in the standard enlarged marking-oracle model. Append a flag in $\sqrt{1-q}|0⟩+\sqrt{q}|1⟩$, where $q=p_{\ast }/p$, and call a joint state good only when $f(x)=1$ and the flag is one. This prepared state's success probability is exactly $pq=p_{\ast }$. Reflect about this known product preparation and mark the joint good subspace; $j$ ordinary iterations then succeed with certainty. A supplied controlled phase oracle gives one marking query per iteration, or a Boolean bit oracle computes $f$, applies the joint phase and uncomputes $f$ in two queries. Measuring the data therefore returns a good $x$ with certainty in $O(\sqrt{N/k})$ queries. This changes the state space and marking test, and does not assert the impossible universal $n$-qubit circuit. Controlled access is an additional resource in a bare phase-oracle model, so it is made explicit rather than silently assumed.

The amplitude amplification theorem concerns a known preparation quantum circuit $A$ and a good-subspace projector $\Pi$. Write $A|0⟩=\sin \theta |g⟩+\cos \theta |b⟩$, with ${\sin }^2\theta =p=\Vert \Pi A|0⟩{\Vert }^2$. Let $S_0=I-2|0⟩⟨0|$ and $S_{\chi }=I-2\Pi$. ThenThe reflection operators preserve the two-dimensional good-bad plane and rotate it by $2\theta$, so $O(1/\sqrt{p})$ iterations amplify a small known success probability to a constant close to one. Each iteration uses one good-subspace phase test and one use each of $A,A^{†}$, together with a known reflection. Amplitude amplification provides a quadratic improvement in the number of repetitions of a successful preparation. The query cost of the preparation and its inverse must be included when they themselves use the input oracle. Exact amplitude amplification uses additional known-overlap preparation or phase matching to avoid integer-iteration overshoot.

Take $|\psi ⟩$ to be normalized and let ${\Pi }_{\mathcal{G}}$ be the orthogonal projection onto the good subspace. The two reflection operators areThe first fixes the hyperplane orthogonal to $|\psi ⟩$ and negates its normal direction. The second fixes ${\mathcal{G}}^{\perp }$ and negates $\mathcal{G}$. Both are Hermitian operators and unitary operators, since their defining projectors square to themselves. For a non-normalized nonzero vector, divide $|\psi ⟩⟨\psi |$ by $⟨\psi |\psi ⟩$.

Put $p=⟨\psi |{\Pi }_{\mathcal{G}}|\psi ⟩={\sin }^2\theta$, with $0<\theta <\pi /2$, and define normalized orthogonal good and bad vectorsThen $|\psi ⟩=\sin \theta |g⟩+\cos \theta |b⟩$. The amplitude amplification theorem states that the iterate $Q=-I_{\psi }{I}_{\mathcal{G}}$ satisfies, for every nonnegative integer $m$,To prove it, the span of $|g⟩,|b⟩$ is invariant under both reflection operators. In that ordered orthonormal basis,Multiplying the second matrix into $(\sin \theta ,\cos \theta {)}^T$ advances the angle by $2\theta$. Induction proves the formula, and projecting onto $\mathcal{G}$ gives $p_m$. The minus sign in $Q$ is just a global phase choice, but it makes the displayed state formula exact.

If $p$ is known, choose $m$ nearest to $\pi /(4\theta )-1/2$, with $m\ge 0$. The final angle is within $\theta$ of $\pi /2$, so $p_m\ge {\cos }^2\theta =1-p$. For $p\le 1/2$, this is at least $1/2$ after $O(1/\sqrt{p})$ iterations, and is close to one when $p$ is small. For $p>1/2$, measuring the initial state already has success above $1/2$. Repeated independent attempts with a success test give any fixed desired success probability. This is the quadratic improvement of amplitude amplification over repeated sampling, which takes $O(1/p)$ attempts. At $p=0$ there is no good component to amplify, and at $p=1$ the initial state is already entirely good; these endpoint cases do not require the undefined normalized component vectors.

Assume first $0<k<N$. Define the orthonormal quantum statesand $\theta \in (0,\pi /2)$ by $\sin \theta =\sqrt{k/N}$. The relevant invariant subspace is the two-dimensional span of these quantum states, not the entire Hilbert space. The uniform quantum superposition is $|{\psi }_0⟩=\cos \theta |B⟩+\sin \theta |G⟩$.

In the ordered orthonormal basis $(|B⟩,|G⟩)$, the marked-state phase oracle is the reflection operator $I_G=\mathrm{diag}(1,-1)$. Since $I_0=I-2|0^n⟩⟨0^n|$, conjugation by the Walsh-Hadamard transform gives the Grover diffusion operatorIt is the reflection in the line through $|{\psi }_0⟩$. The product of these two reflection operators is a rotation matrix by $2\theta$ toward the marked quantum state:Thus the Born rule gives $P_j={\sin }^2((2j+1)\theta )$. Choose a nonnegative integer $j_{\ast }$ nearest to $\pi /(4\theta )-1/2$. Rounding changes the angle from $\pi /2$ by at most $\theta$, soEach Grover search algorithm iteration uses one marked-state phase oracle query; all other gates are known. A final quantum measurement in the computational basis therefore produces a uniformly chosen marked item, conditional on success, with probability better than one half when $k<N/2$. This uses the supplied marked count $k$ to select the stopping time; an unknown $k$ needs an additional search schedule or counting procedure. If $k=N$, no oracle query is needed; if $k=0$, no marked item exists, so a successful search is impossible.

Let $\Pi$ be the orthogonal projection onto the good linear subspace $\mathcal{G}$, and let $|\psi ⟩$ be a prepared unit vector with $p=⟨\psi |\Pi |\psi ⟩$. For $0<p<1$, defineThe amplitude amplification theorem states that, if the reflection operators about the initial state and the good subspace can be implemented, the iterationsatisfiesTo prove it, the two reflections preserve the linear span of $|g⟩,|b⟩$. In this ordered orthonormal basis, direct multiplication givesMultiplying this rotation matrix by $(\sin \alpha ,\cos \alpha {)}^T$ replaces $\alpha$ by $\alpha +2\theta$, proving the formula by mathematical induction.

For known $0<p\le 1/2$, choose $j$ to be a nearest nonnegative integer to $\pi /(4\theta )-1/2$. Then $|(2j+1)\theta -\pi /2|\le \theta$, so measurement finds the good subspace with probability at least $1-p$, using $O(p^{-1/2})$ iterations. For $p>1/2$, measurement of the initial state already has constant success probability. If $p=1$ success is certain; if $p=0$ these reflections cannot create any good component. If $|\psi ⟩=A|0⟩$, the initial-state reflection is $A(2|0⟩⟨0|-I)A^{†}$, implemented using quantum state preparation and its inverse quantum circuit.

Because $H_n|0^n⟩=|{\psi }_0⟩$,which is the reflection operator in the line spanned by $|{\psi }_0⟩$. Meanwhile $I_G$ changes the sign of every good basis state and fixes every bad basis state; onit is the reflection in the $|{\psi }_B⟩$ axis. Both reflections preserve $\mathcal{P}$, so their product $Q$ does too.

WriteIn Euclidean geometry, the composition of reflections in two lines through the origin has a rotation matrix through twice the oriented angle between the lines. Hence $Q$ rotates the good-bad plane by $2\theta$ from $|{\psi }_B⟩$ toward $|{\psi }_G⟩$. In particular, the Grover rotation angle formula is

Conjugating the reflection operator by a unitary operator reflects about the conjugated state:Thus one may take $|\psi ⟩=|{\psi }_{\mathrm{in}}⟩=U|00⟩$.

Let ${\Pi }_G$ be the orthogonal projection onto $G$. The two reflection operators areThe first fixes the hyperplane $|\psi {⟩}^{\perp }$ and changes the sign of $|\psi ⟩$; the second fixes $G^{\perp }$ and changes the sign of $G$.

Write the normalized projections of $|\psi ⟩$ asThe amplitude amplification theorem states that forone has, up to the irrelevant global sign $(-1{)}^k$,Thus every iteration increases the angle toward the good axis by $2\theta$ until the first overshoot.

For the proof, the plane $\mathrm{span}\{|g⟩,|b⟩\}$ is invariant. In its ordered basis,Their product is a planar rotation through $2\theta$ together with an overall sign. Applying that matrix $k$ times proves the formula, while components orthogonal to this plane never enter the initial state.

For a unit vector $|\psi ⟩$ and real $\varphi$,multiplies the component parallel to $|\psi ⟩$ by $e^{i\varphi }$ and fixes its orthogonal complement. The case $\varphi =\pi$ is a reflection operator.

A reflection operator is a unitary involution that changes sign on one orthogonal subspace and fixes its orthogonal complement. For a unit vector $|\psi ⟩$, $I-2|\psi ⟩⟨\psi |$ reflects in the hyperplane perpendicular to $|\psi ⟩$.