Grover's algorithm: Searching with rotations

Imagine a phone book with $N$ entries in random order and a single name you are looking for. With no structure to help, the only classical strategy is to look entry by entry: $N / 2$ queries on average, $N$ in the worst case. In 1996 Lov Grover, at Bell Labs, showed that a quantum computer can find it with about $\frac{π}{4} \sqrt{N}$ queries. For a million entries, around 800 instead of half a million.

The problem

We have $N = 2^{n}$ items and an oracle that recognizes the marked one, $w$ : a function $f (x) = 1$ if $x = w$ and 0 otherwise. Quantumly, the oracle acts as a phase flip:

O | x ⟩ = (- 1)^{f (x)} | x ⟩, O = I - 2 | w ⟩ ⟨ w | .

The oracle flips the sign of the amplitude of the marked item but, on its own, does not change any probability. Something has to turn that sign into probability. That is the job of interference.

The algorithm

Start from the uniform superposition $| s ⟩ = H^{\otimes n} | 0 ⟩ = \frac{1}{\sqrt{N}} \sum_{x} | x ⟩$ and repeat $k$ times the Grover iteration:

G = D O, D = 2 | s ⟩ ⟨ s | - I .

The operator $D$ , called diffusion, is an inversion about the mean: it sends each amplitude $a_{x}$ to $2 \bar{a} - a_{x}$ , where $\bar{a}$ is the average. After the oracle, the marked amplitude is negative and far below the mean; when inverted, it rises well above it. Each iteration pumps a little more amplitude into $| w ⟩$ .

Grover's algorithm step by step. The bars are the amplitudes (real, with sign) and the dashed line is their mean. “Oracle” flips the sign of the marked item; “Diffusion” reflects every amplitude about the mean. The plot on the right shows the probability of success after each iteration: it oscillates as

\sin^{2} ((2 k + 1) θ)

, so iterating too much is as bad as iterating too little.

The geometry: two reflections make a rotation

The whole algorithm happens in a two-dimensional plane. Let $| w ⟩$ be the marked state and $| w^{⟂} ⟩$ the uniform superposition of the unmarked ones. The initial state lies in their span:

| s ⟩ = \sin θ | w ⟩ + \cos θ | w^{⟂} ⟩, \sin θ = \frac{1}{\sqrt{N}} .

Theorem (Grover iteration as a rotation)

On the plane spanned by $| w ⟩$ and $| w^{⟂} ⟩$ , the oracle $O$ is the reflection across $| w^{⟂} ⟩$ and $D$ is the reflection across $| s ⟩$ . Their product $G = D O$ is a rotation by $2 θ$ towards $| w ⟩$ . After $k$ iterations,

G^{k} | s ⟩ = \sin ((2 k + 1) θ) | w ⟩ + \cos ((2 k + 1) θ) | w^{⟂} ⟩,

and the probability of measuring $w$ is $\sin^{2} ((2 k + 1) θ)$ .

Proof

$O$ fixes $| w^{⟂} ⟩$ and flips $| w ⟩$ , so it is the reflection across the line of $| w^{⟂} ⟩$ . $D = 2 | s ⟩ ⟨ s | - I$ fixes $| s ⟩$ and flips every vector orthogonal to it, the reflection across the line of $| s ⟩$ . The composition of two reflections across lines that form an angle $θ$ is a rotation by $2 θ$ (a classical result of plane geometry). The initial state is at angle $θ$ from $| w^{⟂} ⟩$ ; after $k$ rotations it is at angle $(2 k + 1) θ$ .

To reach $| w ⟩$ we want $(2 k + 1) θ \approx π / 2$ , that is,

k \approx \frac{π}{4 θ} - \frac{1}{2} \approx \frac{π}{4} \sqrt{N},

since $θ \approx 1 / \sqrt{N}$ for large $N$ . With $M$ marked items, $\sin θ = \sqrt{M / N}$ and about $\frac{π}{4} \sqrt{N / M}$ iterations are needed. The quadratic speedup comes from the fact that the probability is the square of the amplitude: the amplitude grows linearly with $k$ , so it only has to reach $1$ starting from $1 / \sqrt{N}$ .

It cannot be done better

Before Grover's algorithm was even known, Bennett, Bernstein, Brassard and Vazirani had proved that it was optimal.

Theorem (BBBV, 1997)

Any quantum algorithm that finds the marked item among $N$ with probability at least $2 / 3$ , consulting the oracle as a black box, must make $Ω (\sqrt{N})$ queries.

Idea of the proof (hybrid argument)

Run the algorithm with an oracle that marks nothing. After $T$ queries, the total “query weight” it has placed on all items is $T$ , so some item $w$ has received weight at most $T / N$ . Changing the oracle to mark $w$ perturbs each step by an amount proportional to the square root of that weight, and the perturbations add up to at most $O (T / \sqrt{N})$ in norm. To tell the two situations apart, the final states must differ by a constant, so $T = Ω (\sqrt{N})$ .

Christof Zalka (1999) showed that Grover's algorithm is optimal even in the constant. The consequence is important: for problems with no structure, quantum computers offer a quadratic speedup, not an exponential one. In particular, they are not expected to solve NP-complete problems in polynomial time simply by “trying all the answers at once”.

Amplitude amplification

Brassard, Høyer, Mosca and Tapp (2002) generalized the idea. If a quantum algorithm $𝒜$ succeeds with probability $p$ , it can be turned into one that succeeds with high probability using only $O (1 / \sqrt{p})$ repetitions of $𝒜$ and $𝒜^{- 1}$ , against the $O (1 / p)$ that classical repetition needs. It is a quadratic accelerator for almost any quantum subroutine.

References

L. K. Grover (1996). “A fast quantum mechanical algorithm for database search”. STOC.
C. H. Bennett, E. Bernstein, G. Brassard and U. Vazirani (1997). “Strengths and Weaknesses of Quantum Computing”. SIAM J. Computing, 26(5).
M. Boyer, G. Brassard, P. Høyer and A. Tapp (1998). “Tight bounds on quantum searching”. Fortschritte der Physik, 46.
C. Zalka (1999). “Grover's quantum searching algorithm is optimal”. Physical Review A, 60(4).
G. Brassard, P. Høyer, M. Mosca and A. Tapp (2002). “Quantum amplitude amplification and estimation”. Contemporary Mathematics, 305.

§The problem

§The algorithm

§The geometry: two reflections make a rotation

§It cannot be done better

§Amplitude amplification