Quantum Search and Amplitude Amplification

Many computational problems can be phrased as searching a domain of \(N = 2^n\) candidate bit strings for an item \(x\in\{0,1\}^n\) that passes a verification test. We model that test as a Boolean predicate \(f:\{0,1\}^n\to\{0,1\}\), where \(f(x)=1\) means candidate \(x\) is marked (a valid solution) and \(f(x)=0\) means \(x\) is unmarked.

Suppose we are promised that exactly one of the \(N\) candidates is marked, and our only way to learn about \(f\) is by querying the black box on chosen inputs. How many queries does a classical algorithm need? In the worst case, a deterministic classical search must query \(N-1\) distinct candidates (if all \(N-1\) return \(0\), the remaining untested candidate must be the marked one). What if we use a randomized classical algorithm that is allowed to fail with probability \(1/3\)? If the marked item is hidden uniformly at random among the \(N\) candidates, each classical query tests only a single candidate, so after \(q\) distinct queries the marked item has been found with probability \(q/N\) (plus at most \(1/N\) if the algorithm guesses one remaining item at the end). Reaching success probability \(2/3\) therefore still requires roughly \(2N/3\) queries! Whether deterministic or randomized, classical unstructured search requires a number of queries proportional to \(N\).

Let us start with \(N = 4\) two-bit candidates—\(00, 01, 10, 11\)—and suppose the hidden marked item is \(w = 11\). Keep in mind that our choice of \(11\) is solely so we can write down a concrete numerical example: the search algorithm itself does not know which string is marked and accesses \(f\) exclusively through the oracle.

How does a quantum search begin? Since we have no advance clue about which of the four candidates \(00, 01, 10, 11\) is marked, we initialize two qubits in \(\ket{00}\) and apply \(H\otimes H\) to prepare the uniform superposition of all four candidates:

\[\ket{s} = (H\otimes H)\ket{00} = \frac{\ket{00}+\ket{01}+\ket{10}+\ket{11}}{2}.\]

Next, we query the predicate \(f\) using the phase-oracle construction from Chapter 7 (either by kicking back a phase from an ancilla in \(\ket{-}\) or by the compute, phase, uncompute sequence \(A^\dagger Z_{\mathrm{ans}} A\)), which applies the phase-marking operator

\[O_f\ket{x} = (-1)^{f(x)}\ket{x}.\]

When \(w = 11\) is the marked string (\(f(11)=1\) and \(f(00)=f(01)=f(10)=0\)), one call to \(O_f\) negates the amplitude of \(\ket{11}\) while leaving the other three amplitudes at \(+1/2\):

\[O_f\ket{s} = \frac{\ket{00}+\ket{01}+\ket{10}-\ket{11}}{2}.\]

Has this phase flip increased our chance of observing \(11\) if we measure right now? Not yet: the squared magnitude of every coordinate—both \((+1/2)^2\) and \((-1/2)^2\)—is still \(1/4\)! Just as in Deutsch's algorithm, the oracle has encoded the location of the marked item into a relative minus sign; we now need an interference step that converts that minus sign into an amplitude difference.

What unitary operation can turn the amplitude vector \((1/2, 1/2, 1/2, -1/2)^T\) into a vector concentrated on the marked coordinate? Look at the average (mean) of the four amplitudes after \(O_f\):

\[\mu = \frac{\frac{1}{2} + \frac{1}{2} + \frac{1}{2} - \frac{1}{2}}{4} = \frac{1}{4}.\]

Notice that the three unmarked amplitudes (\(+1/2\)) sit slightly above the mean \(\mu = 1/4\) (by \(+1/4\)), whereas the marked amplitude (\(-1/2\)) sits far below the mean \(\mu = 1/4\) (by \(-3/4\)). What happens if we reflect every coordinate across the mean \(\mu\), replacing each amplitude \(a_x\) with \(2\mu - a_x\)?

\[\text{Unmarked }\bigl(a_x = +\tfrac{1}{2}\bigr):\quad 2\left(\frac{1}{4}\right) - \frac{1}{2} = 0,\qquad\qquad \text{Marked }\bigl(a_{11} = -\tfrac{1}{2}\bigr):\quad 2\left(\frac{1}{4}\right) - \left(-\frac{1}{2}\right) = 1.\]

Every unmarked amplitude drops to \(0\), and the marked amplitude jumps to \(1\)! After just one phase-oracle call and one reflection about the mean, the register is in the state \(\ket{11}\), and a computational-basis measurement finds the marked item \(11\) with probability \(1\).

Why is "reflection about the mean" a valid unitary operation that can be applied without knowing which item is marked? Let us check that it is identical to the diffusion operator \(D\) we built from Hadamard and controlled-\(Z\) gates in Section 8.2.3:

\[D = 2\ketbra{s}{s} - I.\]

For any state \(\ket{a} = \sum_x a_x\ket{x}\) in an \(N\)-item search space where \(\ket{s} = \frac{1}{\sqrt{N}}\sum_x \ket{x}\), the inner product \(\braket{s}{a} = \frac{1}{\sqrt{N}}\sum_x a_x = \sqrt{N}\,\mu\), where \(\mu = \frac{1}{N}\sum_x a_x\) is the arithmetic mean of the amplitudes. Multiplying by \(2\ket{s}\) puts \(\frac{2}{\sqrt{N}}(\sqrt{N}\mu) = 2\mu\) into every coordinate, so subtracting \(\ket{a}\) gives \(D\ket{a} = \sum_x (2\mu - a_x)\ket{x}\)! Because \(D = H^{\otimes n}(2\ketbra{0^n}{0^n}-I)H^{\otimes n}\) is a product of unitary matrices (with \(D^\dagger = D\) and \(D^2 = I\)), it acts directly on the amplitudes by coherent interference—without ever sampling or estimating \(\mu\) classically.

Suppose that among the \(N = 2^n\) basis strings, there are \(M\) marked strings (with \(0 \lt M \lt N\)) satisfying \(f(x)=1\), and \(N-M\) unmarked strings satisfying \(f(x)=0\). Because our starting state \(\ket{s}\) assigns equal amplitude to every string, and both \(O_f\) and \(D\) depend only on whether \(f(x)=1\) or \(f(x)=0\), all \(M\) marked strings will share a common amplitude at every step of the algorithm, and all \(N-M\) unmarked strings will share another common amplitude.

We can therefore bundle the \(M\) marked basis states into a single normalized unit vector \(\ket{G}\) (for "good") and the \(N-M\) unmarked basis states into a single normalized unit vector \(\ket{B}\) (for "bad"):

\[\ket{G} = \frac{1}{\sqrt{M}}\sum_{x:\,f(x)=1}\ket{x},\qquad \ket{B} = \frac{1}{\sqrt{N-M}}\sum_{x:\,f(x)=0}\ket{x}.\]

Because no basis string \(x\) is both marked and unmarked, \(\ket{G}\) and \(\ket{B}\) share no basis terms in common, so their inner product is zero: \(\braket{G}{B} = 0\). Together, the marked and unmarked states span the good and bad subspaces, and the two orthonormal vectors \(\{\ket{B}, \ket{G}\}\) define a two-dimensional plane inside the \(N\)-dimensional state space. In terms of \(\ket{G}\) and \(\ket{B}\), the uniform superposition \(\ket{s} = \frac{1}{\sqrt{N}}\sum_x \ket{x}\) decomposes as

\[\ket{s} = \sqrt{\frac{M}{N}}\,\ket{G} + \sqrt{\frac{N-M}{N}}\,\ket{B} = \sqrt{\frac{M}{N}}\,\ket{G} + \sqrt{1 - \frac{M}{N}}\,\ket{B}.\]

Notice why the coefficients are square roots: \(\ket{G}\) already includes the normalization factor \(1/\sqrt{M}\), so multiplying \(\ket{G}\) by \(\sqrt{M/N}\) gives each marked basis state its proper amplitude \(\frac{1}{\sqrt{M}}\sqrt{\frac{M}{N}} = \frac{1}{\sqrt{N}}\), and the squared magnitudes of the two components sum to \(\frac{M}{N} + \bigl(1 - \frac{M}{N}\bigr) = 1\).

Keep in mind that \(\ket{G}\) and \(\ket{B}\) are bookkeeping vectors for our mathematical analysis: the quantum computer does not know which strings belong to \(\ket{G}\), yet \(O_f\) and \(D\) automatically act within the plane spanned by \(\ket{B}\) and \(\ket{G}\) without needing that knowledge.

Let us draw the two-dimensional plane with the unmarked state \(\ket{B}\) along the horizontal axis and the marked state \(\ket{G}\) along the vertical axis. Because \(0 \lt M \lt N\), we can define an acute angle \(\theta \in (0, \pi/2)\) by setting \(\sin\theta = \sqrt{M/N}\), so that

\[\sin^2\theta = \frac{M}{N},\qquad \cos\theta = \sqrt{1 - \frac{M}{N}}.\]

In this geometric picture, the initial uniform state \(\ket{s}\) is a unit vector tilted at angle \(\theta\) above the horizontal axis \(\ket{B}\):

\[\ket{s} = \sin\theta\,\ket{G} + \cos\theta\,\ket{B}.\]

If we measure \(\ket{s}\) immediately in the computational basis, the probability of obtaining any marked string—the initial success probability—is the sum of squared amplitudes over the \(M\) marked strings, which is simply the squared vertical component \(\sin^2\theta = M/N\). For our four-item example (\(N=4, M=1\)), \(\sin\theta = \sqrt{1/4} = 1/2\), so \(\ket{s}\) starts at \(\theta = \pi/6 = 30^\circ\) above \(\ket{B}\), with initial success probability \(\sin^2(30^\circ) = 1/4\).

Why does the state vector never leave this two-dimensional \(\ket{B}\)–\(\ket{G}\) plane during the algorithm? First, the phase oracle \(O_f\) multiplies every marked string by \(-1\) and leaves every unmarked string unchanged, so \(O_f\ket{G} = -\ket{G}\) and \(O_f\ket{B} = \ket{B}\). Second, the diffusion operator \(D = 2\ketbra{s}{s} - I\) maps any vector \(\ket{v}\) in the plane to \(2\braket{s}{v}\ket{s} - \ket{v}\), which is a linear combination of \(\ket{s}\) and \(\ket{v}\)—and since \(\ket{s}\) itself lies in the \(\ket{B}\)–\(\ket{G}\) plane, \(D\ket{v}\) stays in the plane too!

What do \(O_f\) and \(D\) do geometrically inside the \(\ket{B}\)–\(\ket{G}\) plane? Look at each operation in turn:

• The phase oracle \(O_f = I - 2\ketbra{G}{G}\) preserves the horizontal axis \(\ket{B}\) and negates the vertical axis \(\ket{G}\): it is a reflection across the horizontal axis \(\ket{B}\).
• The diffusion operator \(D = 2\ketbra{s}{s} - I\) preserves the vector \(\ket{s}\) (which lies at angle \(\theta\) above \(\ket{B}\)) and negates the direction perpendicular to \(\ket{s}\): it is a reflection across the line of \(\ket{s}\).

What is the combined effect of performing two reflections in a plane across axes separated by an angle \(\theta\)? Measure every vector's angle from the horizontal axis \(\ket{B}\). A reflection across a mirror line at angle \(\alpha\) sends any vector at angle \(\phi\) to angle \(2\alpha - \phi\). Therefore:

1. Applying \(O_f\) (reflection across \(\ket{B}\), where \(\alpha = 0\)) sends a vector at angle \(\phi\) to angle \(-\phi\).
2. Applying \(D\) (reflection across \(\ket{s}\), where \(\alpha = \theta\)) sends that vector from angle \(-\phi\) to angle \(2\theta - (-\phi) = \phi + 2\theta\).

Two reflections make a rotation! Each combined step \(G_{\mathrm{iter}} = D O_f\)—called one Grover iteration—rotates the state vector in the \(\ket{B}\)–\(\ket{G}\) plane by a fixed angle \(2\theta\) toward the vertical marked axis \(\ket{G}\).

For our four-item search (\(N=4, M=1\)), \(\theta = 30^\circ\). The state starts at \(\ket{s}\) (angle \(\phi_0 = 30^\circ\)); \(O_f\) reflects it across \(\ket{B}\) to \(-30^\circ\); and \(D\) reflects it across \(\ket{s}\) (\(30^\circ\)) to angle \(30^\circ + 2(30^\circ) = 90^\circ\)—pointing straight along \(\ket{G}\), where success is \(100\%\) certain! Even more importantly, this geometric picture warns us what happens if we keep iterating past \(90^\circ\): the next Grover iteration will rotate the vector by another \(2\theta = 60^\circ\) to \(150^\circ\), carrying it away from \(\ket{G}\).

Starting from \(\ket{\psi_0} = \ket{s}\) at angle \(\theta\) above \(\ket{B}\), each Grover iteration \(DO_f\) adds \(2\theta\) to the angle. After \(k\) Grover iterations, the state vector \(\ket{\psi_k} = (DO_f)^k\ket{s}\) sits at angle \((2k+1)\theta\) above \(\ket{B}\):

\[\ket{\psi_k} = \sin\bigl((2k+1)\theta\bigr)\,\ket{G} + \cos\bigl((2k+1)\theta\bigr)\,\ket{B}.\]

Measuring the register after \(k\) iterations yields a marked item with probability equal to the squared vertical component:

\[p_k = \sin^2\bigl((2k+1)\theta\bigr).\]

Which marked item is returned when \(M \gt 1\)? Because \(\ket{G} = \frac{1}{\sqrt{M}}\sum_{f(x)=1}\ket{x}\) weights all \(M\) marked strings equally, the measurement returns one of the \(M\) marked strings chosen uniformly at random, each with probability \(p_k/M\). Notice that the overall success probability \(p_k\) depends solely on the marked fraction \(M/N\) (which fixes \(\theta = \arcsin\sqrt{M/N}\)), never on which specific strings are marked.

To make the success probability \(p_k = \sin^2\bigl((2k+1)\theta\bigr)\) as close to \(1\) as possible, we want the angle \((2k+1)\theta\) to land as close as possible to \(\pi/2\) (\(90^\circ\)), where the state vector aligns with \(\ket{G}\):

\[(2k+1)\theta \approx \frac{\pi}{2} \quad\Longrightarrow\quad k \approx \frac{\pi}{4\theta} - \frac{1}{2}.\]

Rounding to the nearest nonnegative integer \(k = \lfloor \pi/(4\theta)\rfloor\) places the state vector within angle \(\theta\) of the vertical axis \(\ket{G}\), guaranteeing a success probability of at least \(1 - \sin^2\theta = 1 - M/N\). When the marked fraction \(M/N\) is small (\(M \ll N\)), \(\sin\theta \approx \theta = \sqrt{M/N}\), so the optimal number of Grover iterations is

\[k \approx \frac{\pi}{4}\sqrt{\frac{N}{M}}.\]

Instead of the roughly \(N/M\) queries required by classical search, Grover's algorithm finds a marked item with high probability using only about \(\frac{\pi}{4}\sqrt{N/M}\) quantum queries—a quadratic speedup! For example, searching \(N = 1{,}000{,}000\) items for \(M = 1\) marked item takes roughly \(785\) Grover iterations instead of hundreds of thousands of classical queries.

Note two important subtleties. First, while \(N=4, M=1\) (\(\theta = \pi/6\)) happens to hit \((2k+1)\theta = \pi/2\) exactly at \(k=1\) (giving \(p_1 = 1\)), for most values of \(N\) the discrete steps \((2k+1)\theta\) step slightly past or short of \(\pi/2\): for \(N=16, M=1\) (\(\theta = \arcsin(1/4) \approx 14.48^\circ\)), \(k=3\) iterations reach \(7\theta \approx 101.4^\circ\), giving success probability \(\sin^2(101.4^\circ) \approx 0.961\). Second, unlike classical search—where testing more candidates can only increase the chance of finding the mark—running Grover's algorithm for too many iterations causes overshooting: the state vector rotates right past \(\ket{G}\) and back down toward \(-\ket{B}\), causing the success probability to plummet! In our four-item search, \(k=1\) gives \(p_1 = 1\), but \(k=2\) rotates to \(150^\circ\) where \(p_2 = 1/4\), and \(k=3\) rotates to \(210^\circ\) where \(p_3 = 1/4\). Choosing the right stopping rule \(k\) is therefore an essential part of the algorithm.

What if we do not know in advance how many items \(M\) are marked? Without knowing \(M\), we do not know the angle \(\theta = \arcsin\sqrt{M/N}\), and if we guess \(M=1\) when \(M\) is actually large, running \(\frac{\pi}{4}\sqrt{N}\) iterations may wildly overshoot \(\ket{G}\)! Fortunately, because we can perform verification on any candidate string \(x\) returned by measurement using a single classical query \(f(x)\), we can use an exponentially growing randomized schedule: in round \(r = 1, 2, 3, \dots\), pick a random iteration count \(k\) uniformly between \(0\) and \(\lceil c^r\rceil\) (for a constant such as \(c = 6/5\)), run \(k\) Grover iterations, measure a candidate \(x\), and check whether \(f(x)=1\). Once \(c^r\) reaches the scale of \(1/\theta \approx \sqrt{N/M}\), the average of \(\sin^2\bigl((2k+1)\theta\bigr)\) over the range is near \(1/2\), so the procedure finds and verifies a marked item using an expected total of only a constant multiple of \(\sqrt{N/M}\) queries—preserving the quadratic speedup without knowing \(M\)!

What if \(M = 0\) (no item is marked at all)? Then \(O_f = I\), the state never moves from \(\ket{s}\), and no candidate ever passes verification. Once the randomized schedule has expended a fixed multiple of \(\sqrt{N}\) queries without finding a marked item, the algorithm halts and reports that no marked item exists, with an arbitrarily small bounded probability of error if a marked item was actually present.

(At the opposite extreme, if all \(N\) items are marked, \(M=N\), the very first candidate checked before any Grover iterations immediately passes verification with certainty.)

Suppose we have a unitary circuit \(A\) (which might be a quantum heuristic or a coherent version of a randomized classical algorithm) that maps the all-zero state \(\ket{0^n}\) to \(\ket{\psi} = A\ket{0^n}\). Suppose further that a projector \(P_G\) identifies the "good" (successful) measurement outcomes, and that measuring \(\ket{\psi}\) directly succeeds with probability \(p = \|P_G\ket{\psi}\|^2\), where \(0 \lt p \lt 1\). By normalizing the good projection \(P_G\ket{\psi}\) into \(\ket{G}\) and the orthogonal bad projection \((I - P_G)\ket{\psi}\) into \(\ket{B}\), we can write \(\ket{\psi}\) in the exact same two-dimensional plane as before:

\[\ket{\psi} = \sqrt{p}\,\ket{G} + \sqrt{1-p}\,\ket{B} = \sin\theta\,\ket{G} + \cos\theta\,\ket{B},\qquad \sin^2\theta = p.\]

Notice that Grover search is simply the special case where \(A = H^{\otimes n}\) prepares the uniform superposition \(\ket{s}\) and \(p = M/N\).

Where might a general preparation circuit \(A\) come from? If a randomized classical algorithm solves a problem with small success probability \(p\) using random coin flips and reversible logic, we can replace its random bits with qubits initialized in \(\ket{+}\) and run its reversible circuit coherently as \(A\)—provided we uncompute any temporary workspace so the branches remain coherent.

To rotate \(\ket{\psi}\) toward \(\ket{G}\) in the \(\ket{B}\)–\(\ket{G}\) plane, we need two reflections: first, the phase oracle \(O_G = I - 2P_G\) that negates \(\ket{G}\) and preserves \(\ket{B}\); second, the reflection \(R_\psi = 2\ketbra{\psi}{\psi} - I\) across the prepared state \(\ket{\psi}\). How can we implement a reflection across \(\ket{\psi} = A\ket{0^n}\) when \(\ket{\psi}\) is a complicated state produced by the circuit \(A\)?

Just as we conjugated \(2\ketbra{0^n}{0^n} - I\) by \(H^{\otimes n}\) in Section 8.2.3, we simply conjugate the all-zero reflection \(2\ketbra{0^n}{0^n} - I\) by \(A\) and its adjoint \(A^\dagger\):

\[R_\psi = 2\ketbra{\psi}{\psi} - I = 2(A\ket{0^n})(\bra{0^n}A^\dagger) - AA^\dagger = A\bigl(2\ketbra{0^n}{0^n} - I\bigr)A^\dagger.\]

Reading the operator product from right to left shows how \(R_\psi\) works in three steps: first apply the inverse circuit \(A^\dagger\) (which maps \(\ket{\psi}\) back to \(\ket{0^n}\)), then apply the standard reflection \(2\ketbra{0^n}{0^n} - I\) about the all-zero state \(\ket{0^n}\), and finally apply the forward preparation circuit \(A\) (which maps \(\ket{0^n}\) back to \(\ket{\psi}\)).

Crucially, this construction requires coherent access to the unitary preparation circuit \(A\), its inverse circuit \(A^\dagger\), and the phase-marking oracle \(O_G\). Having a classical black box that merely outputs random samples from \(\ket{\psi}\) is not enough: measuring after \(A\) collapses the state vector and prevents the reflection \(R_\psi\) from rotating amplitudes.

Let us compare classical repetition against quantum amplitude amplification. If a single run of a classical procedure succeeds with small probability \(p\), repeating independent classical trials requires roughly \(1/p\) runs to achieve a high probability of at least one success. By contrast, each round of amplitude amplification \(R_\psi O_G\) rotates the state vector by \(2\theta \approx 2\sqrt{p}\) toward \(\ket{G}\), reaching a success probability near \(1\) after only

\[k \approx \frac{\pi}{4\theta} \approx \frac{\pi}{4\sqrt{p}}\]

iterations—reducing the number of repetitions from order \(1/p\) to order \(1/\sqrt{p}\)!

To evaluate the total gate cost honestly, we must count the work performed inside each amplification round. Each round applies \(O_G\) once (at cost \(C_G\)) and \(R_\psi = A(2\ketbra{0^n}{0^n}-I)A^\dagger\) once (which runs both \(A\) and \(A^\dagger\), at cost roughly \(2C_A\)). Including the initial preparation \(A\), the total cost to reach high success probability scales as

\[\text{Total cost} \sim \frac{2C_A + C_G}{\sqrt{p}}.\]

This formula captures both the power and the engineering trade-offs of amplitude amplification: the denominator \(\sqrt{p}\) delivers the quadratic speedup in trial count, while the numerator \(2C_A + C_G\) reminds us that every iteration must pay the full coherent gate cost of preparing, uncomputing, and testing the state. In Chapter 10, we will prove that this \(\sqrt{N}\) scaling is not merely a feature of Grover's construction, but the absolute mathematical limit for any quantum search algorithm.