CHAPTER 11

Grover search and amplitude amplification

Learning goals. Implement two reflections, derive the two-dimensional rotation, choose iteration counts, and include oracle and sampling costs.

11.1 The search problem

A predicate marks M of N candidates. We can coherently implement $O|x\rangle=-|x\rangle$ for marked x and $|x\rangle$ otherwise. For simplicity let $N=2^n$ and prepare

$$|s\rangle=\frac1{\sqrt N}\sum_{x=0}^{N-1}|x\rangle.$$

One measurement of this state succeeds with probability M/N. Grover’s algorithm increases that probability using the oracle and the diffusion operation

$$D=2|s\rangle\langle s|-I.$$

D is a reflection: it keeps $|s\rangle$ and reverses components orthogonal to it. It is unitary because $D^2=I$. It can be implemented using Hadamards and a phase operation on $|0^n\rangle$, up to global phase.

For amplitudes $a_x$, define their mean $\bar a=N^{-1}\sum_xa_x$. Then

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

The “reflection about the mean” description refers to amplitudes, which may be complex; it does not reflect probabilities.

11.2 Four-item worked example

Let N=4 and mark 10. Start with amplitudes $(1,1,1,1)/2$. The oracle gives

$$\left(\tfrac12,\tfrac12,-\tfrac12,\tfrac12\right),\qquad \bar a=\frac{\tfrac12+\tfrac12-\tfrac12+\tfrac12}{4}=\frac14.$$

Diffusion maps an unmarked amplitude to $2(1/4)-1/2=0$, and the marked one to $2(1/4)-(-1/2)=1$. Thus one iteration gives $|10\rangle$ exactly. This special small case illustrates interference but is not the general iteration count [15].

11.3 Rotation in a two-dimensional subspace

Define normalized uniform marked and unmarked states $|G\rangle,|B\rangle$. Then

$$|s\rangle=\sin\theta|G\rangle+\cos\theta|B\rangle,\qquad \sin^2\theta=M/N.$$

The oracle reverses the good component. Diffusion reflects about $|s\rangle$. Their product $DO$ rotates the state in this plane by $2\theta$ toward the marked subspace. After k iterations,

$$|\psi_k\rangle= \sin((2k+1)\theta)|G\rangle+ \cos((2k+1)\theta)|B\rangle,$$ $$P_k=\sin^2((2k+1)\theta).$$

Choose a nonnegative integer k near $\pi/(4\theta)-1/2$ and compare the neighboring integer values. When $M\ll N$, this is approximately $(\pi/4)\sqrt{N/M}$ iterations. Additional iterations can rotate past the target and reduce success.

For N=8,M=1, after one iteration

$$\sin(3\theta)=3\sin\theta-4\sin^3\theta =\frac3{\sqrt8}-\frac4{8\sqrt8} =\frac5{2\sqrt8},$$

so $P_1=25/32$. After two, $P_2=121/128$. The algorithm does not monotonically improve forever.

11.4 General amplitude amplification

Suppose an algorithm A prepares $A|0\rangle=\sqrt p|G\rangle+\sqrt{1-p}|B\rangle$. Replace the uniform-state reflection by $A(2|0\rangle\langle0|-I)A^\dagger$. Alternating it with a phase flip of successful outcomes amplifies the initial success amplitude. The cost includes calls to both A and $A^\dagger$ as well as the success test [16].

Unknown M complicates choosing k. Randomized iteration schedules, counting methods, or fixed-point variants can address this, with their own guarantees and costs. Applying the known-M formula to an unknown success rate is not an exact algorithm.

11.5 What the speedup does and does not establish

Grover achieves a quadratic improvement in black-box query complexity and is optimal in that setting [17]. A practical runtime includes preparation, reversible predicate computation, workspace, fault tolerance, and repetitions. Searching an ordinary database is not automatically one cheap quantum query: data access must be defined.

For an n-bit key with an efficient verification predicate, unstructured quantum search has the query scale $2^{n/2}$. That observation is not a complete cryptanalytic resource estimate. Parallelism, oracle circuits, reversible memory, and error-correction overhead affect the physical cost.

Grover also does not solve NP-complete problems in polynomial time in general. Replacing a $2^n$ exhaustive search by $2^{n/2}$ remains exponential in n. Structure-specific classical or quantum algorithms may perform differently; the black-box lower bound does not apply to every structured task.

11.6 Exercises