Grover's Search Algorithm

Grover's Search Algorithm

The Problem

You have an unsorted database of N items. One item is "marked", it satisfies some property f(x) = 1. You want to find it. You can only access the database through queries: present an item x, learn whether f(x) = 0 or 1.

Classically, you must query items one at a time. On average, you'll find the marked item after N/2 queries; in the worst case, N-1 queries. If N = 1,000,000, that's up to 500,000 queries on average.

Grover's algorithm finds the marked item in approximately $\pi \sqrt{N}/4$ queries, a quadratic speedup. For N = 1,000,000, that's ~785 queries instead of 500,000. For $N=2^{100}$ items (a problem no classical computer could ever touch), Grover's needs only $2^{50}$ queries.

This is a provably optimal quantum algorithm for unstructured search, no quantum algorithm can do better than $O(\sqrt{N})$ for this problem.

Geometric Intuition: Reflection About the Mean

After the oracle marks the target state, all $N$ amplitudes look like: $N-1$ states with amplitude $+1/\sqrt{N}$, and one marked state with amplitude $-1/\sqrt{N}$. The mean amplitude $\bar{a}$ is:

The diffuser step performs "inversion about the mean": each amplitude $a_x$ is replaced by $2\bar{a}-a_x$.