Grover's Algorithm

Grover's algorithm finds a marked item in an unsorted database of N entries in about √N steps — a quadratic speedup over any classical search.

Speedup

quadratic — O(√N) vs O(N)

Primitives

oracle + diffusion

Optimal?

provably optimal for unstructured search

What it does

Grover amplifies the amplitude of the solution state. Start in a uniform superposition (a layer of Hadamards), then repeat ~(π/4)√N times: apply an oracle that flips the phase of the marked state, then the diffusion operator that reflects all amplitudes about their mean. Each iteration rotates the state vector toward the answer.

Circuit sketch

Steps

• Uniform superposition over all N = 2ⁿ states (Hadamards).
• Oracle marks the solution by flipping its phase.
• Diffusion reflects amplitudes about the mean, growing the marked amplitude.
• Repeat ~(π/4)√N times, then measure.

Where it's used

Unstructured search, and as a subroutine inside optimization, SAT solving, and mean/median estimation. The quadratic speedup is modest but very general.

In code (Qiskit)

from qiskit import QuantumCircuit
# 3-qubit Grover skeleton
qc = QuantumCircuit(3)
qc.h(range(3))          # uniform superposition
# ... oracle (phase-flip marked state) ...
# ... diffusion operator ...
qc.measure_all()