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.

One Grover iteration returns a marked label with certainty. Prepare $|s⟩=N^{-1/2}{\sum }_x|x⟩$; apply the supplied phase oracle to negate amplitudes on the $N/4$ marked inputs; apply the Grover diffusion operator $D=2|s⟩⟨s|-I$; and measure in the computational basis. If F prepares $|s⟩$ from $|0⟩$, the reflection is $D=F(2|0⟩⟨0|-I)F^{†}$, requiring no further oracle query.

After the oracle the amplitudes are $1/\sqrt{N}$ on the $3N/4$ unmarked labels and $-1/\sqrt{N}$ on the marked labels. Their average isThe reflection performs inversion about the mean, $a_x\mapsto 2\mu -a_x$. It therefore sends every unmarked amplitude to zero and every marked amplitude to $2/\sqrt{N}$. The resulting normalized state isEach marked label has Born rule probability $4/N$, every unmarked label has probability zero, and the marked probabilities sum to $(N/4)(4/N)=1$. This is one-step exact Grover search with a quarter of the inputs marked, using one reduced-oracle query. The positive integer N must be divisible by four; a qubit implementation may take $N=2^m$, but the stated reflection proof does not assume that register convention.

Summing part (i) over the $S_0$ unmarked indices gives $⟨e_0|A_0⟩=S_0/\sqrt{N}$. The Grover diffusion operator therefore acts asThis is an identity for an unnormalized subset sum; it does not require replacing its norm by one.

The Hadamard gate H and T gate $T=\mathrm{diag}(1,e^{i\pi /4})$ form a universal quantum gate set for single-qubit operations: finite sequences approximate any target single-qubit unitary arbitrarily well, up to a physically irrelevant global phase. Universality is not a claim that every arbitrary rotation has a finite exact H,T word. With products acting right to left, exact Pauli constructions areIndeed $T^2=S$, $T^6=S^{†}$, and $SX{S}^{†}=Y$.

Initialize the search register in $|00⟩$ and the output qubit in $|1⟩$, then apply H to all three. The search state becomes $|s⟩=(|00⟩+|01⟩+|10⟩+|11⟩)/2$, and the output becomes $|-⟩$. The oracle obeysThis phase kickback leaves the output qubit factored out, so subsequent analysis can use the phase oracle $O_f$ on the two search qubits alone. Apply one Grover diffusion operator $D=2|s⟩⟨s|-I$, then measure the search register.

A promise restricts which Boolean functions may be supplied. For the exact one-iteration four-entry search here, promise exactly one marked input. The four functions are $f_{jk}(x)=1$ precisely when $x=jk$, for $jk\in \{00,01,10,11\}$. Other known numbers of marked entries require a correspondingly chosen iteration count; uniqueness is the promise for this particular exact circuit.

In basis order $00,01,10,11$, the requested explicit calculation isThus the promised marked entry is found with probability one.

For two weakly coupled spin-half nuclei in nuclear magnetic resonance, a useful rotating-frame Hamiltonian iswhere $J$ is in hertz and $I_z=Z_1/2$, $S_z=Z_2/2$. Resonant pulses and refocusing separate local rotations from the scalar coupling. For positive $J$, evolution for $t=1/(2J)$ supplies $e^{-i\pi Z_1{Z}_2/4}$. Combining it with local Z phases gives the phase oracleThe scalar global phase is immaterial. Local $\pi$ pulses interchange zero and one, soThis implements the desired change of marked input without an additional output qubit.

Let $x\in \{00,01,10,11\}$ and let $f(x)$ be one only at the marked input. A three-qubit implementation of Grover's algorithm starts with $|00⟩|1⟩$, applies a Hadamard gate to each qubit, queries the reversible quantum oracle $U_f:|x,y⟩\mapsto |x,y\oplus f(x)⟩$, applies the Grover diffusion operator $D=2|s⟩⟨s|-I$ to the first two qubits, and measures those two qubits in the computational basis. Here $|s⟩=\frac{1}{2}{\sum }_x|x⟩$. The full three-wire quantum circuit is the composition

Here $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$. Since $X|-⟩=-|-⟩$, phase kickback gives $U_f(|x⟩|-⟩)=(-1{)}^{f(x)}|x⟩|-⟩$. The third qubit remains separable and unchanged. A direct marked-state phase oracle $O_f|x⟩=(-1{)}^{f(x)}|x⟩$ therefore replaces the three-qubit query using only two qubits:For the explicit choice $f(x)=1$ only at $x=11$, $O_f$ is a Controlled-Z gate. Immediately after it,The mean of these four probability amplitudes is $\overline{a}=1/4$. The Grover diffusion operator maps each probability amplitude $a_x$ to $2\overline{a}-a_x$. The three unmarked probability amplitudes become zero and the marked one becomes one. A single query consequently finds $11$ with probability one.

A gate-level implementation of $D$ is $H^{\otimes 2}(2|00⟩⟨00|-I)H^{\otimes 2}$. Up to an irrelevant global phase, it is $H^{\otimes 2}{X}^{\otimes 2}\mathrm{CZ}{X}^{\otimes 2}{H}^{\otimes 2}$. For any other chosen marked word, conjugate the Controlled-Z gate by Pauli X gates on precisely the positions where the marked word has a zero.

In liquid-state NMR quantum computing, use two distinguishable spin-$1/2$ atomic nuclei in one molecule as the two qubits. Their different resonance frequencies permit selective radiofrequency pulses for one-qubit rotations. In a suitable rotating frame, refocusing removes unwanted one-spin terms while the NMR scalar coupling suppliesAssuming $J>0$, free evolution for $t=1/(2J)$ implements $U_J=e^{-i\pi Z_1{Z}_2/4}$. Define $R_z(\theta )=e^{-i\theta Z/2}$. ThenThis equality follows directly by evaluating the four diagonal entries: the first three are $+1$ and the $11$ entry is $-1$. Negative $J$ can be handled by refocusing or reversing the effective interaction sign. The global phase can be ignored.

Thus the marked-state phase oracle for $11$ requires scalar-coupling evolution and calibrated one-spin rotations. For a marked word $b_1{b}_2$, conjugate by $X_1^{1-b_1}{X}_2^{1-b_2}$, realized as selective $\pi$ pulses. The Grover diffusion operator uses the same entangling operation with additional one-qubit pulses. Liquid-state NMR quantum computing usually reads an ensemble signal and often prepares an effective pseudo-pure deviation from a large mixed background; that reproduces this small quantum algorithm's signal without providing a scalable source of pure initialized qubits.

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

Write $N=2^n$ and $|s⟩=N^{-1/2}{\sum }_{x=0}^{N-1}|x⟩$. The initial Hadamard gates prepare $|s⟩$ in the search register and $|-⟩$ in the final quantum ancilla. Since the Pauli X gate satisfies $X|-⟩=-|-⟩$, the Boolean quantum oracle acts by quantum phase kickback:For a single marked entry this is the marked-state phase oracle $O_a=I-2|a⟩⟨a|$ on the search register. The ancilla stays separate and unchanged throughout.

The Grover diffusion operator is $V=2|s⟩⟨s|-I$, because $H^{\otimes n}|0^n⟩=|s⟩$. The PDF circuit places one diffusion after each oracle call, so the state before measurement isIn the supplied amplitude amplification theorem, take $|\psi ⟩=|s⟩$ and $|\varphi ⟩=|a⟩$. Their overlap has modulus $1/\sqrt{N}$, so the Grover rotation angle is $\theta =\arcsin (N^{-1/2})$. A quantum measurement in the computational basis therefore givesThe inverse sine here is applied to the overlap of the two different states. The converted TeX's self-overlap in the angle definition is a transcription error; the original PDF has $|⟨\varphi |\psi ⟩|$.

If there is no marked entry, the Boolean quantum oracle is the identity. The uniform superposition state is a positive eigenstate of the Grover diffusion operator:Thus every iteration leaves the full state $|s⟩\otimes |-⟩$ unchanged. The measured search bits have the uniform distributionOnly the first $n$ qubits are measured in the printed circuit. If the untouched ancilla were also measured in the computational basis, its bit would be an independent fair bit, giving probability $1/(2N)$ for each joint outcome.

A good item must exist, so assume $1\le k<N$; if $k=0$, the requested search is impossible, while $k=N$ makes every output good. Put $p=k/N$ and $\theta =\arcsin \sqrt{p}$. Normalize the good and bad components of the uniform superposition state asThe Boolean phase oracle negates $|g⟩$ and fixes $|b⟩$. The Grover diffusion operator is $-I_{{\psi }_0}=2|{\psi }_0⟩⟨{\psi }_0|-I$. Its implementation is independent of $f$: conjugate the reflection about $|0^n⟩$ by Hadamard gates. One Grover search algorithm iteration isHence, by the Grover rotation angle formula,Choose the nonnegative integer $j$ nearest to $\pi /(4\theta )-1/2$. Its final angle differs from $\pi /2$ by at most $\theta$, so a computational-basis measurement succeeds with probability at least ${\cos }^2\theta =1-p$. The allowed small-density regime includes $p\le 1/3$, giving the requested $2/3$ bound. Each iteration uses one Boolean phase oracle query, and $j=O(1/\sqrt{p})=O(\sqrt{N/k})$.

For $k=N/4$, $\theta =\pi /6$ and one iteration reaches $3\theta =\pi /2$ exactly. Thus one query gives a good outcome with certainty:This is exact Grover search on four entries applied to a marked fraction of one quarter, not only to a four-element register.

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.

Letwhere $H$ is the Hadamard gate. For a computational-basis string $z$, define the phase reflectionThus $I_0$ changes the sign of $|0^n⟩$, while $I_{x_0}$ changes the sign of the marked state.

Conjugating $I_0$ by $H_n$ reflects in the hyperplane perpendicular to $|s⟩$, sois the Grover diffusion operator, the reflection about $|s⟩$. The Grover iteration operatoris the product of two reflections. It acts as a rotation through $2\theta$ in the plane spanned by the marked state $|x_0⟩$ and the normalized uniform superposition of unmarked states, whereIt is the identity up to sign on the orthogonal complement of that plane.

In an $N$-dimensional computational basis, the uniform superposition state isMeasurement in that basis gives the uniform distribution on a finite set. For $N=2^n$, Hadamard gates prepare it from $|0^n⟩$. Its reflection $2|s_N⟩⟨s_N|-I$ is a Grover diffusion operator.