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

For a permutation $f$ of an $N$-element set and a known marked output subset of size $K$, exactly $K$ inputs have marked outputs. The uniform quantum superposition thus has good probability $K/N$, independent of which permutation the oracle represents. This allows a known-angle amplitude amplification schedule without counting unknown preimages.

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$.

Choose $0<\theta <\pi /2$ with $\sin \theta =\sqrt{p}$. Then $1-2p=\cos 2\theta$ and $2\sqrt{p(1-p)}=\sin 2\theta$. The matrix found in part 2 is a rotation by $2\theta$ in the ordered good-bad plane, with the bad coordinate listed first. The initial coordinate vector is $(\cos \theta ,\sin \theta {)}^T$.

After $r$ rotations its angle from the bad axis is $(2r+1)\theta$. Equivalently, multiplication of the displayed matrix and the addition formulas for sine and cosine prove the assertion by induction from $r=0$. HenceThe Born rule therefore gives good-output probability ${\sin }^2((2r+1)\theta )$. This is the geometric mechanism of amplitude amplification: each coherent iteration rotates the already existing good amplitude toward the good axis.

For $p=t=-1$, the preceding matrix becomesMultiplying it by $(\sin \chi ,\cos \chi {)}^T$ gives $(\sin 3\chi ,\cos 3\chi {)}^T$. The sine and cosine addition identities then prove by induction thatFor $0<\chi \le \pi /4$, the first angle reaching the interval $[\pi /4,3\pi /4]$ gives success at least one half. Its smallest integer iteration count isThe ceiling advances the angle by less than $2\chi$, so the chosen angle remains in that success interval. This is the first half-success time in Grover search. If near-certain rather than half success is desired, choose the nearest integer to $\pi /(4\chi )-1/2$; its success is at least ${\cos }^2\chi$ and the count is asymptotic to $(\pi /4)\sqrt{N/m}$. Both exhibit the quadratic query improvement of amplitude amplification. Success oscillates, so further iterations past the first maximum are not automatically beneficial. The count presumes positive known $m$ (or known $\chi$); if no marked item exists, no number of iterations can produce one.

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.

Prepare the two data qubits in $|s⟩=\frac{1}{2}{\sum }_{x\in B_2}|x⟩$ and a phase ancilla qubit in $|-⟩$. A single Boolean quantum oracle query flips only the marked amplitude. Its success fraction is $p=1/4$, so $\theta =\pi /6$ in amplitude amplification. The fixed diffusion reflection $D=2|s⟩⟨s|-I$ gives $\sin (3\theta )=1$ after one iteration.

Directly, after the query the marked amplitude is $-1/2$ and the other three are $1/2$. Their mean is $1/4$. The diffusion reflection replaces each amplitude $c_x$ by $2(1/4)-c_x$, yielding one at the marked input and zero elsewhere. ThusHere $U_f$ is understood with its target ancilla qubit, and $D$ acts only on the data. It is independent of $f$: $D=H^{\otimes 2}(2|00⟩⟨00|-I)H^{\otimes 2}$, with the central diagonal gate implementable using two Pauli Z gates and one Controlled-Z gate. Measuring the data in the computational basis therefore finds the unique marked string with certainty after one oracle query.

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.

For a positive Hermitian matrix,The HHL algorithm phase-estimates $A$, performs a controlled rotation with amplitude proportional to $1/{\lambda }_i$, uncomputes the estimate, and postselects the rotation ancilla. Resolving the smallest eigenvalue requires phase-estimation precision $O({\lambda }_{\min })$ and evolution time $\Omega (1/{\lambda }_{\min })$. Since ${\lambda }_{\max }\le 1$, this contributes a dependence at least linear in $\kappa$.

The controlled rotation must use a scale $C\le {\lambda }_{\min }$. In the worst input direction its success probability is of orderso obtaining constant success by amplitude amplification costs another $O(\kappa )$ factor. Thus a runtime polynomial in $\log N$ requiresAn exponentially ill-conditioned matrix would require exponentially fine phase resolution or exponentially many amplification steps.

Let the spectral decomposition of the Hermitian matrix beThe HHL algorithm proceeds as follows.

Efficiently prepare the normalized amplitude encoding $|b⟩$.
Apply quantum phase estimation to the simulated evolution $e^{iAt}$, producing an approximation of each eigenvalue: Add one ancilla and perform an eigenvalue-controlled rotationwhere $0<C\le {\min }_j|{\lambda }_j|$.
Uncompute the eigenvalue register. Conditional on measuring the ancilla as $1$, the system register isThe postselection probability can be increased with amplitude amplification.

The ingredients used here are efficient sparse Hamiltonian simulation of $e^{iAt}$ and quantum phase estimation, which converts an eigenphase of that evolution into a binary approximation of ${\lambda }_j$. For sparsity $s$, condition number $\kappa$, and error $ϵ$, the cost is polynomial in $s$, $\kappa$, $1/ϵ$, and $\log N$ under the stated access assumptions.

Finally estimate $⟨x|M|x⟩$ by repeated measurement of an efficient observable decomposition of $M$, or by a Hadamard test when $M$ is unitary. A general efficiently block-encoded Hermitian $M$ can similarly be measured through its block encoding. Repetition and a concentration inequality give additive sampling error $O(1/\sqrt{R})$ after $R$ independent preparations.

If some integer $k$ obeys $(2k+1)\theta =\pi /2$, ordinary amplitude amplification already gives $|g⟩$ exactly. For a general known $\theta$, use exact amplitude amplification. Choose $k$ so thatand put $c=\sin {\theta }^{\prime }/\sin \theta \le 1$. Append an ancilla and coherently arrange that its designated good value has amplitude $c$ conditional on the original register being good. With the enlarged good subspace defined bythe starting state's total good amplitude is $c\sin \theta =\sin {\theta }^{\prime }$.

Apply the amplitude amplification theorem $k$ times to this enlarged problem. Its final good amplitude isThe Boolean quantum oracle implements the reflection $I_G$ by phase kickback, and the known state-preparation circuit implements the reflection about the starting state by prepare--reflect--unprepare. A final computational-basis measurement therefore yields an $x$ with $f(x)=1$ with certainty.

Let ${\Pi }_{\mathcal{G}}$ be the orthogonal projection onto the good linear subspace and writewhere the two displayed states are normalized projections into $\mathcal{G}$ and ${\mathcal{G}}^{\perp }$. Define the reflectionsThe amplitude amplification iterate $Q=R_{\psi }{R}_G$ preserves the good-bad plane, and its $k$th iterate satisfiesThus repeated reflections rotate amplitude toward the good subspace, reaching constant success probability after $O(1/\sin \theta )$ iterations.

Attach a quantum ancilla prepared with amplitudeon $|1⟩$; this is possible because $p>1/4$. Mark a state as good only when both the original success qubit and this ancilla equal one. The enlarged state's good probability is $p{c}^2=1/4$, so its good amplitude is $1/2=\sin (\pi /6)$. One amplitude amplification iteration rotates the angle from $\pi /6$ to $3\pi /6=\pi /2$. It therefore prepares $|{\psi }_1⟩$ exactly, after which the flag and ancillary qubits may be discarded. This is an instance of exact amplitude amplification.

The amplitude amplification success probability isChoose $k$ to be the nearest integer to $\pi /(4\theta )-1/2$. Then $(2k+1)\theta$ differs from $\pi /2$ by at most $\theta$, so $P_k\ge {\cos }^2\theta =1-p$. Since $\theta =\arcsin \sqrt{p}\sim \sqrt{p}$, this usesiterations and makes the good amplitude arbitrarily close to one when $p$ is small.

Choose an integer $k$ large enough thatPrepare an ancillary qubit in $\sqrt{1-c^2}|0⟩+c|1⟩$ and declare only $|\xi ⟩|1⟩$ to be good. The initial good amplitude ofis $pc=\sin {\theta }^{\prime }$. Applying $k$ amplitude amplification iterations gives good amplitudeThe final state is therefore $|\xi ⟩|1⟩$ up to a global phase. Discarding the ancilla prepares $|\xi ⟩$ exactly; this is exact amplitude amplification.

Normalization gives $p^2+q^2=1$. Write $p=\sin \theta$, $q=\cos \theta$ with $0<\theta <\pi /2$, and set $|u⟩=U|b⟩$. Define the two Householder reflectionsThe amplitude amplification iterate $G=R_u{R}_{\xi }$ preserves $\mathrm{span}\{|\xi ⟩,|\varphi ⟩\}$ and rotates that plane through $2\theta$. ConsequentlyIn particular, $O(1/p)$ iterations raise the success probability to a constant close to one.

Prepare $|\xi ⟩=Q^{-1/2}{\sum }_b|b⟩$ in the second register by part (ii), while preserving the first register $|a⟩$. Applying the diagonal unitary $V$ from part (iii) givesThe preparation can be made coherent using amplitude amplification in place of postselection when this map is needed as a subroutine.

To find an input of a permutation whose output lies in a known $K$-element subset, compute the output, apply its marked-state phase oracle, and use uncomputation. A modular-addition quantum oracle costs two forward queries per marked reflection, because modular-oracle inversion by negation supplies its inverse. Amplitude amplification then uses $O(\sqrt{N/K})$ queries for fixed success probability. Positive-square outputs have $K=\lfloor \sqrt{N-1}\rfloor$ and hence query cost $O(N^{1/4})$.