Grover's search algorithm

Deutsch–Jozsa won on an artificial problem. This section tackles a problem everyone understands — finding a needle in a haystack — and this time the opponent is a genuine classical lower bound.

The problem at the door: N drawers, one key

$N=2^n$ drawers, numbered $0$ to $N-1$, exactly one of which (call it $w$) hides the key. You have a black box $f$: give it a number $x$ and it answers $f(x)=1$ if and only if $x=w$. The only classical strategy is opening drawers: $N/2$ on average, $N$ in the worst case, with no shortcut whatsoever — $f$ has no structure to exploit (this is not a sorted phone book; it is shuffled).

The quantum oracle copies last section’s phase kickback (the $\ket{-}$ ancilla is now left implicit):

$$O\ket{x}=(-1)^{f(x)}\ket{x} \qquad\Longleftrightarrow\qquad O=I-2\ket{w}\bra{w}\tag{9.8.1}$$

It does exactly one thing: flip the sign of the target branch.

Why one round of interference no longer suffices

Try copying DJ’s three moves: a row of $H$‘s prepares the uniform superposition $\ket{s}=\frac{1}{\sqrt N}\sum_x\ket{x}$, call the oracle once, then interfere. The trouble: the oracle flips the sign of only one of the $2^n$ amplitudes, and that perturbation affects the overall distribution at order $O(1/\sqrt N)$ — one round of interference cannot wash it out, and a direct measurement still hits with probability about $1/N$. In DJ’s problem, “all the function values conspiring” produced a stark global signal; the search problem’s signal is thread-thin. The way out: stop hoping for a one-shot kill and let a small advantage snowball. Each round twists the amplitude pointing at the target a little larger; twist for $\sqrt N$ rounds. This “amplitude amplifier” is built from two mirrors.

The geometric picture: two mirrors = one rotation

All the action happens in a two-dimensional plane — the one spanned by the target state $\ket{w}$ and the uniform superposition $\ket{s}$. Take the in-plane unit vector perpendicular to $\ket{w}$, $\ket{r}=\frac{1}{\sqrt{N-1}}\sum_{x\ne w}\ket{x}$ (the “uniform superposition of the other drawers”); then

$$\ket{s}=\cos\theta\,\ket{r}+\sin\theta\,\ket{w}, \qquad \sin\theta=\braket{w}{s}=\frac{1}{\sqrt N}\tag{9.8.2}$$

The initial state $\ket{s}$ sits only a small angle $\theta\approx1/\sqrt N$ above the “ground” $\ket{r}$. The Grover iteration has two steps:

1. The oracle $O$: flips the sign of the $\ket{w}$ component = a reflection about $\ket{r}$ (mirror one);
2. The diffusion operator $D=2\ket{s}\bra{s}-I$: a reflection about $\ket{s}$ (mirror two).

Two reflections compose into one 2θ rotationbasic~7 minexpand

Step 1: confirm $O$ is a reflection. For any in-plane state $\ket{\psi}=\cos\phi\ket{r}+\sin\phi\ket{w}$:

$$O\ket{\psi}=\cos\phi\ket{r}-\sin\phi\ket{w}\tag{9.8.3}$$

The angle maps $\phi\mapsto-\phi$: precisely a reflection with $\ket{r}$ as the mirror.

Step 2: confirm $D$ is a reflection. $D=2\ket{s}\bra{s}-I$ satisfies $D\ket{s}=\ket{s}$ (vectors on the mirror stay put) and negates the component perpendicular to $\ket{s}$ — a reflection with $\ket{s}$ (at angle $\theta$) as the mirror: $\phi\mapsto2\theta-\phi$.

Step 3: compose. $O$ first, then $D$:

$$\phi\ \xrightarrow{\ O\ }\ -\phi\ \xrightarrow{\ D\ }\ 2\theta+\phi\tag{9.8.4}$$

Two reflections = one rotation, by angle $2\theta$, toward $\ket{w}$. This is an old theorem of plane geometry (mirrors at angle $\theta$: two reflections make a rotation by $2\theta$), restaged verbatim in Hilbert space.

Step 4: iterate $k$ rounds. Starting angle $\theta$, adding $2\theta$ per round:

$$\phi_k=(2k+1)\theta,\qquad P_{\text{hit}}(k)=\sin^2\big[(2k+1)\theta\big]\tag{9.8.5}$$

We want $\phi_k\approx\pi/2$ (dead-on target), so

$$k_{\text{opt}}\approx\frac{\pi/2-\theta}{2\theta}\approx\frac{\pi}{4}\sqrt N\tag{9.8.6}$$

(The last step uses $\theta\approx\sin\theta=1/\sqrt N$ for large $N$.) $O(\sqrt N)$ queries, each round costing only two rows of $H$‘s and a little phase work — the quadratic speedup is in hand.

Hand-compute N = 4: one iteration, a perfect hit

$N=4$ (two qubits), target $w=10$. Here $\sin\theta=\tfrac12$, $\theta=30^\circ$ — not a “small” angle, which lets us hand-compute a whole round.

Step 0: $\ket{s}=\tfrac12(\ket{00}+\ket{01}+\ket{10}+\ket{11})$, all four amplitudes $0.5$.

Step 1 (oracle): the target flips sign:

$$\big(\tfrac12,\ \tfrac12,\ -\tfrac12,\ \tfrac12\big)\tag{9.8.8}$$

Step 2 (inversion about the mean): the mean is $\bar a=\frac{0.5+0.5-0.5+0.5}{4}=\tfrac14$. Each amplitude $\mapsto 2\times\tfrac14-a_x=\tfrac12-a_x$:

$$\big(0,\ 0,\ 1,\ 0\big)\tag{9.8.9}$$

The state has become exactly $\ket{10}$. Measure: 100% hit, one query. Classically it takes $2.25$ drawer-openings on average (3 in the worst case) to be sure. Geometric check: $\phi_1=(2\times1+1)\times30^\circ=90^\circ$, dead-on target, to the degree.

Quadratic is the limit: the BBBV lower bound

Could a cleverer quantum algorithm manage $\log N$? No. The Bennett–Bernstein–Brassard–Vazirani theorem: any quantum algorithm for unstructured search needs at least $\Omega(\sqrt N)$ oracle queries. The idea is worth remembering: each query perturbs the state by at most $O(1/\sqrt N)$ (it moves the sign of only one branch), while pulling the final states for “the target is $w_1$” and “the target is $w_2$” apart to a distinguishable distance requires a cumulative perturbation of $O(1)$ — divide, and $\Omega(\sqrt N)$ falls out. Grover flies flush against the bound; even the constant $\pi/4$ is optimal.

∎Key formulas

• Grover iteration

  $$G=D\,O,\quad O=I-2\ket{w}\bra{w},\quad D=2\ket{s}\bra{s}-I$$

  Two mirrors: oracle reflection + mean reflection = rotation by 2θ

• Angle parameter

  $$\sin\theta=\sqrt{M/N},\qquad \phi_k=(2k+1)\theta$$

  M is the number of targets; each round turns 2θ toward the target

• Hit probability

  $$P(k)=\sin^2[(2k+1)\theta]$$

  A sinusoidal oscillation — past π/2 it turns back down; count laps and park

• Optimal rounds

  $$k_{\text{opt}}\approx\frac{\pi}{4}\sqrt{N/M}$$

  BBBV lower bound Ω(√N): quadratic speedup is the black-box search limit

?Self-check4 questions

1. 1.

   Geometrically, what are the two steps of a Grover iteration?

   • A reflection about ∣r⟩ (perpendicular to the target), and a reflection about ∣s⟩ (the uniform superposition)
   • A reflection about ∣w⟩, and a reflection about ∣r⟩
   • A rotation by θ, and a rotation by −θ
   • A projective measurement, and a unitary rotation

   Submit
2. 2.

   N = 10⁶ entries, a single target. Roughly how many Grover iterations are optimal? (Integer.)

   300% relative tolerance

   Submit
3. 3.

   N = 4, a single target, and you ran 2 Grover iterations (one too many). What is the hit probability now?

   2% relative tolerance

   Submit
4. 4.

   Which statements about the scope of Grover’s algorithm are correct? (Select all that apply.)

   Select all that apply

   • It gives a quadratic speedup for unstructured search, and the BBBV theorem proves nothing faster is possible
   • It makes NP-complete problems polynomial-time solvable
   • With M targets, the iteration count is about (π/4)√(N/M)
   • The countermeasure for symmetric cryptography is doubling the key length

   Submit

What comes next

The quadratic speedup already touches the ceiling of black-box search; for exponential speedup we must leave the black box behind and mine the problem’s internal structure. One problem’s structure happens to be exactly what quantum mechanics does best — periodicity: factoring large integers reduces to “finding the period of a function”, and finding periods is interference’s signature trade. Next section: Shor’s algorithm, and the sword it dangles over RSA.