A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Grover's algorithm searches an unstructured database of N items for a marked item using only O(sqrt(N)) oracle queries, compared to the classical O(N). It works by repeatedly applying two reflections — an oracle that flips the phase of the target state and a diffusion operator that reflects about the mean amplitude — to amplify the target's amplitude from 1/sqrt(N) to near 1. After approximately (pi/4)*sqrt(N) iterations, measurement yields the target with high probability. This quadratic speedup is provably optimal for unstructured search and has broad applications through amplitude amplification.
Grover's algorithm addresses the most basic computational task: searching. Given a black-box function f:{0,1}^n -> {0,1} that outputs 1 for exactly one input w (the target) and 0 for all others, find w. Classically, this requires O(N) = O(2n) evaluations of f in the worst case. Grover's algorithm finds w using O(sqrt(N)) evaluations — a quadratic speedup. While more modest than Shor's exponential speedup, Grover's applies to any search or optimization problem, making it one of the most broadly applicable quantum algorithms.
The algorithm starts with all n qubits in the uniform superposition |s> = (1/sqrt(N)) sum_x |x>, achieved by applying Hadamard to |0>^n. In this state, every basis state has the same amplitude 1/sqrt(N). The target |w> has no more amplitude than any other state. The algorithm then iteratively amplifies |w>'s amplitude using the Grover iterate G = D * O, where O is the oracle and D is the diffusion operator.
The oracle O acts as O|x> = (-1)^(f(x)) |x> — it flips the phase of the target state and leaves all others unchanged. This is implemented using the same phase kickback trick as in Deutsch-Jozsa. The diffusion operator D = 2|s><s| - I reflects the state about |s>. Concretely, it inverts all amplitudes about their mean: if the mean amplitude is m, a state with amplitude a becomes 2m - a. After the oracle makes the target's amplitude negative, the diffusion operator boosts it above the mean (since the negative amplitude pulls the mean down, and the reflection pushes it up). Each iteration increases the target's amplitude by approximately 2/sqrt(N).
The geometric picture makes this precise. The entire algorithm takes place in the two-dimensional real subspace spanned by |w> and |w_perp> = (1/sqrt(N-1)) sum_{x != w} |x>. The initial state |s> makes an angle theta = arcsin(1/sqrt(N)) with |w_perp>. Each Grover iteration rotates the state vector by 2*theta toward |w>. After k iterations, the angle is (2k+1)*theta. The optimal number of iterations sets (2k+1)*theta ≈ pi/2, giving k ≈ (pi/4)*sqrt(N). At this point, the probability of measuring |w> is sin^2((2k+1)*theta) ≈ 1. Crucially, more iterations rotate past the optimal point, reducing the success probability — the algorithm oscillates rather than monotonically converging. This is why the iteration count must be carefully chosen, and it is why the complexity is O(sqrt(N)), not better.
Grover's quadratic speedup is provably optimal: the BBBV theorem shows no quantum algorithm can solve unstructured search in fewer than Omega(sqrt(N)) queries. However, the quadratic speedup generalizes through amplitude amplification: any classical algorithm that succeeds with probability p can be boosted to near-certainty using O(1/sqrt(p)) repetitions instead of the classical O(1/p). This makes Grover-type speedups applicable to NP search problems, optimization, and satisfiability — any problem where you can verify solutions but must search for them. The practical impact is that a quantum computer effectively takes the square root of the search space size.