Search an unsorted database with quantum amplitude amplification—watch marked states get amplified quadratically faster than classical
Grover's algorithm is a quantum algorithm that searches an unsorted database of N items in O(√N) time, providing a quadratic speedup over the classical O(N) linear search. This is one of the most important quantum algorithms, demonstrating a provable quantum advantage for a practical computational problem.
Imagine you have a database of N items, and exactly one of them is "marked" (the target you're searching for). Classically, you have no choice but to check items one by one—on average, you'll need to check N/2 items, and in the worst case, all N items. This is O(N) complexity. Grover's algorithm does this in approximately √N queries using quantum superposition and interference.
For an n-qubit system, there are N = 2n possible computational basis states |0⟩, |1⟩, ..., |N-1⟩. The algorithm represents the database as a quantum superposition over all these states, and uses quantum interference to amplify the amplitude of the marked state while suppressing the others.
Start with all qubits in |0⟩. Apply Hadamard gates to create an equal superposition:
|ψ⟩ = (1/√N) ∑ |x⟩
Every state has equal amplitude 1/√N, so each has probability 1/N of being measured. This is our starting point—no information about the target yet.
The oracle operator O marks the target state |t⟩ by flipping its phase:
O|x⟩ = (-1)f(x)|x⟩
where f(t) = 1 for the target and f(x) = 0 for all other states. This doesn't change the probabilities (|amplitude|² is the same), but the relative phase is crucial for the next step.
The diffusion operator D inverts all amplitudes about their average value:
D = 2|ψ⟩⟨ψ| - I
where |ψ⟩ is the uniform superposition. Geometrically, this reflects the state vector about the average amplitude. States below average get boosted, states above average get suppressed. The phase-flipped target is below average, so it gets amplified!
Each Grover iteration applies O followed by D. The combination acts like a rotation in a 2D subspace spanned by the target state and the uniform superposition of non-target states. The rotation angle is approximately 2θ where sin²θ = 1/N. After k iterations, the amplitude of the target grows like sin((2k+1)θ), reaching maximum at:
koptimal ≈ (π/4)√N
At this point, measuring the state yields the target with probability close to 1.
The top panel shows the amplitude (real part) of each computational basis state. The target state is highlighted in orange. Initially, all amplitudes are equal at 1/√N. With each Grover iteration, the target amplitude grows while others shrink. The amplitudes oscillate—after the optimal number of iterations, they start decreasing again (overshooting).
The bottom panel plots the probability of measuring the target state versus iteration number. The curve shows a sinusoidal growth reaching a peak near √N iterations. The classical baseline (1/N) is shown for comparison. This visualizes the quadratic speedup: quantum needs ~√N steps, classical needs ~N steps.
Optimal Iterations: Start with 3 qubits (N=8). Reset and step through the algorithm. The optimal iteration count is shown. Notice that the target probability peaks and then starts decreasing if you overshoot.
Scaling: Increase to 4 qubits (N=16). The optimal iterations increase from ~2 to ~3. At 5 qubits (N=32), it's ~4. This is the √N scaling in action—doubling N increases iterations by only √2 ≈ 1.4x.
Amplitude Interference: Watch the bar chart carefully. Non-target amplitudes all decrease together (constructive interference), while the target amplitude increases. This is quantum parallelism—all states evolve simultaneously.
Success Probability: After optimal iterations, click "Measure State" multiple times (resetting between measurements). You'll almost always get the target. Classical random guessing would only succeed 1/N of the time.
Different Targets: Change the target slider or click "Random Target". Run the algorithm. Notice that the number of iterations needed is independent of which state is marked—only depends on N. This is true unstructured search.
Auto Run: Click "Auto Run" to animate the full algorithm. Watch the probability curve trace out its characteristic sinusoidal shape, peaking at the optimal point.
Overshooting: Continue stepping past the optimal iterations. The target probability decreases! The algorithm is periodic—you can rotate all the way back to the initial state. In practice, you measure at the optimal time.
Grover's algorithm is fundamental to quantum computing for several reasons:
While not exponential like Shor's algorithm, Grover's quadratic speedup applies to a broader class of problems. Any problem where you need to find a solution by checking possibilities can potentially benefit from Grover's algorithm on a quantum computer.
The Grover iteration G = D · O can be understood geometrically as a rotation in a two-dimensional subspace:
The initial state is |s⟩ = √(1-1/N)|s'⟩ + √(1/N)|t⟩. Each Grover iteration rotates this state by angle 2θ toward |t⟩, where sin(θ) = 1/√N. After k iterations, the overlap with |t⟩ is sin((2k+1)θ), which reaches maximum when (2k+1)θ ≈ π/2, giving k ≈ (π/4)√N.
The oracle and diffusion operators are both reflections. Two reflections compose to give a rotation—this is the geometric heart of Grover's algorithm. The quantum computer exploits superposition to perform this multi-dimensional rotation efficiently, something classical computers cannot do.