Amplitude Amplification

Amplitude amplification raises the probability that a coherent preparation passes a declared success test. If one execution prepares a good component with probability $a>0$, independent preparation, measurement, and restart needs an expected $1/a$ trials. Given the preparation $\mathcal A$, its inverse, and two exact reflections, coherent amplification reduces the number of component uses to order $1/\sqrt a$.

That square-root improvement is conditional. A measured or irreversible routine is not automatically an invertible preparation, a success predicate is not automatically a cheap coherent reflection, and an unknown $a$ does not supply its own stopping time. This page gives the general theorem, its known- and unknown-success regimes, exact and fixed-point variants, and the resource ledger that must travel with the result. Grover Search retains the uniform marked-item specialization and its search-specific optimality theorem.

Required background. Algorithmic Primitives supplies the access–processing–interference–readout vocabulary used here. Quantum Oracles supplies complete coherent interfaces, inverse-access rules, phase representatives, and the boundary between a query and its implementation.

Helpful background. The Quantum Algorithms and Complexity guide supplies the ten-field claim record. Query Complexity separates fixed-cap from expected query measures and owns general lower-bound methods. Grover Search provides the canonical uniform-search geometry. Phase Kickback derives clean Boolean marking reflections after the underlying oracle has been declared.

The General Success-Amplification Problem

Let $\mathcal H$ be a finite-dimensional Hilbert space with normalized reference state $|0\rangle$. A measurement-free unitary $\mathcal A$ prepares

$$|\psi\rangle = \mathcal A|0\rangle.$$

Let $\Pi_G$ be the orthogonal projector onto the good subspace. The initial acceptance probability is

$$a = \langle\psi|\Pi_G|\psi\rangle = \|\Pi_G|\psi\rangle\|^2, \qquad 0\le a\le1.$$

The primary task is to produce a state whose final $\{\Pi_G,I-\Pi_G\}$ test accepts with substantially larger probability. If an application needs a classical witness, it must additionally specify a readout basis, the map from outcomes to candidates, and a verifier. Acceptance of a subspace and recovery of a useful classical object are not identical output contracts.

Two endpoint cases should be removed before introducing a two-dimensional picture:

• If $a=0$, then $\mathcal A|0\rangle$ has no component in the good subspace. The declared reflections preserve that absence, so ordinary amplitude amplification cannot create success.
• If $a=1$, the prepared state is already good. Measuring immediately is at least as useful as applying an amplification iterate.

For $0<a<1$, the goal is not to copy an unknown amplitude or to measure it without disturbance. The algorithm rotates the entire coherent state within an invariant plane and measures only after the chosen schedule is complete.

The safe asymptotic statement is therefore

$$\text{measure and restart: } \mathbb E[T]=\frac1a,$$ $$\text{coherent amplification: } O\!\left(\frac1{\sqrt a}\right) \text{ component uses}.$$

This is a comparison with incoherent repetition of the declared preparation, not by itself a theorem comparing the best classical and quantum algorithms for an application.

The Ten-Field Amplitude-Amplification Claim Record

Use the following record before accepting an amplification claim. Every field needs a value; an unknown cost is not zero, and an unavailable capability is not silently supplied by notation.

1. Problem family and size. State the family of preparations and success tests, the parameter controlling $a$, and the asymptotic variable.
2. Promise and instance. State whether $a$ is zero, positive, known, unknown, or lower-bounded, and identify the finite instance being checked.
3. Access and encoding. Declare $\mathcal A$, $\mathcal A^\dagger$, $\Pi_G$, the two reflections, every register, and any verifier or phase- family access.
4. Output and use. Specify whether the output is acceptance, a good quantum state, or a measured classical candidate, together with its later use.
5. Success and error. Give the initial success $a$, final acceptance or failure guarantee, approximation metric, and fixed-cap or expected convention.
6. Algorithmic idea. Identify the good–bad invariant plane, reflection order, phase convention, and schedule regime.
7. Executable procedure. Give preparation, iterate count or randomized window, measurement, verification, retries, and stopping behavior.
8. Resource ledger. Count forward and inverse preparations, both reflections, verification, measurements, gates, depth, width, synthesis, and physical resources separately.
9. Classical comparator. Match the input, success predicate, output, access, error, and cost model; distinguish repeated use of the same base routine from the best alternative method.
10. Evidence and limits. State whether the support is an exact theorem, finite arithmetic audit, simulation, or experiment, then name the conclusions and specialist variants it does not establish.

The record exposes common hidden substitutions: an abstract verifier for a unit-cost reflection, source code for licensed inverse access, an expected stopping theorem for a fixed-cap one, or a quadratic reduction in one factor for an end-to-end speedup.

Licensed State Preparation and Success Access

The ordinary amplitude-amplification interface supplies four coherent operations:

$$\mathcal A, \qquad \mathcal A^\dagger, \qquad S_G=I-2\Pi_G, \qquad S_0=I-2|0\rangle\langle0|.$$

The final projective test and any classical candidate verification are additional operations. The following distinctions are operational, not stylistic.

Component	Mathematical role	Access question that must be answered
$\mathcal A$	prepares $	\psi\rangle$
$\mathcal A^\dagger$	reverses the entire preparation	Are every subroutine inverse and every work register available?
$S_G$	changes the phase of the good subspace by $\pi$	How is membership computed, phased, and uncomputed?
$S_0$	changes the reference-state phase by $\pi$	What multi-controlled operation and ancilla cost implement it?
readout and verifier	turns acceptance into a usable result	Is verification exact, noisy, destructive, or separately queried?

A gate-level circuit for $\mathcal A$ normally gives an inverse by reversing the gate order and adjointing each gate. An opaque channel, remote service, measurement-based routine, or dissipative preparation does not. It needs a coherent dilation with retained environment and workspace, and that dilation must itself be accessible in reverse. Reversible Computation owns the general cleanup and inverse-workspace contract; Circuit Model owns registers, composition, measurements, and logical resource currencies.

Likewise, a classical predicate $\chi(x)$ is not yet $S_G$. If a clean XOR oracle is licensed, a minus ancilla yields the Boolean phase $(-1)^{\chi(x)}$ in one query. A predicate circuit with temporary garbage may instead need compute–phase–uncompute. Phase Kickback owns that conversion and its sign checks. This page begins from the resulting reflection and debits whatever construction the access contract requires.

The full action matters outside the one prepared state. The iterate applies $\mathcal A^\dagger$, $S_0$, and $\mathcal A$ after the first success reflection, so a promise stated only on $|0\rangle$ or only on computational- basis inputs may be insufficient to define the coherent sequence.

The Good–Bad Invariant Plane

Assume $0<a<1$ and define the normalized projections

$$|G\rangle = \frac{\Pi_G|\psi\rangle}{\sqrt a}, \qquad |B\rangle = \frac{(I-\Pi_G)|\psi\rangle}{\sqrt{1-a}}.$$

Orthogonality follows from $\Pi_G(I-\Pi_G)=0$, and normalization follows from the definition of $a$. Introduce the unique angle $\theta\in(0,\pi/2)$ satisfying

$$\sin^2\theta=a.$$

Then

$$|\psi\rangle = \sin\theta|G\rangle + \cos\theta|B\rangle.$$

The two basis vectors are the normalized good and bad parts of this particular $|\psi\rangle$. They need not be uniform over basis labels, and each may contain arbitrary internal amplitudes and relative phases. An amplification iterate changes only their two coefficients; it does not redistribute weight within either projection.

The Mathematical Projectors page supplies the range–kernel decomposition and the algebra behind $I-2P$. Here that algebra has two immediate consequences:

$$S_G|G\rangle=-|G\rangle, \qquad S_G|B\rangle=|B\rangle,$$

and reflection about $|\psi\rangle$ maps every linear combination of $|G\rangle$ and $|B\rangle$ back into their span. Thus

$$\mathcal K_\psi = \operatorname{span}\{|G\rangle,|B\rangle\}$$

is invariant under both ideal reflections. The full Hilbert-space evolution relevant to the prepared state reduces exactly to a real two-dimensional rotation even when the good and bad subspaces themselves have high dimension.

Two Reflections and the Generalized Grover Iterate

Fix the sign convention

$$Q = -\mathcal A S_0\mathcal A^\dagger S_G.$$

Because

$$-\mathcal A S_0\mathcal A^\dagger = 2|\psi\rangle\langle\psi|-I,$$

$Q$ first applies the good-subspace reflection and then reflects about the prepared-state axis. Operators act from right to left in the displayed product. In the ordered basis $\{|G\rangle,|B\rangle\}$,

$$S_G = \begin{pmatrix} -1&0\\ 0&1 \end{pmatrix},$$

while

$$2|\psi\rangle\langle\psi|-I = \begin{pmatrix} -\cos2\theta&\sin2\theta\\ \sin2\theta&\cos2\theta \end{pmatrix}.$$

Their product is

$$Q = \begin{pmatrix} \cos2\theta&\sin2\theta\\ -\sin2\theta&\cos2\theta \end{pmatrix}.$$

It has determinant one, eigenvalues $e^{\pm2i\theta}$, and advances a vector written as

$$|\psi(\phi)\rangle = \sin\phi|G\rangle + \cos\phi|B\rangle$$

according to

$$Q|\psi(\phi)\rangle = |\psi(\phi+2\theta)\rangle.$$

Some references absorb the leading minus sign into one reflection or reverse the basis order. Those choices can change the displayed matrix or apparent rotation direction while leaving observable probabilities unchanged. A proof must use one convention consistently rather than combine formulas from different choices.

Exact Rotation and Success Probability

The prepared state begins at angle $\theta$. Repeated application of the same ideal iterate gives, for every integer $r\ge0$,

$$Q^r\mathcal A|0\rangle = \sin\!\left((2r+1)\theta\right)|G\rangle + \cos\!\left((2r+1)\theta\right)|B\rangle.$$

This follows directly by induction from the one-step rotation, or by diagonalizing $Q$. The final good-subspace probability is exactly

$$p_r = \|\Pi_GQ^r|\psi\rangle\|^2 = \sin^2\!\left((2r+1)\theta\right).$$

For one iterate, the triple-angle identity gives a useful polynomial check:

$$p_1 = a(3-4a)^2.$$

The probability is periodic rather than monotone. An integer $r$ that places $(2r+1)\theta$ close to $\pi/2$ gives high success, while another iterate can move the state past the good axis. There is no internal measurement announcing that the peak has been crossed.

Ideal amplification also preserves the normalized direction of each projection. Conditioned on a good final result, the state within the good subspace is $|G\rangle$, exactly the normalized good component originally prepared by $\mathcal A$. The primitive increases its weight; it does not choose a different good-state distribution.

Known Initial Success and Stopping Rules

Suppose $a>0$ and hence $\theta$ are known. Set

$$m = \left\lfloor\frac{\pi}{4\theta}\right\rfloor.$$

If $a\le1/2$, then $\theta\le\pi/4$ and the floor relation places the final angle within $\theta$ of $\pi/2$:

$$\left| (2m+1)\theta- \frac\pi2 \right| \le\theta.$$

Consequently,

$$p_m \ge \cos^2\theta = 1-a.$$

If $a>1/2$, then $m=0$ and $p_m=a$. Together these cases give the precise ordinary-reflection guarantee

$$p_m \ge \max\{a,1-a\} \ge \frac12.$$

Since $\theta=\arcsin\sqrt a\ge\sqrt a$,

$$m \le \frac{\pi}{4\sqrt a},$$

so the schedule uses $O(1/\sqrt a)$ iterates. Repeating the whole amplified run independently $k$ times and verifying each output reduces a failure of at most one half to at most $2^{-k}$. Such repetition requires fresh coherent runs; it is not another free unitary step.

The ordinary $\pi$ reflections do not generally give certainty because the first probability maximum need not occur at an integer iterate. Exact known- $a$ constructions alter the contract. One method adds an auxiliary rotation that attenuates the initial success to

$$\bar a = \sin^2\!\left(\frac{\pi}{4\bar m+2}\right),$$

where

$$\bar m = \left\lceil \frac{\pi}{4\theta}-\frac12 \right\rceil,$$

and then performs $\bar m$ ordinary iterates. Another replaces the terminal reflections by phases computed from $a$. Both achieve exact success with $O(1/\sqrt a)$ component uses, but the ancilla rotation or phase-family access and its synthesis must be counted.

Unknown Success, Randomized Search, and Verification

When $a$ is unknown, using a count optimized for a guessed value can fail by over-rotation. A randomized schedule avoids committing every attempt to one phase. The QSearch strategy of Brassard, Høyer, Mosca, and Tapp has the following pattern:

1. choose a window size that grows geometrically between failed rounds;
2. prepare $\mathcal A|0\rangle$ and choose an iteration count uniformly from the current window;
3. apply that many ordinary iterates, measure, and verify the candidate;
4. stop on verified success and otherwise enlarge the window.

For exact verification and $a>0$, the procedure never returns an invalid candidate and uses an expected

$$\Theta\!\left(\frac1{\sqrt a}\right)$$

applications of $\mathcal A$ and $\mathcal A^\dagger$, together with the corresponding reflections. Randomization works because a sufficiently wide window averages across several rotation phases and therefore avoids a systematic bad stopping angle.

Three qualifications are essential:

• The theorem is an expected-cost statement with an unbounded stopping tail, not an exact finite cap.
• If $a=0$, exact QSearch runs forever. Repeated failure is not a proof that no good state exists.
• Verification is part of the algorithm. A destructive, noisy, or costly verifier changes both correctness and the resource ledger.

If a promise $a\ge a_0>0$ is available, a schedule may cap its largest window at order $1/\sqrt{a_0}$ and repeat enough independent attempts to reach a declared failure probability. Alternatively, a fixed-point sequence can use the same lower bound without oscillating through a single unknown peak. These are different guarantee regimes and should be named separately.

Amplitude Estimation owns numerical estimation of $a$, including the amplitude-specific use of controlled powers, its precision guarantees, and its confidence protocols; this page retains the amplification iterate and its success-boosting schedules.

Exact, Fixed-Point, and Approximate Variants

Generalized reflections attach phases rather than only signs:

$$S_0(\phi) = I+(e^{i\phi}-1)|0\rangle\langle0|,$$ $$S_G(\varphi) = I+(e^{i\varphi}-1)\Pi_G.$$

With

$$Q(\phi,\varphi) = -\mathcal A S_0(\phi)\mathcal A^\dagger S_G(\varphi),$$

arbitrary phases do not retain the ordinary $2\theta$ rotation. In Høyer’s repeatable pseudo-rotation convention, for $\phi\ne\pi$ the phases must obey

$$\tan\frac\varphi2 = (1-2a)\tan\frac\phi2.$$

The condition depends on $a$. Equal arbitrary phases are not automatically matched, and a final exact phase choice is not available from only a $\pi$-reflection interface.

Fixed-point amplification solves another problem: make success uniformly high over a promised interval without the ordinary schedule’s over-rotation. For a lower bound $a\ge a_0>0$, a failure-amplitude target $0<\delta\le1$, and an odd sequence length $L=2\ell+1\ge1$, the Yoder–Low–Chuang construction has

$$P_L(a,\delta) = 1- \delta^2 T_L\!\left( T_{1/L}(1/\delta)\sqrt{1-a} \right)^2.$$

For $x\ge1$, the fractional Chebyshev function in this formula is

$$T_{1/L}(x) = \cosh\!\left( \frac1L\operatorname{arcosh}x \right).$$

If

$$a \ge w(L,\delta) = 1-T_{1/L}(1/\delta)^{-2},$$

then

$$P_L(a,\delta) \ge 1-\delta^2.$$

For a nonzero target $\delta$, a suitable sequence length scales as

$$L = O\!\left( \frac{\log(2/\delta)}{\sqrt{a_0}} \right).$$

Here $\delta^2$ is the failure-probability bound. The paper’s convention counts $L-1=2\ell$ calls to its Boolean target oracle. The guarantee requires both the lower-bound promise and the specifically synthesized phase schedule.

Grover’s earlier recursive $\pi/3$ construction also removes over-rotation. After $k$ recursion levels its failure is $(1-a)^{3^k}$, so ensuring failure at most $\delta^2$ requires

$$3^k \ge \frac{\log(1/\delta^2)}{-\log(1-a_0)}.$$

Its query cost is $O(1/a_0)$ only for fixed target error and is $O(a_0^{-1}\log(1/\delta))$ for small $a_0$ when $\delta$ varies. It therefore loses the quadratic dependence. No finite nontrivial phase sequence can give exact success for every $a$ in a continuous interval.

Approximate implementations require a separate error budget. Let $|\psi\rangle$ and $|\widetilde\psi\rangle$ be normalized, and let $\widetilde Q$ be unitary or, more generally, a contraction. Suppose

$$\|\widetilde Q-Q\|\le\eta$$

and

$$\||\widetilde\psi\rangle-|\psi\rangle\| \le \eta_0.$$

A telescoping sum and contractivity give

$$\| \widetilde Q^r|\widetilde\psi\rangle - Q^r|\psi\rangle \| \le \eta_0+r\eta.$$

For any final projector, the resulting probability difference is at most $2(\eta_0+r\eta)$. A sufficient allocation for overall state error of order $\epsilon$ is therefore $\eta=O(\epsilon/r)$ after budgeting preparation error. This worst-case coherent bound does not model stochastic hardware noise or prove fault-tolerant feasibility.

Query Scaling, Applications, and Ownership Limits

For exactly $r$ ordinary iterates after one initial preparation, the component ledger is

$$N_{\mathcal A}=r+1, \qquad N_{\mathcal A^\dagger}=r,$$ $$N_{S_G}=r, \qquad N_{S_0}=r.$$

Add final measurement and candidate verification separately. A supplied $S_G$ costs one reflection call. A clean Boolean XOR oracle can implement the $\pi$ reflection with one minus-ancilla query, whereas a general $e^{i\varphi\Pi_G}$ operation may require compute–phase–uncompute and two verifier-oracle calls unless arbitrary-phase access is directly licensed.

Currency	What the asymptotic iterate count does not determine
preparation	gates, depth, data loading, random-seed generation, and workspace in $\mathcal A$
inverse preparation	whether every oracle and physical operation is reversibly available
success reflection	predicate construction, cleanup, phase synthesis, and verifier error
reference reflection	multi-controlled-gate, ancilla, routing, and native-gate cost
output	readout basis, candidate verification, retries, and classical decoding
implementation	approximation, noise, logical failure, error correction, and spacetime volume

The $O(1/\sqrt a)$ dependence required to reach any fixed nontrivial constant success probability is worst-case optimal for a generic black-box amplifier: choose $\mathcal A$ as uniform preparation and let one of $N$ basis states be good, so $a=1/N$. A uniformly better dependence would violate the bounded- error unstructured-search lower bound. This is a reduction over a family of access interfaces, not a claim that every fixed preparation is difficult. Query Complexity owns the general lower-bound methodology, and Grover Search owns the search-specific finite constants and optimality theorem.

Useful applications include boosting a coherently implemented one-sided procedure, preparing a state conditioned on a heralded subspace, and reducing the repetition factor inside a larger algorithm. Each application inherits the access obligations above. A classical heuristic can be amplified only after its randomness, workspace, and verification have been embedded in a coherent reversible procedure; the resulting cost must still be compared with the best classical alternative under matched access. Classical Information Review owns that general comparator, while Claims, Hype, and Evidence Standards owns the step from a theorem to a public advantage claim.

Two specialist uses should not be collapsed into the primary theorem:

• Oblivious amplitude amplification acts on an ancilla-success block under linear-combination or block-encoding structure and may work uniformly for an unknown system input. Hamiltonian Simulation and Qubitization and Quantum Signal Processing retain those specialized constructions.
• Variable-time amplitude amplification uses a coherent decomposition into branches with different stopping times. Its cost depends on the stopping-time distribution rather than simply padding every branch to the longest runtime.

Block Encodings and QSVT owns the projected-unitary and block-encoding setting, including robust oblivious-amplification transformations and their normalization and error ledger; this page retains the generic two-reflection theorem, success laws, and schedule families.

Two Reproducible Finite Audits

The following checks use exact arithmetic. They test the rotation law, over-rotation, randomized-window averaging, and component ledgers without sampling uncertainty. Neither finite instance proves the asymptotic theorem by itself.

Exact rational arbitrary-preparer audit

In the ordered effective basis $\{|G\rangle,|B\rangle\}$, take

$$|\psi\rangle = \frac35|G\rangle + \frac45|B\rangle, \qquad a=\frac9{25},$$

so $\sin\theta=3/5$ and $\cos\theta=4/5$. The ideal iterate is

$$Q = \frac1{25} \begin{pmatrix} 7&24\\ -24&7 \end{pmatrix}.$$

Its columns are orthonormal, its determinant is one, and exact multiplication gives

$$Q|\psi\rangle = \frac{117}{125}|G\rangle - \frac{44}{125}|B\rangle.$$

Thus

$$p_1 = \frac{13689}{15625} = 0.876096.$$

A second iterate gives

$$Q^2|\psi\rangle = -\frac{237}{3125}|G\rangle - \frac{3116}{3125}|B\rangle,$$

and hence

$$p_2 = \frac{56169}{9765625} = 0.0057517056.$$

The exact claim record is:

1. Problem family and size. The family consists of arbitrary coherent preparations with a two-outcome good projector; this finite member is represented exactly in its two-dimensional invariant plane.
2. Promise and instance. The instance has known $a=9/25$, with normalized components in the ratio $3:4$ and neither endpoint branch present.
3. Access and encoding. The ordered basis is $\{|G\rangle,|B\rangle\}$, and exact calls to $\mathcal A$, $\mathcal A^\dagger$, $S_G$, and $S_0$ are licensed. Their internal circuits are unspecified.
4. Output and use. The output is the accept/reject result of the good- subspace projector after a chosen number of iterates; no classical witness is claimed.
5. Success and error. The exact probabilities are $9/25$ initially, $13689/15625$ after one iterate, and $56169/9765625$ after two. Numerical and sampling error are absent.
6. Algorithmic idea. The matrix rotates the prepared vector by $2\theta$ per application, so the first iterate approaches the good axis and the second severely overshoots it.
7. Executable procedure. Prepare once, apply $Q$ either once or twice, then perform the good-subspace test. The known-success prescription gives $m=\lfloor\pi/(4\theta)\rfloor=1$.
8. Resource ledger. The one-iterate run uses two forward preparations, one inverse, one good reflection, and one reference reflection. The two- iterate run uses three, two, two, and two, respectively, before one final measurement.
9. Classical comparator. Incoherent repetition of the same base preparation needs an expected $25/9$ trials. This small finite check is not a claim about the best classical algorithm or an asymptotic advantage.
10. Evidence and limits. Exact integer arithmetic verifies the matrix, norms, vectors, probabilities, and ledger. It does not construct $\mathcal A$, implement either reflection, or test noise and hardware.

The norm identities are visible without decimals:

$$117^2+44^2=125^2,$$ $$237^2+3116^2=3125^2.$$

The example is not a four-item uniform search. The effective coefficients can multiply arbitrary normalized states internal to the good and bad subspaces.

Unknown-success randomized-schedule audit

Now take an unknown-success instance whose actual value is

$$a=\frac1{16},$$

and choose $R$ uniformly from $\{0,1,2,3\}$. The exact ordinary-iterate probabilities are

$r$	$p_r$	forward $\mathcal A$	inverse $\mathcal A^\dagger$	each reflection
0	$1/16$	1	0	0
1	$121/256$	2	1	1
2	$3721/4096$	3	2	2
3	$63001/65536$	4	3	3

Putting the probabilities over a common denominator gives

$$\mathbb E[p_R] = \frac14 \left( \frac1{16} + \frac{121}{256} + \frac{3721}{4096} + \frac{63001}{65536} \right) = \frac{157609}{262144}.$$

Therefore

$$\mathbb E[p_R] = 0.601230621337890625.$$

The exact claim record is:

1. Problem family and size. This is one finite member of an unknown-$a$ amplification family; the checked window contains four possible iterate counts.
2. Promise and instance. The schedule is not told $a$ when choosing $R$; the audit fixes the hidden value $a=1/16$ so its exact performance can be enumerated.
3. Access and encoding. Exact forward and inverse preparations, both ordinary $\pi$ reflections, a final measurement, and a candidate verifier are licensed. Phase-family access is not used.
4. Output and use. One attempt returns a measured candidate only when the verifier accepts it; failure causes a later scheduling layer to continue.
5. Success and error. Each $p_r$ is a conditional quantum Born probability, and averaging over the declared uniform classical choice of $R$ gives $157609/262144$. Both layers are evaluated exactly, with no numerical or finite-sampling uncertainty.
6. Algorithmic idea. A window averages several oscillatory phases rather than betting on one stopping angle chosen from an unknown $a$.
7. Executable procedure. Sample $R$, prepare once, apply $Q^R$, measure, and verify. This single window is an auditable component, not the complete geometrically growing QSearch procedure.
8. Resource ledger. Per attempt, the expectations are $5/2$ forward preparations, $3/2$ inverse preparations, $3/2$ calls to each reflection, one measurement, and one verification.
9. Classical comparator. Measure-and-restart use of the base preparation has mean sixteen trials. The window average alone does not establish the full expected $\Theta(1/\sqrt a)$ theorem or a classical runtime advantage.
10. Evidence and limits. Exhaustive exact rational evaluation verifies all four probabilities and resource means. It does not prove growing-window constants, bounded tails, the $a=0$ case, fixed-point guarantees, or an implementation result.

The following single exact-integer audit reproduces both records:

const assert = (condition, label) => {
  if (!condition) throw new Error(label);
};

const equalFraction = (an, ad, bn, bd) => an * bd === bn * ad;

// Rational arbitrary-preparer audit.
const q = [[7n, 24n], [-24n, 7n]];
const applyQ = ([x, y]) => [
  q[0][0] * x + q[0][1] * y,
  q[1][0] * x + q[1][1] * y,
];

const q1Numerator = applyQ([3n, 4n]);
const q2Numerator = applyQ(q1Numerator);

assert(q1Numerator[0] === 117n && q1Numerator[1] === -44n, 'Q psi');
assert(q2Numerator[0] === -237n && q2Numerator[1] === -3116n, 'Q2 psi');
assert(7n * 7n + 24n * 24n === 25n * 25n, 'column norm');
assert(7n * 24n + (-24n) * 7n === 0n, 'column orthogonality');
assert(7n * 7n - 24n * (-24n) === 25n * 25n, 'determinant');
assert(117n ** 2n + 44n ** 2n === 125n ** 2n, 'first state norm');
assert(237n ** 2n + 3116n ** 2n === 3125n ** 2n, 'second state norm');
assert(equalFraction(117n ** 2n, 125n ** 2n, 13689n, 15625n), 'p1');
assert(equalFraction(237n ** 2n, 3125n ** 2n, 56169n, 9765625n), 'p2');
assert(18n < 25n, 'theta below pi/4 from (3/5)^2 < 1/2');
assert(2n * 625n > 196n, 'theta above pi/8 from sqrt(2) > 14/25');
const firstAuditLedgers = [
  { r: 1n, forward: 2n, inverse: 1n, good: 1n, reference: 1n },
  { r: 2n, forward: 3n, inverse: 2n, good: 2n, reference: 2n },
];
firstAuditLedgers.forEach(({ r, forward, inverse, good, reference }) => {
  assert(forward === r + 1n, `r=${r} forward ledger`);
  assert(inverse === r, `r=${r} inverse ledger`);
  assert(good === r && reference === r, `r=${r} reflection ledger`);
});
const p1Decimal = Number(13689n) / Number(15625n);
const p2Decimal = Number(56169n) / Number(9765625n);
assert(p1Decimal === 0.876096, 'p1 decimal');
assert(p2Decimal === 0.0057517056, 'p2 decimal');

// Unknown-success window at a = 1/16, derived by exact recurrence.
const gcd = (a, b) => b === 0n ? (a < 0n ? -a : a) : gcd(b, a % b);
const fraction = (n, d) => {
  const sign = d < 0n ? -1n : 1n;
  const divisor = gcd(n, d);
  return [sign * n / divisor, sign * d / divisor];
};
const subtract = ([an, ad], [bn, bd]) =>
  fraction(an * bd - bn * ad, ad * bd);
const multiply = ([an, ad], [bn, bd]) => fraction(an * bn, ad * bd);
const square = ([n, d]) => fraction(n * n, d * d);

const sineTheta = [1n, 4n];
const successA = square(sineTheta);
const sineThreeTheta = multiply(sineTheta,
  subtract([3n, 1n], multiply([4n, 1n], successA)));
const twiceCosineTwoTheta = subtract([2n, 1n],
  multiply([4n, 1n], successA));
assert(equalFraction(successA[0], successA[1], 1n, 16n), 'a = 1/16');
assert(equalFraction(sineThreeTheta[0], sineThreeTheta[1], 11n, 16n),
  'sin 3 theta');
assert(equalFraction(twiceCosineTwoTheta[0], twiceCosineTwoTheta[1], 7n, 4n),
  '2 cos 2 theta');

const amplitudes = [sineTheta, sineThreeTheta];
for (let r = 1; r < 3; r += 1) {
  amplitudes.push(subtract(multiply(twiceCosineTwoTheta, amplitudes[r]),
    amplitudes[r - 1]));
}
const probabilities = amplitudes.map(square);
const expectedProbabilities = [
  [1n, 16n], [121n, 256n], [3721n, 4096n], [63001n, 65536n],
];
expectedProbabilities.forEach(([n, d], r) => {
  assert(equalFraction(probabilities[r][0], probabilities[r][1], n, d),
    `window p${r}`);
});

const commonDenominator = 65536n;
const numeratorSum = probabilities.reduce(
  (sum, [n, d]) => sum + n * (commonDenominator / d),
  0n,
);

assert(numeratorSum === 157609n, 'window probability sum');
assert(equalFraction(numeratorSum, 4n * commonDenominator,
  157609n, 262144n), 'window mean');
const windowDecimal = Number(157609n) / Number(262144n);
assert(windowDecimal === 0.601230621337890625, 'window decimal');
const iterations = [0n, 1n, 2n, 3n];
const forwardSum = iterations.reduce((sum, r) => sum + r + 1n, 0n);
const inverseSum = iterations.reduce((sum, r) => sum + r, 0n);
const goodReflectionSum = iterations.reduce((sum, r) => sum + r, 0n);
const referenceReflectionSum = iterations.reduce((sum, r) => sum + r, 0n);
assert(equalFraction(forwardSum, 4n, 5n, 2n), 'forward mean 5/2');
assert(equalFraction(inverseSum, 4n, 3n, 2n), 'inverse mean 3/2');
assert(equalFraction(goodReflectionSum, 4n, 3n, 2n),
  'good-reflection mean 3/2');
assert(equalFraction(referenceReflectionSum, 4n, 3n, 2n),
  'reference-reflection mean 3/2');
assert(equalFraction(4n, 4n, 1n, 1n), 'one measurement per attempt');
assert(equalFraction(4n, 4n, 1n, 1n), 'one verification per attempt');

console.log('exact amplitude-amplification audits: PASS');

Common Amplitude-Amplification Failures

Omitting the inverse preparation. The reflection about $\mathcal A|0\rangle$ contains $\mathcal A^\dagger$. A sampler that can only run forward, or a process that discards measurement records, does not satisfy the ordinary interface.

Treating the success reflection as free. A mathematical projector does not construct its own coherent phase oracle. Predicate evaluation, garbage cleanup, phase synthesis, and verification can dominate the total cost.

Calling measure-and-restart a classical lower bound. The $1/a$ mean describes repetition of the declared base preparation. It is not a lower bound on every classical algorithm for the surrounding problem.

Assuming more iterations always help. Ordinary amplification is a rotation. Passing the peak decreases success and can nearly erase the good component.

Ignoring the zero-success branch. No sequence generated by the declared reflections can produce a component that was initially absent. Unknown-$a$ QSearch therefore needs a promise or cutoff if $a=0$ is possible.

Equating exact and fixed-point amplification. Exact phase matching uses known amplitude information or attenuation. Fixed-point schedules use a lower bound and nonzero tolerated failure over an interval. Their guarantees and access requirements are different.

Substituting arbitrary equal phases. Høyer’s matching relation depends on $a$. Replacing both $\pi$ phases by the same convenient angle does not in general produce the desired rotation.

Using “oblivious” as a synonym for ordinary amplification. Oblivious variants require additional block structure and act uniformly over system inputs. Their hypotheses cannot be inferred from the state-specific theorem.

Dropping coherent error accumulation. A small systematic error per iterate can accumulate linearly in a worst-case norm bound. The amplification count must be joined to synthesis and fault-tolerance tolerances.

Reporting queries as total runtime. Preparation, inverse access, reflections, verification, measurements, retries, compilation, routing, classical processing, and physical spacetime remain separate resources.

Exercises

1. Normalize the good–bad decomposition

Let $|\psi\rangle$ be normalized and $a=\langle\psi|\Pi_G|\psi\rangle$. For $0<a<1$, prove that the definitions of $|G\rangle$ and $|B\rangle$ give an orthonormal pair and reconstruct $|\psi\rangle$. Then explain the $a=0$ and $a=1$ branches without dividing by zero.

Solution

Because $\Pi_G$ is an orthogonal projector,

$$\|\Pi_G|\psi\rangle\|^2 = \langle\psi|\Pi_G^2|\psi\rangle = a.$$

Similarly,

$$\|(I-\Pi_G)|\psi\rangle\|^2 = \langle\psi|(I-\Pi_G)|\psi\rangle = 1-a.$$

Thus the stated denominators normalize the two vectors. Their inner product is

$$\langle G|B\rangle = \frac{ \langle\psi|\Pi_G(I-\Pi_G)|\psi\rangle }{\sqrt{a(1-a)}} = 0.$$

Adding the two projected components gives

$$\sqrt a|G\rangle + \sqrt{1-a}|B\rangle = \Pi_G|\psi\rangle + (I-\Pi_G)|\psi\rangle = |\psi\rangle.$$

With $a=\sin^2\theta$ and $0<\theta<\pi/2$, the positive square roots are $\sin\theta$ and $\cos\theta$. If $a=0$, the good projection is the zero vector and no normalized $|G\rangle$ is defined or needed; the state is entirely bad. If $a=1$, the bad projection vanishes and the state is already entirely good.

2. Derive the reflection rotation and eigenphases

First use the Mathematical Projectors algebra to prove that $I-2P$ is a self-adjoint unitary for every orthogonal projector $P$. Then derive the two matrices defining $Q$, prove invariance of the good–bad plane, and find the eigenvalues of $Q$.

Solution

For $P=P^\dagger=P^2$,

$$(I-2P)^\dagger = I-2P,$$

and

$$(I-2P)^2 = I-4P+4P^2 = I.$$

The operator is therefore self-adjoint and its own inverse, hence unitary. Taking $P=\Pi_G$ gives

$$S_G = \begin{pmatrix} -1&0\\ 0&1 \end{pmatrix}$$

in the good–bad basis. Since $|\psi\rangle=(\sin\theta,\cos\theta)^{\mathsf T}$,

$$2|\psi\rangle\langle\psi|-I = \begin{pmatrix} 2\sin^2\theta-1&2\sin\theta\cos\theta\\ 2\sin\theta\cos\theta&2\cos^2\theta-1 \end{pmatrix}$$ $$= \begin{pmatrix} -\cos2\theta&\sin2\theta\\ \sin2\theta&\cos2\theta \end{pmatrix}.$$

Both matrices map the span of $|G\rangle$ and $|B\rangle$ to itself. Their product is

$$Q = \begin{pmatrix} \cos2\theta&\sin2\theta\\ -\sin2\theta&\cos2\theta \end{pmatrix}.$$

Its characteristic polynomial is

$$\lambda^2 - 2\cos2\theta\,\lambda + 1,$$

whose roots are $e^{\pm2i\theta}$. Multiplying the matrix by $(\sin\phi,\cos\phi)^{\mathsf T}$ gives $(\sin(\phi+2\theta),\cos(\phi+2\theta))^{\mathsf T}$, proving the stated rotation law.

3. Reproduce the rational arbitrary-preparer audit

For $|\psi\rangle=(3|G\rangle+4|B\rangle)/5$, reproduce $Q|\psi\rangle$, $Q^2|\psi\rangle$, both exact success probabilities, the norm checks, and the component ledgers for one and two iterates.

Solution

Here

$$\cos2\theta = \frac{16-9}{25} = \frac7{25}, \qquad \sin2\theta = 2\frac35\frac45 = \frac{24}{25}.$$

Therefore

$$Q \begin{pmatrix} 3/5\\ 4/5 \end{pmatrix} = \frac1{125} \begin{pmatrix} 7\cdot3+24\cdot4\\ -24\cdot3+7\cdot4 \end{pmatrix} = \frac1{125} \begin{pmatrix} 117\\ -44 \end{pmatrix}.$$

Applying $Q$ again gives

$$\frac1{3125} \begin{pmatrix} 7\cdot117-24\cdot44\\ -24\cdot117-7\cdot44 \end{pmatrix} = \frac1{3125} \begin{pmatrix} -237\\ -3116 \end{pmatrix}.$$

Hence

$$p_1 = \frac{117^2}{125^2} = \frac{13689}{15625},$$ $$p_2 = \frac{237^2}{3125^2} = \frac{56169}{9765625}.$$

The identities $117^2+44^2=125^2$ and $237^2+3116^2=3125^2$ verify normalization. For $r=1$, the tuple

$$(N_{\mathcal A},N_{\mathcal A^\dagger},N_{S_G},N_{S_0}) = (2,1,1,1)$$

is followed by one measurement. For $r=2$, it is $(3,2,2,2)$. Candidate verification, if required, is additional.

4. Prove the known-success stopping guarantee

Let $m=\lfloor\pi/(4\theta)\rfloor$. Prove $p_m\ge\max\{a,1-a\}$, show the resulting square-root scaling, and explain why certainty needs attenuation or a phase-adjusted final iterate.

Solution

For $0<a\le1/2$, one has $0<\theta\le\pi/4$. From

$$m \le \frac{\pi}{4\theta} < m+1$$

we obtain

$$-\theta \le \frac\pi2-(2m+1)\theta < \theta.$$

Writing the difference as $d$ gives

$$p_m = \sin^2\!\left(\frac\pi2-d\right) = \cos^2d \ge \cos^2\theta = 1-a.$$

For $a>1/2$, $\theta>\pi/4$, so $m=0$ and $p_m=a$. Thus the two cases give $p_m\ge\max\{a,1-a\}$. Since $\theta=\arcsin\sqrt a\ge\sqrt a$,

$$m \le \frac\pi{4\sqrt a}.$$

Ordinary iterates sample only angles $(2m+1)\theta$, which need not equal $\pi/2$ for an integer $m$. Attenuation changes the initial angle to one that lands exactly after an integer number of ordinary steps. A phase-adjusted terminal step instead changes the last rotation. Both require additional known-$a$ operations beyond the ordinary reflection interface.

5. Audit an unknown-success window

For actual $a=1/16$, choose $R$ uniformly from $\{0,1,2,3\}$. Reproduce the four probabilities and their mean. Explain why candidate verification and the $a=0$ stopping contract cannot be omitted from a full QSearch claim.

Solution

Let $s=\sin\theta=1/4$. Multiple-angle identities give

$$\sin3\theta = s(3-4s^2) = \frac{11}{16},$$ $$\sin5\theta = s(5-20s^2+16s^4) = \frac{61}{64},$$ $$\sin7\theta = s(7-56s^2+112s^4-64s^6) = \frac{251}{256}.$$

Squaring these amplitudes together with $\sin\theta=1/4$ gives

$$(p_0,p_1,p_2,p_3) = \left( \frac1{16}, \frac{121}{256}, \frac{3721}{4096}, \frac{63001}{65536} \right).$$

Over the common denominator $65536$, their numerator sum is $157609$, so

$$\mathbb E[p_R] = \frac{157609}{4\cdot65536} = \frac{157609}{262144}.$$

The mean forward count is $(1+2+3+4)/4=5/2$, and the mean inverse and each reflection count are $(0+1+2+3)/4=3/2$. Measurement alone can return an invalid candidate, so a verifier decides whether to stop. When $a=0$, every attempt fails; an uncapped exact procedure runs forever. A bounded decision claim therefore needs a positive-success promise or an explicit cutoff and error guarantee.

6. Check generalized and fixed-point phases

Use Høyer’s matching condition at $a=1/4$ and $\phi=\pi/2$. Then evaluate the Yoder–Low–Chuang threshold for $L=3$, $\delta=3\sqrt3/14$, and $a_0=1/4$.

Solution

The phase condition gives

$$\tan\frac\varphi2 = (1-2a)\tan\frac\phi2 = \frac12.$$

Therefore

$$\varphi = 2\arctan\frac12,$$

which is not $\phi=\pi/2$. Equal arbitrary phases would fail this matching test.

For the fixed-point values,

$$T_3\!\left(\frac2{\sqrt3}\right) = 4\left(\frac2{\sqrt3}\right)^3 - 3\left(\frac2{\sqrt3}\right) = \frac{14}{3\sqrt3} = \frac1\delta.$$

On the $x\ge1$ branch,

$$T_{1/3}(1/\delta) = \frac2{\sqrt3}.$$

Hence

$$w(3,\delta) = 1-\left(\frac2{\sqrt3}\right)^{-2} = \frac14.$$

At $a=a_0=1/4$, the argument of $T_3$ is one, so

$$P_3 = 1-\delta^2T_3(1)^2 = 1-\frac{27}{196} = \frac{169}{196}.$$

This is a uniform lower-bound guarantee with failure at most $27/196$, not exact success. In the paper’s convention, $L=3$ uses $L-1=2$ Boolean target- oracle calls.

7. Budget approximate iterates

Assume normalized $|\psi\rangle$ and $|\widetilde\psi\rangle$, unitary $Q$, contractive $\widetilde Q$, $\|\widetilde Q-Q\|\le\eta$, and $\||\widetilde\psi\rangle-|\psi\rangle\|\le\eta_0$. Prove the linear telescoping bound and translate a target final state error $\epsilon$ into a sufficient per-iterate precision.

Solution

Add and subtract $\widetilde Q^r|\psi\rangle$. The preparation term satisfies

$$\| \widetilde Q^r(|\widetilde\psi\rangle-|\psi\rangle) \| \le \eta_0$$

by contractivity. For the iterate term, use

$$\widetilde Q^r-Q^r = \sum_{j=0}^{r-1} \widetilde Q^{r-1-j} (\widetilde Q-Q) Q^j.$$

Every summand has operator norm at most $\eta$, so

$$\| \widetilde Q^r|\widetilde\psi\rangle - Q^r|\psi\rangle \| \le \eta_0+r\eta.$$

If $\eta_0\le\epsilon/2$, choosing

$$\eta \le \frac{\epsilon}{2r}$$

is sufficient for final state error at most $\epsilon$. A final projector’s probability error is at most twice the state-vector distance. The bound still does not price synthesis, inverse circuits, ancillas, logical failure, error-correction cycles, routing, calibration, or physical time; those enter the implementation ledger separately.

8. Repair an amplitude-amplification overclaim

Repair the sentence: “A quantum subroutine always turns a classical $1/a$ runtime into an optimal $1/\sqrt a$ algorithm.” Use the full chapter record and state exactly what can be concluded.

Solution

One defensible replacement is the following record.

1. Problem family and size. Consider a family of coherent preparation and acceptance-test pairs indexed by an input size, with initial success $a=a(n)>0$.
2. Promise and instance. State whether each $a$ is known, merely positive, or bounded below by $a_0(n)$. The stopping and failure theorem depends on this promise.
3. Access and encoding. License a measurement-free unitary $\mathcal A$, its implementable inverse, exact good and reference reflections, all work registers, final readout, and candidate verification.
4. Output and use. Say whether success means an accepted quantum state or a verified classical candidate, and specify what downstream procedure consumes it.
5. Success and error. For known $a$, ordinary amplification reaches success at least $\max\{a,1-a\}$ with $O(1/\sqrt a)$ iterates. Unknown-$a$ QSearch instead gives an expected-cost guarantee for $a>0$; fixed-point schedules require $a\ge a_0$ and nonzero tolerated failure.
6. Algorithmic idea. Two licensed reflections rotate the normalized good and bad projections within their invariant plane; schedule choice controls over-rotation.
7. Executable procedure. Prepare, apply the schedule appropriate to the promise, measure, verify, and either stop or retry according to an explicit fixed-cap or expected convention.
8. Resource ledger. For $r$ ordinary iterates count $r+1$ forward preparations, $r$ inverses, $r$ calls to each reflection, then measurement and verification. Add construction, gates, depth, width, cleanup, synthesis, error correction, and physical time.
9. Classical comparator. The $1/a$ quantity is the mean number of independent trials of the same base preparation. Calling it a classical runtime bound requires a matched classical algorithm and equivalent input, access, output, error, and verification costs.
10. Evidence and limits. The ideal theorem establishes a generic coherent square-root reduction in the success-probability factor. Grover reduction makes that dependence worst-case optimal for fixed nontrivial target success under the black-box family. It does not prove that every application gains a quadratic gate count, runtime, or practical advantage, and it does not import oblivious, variable-time, estimation, or fixed-point hypotheses automatically.

References

• A. Ambainis, “Variable Time Amplitude Amplification and a Faster Quantum Algorithm for Solving Systems of Linear Equations,” 29th International Symposium on Theoretical Aspects of Computer Science, LIPIcs 14, 636–647 (2012), doi:10.4230/LIPIcs.STACS.2012.636.
• D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma, “Simulating Hamiltonian Dynamics with a Truncated Taylor Series,” Physical Review Letters 114, 090502 (2015), doi:10.1103/PhysRevLett.114.090502.
• M. Boyer, G. Brassard, P. Høyer, and A. Tapp, “Tight Bounds on Quantum Searching,” Fortschritte der Physik 46, 493–505 (1998), arXiv:quant-ph/9605034.
• G. Brassard, P. Høyer, M. Mosca, and A. Tapp, “Quantum Amplitude Amplification and Estimation,” Contemporary Mathematics 305, 53–74 (2002), doi:10.1090/conm/305/05215.
• L. K. Grover, “A Fast Quantum Mechanical Algorithm for Database Search,” in Proceedings of the 28th Annual ACM Symposium on Theory of Computing, 212–219 (1996), doi:10.1145/237814.237866.
• L. K. Grover, “Fixed-Point Quantum Search,” Physical Review Letters 95, 150501 (2005), doi:10.1103/PhysRevLett.95.150501.
• P. Høyer, “On Arbitrary Phases in Quantum Amplitude Amplification,” Physical Review A 62, 052304 (2000), doi:10.1103/PhysRevA.62.052304.
• M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 10th Anniversary Edition, Cambridge University Press (2010), doi:10.1017/CBO9780511976667.
• T. J. Yoder, G. H. Low, and I. L. Chuang, “Fixed-Point Quantum Search with an Optimal Number of Queries,” Physical Review Letters 113, 210501 (2014), doi:10.1103/PhysRevLett.113.210501.
• C. Zalka, “Grover’s Quantum Searching Algorithm Is Optimal,” Physical Review A 60, 2746–2751 (1999), doi:10.1103/PhysRevA.60.2746.