Amplitude Amplification

algorithmsReading-focused

10 min read

Amplitude Amplification

The geometric picture behind Grover's algorithm, two reflections make a rotation, and why unstructured search takes only O(√N) queries instead of O(N).

Suggested before this lesson

The Bernstein-Vazirani Algorithm

Deutsch-Jozsa and Bernstein-Vazirani both answer a yes/no or read-out-a-string question in one query. This lesson starts a different kind of problem, unstructured search, where one query can't possibly be enough, but a clever sequence of them still beats any classical approach by a quadratic factor. The technique is amplitude amplification, and Grover's algorithm (next lesson) is what you get from applying it.

The Search Problem

You're given an oracle for $f:\{0,1\}^n \to \{0,1\}$ again, but this time the promise is different: exactly one input $\omega$ (out of $N = 2^n$ total) has $f(\omega) = 1$ ; every other input has $f(x) = 0$ . Find $\omega$ . Classically, with no structure to exploit, you have to check inputs one at a time; the expected number of queries before finding $\omega$ is $O(N)$ .

Two Special States

Write $|\omega\rangle$ for the marked basis state you're looking for, and $|s'\rangle$ for the uniform superposition over every other basis state (all $N-1$ unmarked ones, equally weighted, normalized). These two are orthogonal, $\langle\omega|s'\rangle = 0$ , and together they span a 2D plane inside the full $N$ -dimensional space, the only plane this entire algorithm ever needs.

The starting state, uniform superposition over everything ( $H^{\otimes n}|0\rangle^{\otimes n}$ , from Superposition and Interference at Scale), decomposes inside that plane as

$|s\rangle = \sin\theta\,|\omega\rangle + \cos\theta\,|s'\rangle, \qquad \sin\theta = \frac{1}{\sqrt N}$

Every basis state has equal amplitude $1/\sqrt N$ to start, so $|\omega\rangle$ 's own slice of that is exactly $\sin\theta = 1/\sqrt N$ , small for large $N$ : this is the whole problem in one picture. Measuring right now succeeds with probability $\sin^2\theta = 1/N$ , exactly as bad as guessing randomly. The algorithm's job is to rotate $|s\rangle$ toward $|\omega\rangle$ before measuring.

Two Reflections Make a Rotation

The oracle $O$ flips the sign of $|\omega\rangle$ 's amplitude and leaves everything orthogonal to it alone: a reflection about $|s'\rangle$ (the axis it doesn't touch).

The diffusion operator $D = 2|s\rangle\langle s| - I$ is a reflection about $|s\rangle$ itself, the original uniform superposition axis, regardless of what the oracle just did to the state.

A basic fact from plane geometry: reflecting about one line, then reflecting about a second line at angle $\theta$ to the first, is the same as a single rotation by $2\theta$ . That's exactly $D \cdot O$ : reflect about $|s'\rangle$ , then about $|s\rangle$ (which sits at angle $\theta$ from $|s'\rangle$ ), composes into a rotation by $2\theta$ , rotating the state vector toward $|\omega\rangle$ . One application of $D\cdot O$ is called one Grover iteration.

Iterating

After $k$ Grover iterations, the state sits at angle $(2k+1)\theta$ from the $|s'\rangle$ axis (the original $\theta$ , plus $k$ rotations of $2\theta$ each), so the probability of measuring $|\omega\rangle$ is

$P(\omega) = \sin^2\big((2k+1)\theta\big)$

This grows with $k$ up to a peak near $(2k+1)\theta \approx \tfrac{\pi}{2}$ , then decreases again if you keep iterating past it, overshooting is real, unlike classical search where more checking can never hurt. Solving for the peak gives the optimal iteration count:

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

$O(\sqrt N)$ iterations, each one query to the oracle, versus $O(N)$ classically: a quadratic speedup. It's smaller than Deutsch-Jozsa's exponential gap, but it applies to a much more general problem: searching anything representable as "find the input a black-box function accepts," with no structure to exploit at all.

Watch the rotation toward

∣ ω ⟩

Slide $k$ to add Grover iterations and see the state vector rotate by $2\theta$ each time, with the success probability tracking $\sin^2((2k+1)\theta)$ below.

N =

State in the (|s'⟩, |ω⟩) plane

$Grover iterations k$

$P (measure ω)$

47.3%

$k_{opt} \approx \frac{π}{4} N \approx 3$

Each iteration rotates the state by $2\theta$ toward $|\omega\rangle$ . Slide $k$ up past $k_{\text{opt}}$ and watch the success probability peak, then fall again, overshoot is real in Grover's algorithm, unlike classical search. Try a bigger $N$ : the starting angle $\theta$ shrinks, so more iterations are needed, but the achievable peak probability stays close to 1.

Check your understanding

Why does composing the oracle reflection and the diffusion reflection produce a rotation, specifically, toward the marked state?

Reflecting twice about the same line always rotates by 90°.

Composing two reflections about two lines that meet at angle

\theta

is a rotation by

2\theta

, and here the diffusion axis

|s\rangle

sits at angle

\theta

from the oracle's axis

|s'\rangle

, rotating the state toward

|\omega\rangle

by construction.

The oracle and diffusion operators happen to be inverses of each other.

It's a numerical coincidence specific to

N=4

Check your understanding

If you keep applying Grover iterations well past the optimal count

k_{\text{opt}}

, what happens to the success probability?

It keeps increasing, approaching 1 asymptotically.

It stays flat at its peak value forever.

It decreases again, since the rotation keeps going past

|\omega\rangle

and starts rotating back away from it.

It immediately drops to 0.