Quantum Algorithms · Chapter 05
In Quantum Computing we met Grover search: one marked item among \(N\), found with about \(\sqrt N\) queries. Since then we have learned to build clean oracles, to reflect about any state we can prepare, and to read eigenphases with phase estimation.
Search is a special case of a broader situation. Suppose some procedure, a heuristic, a sampler, or a randomized algorithm made reversible, produces a good answer with small probability, and good answers can be recognized. Can we raise the success probability without already knowing a good answer? And if we only want to know how likely success is, can we learn that probability faster than by sampling?
We find that two reflections, one about the prepared state and one about the good answers, compose into a rotation in a plane, and the rotation moves the state toward success. Because a rotation can overshoot, we must decide how many times to apply it, and changing the phases of the reflections gives exact or overshoot-free versions. A rotation’s angle is an eigenphase, so phase estimation can measure it, which estimates probabilities with quadratically fewer calls than sampling. We then build a minimum-finding algorithm from these pieces and prove that no algorithm searches an unstructured list faster.
Amplification is one rotation fixed by two reflections; letting the reflections be chosen by a graph gives a quantum walk.
How can a useful but unlikely outcome be made observable without knowing the answer?
Amplification and estimation are two uses of one rotation: apply it to raise a probability, or measure its angle to learn the probability.
Raise small success probabilities by composing reflections, control the rotation with phase sequences, estimate probabilities with amplitude estimation, and know the limits of these speedups.
Use reflections about prepared states and clean phase oracles (Coherent Computation), and phase estimation on superpositions of eigenstates (Fourier Methods).
A preparation with success probability p = 0.01: seven iterations reach success 0.995, fourteen nearly undo it, and amplitude estimation reads p from the eigenphases of the same iterate.
Reflections are ideal and require both A and A†. Speedups are in queries or calls to A; each call may be expensive. Amplitude estimation requires long coherent circuits and controlled access.
5.1
The state a procedure prepares lives in a space of dimension \(2^n\). How can we follow what reflections do to it without tracking every amplitude? We first split the state into a good part and a bad part, which picks out a plane. Then we show that the two reflections we can build act inside that plane and compose to a rotation. The angle of the rotation finally tells us how many times to apply it.
good subspacesuccess probability
What does a success probability look like geometrically? Let \(A\) be a preparation circuit on \(n\) qubits, and let a predicate \(\chi(x)\in\{0,1\}\) mark the good basis states. The predicate defines the good subspace, spanned by basis states with \(\chi(x)=1\), and the bad subspace, its orthogonal complement. Split the prepared state into its components in each:
\[A\ket{0^n}=\ket\psi=\sin\theta\,\ket G+\cos\theta\,\ket B,\qquad0\le\theta\le\tfrac\pi2,\]
where \(\ket G\) and \(\ket B\) are the normalized good and bad components. Measuring \(\ket\psi\) gives a good outcome with success probability \(p=\sin^2\theta\).
The decomposition is the key simplification. The space has dimension \(2^n\), but we will find that both operations we use map the plane spanned by \(\ket G\) and \(\ket B\) to itself. So we can draw the whole algorithm in two dimensions, with \(\ket B\) along the horizontal axis and \(\ket G\) along the vertical. The state starts at angle \(\theta\) above the horizontal. Success means getting close to the vertical axis.
Nothing requires \(A\) to produce a uniform superposition or the good states to be equally weighted. For Grover search, \(A=H^{\otimes n}\), there are \(t\) marked items among \(N\), and \(\sin^2\theta=t/N\). For a randomized heuristic made reversible, \(A\) might put large amplitude on promising candidates, and \(p\) is whatever it is. The plane picture covers both.
For \(A=H^{\otimes 3}\) and the predicate \(\chi(x)=1\) exactly for \(x\in\{011,101\}\), find \(\ket G\), \(\ket B\), and \(\theta\).
\(\ket G=\frac{1}{\sqrt2}(\ket{011}+\ket{101})\), \(\ket B=\frac{1}{\sqrt6}\sum_{x\notin\{011,101\}}\ket x\). The good component of \(\ket\psi\) has squared length \(2/8\), so \(\sin\theta=1/2\) and \(\theta=30^\circ\).
A preparation gives amplitudes \(\frac12,\frac12,\frac{1}{\sqrt2},0\) on \(\ket{00},\ket{01},\ket{10},\ket{11}\), and \(\chi\) marks \(01\) and \(11\). Find \(p\) and \(\ket G\).
The good component is \(\frac12\ket{01}\), so \(p=\frac14\) and \(\ket G=\ket{01}\). The amplitude on \(\ket{11}\) is zero; a marked state with zero amplitude is not part of \(\ket G\).
Why is the plane spanned by \(\ket G\) and \(\ket B\) different for different preparations \(A\), even with the same predicate?
\(\ket G\) is the normalized projection of \(A\ket{0^n}\) onto the good subspace, so it depends on the relative amplitudes \(A\) assigns to good states. Two preparations with the same predicate can have different \(\ket G\) and \(\ket B\), and therefore different planes and angles. Amplification never changes the relative weights within the good component; it rescales the good component as a whole.
amplitude amplificationGrover iterate
Which operations can move the state within the plane? We have two reflections available. The predicate gives a phase oracle, built cleanly by compute–copy–uncompute:
\[S_G=I-2\Pi_G,\]
which negates good states and leaves bad ones alone; \(\Pi_G\) is the projection onto the good subspace. In the plane, \(S_G\) reflects across the horizontal axis. The preparation gives the reflection about \(\ket\psi\), built from \(A\), its inverse and a zero-state reflection,
\[R_\psi=A(2\ket{0^n}\bra{0^n}-I)A^\dagger=2\ket\psi\bra\psi-I,\]
which needs both \(A\) and \(A^\dagger\). Composing two reflections across lines at angle \(\theta\) gives a rotation by \(2\theta\). Let us check this by multiplying matrices in the basis \((\ket G,\ket B)\):
\[S_G=\begin{pmatrix}-1&0\\0&1\end{pmatrix},\quad R_\psi=\begin{pmatrix}-\cos2\theta&\sin2\theta\\\sin2\theta&\cos2\theta\end{pmatrix},\quad Q=R_\psi S_G=\begin{pmatrix}\cos2\theta&\sin2\theta\\-\sin2\theta&\cos2\theta\end{pmatrix}.\]
\(Q\) is the Grover iterate, a rotation by \(2\theta\) toward \(\ket G\). Applying it \(k\) times to \(\ket\psi\), which sits at angle \(\theta\),
\[Q^k\ket\psi=\sin\big((2k+1)\theta\big)\ket G+\cos\big((2k+1)\theta\big)\ket B.\]
This is amplitude amplification, due to Brassard, Høyer, Mosca, and Tapp (2002), generalizing Grover (1996). When \(p\) is small, \(\theta\approx\sqrt p\), and reaching angle near \(\pi/2\) takes about \(\frac{\pi}{4\sqrt p}\) iterations. Classical repetition of \(A\) with checking needs about \(1/p\) tries. The speedup is quadratic, in units of calls to \(A\) and the predicate.
Each iteration costs one oracle call for \(S_G\), one \(A^\dagger\), one \(A\), and a zero-state reflection. If \(A\) is expensive, as it often is in applications, the count of \(A\)-calls dominates the cost, not the count of oracle queries.
For \(p=1/4\), compute the success probability after one iteration.
\(\theta=\pi/6\), so after one iteration the angle is \(3\theta=\pi/2\) and the success probability is \(1\). This is the four-item search with one marked item.
Verify the product \(R_\psi S_G\) by applying it to \(\ket G\).
\(S_G\ket G=-\ket G\), with coordinates \((-1,0)\) in the basis \((\ket G,\ket B)\). \(R_\psi\) maps \((-1,0)\) to \((\cos2\theta,-\sin2\theta)\), the first column of \(Q\). Measured from the \(\ket B\) axis, \(\ket G\) sits at \(90^\circ\) and \(Q\ket G\) at \(90^\circ+2\theta\): a rotation by \(2\theta\) in the same direction that carries \(\ket\psi\) from \(\theta\) to \(3\theta\).
A programmer implements \(S_GR_\psi\) instead of \(R_\psi S_G\). Does amplification still work?
\(S_GR_\psi=(R_\psi S_G)^{-1}=Q^{-1}\), a rotation by \(2\theta\) in the opposite direction. Starting at angle \(\theta\), \(k\) iterations reach angle \(\theta-2k\theta\), so the success probability is \(\sin^2((2k-1)\theta)\). The first iteration only reflects \(\ket\psi\) to angle \(-\theta\) and gains nothing; after that the magnitude grows as before. The reversed order costs one wasted iteration, and an iteration count chosen for \(Q\) is off by one.
The rotation does not stop at the good axis. Iterate too many times and the state swings past it, and the success probability falls again. With \(p\) known, choose
\[k=\operatorname{round}\!\left(\frac{\pi}{4\theta}-\frac12\right),\]
which puts \((2k+1)\theta\) within \(\theta\) of \(\pi/2\). The success probability is then at least \(\cos^2\theta=1-p\).
This overshoot is a real hazard. For \(p=1/4\) one iteration gives certainty and a second gives \(\sin^2(5\pi/6)=1/4\), back where we started. Unlike classical repetition, where more tries never hurt, more iterations can undo the work.
What if \(p\) is unknown? Guessing a single \(k\) can land anywhere on the oscillation. The remedy, exponential search (Boyer, Brassard, Høyer, Tapp, 1996), picks \(k\) uniformly at random from \(\{0,\ldots,K-1\}\), runs, checks the result, and if it fails multiplies \(K\) by a factor such as \(6/5\). Averaged over a random \(k\), the success probability is close to \(1/2\) once \(K\) exceeds about \(1/\sin2\theta\). The expected total number of iterations is \(O(1/\sqrt p)\), the same order as if \(p\) were known. If no good item exists, the procedure never succeeds; it must stop after a budget of order \(\sqrt{N}\) and report “none found” with a stated error probability.
For \(p=0.01\), give the optimal \(k\) and the success probability. How many classical tries reach the same success probability?
\(\theta=\arcsin0.1\approx5.74^\circ\). \(\pi/(4\theta)-1/2\approx7.33\), so \(k=7\), and \(\sin^2(15\theta)\approx\sin^2(86.1^\circ)\approx0.995\). Classically, \(1-0.99^R\ge0.995\) needs \(R\ge\ln0.005/\ln0.99\approx527\) tries, against 7 iterations (about 15 calls to \(A\) or \(A^\dagger\)).
With \(p=0.01\) and \(k=14\) by mistake, what is the success probability?
\((2k+1)\theta=29\theta\approx166.5^\circ\), and \(\sin^2(166.5^\circ)\approx0.055\). Doubling the right count almost undoes the amplification.
Why does the average of \(\sin^2((2k+1)\theta)\) over \(k\in\{0,\ldots,K-1\}\) approach \(1/2\) for large \(K\)?
\(\sin^2u=\frac12(1-\cos2u)\), and the average of \(\cos(2(2k+1)\theta)\) over many consecutive \(k\) is a sum of equally spaced points on the circle, which nearly cancels once \(K\cdot4\theta\) covers a full turn. Precisely, the average is \(\frac12-\frac{\sin(4K\theta)}{4K\sin2\theta}\), within \(\frac{1}{4K\sin2\theta}\) of \(\frac12\).
5.2
The ordinary iterate rotates by a fixed angle, so it usually misses the good axis and can swing past it. Ordinary amplification uses phase flips of exactly \(-1\). Can other phases fix both problems? When \(p\) is known, a small change makes the rotation land exactly on the good axis. When \(p\) is unknown, phases of \(e^{i\pi/3}\) give a procedure that never overshoots, at a cost in speed. Choosing phases to shape a response will later become a general method, polynomial transformations.
With the ordinary iterate, success probability \(1-p\) is guaranteed, but certainty generally is not: \((2k+1)\theta\) hits \(\pi/2\) exactly only for special \(\theta\). When \(p\) is known exactly, we can fix this.
One clean method of exact amplitude amplification lowers the angle slightly so that it divides evenly. Choose \(k=\lceil\pi/(4\theta)-1/2\rceil\) and set \(\theta'=\pi/(4k+2)\). Then \((2k+1)\theta'=\pi/2\) exactly, and the choice of \(k\) guarantees \(\theta'\le\theta\). Now reduce the success probability from \(p=\sin^2\theta\) to \(p'=\sin^2\theta'\): add one flag qubit, rotate it to \(\sqrt{1-p'/p}\,\ket0+\sqrt{p'/p}\,\ket1\), and redefine success as “the original predicate holds and the flag is \(1\).” The new preparation \(A'=A\otimes R_{\text{flag}}\) succeeds with probability exactly \(p\cdot p'/p=p'\). Amplify \(A'\) for \(k\) iterations; the success probability is \(\sin^2((2k+1)\theta')=1\).
For \(p=1/2\): \(\theta=\pi/4\), \(k=\lceil1-\frac12\rceil=1\), \(\theta'=\pi/6\), \(p'=1/4\). A fair flag halves the success probability to \(1/4\), and one ordinary iteration then succeeds with certainty. Without the flag, one iteration on \(p=1/2\) gives \(\sin^2(3\pi/4)=1/2\), no improvement at all.
Another method, also given by Brassard, Høyer, Mosca, and Tapp, keeps the original preparation and tunes the phases of the last iteration instead. Both methods need \(p\) exactly; with \(p\) only estimated, they inherit the estimation error. Exactness is also limited by how accurately the flag rotation or phases can be implemented. If \(p=0\), no phase sequence helps: amplification can only rescale a good component that \(A\) actually produces.
Apply the flag method to \(p=0.3\). Find \(k\), \(\theta'\), and the flag probability.
\(\theta=\arcsin\sqrt{0.3}\approx33.2^\circ\). \(\pi/(4\theta)-1/2\approx0.855\), so \(k=1\) and \(\theta'=30^\circ\), \(p'=1/4\). The flag is \(1\) with probability \(p'/p=0.25/0.3\approx0.833\). One iteration on the joint preparation succeeds with certainty.
Why must \(\theta'\le\theta\) for the flag method to work?
The flag can only reduce the success probability, since \(p'=p\cdot\Pr[\text{flag}=1]\le p\). So we can reach \(\theta'\) only if \(\sin^2\theta'\le\sin^2\theta\). Taking \(k\) as a ceiling ensures \(4k+2\ge\pi/\theta\), that is \(\theta'\le\theta\).
Suppose \(p\) is believed to be \(1/2\) but is actually \(0.45\). What success probability does the flag method designed for \(1/2\) give?
The flag still halves the probability: \(p'=0.225\), \(\theta'=\arcsin\sqrt{0.225}\approx28.3^\circ\). One iteration gives \(\sin^2(84.9^\circ)\approx0.992\). The method degrades gracefully for small errors but is no longer exact.
Overshoot comes from rotating by a fixed angle. Is there a way to move toward the good axis that never goes past it, whatever \(p\) is? Replace the two \(-1\) phases by \(e^{i\pi/3}\). Define
\[R_0=I+(e^{i\pi/3}-1)\ket{0^n}\bra{0^n},\qquad R_G=I+(e^{i\pi/3}-1)\Pi_G,\]
and the new preparation \(A_1=A\,R_0\,A^\dagger\,R_G\,A\). How likely is \(A_1\) to fail? Write \(\omega=e^{i\pi/3}\), \(\epsilon=1-p\), and \(\ket\psi=A\ket{0^n}=\sqrt p\ket G+\sqrt\epsilon\ket B\). Then \(AR_0A^\dagger=I+(\omega-1)\ket\psi\bra\psi\), so
\[A_1\ket{0^n}=R_G\ket\psi+(\omega-1)\braket{\psi}{R_G\psi}\,\ket\psi.\]
Here \(R_G\ket\psi=\omega\sqrt p\ket G+\sqrt\epsilon\ket B\), and \(\braket{\psi}{R_G\psi}=\omega p+\epsilon=\omega+\epsilon(1-\omega)\). The bad amplitude is therefore
\[\sqrt\epsilon\,\big[1+(\omega-1)\big(\omega+\epsilon(1-\omega)\big)\big]=\sqrt\epsilon\,\big[(\omega^2-\omega+1)-\epsilon(1-\omega)^2\big].\]
The choice \(\omega=e^{i\pi/3}\) is what makes this work: \(\omega^3=-1\), and \(\omega^3+1=(\omega+1)(\omega^2-\omega+1)\), so \(\omega^2-\omega+1=0\). Also \(|1-\omega|=1\). The bad amplitude has magnitude \(\sqrt\epsilon\cdot\epsilon\), so \(A_1\) fails with probability exactly \(\epsilon^3\). This is Grover’s fixed-point search (2005).
The failure probability never increases: \(\epsilon^3\le\epsilon\) for every \(\epsilon\in[0,1]\). Recursion helps more: \(A_2\) built from \(A_1\) fails with \(\epsilon^9\), and so on. This fixed-point amplification is robust when \(p\) is unknown or varies between inputs.
The price is speed. Each level triples the number of calls to \(A\) and \(A^\dagger\), while the failure only cubes. Starting from small \(p\), the failure \(1-p\) is close to \(1\), and cubing it barely helps: this recursion needs order \(1/p\) calls to reach constant success, losing the quadratic speedup. More sophisticated phase sequences (Yoder, Low, and Chuang, 2014) achieve fixed-point behavior with the optimal \(O(1/\sqrt{p_{\min}})\) calls, given a known lower bound \(p_{\min}\) on \(p\). Their phases are chosen by the polynomial design we develop later for general matrices.
Apply one level of the \(\pi/3\) construction when \(p=1/2\). Compare with one ordinary iteration.
Failure becomes \((1/2)^3=1/8\), success \(7/8\), using three calls to \(A\) or \(A^\dagger\). One ordinary iteration on \(p=1/2\) gives success \(1/2\) (no change), using also three calls. The fixed-point step wins here because \(p\) is large.
Starting from \(p=0.01\), how many recursion levels does the \(\pi/3\) method need to reach success \(0.5\), and how many calls to \(A\) or \(A^\dagger\)?
Failure after \(L\) levels is \(0.99^{3^L}\). We need \(3^L\ln(0.99)\le\ln0.5\), i.e. \(3^L\ge69\), so \(L=4\) (\(3^4=81\)). Calls: \(3^4=81\). Ordinary amplification reaches about \(0.995\) with \(7\) iterations, about \(15\) calls. Fixed-point robustness here costs a factor of about five; for smaller \(p\) the gap grows like \(1/\sqrt p\).
Why can no amplification method that uses a fixed number of calls be both overshoot-free for every \(p\in(0,1]\) and reach success \(1/2\) for arbitrarily small \(p\)?
Any method making \(c\) calls to \(A\) has success probability that is a polynomial of degree about \(2c\) in the amplitude \(\sin\theta\) (a fact we prove when we study polynomial transformations), and so for \(p\) much smaller than \(1/c^2\) it can increase \(p\) only by a bounded factor of order \(c^2\). Reaching \(1/2\) from arbitrarily small \(p\) with fixed \(c\) is impossible. The number of calls must grow with \(1/\sqrt{p_{\min}}\).
5.3
Sometimes we do not want a good answer; we want to know how likely one is. Estimating \(p\) by sampling costs order \(1/\epsilon^2\) runs. Can the rotation do better? The Grover iterate is a rotation by \(2\theta\), and a rotation’s angle is an eigenphase, which phase estimation reads with order \(1/\epsilon\) controlled operations. So we first find the eigenvalues of the iterate, then turn the phase precision into a precision for \(p\), and finally use the result to estimate averages.
What are the eigenvalues of the iterate? A rotation of the plane by \(2\theta\) has no real eigenvectors, but it has complex ones. For \[Q=\begin{pmatrix}\cos2\theta&\sin2\theta\\-\sin2\theta&\cos2\theta\end{pmatrix}\], try \(\ket{v_\pm}=\frac{1}{\sqrt2}(\ket G\pm i\ket B)\):
\[Q\ket{v_\pm}=e^{\pm2i\theta}\ket{v_\pm}.\]
(Check \(\ket{v_+}\): the first coordinate is \(\cos2\theta+i\sin2\theta=e^{2i\theta}\), the second is \(-\sin2\theta+i\cos2\theta=ie^{2i\theta}\).) These iterate eigenvalues are the whole story: in the plane, \(Q\) has eigenphases \(\pm2\theta\), or \(\pm\theta/\pi\) as fractions of a full turn.
The prepared state is an equal-weight combination of the two eigenvectors:
\[\ket\psi=\frac{-ie^{i\theta}}{\sqrt2}\ket{v_+}+\frac{ie^{-i\theta}}{\sqrt2}\ket{v_-}.\]
Both coefficients have squared magnitude \(\frac12\). Phase estimation on a superposition of eigenstates samples one eigenphase with probability given by its squared coefficient. So phase estimation of \(Q\) on \(\ket\psi\) returns an estimate of either \(\theta/\pi\) or \(1-\theta/\pi\), each with probability \(\frac12\). Either one gives \(\theta\) and hence \(p=\sin^2\theta\), since \(\sin^2(\pi-\theta)=\sin^2\theta\). We need not know \(\ket G\) or \(\ket B\): \(\ket\psi=A\ket{0^n}\) is all we prepare.
Verify that \[\frac{-ie^{i\theta}}{\sqrt2}\ket{v_+}+\frac{ie^{-i\theta}}{\sqrt2}\ket{v_-}=\sin\theta\ket G+\cos\theta\ket B\].
The \(\ket G\) coefficient is \[\frac12(-ie^{i\theta}+ie^{-i\theta})=\frac{-i}{2}(e^{i\theta}-e^{-i\theta})=\frac{-i}{2}\cdot2i\sin\theta=\sin\theta\]. The \(\ket B\) coefficient is \[\frac12(-ie^{i\theta}\cdot i+ie^{-i\theta}\cdot(-i))=\frac12(e^{i\theta}+e^{-i\theta})=\cos\theta\].
For \(p=1/4\), what eigenphases (as fractions of a turn) does phase estimation see?
\(\theta=\pi/6\), so \(\theta/\pi=1/6\) and \(1-\theta/\pi=5/6\). With \(m\) control qubits, outcomes cluster near \(2^m/6\) and \(5\cdot2^m/6\).
What happens to the eigenphases when \(p=0\) or \(p=1\)? Is phase estimation still informative?
For \(p=0\), \(\theta=0\) and \(Q\) acts as the identity on \(\ket\psi=\ket B\): eigenphase \(0\). For \(p=1\), \(\theta=\pi/2\) and \(Q=-I\) on \(\ket\psi=\ket G\): eigenphase \(1/2\). The plane degenerates to a line, but phase estimation still returns exactly \(0\) or \(1/2\), giving \(p=0\) or \(p=1\).
How precisely does this determine \(p\), and at what cost? Amplitude estimation runs phase estimation with \(m\) control qubits on controlled powers of \(Q\), starting from \(A\ket{0^n}\). With \(M=2^m\), an outcome \(j\) gives \(\tilde\theta=\pi j/M\) and \(\tilde p=\sin^2\tilde\theta\). The phase is resolved to about \(\pi/M\) in \(\theta\). How does that translate into error in \(p\)?
Since \(\frac{d}{d\theta}\sin^2\theta=\sin2\theta=2\sqrt{p(1-p)}\), an error \(\delta\) in \(\theta\) gives error about \(2\sqrt{p(1-p)}\,\delta\) in \(p\). The precise bound of Brassard, Høyer, Mosca, and Tapp says that with probability at least \(8/\pi^2\),
\[|\tilde p-p|\le\frac{2\pi\sqrt{p(1-p)}}{M}+\frac{\pi^2}{M^2}.\]
The cost is \(M-1\) applications of controlled-\(Q\), each containing one \(A\), one \(A^\dagger\), and one oracle call. So precision \(\epsilon\) costs order \(1/\epsilon\) calls to \(A\). Classical sampling, running \(A\) and checking, needs order \(p(1-p)/\epsilon^2\) runs for the same precision with constant confidence.
Three conditions make the comparison fair. Amplitude estimation needs coherent access to \(A\) and \(A^\dagger\), not just samples; it needs controlled-\(Q\), which in turn needs controlled \(A\) or a construction that avoids it; and its circuits are long and coherent, with depth of order \(1/\epsilon\), whereas sampling uses many short independent runs. On noisy hardware the long coherent circuit is the hard part. Variants that replace the Fourier transform by classical post-processing of several shorter amplification runs (for example Suzuki et al., 2020) trade some of the coherence for more repetitions, keeping the \(1/\epsilon\) scaling under suitable assumptions.
With \(m=8\) and \(p\approx0.3\), estimate the error bound in \(p\).
\(M=256\). \(2\pi\sqrt{0.21}/256\approx2\pi\times0.458/256\approx0.0112\), plus \(\pi^2/65536\approx0.00015\). So \(|\tilde p-p|\lesssim0.011\) with probability at least \(0.81\), using \(255\) controlled-\(Q\) calls.
How many classical samples give the same precision (\(0.011\)) at a similar confidence, using the Chebyshev bound with the actual variance?
Chebyshev: \(\Pr[\text{error}>\epsilon]\le p(1-p)/(R\epsilon^2)\). For failure probability \(0.19\): \(R\ge0.21/(0.19\times0.011^2)\approx9{,}100\). Sharper (Chernoff) bounds reduce this to a few thousand, still an order of magnitude above 255.
Why does the error bound depend on \(\sqrt{p(1-p)}\), and what does this mean for estimating very small probabilities?
The factor is the derivative of \(\sin^2\theta\) with respect to \(\theta\) (divided by 2). For small \(p\), \(\sqrt{p}\) is small, so the absolute error is about \(2\pi\sqrt p/M\): relative error \(\approx2\pi/(M\sqrt p)\). Estimating \(p\) to constant relative error therefore costs \(M\approx1/\sqrt p\), the same as amplifying it, versus \(1/p\) samples classically.
Monte Carlo estimationquadratic speedup
Where would a faster estimate of a probability matter? A common case is Monte Carlo estimation: computing the average of a function \(v(x)\in[0,1]\) over a distribution \(q(x)\), such as an expected payoff in finance or an integral in physics. Classically, sample \(x\) from \(q\), evaluate \(v\), and average; precision \(\epsilon\) needs order \(1/\epsilon^2\) samples.
To use amplitude estimation, turn the mean into a success probability. Suppose a circuit \(P\) prepares \(\sum_x\sqrt{q(x)}\ket x\), and a clean circuit computes \(v(x)\) and rotates an extra qubit:
\[\ket x\ket0\mapsto\ket x\big(\sqrt{1-v(x)}\ket0+\sqrt{v(x)}\ket1\big),\]
with \(v(x)\) uncomputed afterwards. Define \(A\) as \(P\) followed by this rotation, and call the extra qubit being \(1\) a success. Then
\[p=\sum_xq(x)\,v(x)=\mathbb E[v].\]
Amplitude estimation gives \(\mathbb E[v]\) to precision \(\epsilon\) with order \(1/\epsilon\) uses of \(A\), a quadratic speedup over classical sampling in the number of samples. Montanaro (2015) extends this to random variables with bounded variance rather than bounded range.
The speedup is in sample complexity, and the conditions matter. The distribution must be preparable coherently by a circuit \(P\), not merely sampled; loading an empirical distribution of \(N\) data points costs order \(N\). The function \(v\) must be computed reversibly and its value encoded in an amplitude, with arithmetic and rotation errors added to \(\epsilon\). And the quadratic gain must outweigh the overhead of fault-tolerant execution. Resource studies for option pricing (for example Chakrabarti et al., 2021) find that the advantage requires substantially better hardware than exists today. A quadratic speedup is real, but it is the kind whose practical value depends on constants.
For \(v(x)\in\{0,1\}\), show that the construction reduces to ordinary amplitude estimation of a predicate.
When \(v(x)\in\{0,1\}\), the rotation sends \(\ket x\ket0\) to \(\ket x\ket{v(x)}\), a bit oracle. Success means \(v(x)=1\), and \(p=\sum_xq(x)v(x)\) is the probability that a sample from \(q\) satisfies the predicate.
Classical precision \(10^{-4}\) needs about \(10^8\) samples. About how many uses of \(A\) does amplitude estimation need, and what else must be counted?
About \(10^4\) (times a modest constant for confidence). One must also count the gates in each \(A\) (state preparation, arithmetic for \(v\), the controlled rotation, uncomputation), controlled access, the circuit depth of order \(10^4\) sequential applications of \(Q\), and error-correction overhead. If one quantum use of \(A\) costs \(10^4\) times more wall-clock time than a classical sample, the advantage disappears.
A dataset of \(N=10^6\) records is given as a classical file, and we want the average of a field. Does amplitude estimation give a speedup?
Not end to end. Preparing a state with amplitudes \(\sqrt{q(x)}\) over the records requires reading them, costing order \(N\), and a classical program computes the exact average in order \(N\) as well. Sampling a uniform record classically and averaging needs order \(1/\epsilon^2\) samples, independent of \(N\). The quantum speedup applies when the distribution is defined by a process that can be run coherently, not when it is defined by a list.
5.4
Amplification is a subroutine. What larger algorithms can classical control build from it, and how far can the speedup go? Repeated threshold searches find the minimum of a list in about \(\sqrt N\) queries. A lower bound then shows that no quantum algorithm searches an unstructured list faster, so any larger gain must come from structure.
minimum findingthreshold search
Can amplification find the smallest entry of a list? Given \(N\) values \(T(0),\ldots,T(N-1)\), accessible through a clean oracle, we want an index of the minimum. Classically this needs \(N\) queries. A quantum algorithm for minimum finding (Dürr and Høyer, 1996) uses amplification inside a classical loop:
Why is the total cost only \(O(\sqrt N)\)? When the current candidate has rank \(r\) (there are \(r-1\) smaller values), threshold search costs about \(\sqrt{N/(r-1)}\). The new candidate is uniformly distributed among the smaller values, so the rank roughly halves on average each round. How often is a given rank visited? Consider the \(r\) smallest values. The first candidate that falls among them is equally likely to be any of them, because each pick is uniform over a set that contains all \(r\). Once a candidate is among them, every later candidate is smaller still. So the value of rank \(r\) is ever selected only if it is the first of the \(r\) smallest to be picked, which has probability \(1/r\). The expected total cost is therefore at most
\[\sum_{r=2}^N\frac1r\sqrt{\frac{N}{r-1}}\le\sqrt N\sum_{k=1}^\infty k^{-3/2}=O(\sqrt N),\]
since the series converges (to about \(2.61\)). Dürr and Høyer’s constant analysis, which we quote, gives success probability at least \(1/2\) within \(22.5\sqrt N\) queries.
The predicate needs a comparator: a clean circuit for \([T(x)<T(y)]\) with \(y\) a classical constant in each round. Its cost, and the cost of the oracle for \(T\), multiply the query count. Minimum finding underlies quantum speedups for many optimization subroutines, always quadratic and always in a query model.
For \(N=10^6\), compare the classical query count with \(22.5\sqrt N\).
Classical: \(10^6\). Quantum: \(22{,}500\), with success probability at least \(1/2\). The constant matters: the advantage appears only for \(N\) above a few thousand, before counting the cost of each quantum query.
Why must each threshold search use exponential search rather than a fixed number of iterations?
The number of values below the current threshold, \(r-1\), is unknown and changes every round. A fixed iteration count would overshoot or undershoot depending on \(r\). Exponential search handles unknown \(p=(r-1)/N\) at the optimal expected cost \(O(\sqrt{N/(r-1)})\).
If the values have ties and we want all indices of the minimum, how does the cost change?
After finding the minimum value \(T_{\min}\), search for indices with \(T(x)=T_{\min}\) repeatedly, removing each found index from the predicate. Finding all \(t\) of them costs \(\sum_{i=1}^{t}\sqrt{N/i}=O(\sqrt{Nt})\). Outputting \(t\) items costs at least \(t\), so for \(t\) close to \(N\) the advantage vanishes.
Can a cleverer quantum algorithm search faster than \(O(\sqrt{N})\)? No, as a quoted theorem. Bennett, Bernstein, Brassard, and Vazirani (1997) proved that any quantum algorithm finding a single marked item among \(N\) with bounded error needs \(\Omega(\sqrt N)\) queries, and Zalka later showed Grover’s algorithm is optimal even in its constant. This query lower bound holds for every algorithm that accesses the list only through the oracle, which is what “unstructured” means.
Three consequences follow. First, amplification cannot solve NP-complete problems in polynomial time by brute force: searching \(2^n\) assignments costs \(2^{n/2}\) queries, still exponential. Second, any further speedup must come from structure. Period finding is exponentially faster than search because periodicity is structure that the Fourier transform exploits; quantum walks exploit graph structure for problems like element distinctness. Third, the quadratic speedup over brute force may not beat the best classical algorithm, which usually uses structure too. For satisfiability, classical algorithms far better than \(2^n\) exist, and Grover-based speedups must be compared against them, often by amplifying a classical randomized algorithm’s success probability, which the good–bad plane allows for any preparation.
Amplification rotates within a plane fixed by two reflections. If the reflections are instead determined by the local structure of a graph, they act on many planes at once, and the speed of each rotation depends on the graph.
A satisfiability instance has \(n=60\) variables. How many queries does Grover search over all assignments need, and how does that compare with a classical algorithm running in time \(1.3^n\)?
Grover: about \(\frac\pi4\cdot2^{30}\approx8.4\times10^8\) queries (with one solution). Classical \(1.3^{60}\approx6.9\times10^6\). The structured classical algorithm is far faster than unstructured quantum search. A fair quantum approach amplifies the classical algorithm’s success probability instead, gaining a square root of its cost.
Does the \(\Omega(\sqrt N)\) lower bound imply that no quantum algorithm can solve some NP-complete problem in polynomial time?
No. The bound covers algorithms that treat the problem as a black box. An algorithm that uses the structure of a specific problem’s description is outside the model. Whether NP-complete problems have efficient quantum algorithms is open; it is widely believed they do not, but the search lower bound is evidence, not proof.
Amplitude estimation achieves error \(\epsilon\) with \(O(1/\epsilon)\) queries. Is that also optimal?
Yes, in the query model: \(\Omega(1/\epsilon)\) queries are needed to estimate a probability to additive precision \(\epsilon\) (a result related to the search lower bound, since distinguishing \(p=0\) from \(p=\epsilon\) is a search problem). This \(1/\epsilon\) limit is the analogue of the Heisenberg limit in quantum metrology, which we meet again when estimating phases with feedback.
Attempt each question before opening a hint. Explain your reasoning, then compare it with the solution.
A preparation succeeds with probability p = 1/9. What is the success probability after one and after two amplification iterations?
sin θ = 1/3, so θ ≈ 19.47°.
Compute sin²(3θ) and sin²(5θ).
3θ ≈ 58.4°, so one iteration gives sin²(58.4°) ≈ 0.727. 5θ ≈ 97.4°, so two iterations give sin²(97.4°) ≈ 0.984. Two is optimal here: round(π/(4θ) − 1/2) = round(1.81) = 2.
Grover search runs over \(N=16\) items with uniform preparation. (a) With one marked item, find \(\theta\), the optimal number of iterations, and the success probability. (b) With four marked items, how many iterations give certainty?
\(\sin^2\theta=t/N\), and \(k=\mathrm{round}(\pi/(4\theta)-1/2)\).
For \(t=4\), \(\sin\theta=1/2\).
(a) \(\sin\theta=1/4\), so \(\theta\approx0.2527\) and \(\pi/(4\theta)-1/2\approx2.61\), giving \(k=3\). The success probability is \(\sin^2(7\theta)\approx0.961\). Classical guessing with checking needs about \(16\ln(1/0.039)\approx52\) tries for the same confidence, or \(16\) to be sure. (b) With \(t=4\), \(\theta=\pi/6\) and one iteration reaches \(3\theta=\pi/2\) exactly: certainty. A second iteration would give \(\sin^2(5\pi/6)=1/4\), so the number of iterations must be matched to \(t\).
A preparation already succeeds with probability \(p=0.9\). Compare one ordinary amplification iteration with one level of the \(\pi/3\) fixed-point construction. Which should you use if you only know that \(p\) is “probably large”?
Ordinary: \(\sin^2(3\theta)\) with \(\sin^2\theta=0.9\).
Fixed point: the failure probability \(\epsilon\) becomes \(\epsilon^3\).
The ordinary iterate rotates by \(2\theta\), and here \(\theta\approx1.249\) is already close to \(\pi/2\). One iteration overshoots to \(\sin^2(3\theta)=0.9\,(3-4\times0.9)^2=0.324\): the success probability drops from \(0.9\) to about \(0.32\). The fixed-point construction turns failure \(0.1\) into \(0.1^3=0.001\), giving success \(0.999\), at a cost of three calls to \(A\) or \(A^\dagger\). When \(p\) is uncertain and possibly large, the fixed-point method is the safe choice: it never makes things worse. Its weakness is the small-\(p\) regime, where it loses the quadratic speedup.
Amplitude estimation with m = 6 control qubits returns j = 11. What is the estimate of p, and what does the error bound say if p is near this estimate?
θ̃ = πj/2^m.
Use |p̃ − p| ≤ 2π√(p(1−p))/M + π²/M².
θ̃ = 11π/64 ≈ 0.540 rad, so p̃ = sin²(0.540) ≈ 0.264. With M = 64 and p ≈ 0.264, the bound is 2π√(0.194)/64 + π²/4096 ≈ 0.0433 + 0.0024 ≈ 0.046, with probability at least 8/π² ≈ 0.81. The estimate is p ∈ [0.22, 0.31] with that confidence, from 63 controlled-Q calls.
Apply exact amplification to \(p=0.1\). Find \(\theta\), the number of iterations \(k\), the reduced angle \(\theta'\), the new success probability \(p'\), and the flag-qubit probability \(p'/p\). Check that the final success probability is \(1\).
\(k=\lceil\pi/(4\theta)-1/2\rceil\) and \(\theta'=\pi/(4k+2)\).
\(\sin(\pi/10)=(\sqrt5-1)/4\approx0.309\).
\(\theta=\arcsin\sqrt{0.1}\approx0.3218\), so \(\pi/(4\theta)-1/2\approx1.94\) and \(k=2\). Then \(\theta'=\pi/10\approx0.3142\le\theta\), and \(p'=\sin^2(\pi/10)\approx0.0955\). The flag qubit is rotated to \(\ket1\) with probability \(p'/p\approx0.955\), so \(A'=A\otimes R_{\text{flag}}\) succeeds with probability exactly \(p'\). Two iterations take the angle to \(5\theta'=\pi/2\), so the success probability is \(\sin^2(\pi/2)=1\). Without the flag, two iterations give \(\sin^2(5\theta)\approx\sin^2(1.609)\approx0.9985\). Exactness matters when the amplified routine is used inside a larger coherent algorithm, where a small failure amplitude would propagate.
Amplitude estimation with \(m=4\) (\(M=16\)) is applied to a preparation with \(p=1/4\). (a) Which eigenphases does phase estimation see, and which outcomes \(j\) are most likely? (b) List the estimates \(\sin^2(\pi j/M)\) available for \(j=0,\dots,8\) and find the estimate produced. (c) Compare its error with the stated bound.
\(\theta=\pi/6\), and the eigenphases are \(\theta/\pi\) and \(1-\theta/\pi\).
\(M\theta/\pi=16/6\approx2.67\).
(a) \(\theta=\pi/6\), so the eigenphases are \(1/6\) and \(5/6\). Then \(M/6\approx2.67\) and \(5M/6\approx13.33\), and the most likely outcomes are \(j=3\) and \(j=13\). (b) For \(j=0,\dots,8\) the estimates are \(0,\ 0.038,\ 0.146,\ 0.309,\ 0.5,\ 0.691,\ 0.854,\ 0.962,\ 1\). Both \(j=3\) and \(j=13\) give \(\tilde p=\sin^2(3\pi/16)\approx0.309\). (c) The error is about \(0.059\). The bound is \(2\pi\sqrt{3/16}/16+\pi^2/256\approx0.209\), so the result lies comfortably inside it. The estimates are not evenly spaced in \(p\): they are dense near \(0\) and \(1\) and sparse near \(1/2\), which is why the error bound contains \(\sqrt{p(1-p)}\).
Set up mean estimation for \(x\) uniform on \(\{0,1,2,3\}\) and \(v(x)=x/3\). Describe the preparation \(A\), compute the success probability \(p\), and show that amplitude estimation with \(m=2\) returns \(\mathbb E[v]\) exactly.
\(P=H\otimes H\), followed by a rotation of a flag qubit by \(\sqrt{v(x)}\).
With \(p=1/2\), \(\theta=\pi/4\) and the eigenphases are \(1/4\) and \(3/4\).
Let \(P=H^{\otimes2}\) prepare \(\frac12\sum_x\ket x\). Then compute \(v(x)\), rotate a flag to \(\sqrt{1-v(x)}\ket0+\sqrt{v(x)}\ket1\), and uncompute \(v(x)\). Success means the flag is \(1\), with probability \(p=\frac14\sum_xv(x)=\frac14(0+\frac13+\frac23+1)=\frac12=\mathbb E[v]\). So \(\theta=\pi/4\), and \(Q\) has eigenphases \(\theta/\pi=1/4\) and \(3/4\). Both are exact grid points for \(M=4\), so phase estimation returns \(j=1\) or \(j=3\) with certainty. Either gives \(\tilde\theta=\pi/4\) or \(3\pi/4\), and \(\tilde p=\sin^2\tilde\theta=1/2\). The answer is exact here only because the phase happened to lie on the grid. In general, the rotation angles must also be computed to finite precision, and that error is added to the estimate.
A student proposes to amplify an amplified procedure: first build \(A'=Q^kA\), which succeeds with probability \(\sin^2((2k+1)\theta)\), then amplify \(A'\). “Each stage gives a square root, so two stages give a fourth-root speedup.” Count the total number of calls to \(A\) or \(A^\dagger\) needed to reach constant success, for small \(\theta\), and compare with direct amplification.
\(A'\) uses \(2k+1\) calls, and its angle is \(\theta'=(2k+1)\theta\).
Amplifying \(A'\) needs about \(\pi/(4\theta')\) iterations, each with one \(A'\) and one \(A'^\dagger\).
Direct amplification needs about \(\pi/(4\theta)\) iterations, each using \(A\) and \(A^\dagger\) once: about \(\pi/(2\theta)\) calls. The nested scheme starts from angle \(\theta'=(2k+1)\theta\) and needs about \(\pi/(4\theta')\) outer iterations. Each uses \(A'\) and \(A'^\dagger\), so \(2(2k+1)\) calls of \(A\) or \(A^\dagger\). The total is \(\frac{\pi}{4(2k+1)\theta}\cdot2(2k+1)=\frac{\pi}{2\theta}\), exactly the same. Nesting only regroups the rotation into larger steps. It cannot beat the \(\Omega(\sqrt N)\) lower bound, because the composite routine is itself an algorithm that calls the oracle.
A classical randomized algorithm for a search problem runs in time T and succeeds with probability p. Describe how to obtain a quantum algorithm with success probability at least 1/2 and estimate its running time. What must be true of the classical algorithm?
Make the classical algorithm reversible: its random bits become a uniform superposition prepared by Hadamards.
Each call to A costs about T, and about 1/√p calls are needed.
Treat the random bits as an input register prepared in uniform superposition; the reversible version of the algorithm (Coherent Computation) is the preparation A, and checking the output is the predicate. Amplification with unknown p (exponential search) reaches success 1/2 with O(1/√p) calls to A and A†, for total time O(T/√p) versus O(T/p) classically. This requires a reversible implementation of the algorithm and a coherent checker, and the overhead of reversibility (garbage removal, roughly a factor of two plus workspace) is included in T.
When \(p\) is small, the useful target is relative precision: \(|\tilde p-p|\le\epsilon_rp\). (a) Show that classical sampling needs about \(1/(\epsilon_r^2p)\) samples (using the variance \(p(1-p)\)), while amplitude estimation needs \(M\) of order \(1/(\epsilon_r\sqrt p)\). (b) Evaluate both for \(p=10^{-4}\) and \(\epsilon_r=0.1\), ignoring constant confidence factors. (c) What extra assumption does the quantum count carry?
Set \(\sqrt{p/R}\approx\epsilon_rp\) for sampling.
Set \(2\pi\sqrt p/M\approx\epsilon_rp\) for amplitude estimation.
(a) Sampling has standard deviation \(\sqrt{p(1-p)/R}\approx\sqrt{p/R}\). Setting this equal to \(\epsilon_rp\) gives \(R\approx1/(\epsilon_r^2p)\). For amplitude estimation the leading error is \(2\pi\sqrt{p}/M\), and setting it equal to \(\epsilon_rp\) gives \(M\approx2\pi/(\epsilon_r\sqrt p)\). The \(\pi^2/M^2\) term is then negligible. (b) Sampling: \(1/(0.01\times10^{-4})=10^6\) samples. Amplitude estimation: \(M\approx2\pi/(0.1\times0.01)\approx6.3\times10^3\), so \(M=2^{13}=8192\) and about \(8\times10^3\) uses of \(A\). The ratio grows as \(1/(\epsilon_r\sqrt p)\). (c) The quantum count assumes coherent, controllable access to \(A\) and \(A^\dagger\) and a circuit about \(8000\) iterations deep that stays coherent throughout, while sampling uses a million short independent runs. The comparison in calls is fair only after both sides price these differences.
Where this leads. the Quantum Walks chapter composes reflections chosen from the local structure of a graph, giving quantum walks whose speed is governed by spectral gaps.