🔍

Topic 7 of 12

Grover's Search Algorithm

Grover's algorithm searches an unsorted database of N items for a marked entry in O(√N) steps — a quadratic speedup over the classical O(N) requirement. While not exponential, this is provably optimal for quantum computers (Bennett et al. 1997) and translates to massive practical gains: searching one trillion items in a million steps instead of half a trillion.

Key Concepts

Unstructured Search

Given N items with no ordering or structure, find the unique marked item

|\omega\rangle

. Classically, each query checks one item; expected O(N/2) queries. Quantum mechanics allows amplitude amplification to boost the probability of finding

|\omega\rangle

to near certainty in O(√N) queries.

Grover Oracle

The oracle

U_\omega|x\rangle = -|x\rangle

x = \omega

, else

+|x\rangle

. It marks the target by flipping its phase — a phase oracle. Implemented as a black box that recognizes the answer without revealing it. Each application constitutes one 'query.'

Grover Diffusion Operator

The operator

U_s = 2|s\rangle\langle s| - I

where

|s\rangle = H^{\otimes n}|0^n\rangle

is the uniform superposition. It reflects amplitudes about the mean, amplifying the marked state's amplitude and suppressing all others. Also called inversion-about-the-mean.

Amplitude Amplification

Alternating oracle

U_\omega

and diffusion

U_s

rotates the state toward

|\omega\rangle

by angle

2\theta

per iteration where

\sin\theta = 1/\sqrt{N}

. After

k \approx \frac{\pi}{4}\sqrt{N}

iterations, the probability of measuring

|\omega\rangle

approaches 1.

Optimality

Grover's algorithm is provably optimal: no quantum algorithm can search N items in fewer than

\Omega(\sqrt{N})

queries (BBBV theorem, 1997). The quadratic speedup cannot be improved — there is no quantum algorithm that searches in O(N^{1/3}) or better.

Multiple Solutions

If there are

M

marked items among

N

, the optimal number of Grover iterations is

\frac{\pi}{4}\sqrt{N/M}

. With

M = N/4

, only 1 iteration suffices. The BBHT algorithm handles unknown

M

with a quantum exponential search that finds a solution in

O(\sqrt{N/M})

queries.

Key Equations

Grover Iteration Count

k^* = \left\lfloor \frac{\pi}{4}\sqrt{N} \right\rfloor

Optimal number of Grover iterations for N items (1 marked solution).

Success Probability

P_{\text{success}}(k) = \sin^2\!\left((2k+1)\arcsin\frac{1}{\sqrt{N}}\right)

Probability of measuring the marked item after k Grover iterations.

Classical vs Quantum Queries

Q_{\text{classical}} = O(N), \quad Q_{\text{quantum}} = O(\sqrt{N})

Quantum gives a quadratic speedup — square root instead of linear in N.

Grover Operator

G = U_s \cdot U_\omega = (2|s\rangle\langle s|-I)(I - 2|\omega\rangle\langle\omega|)

One Grover iteration: oracle then diffusion about mean.

Worked Example

Grover's Search for N=4

Problem

For $N=4$ items (2-qubit register), find the optimal number of Grover iterations and the success probability.

Solution

Compute optimal iterations:

k^* = \left\lfloor\frac{\pi}{4}\sqrt{4}\right\rfloor = \left\lfloor\frac{\pi}{4}\cdot 2\right\rfloor = \left\lfloor\frac{\pi}{2}\right\rfloor = \lfloor 1.571 \rfloor = 1

After 1 iteration, success probability:

P = \sin^2\!\left(3\arcsin\frac{1}{2}\right) = \sin^2\!\left(3 \cdot \frac{\pi}{6}\right) = \sin^2\!\left(\frac{\pi}{2}\right) = 1

Answer 1 iteration gives P(success) = 100% for N=4.

Practice

Exercises

5 problems

1 of 5

For $N=4$ items, the optimal Grover iterations $= \lfloor \pi\sqrt{N}/4 \rfloor$ . How many?

Your answer

iterations

2 of 5

For $N=16$ , optimal iterations $= \lfloor \pi\sqrt{16}/4 \rfloor = \lfloor \pi \rfloor$ . How many?

Your answer

iterations

3 of 5

Classical random search of $N=1000$ items: expected number of queries = $N/2$ . How many?

Unlock Exercise 3

Subscribe to PhysWeb Pro to access all exercises and track your progress.

Upgrade to Pro →

4 of 5

Grover's algorithm searches $N=1000$ items in $O(\sqrt{N})$ queries. $\sqrt{1000} \approx$ ?

Unlock Exercise 4

Subscribe to PhysWeb Pro to access all exercises and track your progress.

Upgrade to Pro →

5 of 5

The quantum/classical speedup ratio for $N=10000$ : classical needs $N/2=5000$ , quantum needs $\sqrt{N}=100$ . Ratio classical/quantum?

Unlock Exercise 5

Subscribe to PhysWeb Pro to access all exercises and track your progress.

Upgrade to Pro →

Key Takeaways

Grover finds a marked item in $O(\sqrt{N})$ queries — a quadratic speedup over classical $O(N)$ .
Each iteration applies the oracle (phase flip on target) then diffusion (inversion about the mean).
Optimal iterations: $k^* = \lfloor \frac{\pi}{4}\sqrt{N} \rfloor$ ; over-iterating reduces success probability.
The quadratic speedup is provably optimal — no quantum algorithm can do better than $O(\sqrt{N})$ .
With $M$ solutions among $N$ items, optimal iterations become $\frac{\pi}{4}\sqrt{N/M}$ .