A quantum search algorithm achieving quadratic speedup — searching N items in O(√N) steps instead of classical O(N). Visualize amplitude amplification in real time.
Apply Hadamard gates to all qubits, creating an equal superposition of all N database states. Each state gets amplitude 1/√N.
The oracle marks the target state by flipping its amplitude from positive to negative — a phase kickback that encodes the solution.
The Grover diffusion operator reflects amplitudes about the mean, amplifying the target and suppressing others. Repeat √N times.
Simplified quantum circuit for 3-qubit Grover's algorithm. H = Hadamard gate, O = Oracle, D = Grover Diffusion operator.
Linear scan checks each item one by one. On average, finds the target in N/2 checks. Worst case: N checks.
Amplitude amplification concentrates probability into the target state after just O(√N) oracle calls.
| N (Database Size) | Qubits (n) | Classical (avg N/2) | Quantum (≈ π/4 · √N) | Speedup |
|---|
Grover's iteration is a rotation of angle 2θ in a 2D subspace spanned by |target⟩ and |uniform⟩. After k = π/(4θ) iterations, we reach near-certainty.
The target amplitude grows sinusoidally. The optimal iteration count is ⌊π√N / 4⌋ which maximises the probability of measuring the target state.
Lower-bound proofs confirm no quantum algorithm can solve unstructured search in fewer than O(√N) oracle queries.
With k solutions, optimal iterations drop to ≈ π√(N/k)/4, offering even greater speedup.
Powers attacks on symmetric crypto, SAT solving, constraint satisfaction, and database search.
Lov Grover published the algorithm at Bell Labs in 1996 — a landmark in quantum computation.