Grover's algorithm

Remarks

The algorithm starts from the uniform superposition $\lvert s \rangle = N^{-1/2} \sum_x \lvert x \rangle$. Each iteration applies the oracle and then the reflection $2 \lvert s \rangle\langle s \rvert - I$. Together these two reflections rotate the state by an angle $2\theta$ in the plane spanned by $\lvert s \rangle$ and $\lvert w \rangle$. So after $r$ iterations the state makes angle $(2r+1)\theta$ with the axis orthogonal to $\lvert w \rangle$. The choice of $r$ makes this angle differ from $\pi/2$ by at most $\theta$, so the success probability is at least $\cos^2 \theta = 1 - 1/N$.

Example: for $N = 4$ one has $\theta = \pi / 6$, and a single iteration rotates $\lvert s \rangle$ from angle $\pi/6$ to angle $\pi/2$. So one query finds $w$ with certainty, while a classical search needs up to three queries.

Any classical algorithm needs about $N/2$ queries on average. Bennett, Bernstein, Brassard and Vazirani proved that every quantum algorithm needs $\Omega(\sqrt{N})$ queries, so the speedup is optimal.

Going deeper

For a student

Grover's method is an instance of amplitude amplification: two reflections, one about the marked states and one about the start state, rotate the state toward the answer. The same idea speeds up any algorithm that succeeds with small probability $p$, using about $1/\sqrt{p}$ repetitions instead of $1/p$. Applied to brute-force search, it gives a quadratic speedup for NP problems such as SAT. It does not put NP inside BQP, because $\sqrt{2^n}$ is still exponential.