Grover's algorithm is the second-most-famous quantum algorithm after Shor's, and it is by far the easier one to actually build. You can implement a working version in about forty lines of Qiskit and watch the marked state emerge from the noise floor.
It's also the algorithm most commonly misunderstood. This guide builds it step by step, shows the mistake that almost every beginner makes, and is honest about what the speedup does and does not buy you.
The Problem: Unstructured Search
You have N possibilities. Exactly one of them (or a few) satisfies some condition. You have no structure to exploit — no sorting, no index, no gradient, nothing that lets you rule out half the space with one look. Your only tool is a checker function: hand it a candidate, it tells you yes or no.
Classically, you have no choice but to try candidates one at a time. On average that's N/2 checks, and N in the worst case. Grover's algorithm finds the answer in roughly (π/4)√N checks. For N = 1,000,000 that's about 785 instead of 500,000.
The word unstructured is doing enormous work here. It does not mean "hard". It means "the only thing you can do is test candidates". If your problem has any exploitable structure — sorted data, a hash index, a metric that lets you prune — classical algorithms will use it and will crush Grover. The classic "search a database of N records" framing is genuinely misleading, and we'll come back to why.
The Core Idea: Amplitude Amplification
Start with every state equally likely. Then repeat two operations:
- The oracle flips the sign of the amplitude of the marked state, leaving everything else alone. Probabilities don't change — all amplitudes are still ±1/√N — but the marked one now points the other way.
- The diffusion operator reflects every amplitude about their mean. Since the marked amplitude is negative it sits far below the mean, so reflecting it sends it well above; every other amplitude drops slightly.
Each round is a rotation of the state vector toward the target by a fixed angle. That's the whole algorithm. The rotation angle is fixed, which is exactly why you can overshoot — more on that shortly.
Step 1: Uniform Superposition
Apply a Hadamard gate to every qubit. Three qubits give eight basis states each with amplitude 1/√8.
from qiskit import QuantumCircuit, transpile
from qiskit_aer import AerSimulator
import math
n = 3 # 3 qubits -> N = 8 states
marked = "101" # the state we want to find
qc = QuantumCircuit(n, n)
qc.h(range(n)) # uniform superposition
If you measure here you get a uniform random bitstring — 12.5% for each of the eight outcomes. That's the baseline to beat.
Step 2: The Oracle
The oracle must apply a phase of −1 to |101⟩ and +1 to everything else. The trick is a multi-controlled Z gate: it flips the sign of |111⟩ only. To mark a different pattern, sandwich it with X gates on the qubits that should be 0.
Qiskit has no mcz, so we build it the standard way — an H on the target, a multi-controlled X (Toffoli generalized), an H back:
def oracle(n, marked):
"""Phase-flip the marked basis state."""
qc = QuantumCircuit(n, name="Oracle")
rev = marked[::-1] # Qiskit is little-endian
for i, bit in enumerate(rev):
if bit == "0":
qc.x(i)
qc.h(n - 1) # multi-controlled Z
qc.mcx(list(range(n - 1)), n - 1)
qc.h(n - 1)
for i, bit in enumerate(rev):
if bit == "0":
qc.x(i)
return qc
Watch the endianness. Qiskit orders bitstrings with qubit 0 on the right, so marked[::-1] maps the string to qubit indices. Getting this backwards is the second most common bug in Grover implementations and it fails silently — you'll amplify 101 reversed and wonder why.
Step 3: The Diffusion Operator
Inversion about the mean is H⊗n, then X⊗n, then a multi-controlled Z, then X⊗n, then H⊗n. Structurally it's a reflection about the uniform superposition state:
def diffuser(n):
"""Inversion about the mean."""
qc = QuantumCircuit(n, name="Diffuser")
qc.h(range(n))
qc.x(range(n))
qc.h(n - 1)
qc.mcx(list(range(n - 1)), n - 1)
qc.h(n - 1)
qc.x(range(n))
qc.h(range(n))
return qc
Note the diffuser knows nothing about the marked state. It is the same circuit for every search problem — only the oracle changes.
Step 4: Iterate the Right Number of Times
This is where people go wrong. The optimal count is:
k = floor( (π/4) · √(N/M) )
where N = 2ⁿ and M is the number of marked states. For N = 8, M = 1: k = floor(2.22) = 2.
Here's the complete program:
def grover(n, marked, iterations):
qc = QuantumCircuit(n, n)
qc.h(range(n)) # uniform superposition
orc, dif = oracle(n, marked), diffuser(n)
for _ in range(iterations):
qc.compose(orc, inplace=True) # phase-flip the target
qc.compose(dif, inplace=True) # amplify it
qc.measure(range(n), range(n))
return qc
N = 2 ** n
optimal = math.floor(math.pi / 4 * math.sqrt(N))
print(f"N = {N}, optimal iterations = {optimal}")
sim = AerSimulator()
qc = grover(n, marked, optimal)
counts = sim.run(transpile(qc, sim), shots=4096).result().get_counts()
print(sorted(counts.items()))
Real output from this exact code (Qiskit 2.5, Aer 0.17):
N = 8, optimal iterations = 2
[('000', 35), ('001', 34), ('010', 33), ('011', 27),
('100', 33), ('101', 3866), ('110', 35), ('111', 33)]
94.4% on 101, versus 12.5% by chance. Two oracle calls where classical search would need 4.5 on average.
The Mistake: More Iterations Make It Worse
The intuition "more amplification is better" is wrong, and it's the single biggest trap in Grover's algorithm. Each iteration rotates the state by a fixed angle θ where sin(θ/2) = √(M/N). After the optimal number of rounds you're aligned with the target. Keep going and you rotate straight past it, back down toward the unmarked states — and eventually back to where you started. Success probability oscillates as sin²((2k+1)·θ/2).
Just loop the iteration count and watch. Measured counts over 4096 shots each:
iters=0 P(101)=0.127 <- uniform, no better than guessing
iters=1 P(101)=0.779
iters=2 P(101)=0.944 <- optimal
iters=3 P(101)=0.320 <- overshooting
iters=4 P(101)=0.013 <- worse than random guessing!
iters=5 P(101)=0.556
iters=6 P(101)=1.000 <- period brings it back around
iters=7 P(101)=0.586
Four iterations gives you a 1.3% success rate. You did twice the optimal work and ended up nine times worse than doing nothing at all. This is not noise or a bug — it is exactly what the math says should happen, and it's the reason you must compute k in advance rather than "running it a while".
The awkward corollary: computing k requires knowing M, the number of solutions. If you don't know how many marked states exist, you need quantum counting (an amplitude-estimation routine) first, or you use randomized iteration counts, which costs you a constant factor. Textbook presentations tend to skip this.
What the Speedup Actually Buys You
Be precise about this, because a lot of writing on Grover is not.
It is quadratic, not exponential. √N versus N. Shor's factoring algorithm is exponential — that's a categorically different thing. A quadratic speedup is real and provably optimal (no quantum algorithm can beat √N for unstructured search), but it is fragile: it can be eaten entirely by the constant-factor overhead of error correction, which is substantial.
It does not make NP-hard problems easy. You can apply Grover to brute-force SAT and go from 2ⁿ to 2^(n/2). That's a genuine improvement, and it is also still exponential. NP-hard problems remain NP-hard. Real SAT solvers use clause learning and structure that Grover, by definition, cannot exploit — which is why classical solvers routinely handle instances with millions of variables.
The "database search" framing is misleading. Grover needs an oracle — a circuit that recognizes the answer — not a stored database. If you actually had N records in memory, you would first need to load them into quantum superposition, which costs O(N) and destroys the speedup outright. Grover is useful when the marked item is defined by a computable property (this key decrypts the ciphertext, this input hashes to that digest) rather than looked up in a table.
The real applications: cryptanalysis (Grover halves the effective key length of symmetric ciphers, which is exactly why AES-256 is recommended over AES-128 for post-quantum security), and as a subroutine inside larger algorithms via amplitude amplification. Grover's original 1996 paper is worth reading directly — see our breakdown of the paper.
Running on Real Hardware
Moving to a QPU, the picture changes fast. Multi-controlled X gates are not native to any hardware — transpilation decomposes each one into a cascade of CNOTs and single-qubit rotations, and the cost grows steeply with the number of controls. A 4-qubit MCX can become 20+ two-qubit gates. Multiply that by two per Grover iteration, times k iterations, and depth explodes.
# Check what your circuit actually costs before submitting
qc = grover(3, "101", 2)
print(qc.decompose().count_ops())
On NISQ devices, two-qubit gate error sits around 0.5–1%. A few hundred entangling gates and your output is indistinguishable from uniform random. Published hardware demonstrations of Grover are almost all 2–3 qubits, and they are demonstrations, not useful computations. Add shot noise on top and you need enough samples to distinguish a modest peak from the floor.
The practical advice: develop and debug on simulators, where you can verify correctness exactly. Only move to real hardware when you understand what your circuit costs in native gates — and expect degraded results.
Next Steps
- Qiskit SDK guide — full setup, backends, and transpiler options
- QAOA tutorial — the other big near-term algorithm, applied to Max-Cut
- Compare the SDKs — the same Grover circuit in Cirq or PennyLane
- Glossary — superposition, quantum advantage, and the rest of the vocabulary