Amplitude Amplification

Grover's search is not really about searching — it is the first sighting of a general engine. Take any quantum subroutine $A$ that, from $|0\rangle$ , gives the right answer with probability $p=a^2$ . Classically you run $A$ and check, run and check, about $1/p$ times before a success surfaces. Amplitude amplification reaches the same near-certain success with only $O(1/a)=O(1/\sqrt{p})$ invocations of $A$ and $A^{-1}$ — a quadratic speedup costing nothing beyond the ability to recognize a good answer. The reason it works is a piece of two-dimensional geometry. Brassard, Høyer, Mosca, and Tapp observed that $|\psi\rangle=A|0\rangle$ splits into orthogonal good and bad parts, $|\psi\rangle=\sin\theta\,|\psi_g\rangle+\cos\theta\,|\psi_b\rangle$ with $\sin^2\theta=p$ . The amplification operator $Q$ — a product of two reflections, one about the good subspace and one about $|\psi\rangle$ — is a rigid rotation by $2\theta$ inside the plane those two vectors span. The dynamics never leaves that plane, so the algorithm is exactly solvable: after $k$ rounds the good amplitude is $\sin((2k+1)\theta)$ , and you steer to the good axis in $\approx\pi/(4\theta)$ turns. The same $Q$ runs a second machine. Its eigenvalues are $e^{\pm 2i\theta}$ , so feeding $Q$ to quantum phase estimation reads $\theta$ — and hence $p$ — to a precision improving linearly in the $Q$ -calls, quadratically beating statistical sampling. That is amplitude estimation, the counting-and-integration cousin behind quantum Monte Carlo. One rotation, two payoffs.

Key takeaways

Amplitude amplification generalizes Grover: given any unitary $A$ preparing success amplitude $a=\sin\theta$ on a good subspace, $Q=-AS_0A^{-1}S_\chi$ rotates the state to near-certain success in $O(1/a)$ steps.
The state $A|0\rangle$ lives in a two-dimensional plane where $Q$ is a rotation by $2\theta$ , so $k$ rounds give good amplitude $\sin((2k+1)\theta)$ .
Choosing $k\approx\pi/(4\theta)\approx\pi/(4a)$ maximizes success — the quadratic speedup $O(1/a)$ versus classical $O(1/a^2)$ — with no advance knowledge of which inputs are good.
The same $Q$ has eigenphases $\pm 2\theta$ ; phase estimation on it estimates $p=\sin^2\theta$ to error $O(1/2^m)$ in the number $2^m$ of $Q$ -calls, a quadratically faster analog of Monte Carlo.
Special cases recover Grover search ( $a=\sqrt{M/N}$ ) and quantum counting; fixed-point and oblivious variants remove overshoot and the need to invert $A$ .
Key idea: any preparation $A|0\rangle=\sin\theta\,|\psi_g\rangle+\cos\theta\,|\psi_b\rangle$ confines the dynamics of $Q=-AS_0A^{-1}S_\chi$ to a 2D plane where $Q$ rotates by $2\theta$ ; $k$ iterations lift the success amplitude to $\sin((2k+1)\theta)$ , reaching certainty in $O(1/\theta)=O(1/a)$ steps.

The core insight

Any state preparation $A|0\rangle=\sin\theta\,|\psi_g\rangle+\cos\theta\,|\psi_b\rangle$ confines the dynamics of $Q=-AS_0A^{-1}S_\chi$ to a 2D plane where $Q$ is a rotation by $2\theta$ ; $k$ iterations boost the success amplitude to $\sin((2k+1)\theta)$ , giving certainty in $O(1/\theta)=O(1/a)$ steps.

Where this lives today

Amplitude estimation has become the near-term workhorse of quantum-advantage claims outside cryptography. Montanaro showed in 2015 that it gives a generic quadratic speedup for Monte Carlo estimation, and IBM's Woerner and Egger turned that into algorithms for financial risk — pricing options and value-at-risk with $O(1/\epsilon)$ instead of $O(1/\epsilon^2)$ samples. The catch is depth: textbook amplitude estimation runs full phase estimation on $Q$ , demanding long coherent circuits noisy hardware cannot sustain. That gap drives near-term variants — maximum-likelihood and iterative amplitude estimation replace the register with shallow $Q^k$ circuits plus classical post-processing. In the fault-tolerant direction, the oblivious form of amplitude amplification — amplifying a target unitary without inverting the full preparation — is a core subroutine of linear-combination-of-unitaries and qubitization, the backbone of modern Hamiltonian simulation and quantum linear algebra. Open questions stay sharp: how far can depth be cut before the speedup is lost, and can fixed-point and oblivious ideas combine into one robust, measurement-tolerant amplifier.

The physical picture

Forget databases and picture a single arrow on the unit circle. The horizontal axis is the bad direction $|\psi_b\rangle$ (every wrong answer collapsed to one vector); the vertical axis is the good direction $|\psi_g\rangle$ . Preparing $A|0\rangle$ places the arrow at angle $\theta$ above the horizontal, so its height — the good amplitude — is $\sin\theta$ , and the success probability is that height squared, $\sin^2\theta$ . Amplification is just tilting this arrow toward the vertical: each $Q$ is a matched pair of mirror reflections whose net effect is a clean rotation by $2\theta$ , ratcheting the arrow up by the same fixed angle every round. You only climb from $\theta$ to $90°$ , about $\pi/(4\theta)$ turns.

Figure

The two-dimensional Grover plane for N = 4 items with M = 1 marked, so θ = 30°. The prepared state has good amplitude sin θ = 0.5 and success probability 0.25. One application of Q rotates it by 2θ = 60° onto the good axis, where the amplitude is 1 and the success probability is exactly 1.00 — a single query solves the four-item search

The speedup is geometric. Sample classically and the probability accumulates linearly with tries, so you wait $\sim 1/\sin^2\theta$ rounds for a hit. Amplify quantumly and it is the amplitude that grows linearly with $Q$ -calls; because probability is amplitude squared, certainty arrives in $\sim 1/\sin\theta$ calls — the square root in the exponent lives exactly in that squaring. But the same fixed rotation rate carries a warning: keep turning past the vertical and the arrow swings past $90°$ and back down, so the success probability rises, peaks, and falls. There is a right number of iterations, and overshooting throws the answer away.

Figure

Success probability sin²((2k+1)θ) versus iteration count k for a hard instance with θ = 9°, initial p = 0.024. The probability climbs almost to 1, peaking at 0.976 at k = 4 and k = 5 — bracketing the ideal π/(4θ) ≈ 5 — then overshoots and falls back toward 0.024 by k = 9. The rotation is periodic, so more iterations is not better

For estimation the same plane is read rather than stopped: the eigenvalues $e^{\pm 2i\theta}$ encode $\theta$ , and phase estimation acts as a tachometer, reading $p=\sin^2\theta$ to error $\sim1/2^m$ in $2^m$ calls — quadratically better than classical sampling.

The core equations

Everything begins with a single structural claim: the initial state, however complicated $A$ is, is a two-term superposition once you group outcomes into good and bad. This is a definition, not an approximation — $|\psi_g\rangle,|\psi_b\rangle$ are the normalized projections onto the two subspaces, and $\theta$ is fixed by the success probability.

A|0\rangle=|\psi\rangle=\sin\theta\,|\psi_g\rangle+\cos\theta\,|\psi_b\rangle \qquad (1)

where: $A$ — state-preparation unitary (the subroutine being amplified); $|\psi_g\rangle$ — normalized projection onto the good subspace (success outcomes); $|\psi_b\rangle$ — normalized projection onto the orthogonal bad subspace; $\theta$ — angle with $\sin^2\theta=a^2=p$ the initial success probability, $a=\sin\theta$ the success amplitude. Reading: the whole state is one arrow in a 2D plane at height $\sin\theta$ ; all dynamics is its motion. The amplifier is built from two reflections. The oracle $S_\chi$ flips the sign of every good basis state — in the plane, a reflection across the bad axis. The initial-state reflection $S_0$ flips everything except $|0\rangle$ , and conjugating by $A$ turns it into a reflection about $|\psi\rangle$ .

S_\chi=I-2\!\!\sum_{x:\chi(x)=1}\!\!|x\rangle\langle x|,\qquad S_0=I-2|0\rangle\langle0| \qquad (2)

where: $\chi$ — Boolean predicate; $\chi(x)=1$ iff $x$ is good; $S_\chi$ — reflection negating the good subspace (across the $|\psi_b\rangle$ axis, angle $0$ ); $S_0$ — reflection about $|0\rangle$ , which $A(\cdot)A^{-1}$ maps to a reflection about $|\psi\rangle$ (axis at angle $\theta$ ). Reading: two mirrors, one on the bad axis, one tilted by $\theta$ . The amplification operator composes them. A product of two reflections whose axes differ by $\theta$ is a rotation by $2\theta$ ; the leading minus sign fixes it to be a proper rotation rather than a rotation-reflection.

Q=-A\,S_0\,A^{-1}\,S_\chi,\qquad AS_0A^{-1}=2|\psi\rangle\langle\psi|-I \qquad (3)

where: $AS_0A^{-1}$ — reflection about the prepared state $|\psi\rangle=A|0\rangle$ ; $Q$ — Grover-type iterate acting as a rotation by $2\theta$ in $\mathrm{span}\{|\psi_g\rangle,|\psi_b\rangle\}$ . Each $Q$ uses $A$ once and $A^{-1}$ once. Reading: $Q$ is a single, exactly-known rotation — why the algorithm is solvable in closed form. Applying $Q$ a total of $k$ times simply adds $k$ copies of the $2\theta$ turn to the initial angle $\theta$ .

Q^k\,A|0\rangle=\sin\!\big((2k+1)\theta\big)\,|\psi_g\rangle+\cos\!\big((2k+1)\theta\big)\,|\psi_b\rangle \qquad (4)

where: $k$ — number of amplification rounds; $(2k+1)\theta$ — total angle above the bad axis. The success probability after $k$ rounds is $\sin^2((2k+1)\theta)$ , near $1$ when $(2k+1)\theta\approx\pi/2$ . Solving $(2k+1)\theta=\pi/2$ and rounding to the nearest integer gives the optimal round count, with residual failure no larger than the initial success probability.

k_{\mathrm{opt}}=\left\lfloor\frac{\pi-2\theta}{4\theta}\right\rceil\approx\frac{\pi}{4\theta},\qquad p_{\mathrm{succ}}=\sin^2\!\big((2k_{\mathrm{opt}}+1)\theta\big)\ge 1-\sin^2\theta \qquad (5)

where: $\lfloor\cdot\rceil$ — round to nearest integer; $p_{\mathrm{succ}}$ — probability that measuring $Q^{k}A|0\rangle$ yields a good outcome. For $a\ll1$ , $\theta\approx a$ and $k_{\mathrm{opt}}\approx\pi/(4a)$ . Reading: the total number of calls to $A$ is $2k_{\mathrm{opt}}+1=O(1/a)$ , versus the classical $O(1/a^2)$ — the quadratic speedup. For estimation, what matters is not iterating $Q$ but reading its spectrum: in the invariant plane $Q$ is a rotation by $2\theta$ , so its eigenvalues are $e^{\pm 2i\theta}$ and the initial state is an equal-weight superposition of the two eigenvectors.

Q\,|\omega_\pm\rangle=e^{\pm 2i\theta}\,|\omega_\pm\rangle,\qquad A|0\rangle=\frac{-i}{\sqrt2}\big(e^{i\theta}|\omega_+\rangle-e^{-i\theta}|\omega_-\rangle\big) \qquad (6)

where: $|\omega_\pm\rangle$ — eigenvectors of $Q$ ; $\pm 2\theta$ — eigenphases carrying $\theta$ and hence $p=\sin^2\theta$ . Because $A|0\rangle$ overlaps both equally, phase estimation succeeds whichever sign it locks onto. Reading: the angle you want to amplify is literally the phase of $Q$ — so hand $Q$ to phase estimation. Phase estimation with an $m$ -qubit register produces an integer $y$ ; the estimator $\sin^2(\pi y/2^m)$ returns the success probability $p=\sin^2\theta$ (both $\pm\theta$ map to the same $\sin^2$ , so the sign ambiguity is harmless).

\tilde p=\sin^2\!\Big(\frac{\pi y}{2^m}\Big),\qquad |\tilde p-p|\le\frac{2\pi\sqrt{p(1-p)}}{2^m}+\frac{\pi^2}{2^{2m}} \qquad (7)

where: $y$ — integer read by the register; $2^m=N_Q$ — number of controlled- $Q$ applications; the bound holds with probability $\ge 8/\pi^2$ (the standard phase-estimation figure). Reading: error falls as $1/2^m$ in the $Q$ -calls, quadratically better than the $1/\sqrt{N_Q}$ of Monte Carlo; $\tilde p$ estimates the probability, and the amplitude follows as $\tilde a=\sin(\pi y/2^m)$ . The counting special case takes $A=H^{\otimes n}$ so $p=M/N$ , turning the probability estimate into a cardinality estimate.

\tilde M=N\sin^2\!\Big(\frac{\pi y}{2^m}\Big),\qquad |\tilde M-M|=O\!\big(\sqrt{M}\big)\ \text{with}\ O(\sqrt N)\ \text{queries} \qquad (8)

where: $M$ — number of marked items among $N$ ; $\theta=\arcsin\sqrt{M/N}$ . Existence testing ( $M=0$ ?) is the crudest instance. Reading: counting estimates how many marked items exist, not just whether one does — quadratically faster than sampling.

Derivation AThe amplification operator is a plane rotation by twice theta

The goal is to prove that $Q=-AS_0A^{-1}S_\chi$ never leaves the plane spanned by the good and bad components of the initial state, and inside it acts as an ordinary rotation by the fixed angle $2\theta$ . This single fact makes the whole algorithm exactly solvable rather than a high-dimensional mess: once the motion is a $2\times2$ rotation, the $\sin((2k+1)\theta)$ amplitude, the optimal count, and the eigenphases for estimation all follow by elementary trigonometry.

Step 1. Write the plane as $\mathcal H_\psi=\mathrm{span}\{|\psi_b\rangle,|\psi_g\rangle\}$ and note that $S_\chi$ fixes $|\psi_b\rangle$ and sends $|\psi_g\rangle\to-|\psi_g\rangle$ , so on this plane $S_\chi=\mathrm{diag}(1,-1)$ — the reflection across the bad axis at angle $0$ . Why: a sign flip of one axis is exactly a mirror reflection across the other.

Step 2. Since $S_0=2|0\rangle\langle0|-I$ and $A$ maps $|0\rangle\mapsto|\psi\rangle$ , conjugation gives $AS_0A^{-1}=2|\psi\rangle\langle\psi|-I$ , the reflection about the line through $|\psi\rangle$ , which sits at angle $\theta$ from the bad axis. Why: conjugating by $A$ carries the reflection about $|0\rangle$ to one about whatever $A$ actually built, $|\psi\rangle$ .

Step 3. Compose the two mirrors: $Q=-(2|\psi\rangle\langle\psi|-I)(\,\mathrm{diag}(1,-1)\,)$ . A reflection across an axis at angle $\theta$ followed by a reflection across an axis at angle $0$ is a rotation by $2(\theta-0)=2\theta$ ; the overall $-1$ converts the rotation-reflection into a proper rotation. Why: two reflections make a rotation by twice the angle between their axes — Grover's algorithm is this theorem in disguise.

Step 4. In the ordered basis $(|\psi_b\rangle,|\psi_g\rangle)$ this reads

Q=\begin{pmatrix}\cos2\theta&-\sin2\theta\\ \sin2\theta&\cos2\theta\end{pmatrix},\qquad Q\begin{pmatrix}\cos\phi\\ \sin\phi\end{pmatrix}=\begin{pmatrix}\cos(\phi+2\theta)\\ \sin(\phi+2\theta)\end{pmatrix}

so any arrow at angle $\phi$ is turned to $\phi+2\theta$ , and the plane is invariant. Why: this matrix form is the boxed claim; every downstream number is a substitution into it. *As a check: when $\sin\theta=\sqrt{M/N}$ this matrix form reproduces the standard Grover geometry, and the $N=4$ , $M=1$ case gives $\theta=30°$ and $Q$ a $60°$ rotation, consistent with the figure above.*

Go deeper · Derivation B · 1 minOptimal iteration count and the quadratic speedup

Derivation BOptimal iteration count and the quadratic speedup

The goal is to turn the closed-form amplitude $\sin((2k+1)\theta)$ into a concrete recipe: how many times to apply $Q$ , what success probability that guarantees, and why the total calls to $A$ scale as $1/a$ rather than the classical $1/a^2$ . We also handle the practical wrinkle that $\theta$ is usually unknown in advance, showing that a geometric schedule of guesses recovers the same $O(1/a)$ cost in expectation.

Step 1. The success probability after $k$ rounds is $\sin^2((2k+1)\theta)$ , maximized when the argument equals $\pi/2$ . Solving $(2k+1)\theta=\pi/2$ gives the ideal real count $k^*=\pi/(4\theta)-\tfrac12$ ; since $k$ must be an integer, round to the nearest one. Why: the arrow should land as close to the good axis as a whole number of $2\theta$ steps allows.

Step 2. Rounding leaves the final angle within $\theta$ of $\pi/2$ , so

p_{\mathrm{succ}}=\sin^2\!\big((2k_{\mathrm{opt}}+1)\theta\big)\ge\cos^2\theta=1-\sin^2\theta=1-a^2

the failure probability is at most $a^2$ , tiny in the small- $a$ regime where amplification is worth doing. Why: rounding is off by at most $\theta/2$ , and $\sin^2$ near its peak loses only $O(\theta^2)=O(a^2)$ .

Step 3. Count the calls: $2k_{\mathrm{opt}}+1\approx\pi/(2\theta)\to\pi/(2a)$ as $a\to0$ , since each $Q$ contains one $A$ and one $A^{-1}$ . Classically you repeat $A$ about $1/p=1/a^2$ times to see one success, so the quantum cost $O(1/a)=O(1/\sqrt p)$ is the square root. Why: amplitude grows linearly with $Q$ -calls but probability grows linearly with classical tries, and probability is amplitude squared.

Step 4. If $\theta$ is unknown, pick $k$ uniformly in $[0,\lceil 1/a'\rceil)$ for a guess $a'$ grown geometrically until a measurement returns a good state; expected total calls remain $\Theta(1/a)$ . Why: the true $\theta$ is bracketed within a constant factor after $O(\log(1/a))$ stages, and the geometric sum of stage costs is dominated by its last term $O(1/a)$ . *As a check: setting $a=\sqrt{M/N}$ recovers Grover's iteration count $\lfloor(\pi/4)\sqrt{N/M}\rfloor$ , and the $N=4$ , $M=1$ case gives $k_{\mathrm{opt}}=1$ and $p_{\mathrm{succ}}=1$ exactly.*

Go deeper · Derivation C · 1 minAmplitude estimation from the eigenphases of Q

Derivation CAmplitude estimation from the eigenphases of Q

The goal is to show that the very same operator $Q$ , instead of being iterated a fixed number of times, can be handed to quantum phase estimation to read $\theta$ — and hence $p=\sin^2\theta$ — to $m$ bits, with error shrinking as $1/2^m$ in the $Q$ -calls. This is a genuinely quadratic improvement over classical estimation and the heart of quantum counting and quantum Monte Carlo, so we do the error propagation from phase to probability carefully.

Step 1. From equation (6), $A|0\rangle$ is an equal-magnitude superposition of the two eigenvectors $|\omega_\pm\rangle$ of $Q$ , eigenvalues $e^{\pm 2i\theta}$ — exactly the input phase estimation wants. Why: with equal overlaps on the two eigenvectors, either eigenphase is read with probability one-half.

Step 2. Apply phase estimation to controlled powers of $Q$ ; it returns $y$ with $y/2^m$ approximating either $\theta/\pi$ or $1-\theta/\pi$ (the eigenphases $\pm2\theta$ as fractions of $2\pi$ ), both carrying the same $|\theta|$ . Why: the inverse QFT concentrates amplitude on the grid point nearest the true phase.

Step 3. Map the phase to the probability using $p=\sin^2\theta$ :

\tilde p=\sin^2\!\Big(\frac{\pi y}{2^m}\Big),\qquad \frac{\mathrm dp}{\mathrm d\theta}=\sin2\theta=2\sqrt{p(1-p)}

The $\pm$ sign ambiguity is invisible because $\sin^2$ is even in $\theta$ . Why: we want the probability, which is a single-valued function of $|\theta|$ , so the two-fold phase ambiguity of estimation does no harm.

Step 4. Standard phase estimation guarantees $|\theta-\pi y/2^m|\le\pi/2^m$ with probability $\ge 8/\pi^2$ . Propagating through $p=\sin^2\theta$ with the derivative above, and keeping the second-order term, gives

|\tilde p-p|\le\frac{2\pi\sqrt{p(1-p)}}{2^m}+\frac{\pi^2}{2^{2m}}

so with $N_Q=2^m$ calls the error is $O(1/N_Q)$ versus $O(1/\sqrt{N_Q})$ for $N_Q$ samples. Why: the leading term is the linearized error and $\pi^2/2^{2m}$ is the curvature correction, dominant only near $p=0,1$ where the slope vanishes. *As a check: the counting instance $N=256$ , $M=20$ with $m=8$ gives $y=23$ and $\tilde M=19.86$ .*

Limiting cases

How the iteration count and estimation precision behave across regimes of the success amplitude $a=\sin\theta$ :

Case	Result	Meaning
Small success ( $a\ll1$ )	$k_{\mathrm{opt}}\approx\dfrac{\pi}{4a}-\dfrac12,\quad p_{\max}\to1$	Here $\theta\approx a$ , so $\approx\pi/(4a)$ rounds — the canonical $O(1/\sqrt p)$ speedup over $1/p$ classical repetitions.
Already-good state ( $a\to1$ )	$\theta\to\pi/2,\quad k_{\mathrm{opt}}\to0$	If $A$ already succeeds, $Q$ overshoots immediately; zero or one round is best. Amplification helps most when $a$ is small.
Half-success ( $a=1/\sqrt2$ , $\theta=\pi/4$ )	$k=1\Rightarrow\sin\tfrac{3\pi}{4}=\tfrac{1}{\sqrt2}$	Degenerate case: $Q$ rotates by $\pi/2$ , so the probability cycles $1/2\to1\to1/2\to0$ — pure overshoot.
Exact search ( $N=4$ , $M=1$ )	$\theta=\pi/6,\ k_{\mathrm{opt}}=1,\ p=1$	One iteration lands on the good axis; the four-item search is deterministic in a single query.
Estimation precision ( $m$ ancilla qubits)	$\|\tilde p-p\|\le\dfrac{2\pi\sqrt{p(1-p)}}{2^m}+\dfrac{\pi^2}{2^{2m}}$	Error scales as $1/2^m$ in the $Q$ -queries, versus $1/\sqrt{2^m}$ for Monte Carlo — a quadratic improvement.

Common trapMore iterations is always better

Not here. The success probability $\sin^2((2k+1)\theta)$ oscillates in $k$ , so once the arrow reaches the good axis, further $Q$ 's swing it past $90°$ and the probability falls — down and up again with period $\pi/(2\theta)$ . This is the souffle problem: stop at the peak or the answer deflates. If $\theta$ is unknown, use exponential search or a fixed-point scheme; running $\sim1/\theta^2$ rounds "to be safe" both overshoots and destroys the speedup. Second trap: $Q$ needs $A^{-1}$ , so $A$ must be a clean unitary with no mid-circuit measurements, else the reflection $2|\psi\rangle\langle\psi|-I$ cannot be built and you need the oblivious variant.

Worked examples

1 · Exact four-item search (fully worked)

A database has $N=4$ entries with exactly $M=1$ marked. Prepare the uniform superposition with $A=H^{\otimes 2}$ , so $a=\sqrt{M/N}$ . Find the optimal number of Grover iterations and the success probability.

Step 1. The success amplitude is $a=\sqrt{1/4}=1/2$ , so $\theta=\arcsin(1/2)=\pi/6=30°$ and the initial success probability is $\sin^2\theta=1/4$ — a blind measurement finds the marked item one in four.

Step 2. The ideal real count is $k^*=\pi/(4\theta)-\tfrac12=\tfrac{3}{2}-\tfrac12=\mathbf{1}$ , already an integer, so $k_{\mathrm{opt}}=1$ : a single Grover iterate.

Step 3. After one round the total angle is $3\theta=90°$ , so the amplitude is $\sin 90°=1$ and the success probability is $\sin^2 90°=\mathbf{1}$ — the four-item search is solved deterministically with one oracle query, the smallest instance where Grover beats classical (up to 3 queries) with certainty. k_opt = 1, and one query gives p = 1 exactly.

2 · Quantum counting of marked items (fully worked)

An unstructured space of $N=256$ items contains an unknown number $M$ of marked ones; the true value is $M=20$ . Run amplitude estimation with an $m=8$ -qubit register on the Grover $Q$ . What count does it report, and how does the cost compare to classical sampling?

Step 1. The relevant angle is $\theta=\arcsin\sqrt{20/256}=0.2833\ \mathrm{rad}=16.23°$ , and $p=M/N=0.0781$ is the fraction the estimator targets.

Step 2. Phase estimation reads the integer nearest $2^m\theta/\pi=23.08$ , so $y=\mathbf{23}$ . Mapping back, $\tilde p=\sin^2(\pi\cdot23/256)=0.0776$ and $\tilde M=N\tilde p=\mathbf{19.86}$ , which rounds to the correct $M=20$ .

Step 3. Compare costs at target precision $\epsilon=0.005$ in $p$ . Classically you need about $p(1-p)/\epsilon^2\approx\mathbf{2880}$ samples. Quantumly the bound $2\pi\sqrt{p(1-p)}/2^m\le\epsilon$ needs $2^m\gtrsim 337$ , i.e. $m=9$ and $\sim 512$ applications of $Q$ . Roughly $2880$ classical samples versus $\sim 512$ quantum queries is the square-root advantage; pushing $\epsilon$ down $10\times$ widens the gap another $10\times$ . The register reports M̃ = 19.86 ≈ 20, at O(√) fewer queries than classical counting.

3 · The half-success cycle (overshoot by hand)

A subroutine already succeeds with probability $1/2$ , so $a=1/\sqrt2$ and $\theta=\pi/4$ . Each $Q$ rotates by $2\theta=90°$ , so $(2k+1)\cdot45°$ runs $45°,135°,225°,315°$ for $k=0,1,2,3$ and every $\sin^2$ equals $\tfrac12$ — the arrow jumps a quarter turn each round and never lands on the good axis; the true peak would need a fractional $k=\tfrac12$ . At θ = 45° the probability is stuck at 1/2 for all integer k — the count must match θ, not merely be "large".

Physics of the portrait

Amplitude amplification is where a database trick became a general theory of quadratic quantum speedups. Grover found the search algorithm in 1996; a Montreal-led group — Gilles Brassard with Peter Høyer, Michele Mosca, and Alain Tapp — saw that the mechanism was not about searching but about rotating an amplitude, and built the framework that carries their initials.

Origins · 1 minGilles Brassard and how this was discovered

Gilles Brassard

b. 1955 · quantum algorithms, cryptography, and information

Gilles Brassard is a Canadian computer scientist at the Université de Montréal whose fingerprints are on two founding results of quantum information. In 1984, with Charles Bennett, he invented the BB84 protocol for quantum key distribution — arguably the first practical quantum-information technology — and later co-founded quantum teleportation. His second great theme is the algebra of quantum search. After Grover's 1996 algorithm, Brassard and collaborators asked what was really doing the work; the answer was geometric — any subroutine's success amplitude can be rotated toward certainty by a product of two reflections. With Høyer, Mosca, and Tapp he published the unifying "Quantum Amplitude Amplification and Estimation" in 2000, reframing Grover's algorithm as one instance of a primitive that quadratically speeds up any bounded-error quantum subroutine — the engine behind quantum counting, quantum Monte Carlo, and the amplitude-estimation routines now central to quantum finance. His style throughout is to find the simple structural reason an algorithm works, then generalize until the original result is a footnote.

History

1996

— Grover publishes the quantum search algorithm

1997

— Boyer, Brassard, Høyer and Tapp give tight bounds and the amplitude picture of search

1998

— Brassard, Høyer and Tapp introduce quantum counting via phase estimation

2000

— Brassard, Høyer, Mosca and Tapp unify it as quantum amplitude amplification and estimation

2014

— Yoder, Low and Chuang give provably optimal fixed-point amplitude amplification

Going further

Texts. Nielsen and Chuang, Quantum Computation and Quantum Information, §6.1–6.3 · Brassard, Høyer, Mosca and Tapp, "Quantum Amplitude Amplification and Estimation", AMS Contemporary Mathematics 305 (2002) · Preskill, Lecture Notes on Quantum Computation, Ch. 6 · Kitaev, Shen and Vyalyi, Classical and Quantum Computation, §13 · Watrous, The Theory of Quantum Information (Grover and amplification) · Montanaro, "Quantum speedup of Monte Carlo methods", Proc. R. Soc. A 471 (2015). The key results to keep in mind are: (1) $Q$ acts as $R(2\theta)$ in the invariant plane; (2) $Q^kA|0\rangle$ has good amplitude $\sin((2k+1)\theta)$ ; (3) $k_{\mathrm{opt}}\approx\pi/(4\theta)$ with failure $\le\sin^2\theta$ , and the exact $N=4,\,M=1$ case gives $k_{\mathrm{opt}}=1$ , $p=1$ ; (4) eigenphases $\pm2\theta$ with phase error $\le\pi/2^m$ propagating through $p=\sin^2\theta$ to $|\tilde p-p|\le 2\pi\sqrt{p(1-p)}/2^m+\pi^2/2^{2m}$ ; (5) counting $N=256,\,M=20,\,m=8$ gives $y=23$ , $\tilde M=19.86$ . The $\ge 8/\pi^2$ success figure is the standard phase-estimation bound. Convention: $a=\sin\theta$ is the amplitude, $p=a^2$ the probability, so the estimator $\sin^2(\pi y/2^m)$ returns $p$ .

Prerequisites. Grover's Search Algorithm · Quantum Phase Estimation · Quantum Fourier Transform · Quantum Parallelism and the Oracle Model. Leads to. Hidden Subgroup Problem · Shor's Factoring Algorithm.

Ask the tutor: Give me your subroutine's success probability and I will find $k_{\mathrm{opt}}$ , the resulting success, and when overshoot bites.

Is amplitude amplification just Grover's algorithm with new notation?

No — Grover is one special case. Grover fixes $A=H^{\otimes n}$ , so the initial state is uniform and the amplitude is forced to $a=\sqrt{M/N}$ . Amplitude amplification allows $A$ to be any unitary, including a biased preparation that already raises the success probability, or a whole randomized subroutine. Everything downstream — the $2\theta$ rotation, the $\sin((2k+1)\theta)$ amplitude, the $O(1/a)$ count — is identical, but the framework applies to any recognizable-success problem. That generality is the point: a database trick becomes a universal quadratic speedup for bounded-error quantum algorithms.

How can it help if you do not know theta in advance?

Usually you do not know the success probability of $A$ , so $k_{\mathrm{opt}}$ is not directly computable. The fix is exponential search: guess an amplitude $a'$ , run with a random $k$ in $[0,\lceil 1/a'\rceil)$ , measure, check; on failure shrink the guess geometrically and retry. Because the true $\theta$ gets bracketed within a constant factor after $O(\log(1/a))$ stages of geometrically growing cost, the expected calls stay $\Theta(1/a)$ — the same speedup without prior knowledge. Fixed-point amplitude amplification skips the tuning entirely by making the probability climb monotonically toward 1.

What exactly does amplitude estimation estimate — the amplitude or the probability?

The natural output is the success probability $p=\sin^2\theta$ . Phase estimation on $Q$ returns an integer $y$ , and $\sin^2(\pi y/2^m)$ approximates $\sin^2\theta=p$ ; the amplitude follows as $\tilde a=\sin(\pi y/2^m)$ . Some references (including the original Brassard–Høyer–Mosca–Tapp paper) reserve " $a$ " for the probability itself, which is why the same formula appears with different letters. Whatever the notation, the machine measures $\theta$ and reports a function of it; the bound $|\tilde p-p|\le 2\pi\sqrt{p(1-p)}/2^m+\pi^2/2^{2m}$ is for the probability, and the $\sqrt{p(1-p)}$ factor is exactly the derivative $\mathrm dp/\mathrm d\theta=\sin2\theta$ converting phase error into probability error.

Why does estimation need the eigenstructure of Q rather than just counting iterations?

Estimation wants the angle $\theta$ itself, not merely a good state. That angle is encoded in the eigenphases $e^{\pm2i\theta}$ of $Q$ , and the standard tool for reading an eigenphase is phase estimation, which interferes controlled powers $Q^{2^j}$ through an inverse QFT to write the phase into an ancilla in one coherent shot. You could instead iterate $Q$ and binary-search for the best $k$ , but that reintroduces statistical sampling and loses the advantage. Phase estimation extracts $m$ bits of $\theta$ with error $1/2^m$ in the query count — the whole reason amplitude estimation beats Monte Carlo.

Why must A be a clean unitary with no mid-circuit measurements?

Because the amplifier explicitly uses $A^{-1}$ . The reflection about the prepared state is $AS_0A^{-1}=2|\psi\rangle\langle\psi|-I$ , and building it means running the preparation backward. If $A$ contains mid-circuit measurements, resets, or any irreversible step, it has no unitary inverse, so that reflection cannot be built and standard amplification does not apply. The escape hatch is oblivious amplitude amplification, which amplifies a target action without inverting the full preparation, at the price of extra structural assumptions (typically that the useful part acts as an isometry on a flagged subspace) — this is what lets amplification live inside linear-combination-of-unitaries and qubitization routines.

Does the quadratic speedup ever become exponential with more cleverness?

Not for unstructured problems — and that is a theorem, not a shortcoming of the technique. The query lower bound for search shows $\Omega(\sqrt{N/M})$ queries are necessary, so Grover and amplitude amplification are optimal: no rearrangement of reflections beats them on a black-box oracle. Exponential speedups (Shor's factoring, hidden-subgroup problems) come from structure — periodicity the Fourier transform exposes — not from amplitude tricks. Amplitude amplification's value is precisely that it needs no structure: wrap any verifiable bounded-error subroutine for a guaranteed square-root reduction. When structure exists you reach for the QFT; when it does not, the $2\theta$ rotation is the best there is.