Chapter 12

Grover search as two reflections

An oracle call flips the sign of one amplitude and changes no measurement probability. How can a sign flip, followed by a second operation, increase the answer's probability, and why must we stop repeating that pair?

Before you start: Amplitudes and relative signs (Chapter 1); reversible evaluation of a function as an oracle (Chapter 4); turning a function value into a phase, and the uniform superposition made by $H^{\otimes n}$ (Chapter 10). The double-angle formulas for sine and cosine. Notation guide.

A checker and nothing else

Suppose a routine can check a proposed answer, and exactly one of $N$ candidates passes: a key that decrypts a message, an assignment that satisfies a set of constraints. Suppose also that nothing about the routine suggests where to look, so the only use of it is to try candidates. Classically, finding the answer takes about $N/2$ checks on average and $N-1$ in the worst case.

A quantum computer can run the same check on a superposition of all candidates. Chapter 10 showed what that produces: the answer's amplitude changes sign, and every measurement probability stays at $1/N$. The sign is information that a measurement cannot yet see. This chapter follows the one further operation that makes it visible, first on four candidates by arithmetic and then in general as a rotation. The rotation also shows why the iterations must be counted: it does not stop at the answer.

Specify the search problem

Let $N=2^n\ge2$ candidate strings contain exactly one marked item $w$. The oracle recognises it coherently: $O_w|x\rangle=(-1)^{[x=w]}|x\rangle$. Here $[x=w]$ is one if the equality holds and zero otherwise. It can be obtained from a reversible Boolean checker using the $|-\rangle$ target of Chapter 10.

Prepare $|s\rangle=N^{-1/2}\sum_x|x\rangle$ with $H^{\otimes n}$. A direct measurement finds $w$ with probability $1/N$. One oracle call flips its amplitude's sign but leaves every probability unchanged. The next operation must convert that phase difference into a probability difference.

The diffusion operator reflects amplitudes about their mean

Define $D=2|s\rangle\langle s|-I$. It fixes the component along $|s\rangle$ and negates every orthogonal component, so $D^2=I$. If $|\psi\rangle=\sum_xa_x|x\rangle$ and $\bar a=N^{-1}\sum_xa_x$, then

$$D|\psi\rangle=\sum_x(2\bar a-a_x)|x\rangle.$$

This formula works for complex amplitudes too; $\bar a$ is an amplitude mean, not a probability mean. The circuit identity $D=H^{\otimes n}(2|0^n\rangle\langle0^n|-I)H^{\otimes n}$ shows that diffusion does not require knowledge of $w$. The marked-item information enters only through the oracle.

One iteration with four candidates

Take $N=4,w=2$. The initial amplitudes are $(1/2,1/2,1/2,1/2)$. The oracle gives $(1/2,1/2,-1/2,1/2)$, whose mean is $1/4$. Diffusion maps each amplitude to $1/2-a_x$: the three unmarked amplitudes become zero and the marked one becomes one. A single iteration $G=DO_w$ therefore finds the answer with certainty.

The example makes the sequence explicit: a sign change first, then cancellation on unmarked states and reinforcement on the marked state. Measuring between these two operations would prevent that interference.

Reduce the general problem to a plane

Let $|r\rangle=(N-1)^{-1/2}\sum_{x\ne w}|x\rangle$, orthogonal to $|w\rangle$. The initial state is

$$|s\rangle=\sin\theta|w\rangle+\cos\theta|r\rangle,\qquad \sin\theta=\frac1{\sqrt N}.$$

Both the oracle and diffusion map this plane to itself, and inside it each is a reflection. The oracle negates the $|w\rangle$ component and leaves every unmarked basis state, hence $|r\rangle$, unchanged: it reflects about the $|r\rangle$ axis. Diffusion, $2|s\rangle\langle s|-I$, keeps the component along $|s\rangle$ and negates the component perpendicular to it: it reflects about the line through $|s\rangle$.

Two reflections about lines that meet at angle $\theta$ compose to a rotation by $2\theta$. To see this, describe a real unit vector in the plane by its angle $\alpha$ from $|r\rangle$, measured towards $|w\rangle$, so that its column in the ordered basis $(|w\rangle,|r\rangle)$ is $(\sin\alpha,\cos\alpha)^T$. The oracle sends $\alpha$ to $-\alpha$. Reflection about the line at angle $\theta$ sends any angle $\beta$ to $2\theta-\beta$. Applying one and then the other gives $\alpha\mapsto2\theta+\alpha$. In matrix form, the iteration $G=DO_w$ is

$$G=\begin{pmatrix}\cos2\theta&\sin2\theta\\-\sin2\theta&\cos2\theta\end{pmatrix}.$$

The same matrix from the definitions of $D$ and $O_w$, entry by entry

We can calculate diffusion in this basis directly from its definition. The projector is the column for $|s\rangle$ multiplied by its row:

$$|s\rangle\langle s|=\begin{pmatrix}\sin^2\theta&\sin\theta\cos\theta\\\sin\theta\cos\theta&\cos^2\theta\end{pmatrix}.$$

Multiplying by two and subtracting the identity gives diagonal entries $2\sin^2\theta-1=-\cos2\theta$ and $2\cos^2\theta-1=\cos2\theta$. Its off-diagonal entries are $2\sin\theta\cos\theta=\sin2\theta$. In particular, diffusion mixes marked and unmarked amplitudes; it is not diagonal in this basis.

The oracle is diagonal here because it negates $|w\rangle$ and leaves every unmarked basis state, hence $|r\rangle$, unchanged. To form $G=DO_w$, multiply $D$ by this diagonal matrix on the right: negate the first column of $D$ and retain the second. This explains each sign in the rotation matrix above.

Both oracle and diffusion preserve this plane. In the ordered basis $(|w\rangle,|r\rangle)$, write $|s\rangle$ as the real column $(\sin\theta,\cos\theta)^T$. The two individual matrices are

$$O_w=\begin{pmatrix}-1&0\\0&1\end{pmatrix},\qquad D=\begin{pmatrix}-\cos2\theta&\sin2\theta\\\sin2\theta&\cos2\theta\end{pmatrix}.$$

Multiplying the two reflections in circuit order, oracle first, gives the rotation matrix above.

Multiplying $G$ by $(\sin\alpha,\cos\alpha)^T$ gives $(\sin(\alpha+2\theta),\cos(\alpha+2\theta))^T$, as the angle argument requires. The start state $|s\rangle$ is at angle $\theta$. Thus after $k$ iterations,

$$G^k|s\rangle=\sin((2k+1)\theta)|w\rangle+\cos((2k+1)\theta)|r\rangle,\quad p_k=\sin^2((2k+1)\theta).$$

Writing the plane in terms of $|w\rangle$ is for analysis; the circuit never needs to prepare that unknown basis vector directly.

Choose when to stop

The first probability maximum occurs near $(2k+1)\theta=\pi/2$. Choose a nonnegative integer nearest to $\pi/(4\theta)-1/2$. For large $N$, $\theta\approx1/\sqrt N$, giving $k\approx(\pi/4)\sqrt N$. Rounding introduces at most an angular error $\theta$, so for this single-target setting the resulting success probability is at least $\cos^2\theta=1-1/N$.

For $N=8$, the initial success chance is $1/8$. One iteration raises it to $25/32\approx0.781$; two raise it to $121/128\approx0.945$; three reduce it to $169/512\approx0.330$. Continuing indefinitely is not harmless. The state rotates past the target and its overlap falls again. Later peaks exist, and one may happen to be higher than the first, but each costs more queries; the stopping rule aims at the first.

If $1\le M<N$ targets are marked, replace $|w\rangle$ by the uniform superposition of targets and use $\sin\theta=\sqrt{M/N}$. The same rotation formula follows, but the stopping count depends on $M$. An unknown target count requires an additional strategy; the single-target prescription cannot simply be assumed.

What the square-root speedup counts

We use asymptotic notation to compare resource growth as $N$ increases. A query count $Q(N)=O(g(N))$ has an upper bound $C g(N)$ for sufficiently large $N$, for a constant $C$ independent of $N$. Writing $Q(N)=\Theta(g(N))$ means there are also a positive lower constant $c$ and bounds $c g(N)\le Q(N)\le C g(N)$. Thus a $\Theta(\sqrt N)$ claim combines an algorithm using at most a constant times $\sqrt N$ queries with a theorem excluding asymptotically smaller counts under the same problem assumptions.

For unstructured search with a unique target and bounded error, the oracle-query complexity is $\Theta(\sqrt N)$ quantumly versus $\Theta(N)$ classically. The lower bound is a theorem, not proved by the two-reflection calculation. This is a quadratic improvement, not an exponential one.

Total runtime includes the reversible checker, diffusion, preparation, and final verification of the candidate. If data must first be loaded into a memory, account for that cost and whether it is reused across searches. If the candidates are defined implicitly and the predicate is inexpensive, the oracle model can better reflect the task. Neither the existence of a checker nor the query bound alone establishes a practical advantage.

Where this leaves us

A sign change makes the answer more likely because the second operation acts on amplitudes, not probabilities. Flipping one sign lowers the mean amplitude, the marked amplitude now lies furthest below that mean, and reflection about the mean raises it while lowering the rest. In the plane of $|w\rangle$ and $|r\rangle$ the two reflections are a rotation by $2\theta$, with $\sin\theta=1/\sqrt N$, so about $(\pi/4)\sqrt N$ iterations bring the state close to $|w\rangle$. We must stop there because the rotation does not: the next iterations carry the state away from the answer. What the $\sqrt N$ counts is oracle queries, under the assumptions stated in the previous section.

This chapter, like the two before it, treated every gate as exact and the register as isolated for the whole run. A search over many candidates needs on the order of $\sqrt N$ coherent iterations, each of which gives the surroundings a chance to interact with the register. The next chapter describes what such an interaction does to a state.

Problems

1. Reproduce $p_1=25/32$ for $N=8$ using mean reflection.

Worked answer

Write each initial amplitude as $a=1/\sqrt8$. After the oracle there are seven $+a$ amplitudes and one $-a$, so the sum is $6a$ and the mean is $6a/8=3a/4$.

$$a'_w=2(3a/4)-(-a)=5a/2,\qquad a'_{x\ne w}=2(3a/4)-a=a/2.$$

Squaring the marked amplitude gives $p_1=25a^2/4=25/32$. The seven others contribute $7a^2/4=7/32$, checking total probability one. The probability gain comes from the amplitude update; squaring before averaging would give the wrong result.

2. For $N=4$ with one target, what happens after a second iteration?

Worked answer

For four candidates, $\sin\theta=1/2$, so $\theta=\pi/6$. After the first iteration the marked amplitude is $\sin(3\theta)=1$, and all others are zero. After the second,

$$p_2=\sin^2((2\cdot2+1)\theta)=\sin^2(5\pi/6)=1/4.$$

One can also check directly: starting from $|w\rangle$, the next oracle gives marked amplitude $-1$ and unmarked amplitudes zero. Their mean is $-1/4$. Diffusion makes the marked amplitude $1/2$ and each unmarked amplitude $-1/2$, so all four probabilities are $1/4$. The algorithm has already passed its first optimum.

References and further reading

Nielsen & Chuang, §6.1 (search and geometry) and §6.6 (optimality). The original construction is Grover, A fast quantum mechanical algorithm for database search.