Skip to content

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⟩=−|x⟩O|x\rangle=-|x\rangle for marked x and |x⟩|x\rangle otherwise. For simplicity let N=2 n N=2^n and prepare

|s⟩=1 N∑x=0 N−1|x⟩.|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⟩⟨s|−I.D=2|s\rangle\langle s|-I.

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

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

(D|ψ⟩)x=2 a‾−a x.(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(1,1,1,1)/2. The oracle gives

(1 2,1 2,−1 2,1 2),a‾=1 2+1 2−1 2+1 2 4=1 4.\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 2(1/4)-1/2=0, and the marked one to 2(1/4)−(−1/2)=1 2(1/4)-(-1/2)=1. Thus one iteration gives |10⟩|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⟩,|B⟩|G\rangle,|B\rangle. Then

|s⟩=sin θ|G⟩+cos θ|B⟩,sin 2 θ=M/N.|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⟩|s\rangle. Their product D O DO rotates the state in this plane by 2 θ 2\theta toward the marked subspace. After k iterations,

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

Choose a nonnegative integer k near π/(4 θ)−1/2\pi/(4\theta)-1/2 and compare the neighboring integer values. When M≪N M\ll N, this is approximately (π/4)N/M(\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 θ)=3 sin θ−4 sin 3 θ=3 8−4 8 8=5 2 8,\sin(3\theta)=3\sin\theta-4\sin^3\theta =\frac3{\sqrt8}-\frac4{8\sqrt8} =\frac5{2\sqrt8},

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

Figure 11.1. Grover success probability oscillates with iteration count.

## 11.4 General amplitude amplification

Suppose an algorithm A prepares A|0⟩=p|G⟩+1−p|B⟩A|0\rangle=\sqrt p|G\rangle+\sqrt{1-p}|B\rangle. Replace the uniform-state reflection by A(2|0⟩⟨0|−I)A†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†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 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 2^n exhaustive search by 2 n/2 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.

Laboratory L15 — Amplitude amplification. Choose register size, marked items, iterations, shots, and seed. Inspect signed amplitudes after each iteration and the complete success curve. Deliberately over-rotate.

## 11.6 Exercises

11.1. For N=4,M=1, calculate success after two iterations.

Show solution / guidance

θ=π/6\theta=\pi/6, so P 2=sin 2(5 π/6)=1/4 P_2=\sin^2(5\pi/6)=1/4. The second iteration undoes the perfect success of the first.

11.2. For M=N/2, does the ordinary iteration improve success?

Show solution / guidance

θ=π/4\theta=\pi/4, so sin 2((2 k+1)π/4)=1/2\sin^2((2k+1)\pi/4)=1/2 for every integer k. This reflection schedule cannot improve it.

11.3. Prove D preserves the vector norm.

Show solution / guidance

Let P=|s⟩⟨s|P=|s\rangle\langle s|, with P 2=P=P†P^2=P=P^\dagger. Then D†D=(2 P−I)2=4 P 2−4 P+I=I D^\dagger D=(2P-I)^2=4P^2-4P+I=I.

11.4. A state preparation costs 100 gates, its inverse costs 100, and a success oracle costs 500. Estimate gate work for 20 amplification iterations, excluding reflection overhead.

Show solution / guidance

20(100+100+500)=14,000 20(100+100+500)=14{,}000 gates, plus the initial preparation and omitted reflections. Counting only 20 oracle queries would conceal most details.

11.5. With independent success probability P per run, how many runs make failure at most δ\delta?

Show solution / guidance

Failure is (1−P)r(1-P)^r. For 0<P<1 0<P<1, choose r≥log δ/log(1−P)r\ge\log\delta/\log(1-P) and round up. Verification of the proposed answer must also be included.

IN THIS CHAPTER