algorithms intermediate · 24 min read · April 22, 2026

Grover's Search and Amplitude Amplification

Grover's algorithm finds a marked element in an unstructured list of N items with O(√N) queries — a provable quadratic speedup. This tutorial derives the algorithm geometrically as a rotation in a 2D subspace, gives the exact optimal iteration count, and shows how amplitude amplification generalizes the trick far beyond search.

Prerequisites: Tutorial 9: Bernstein-Vazirani and Simon

Deutsch-Jozsa and Simon solved problems with a very specific algebraic structure. Grover’s algorithm solves a problem with no structure — and still beats classical algorithms. Given an unsorted list of $N$ items and a black-box test that recognizes the right one, Grover finds it in $O(\sqrt{N})$ queries. Classical algorithms need $\Theta(N)$ in the worst case.

The speedup is “only” quadratic — not exponential like Shor — but it’s universally applicable. Any NP search problem whose verifier runs in polynomial time gets a quadratic quantum speedup. That includes SAT, graph coloring, hash preimage finding, and a long list of cryptographic primitives. Grover is the quantum algorithm that affects the broadest variety of real problems.

The problem

You have a function $f: \{0, 1\}^n \to \{0, 1\}$ accessed as an oracle. There are $k$ “marked” inputs — those with $f(x) = 1$ — among $N = 2^n$ total. Your job: find any marked input.

Classical bound. To have a constant probability of success, you need $\Theta(N/k)$ queries. In the single-solution worst case ($k = 1$), that’s $\Theta(N)$.

Quantum bound. $\Theta(\sqrt{N/k})$ queries. For $k = 1$: $\sim \tfrac{\pi}{4}\sqrt{N}$.

The oracle

Same reversible oracle as before:

$$U_f\,|x\rangle|y\rangle = |x\rangle|y \oplus f(x)\rangle.$$

With phase kickback (target in $|-\rangle$), this becomes a phase oracle:

$$O\,|x\rangle = (-1)^{f(x)}|x\rangle = \begin{cases}-|x\rangle & x \text{ is marked} \\ +|x\rangle & x \text{ is unmarked}\end{cases}$$

The setup

Prepare the uniform superposition:

$$|\psi\rangle = H^{\otimes n}|0^n\rangle = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}|x\rangle.$$

Every basis state has amplitude $1/\sqrt{N}$. If you measured now, each marked state would show up with probability $1/N$ — pointless.

Grover’s trick: amplify the amplitudes of marked states and suppress the others, by repeatedly applying a two-step “Grover iteration” that rotates the state vector toward the marked subspace.

The geometric picture

Split the state space into two orthogonal subspaces:

• $|B\rangle = \frac{1}{\sqrt{k}}\sum_{x \in M}|x\rangle$ — uniform superposition over marked (“good”) states, where $M$ is the set of marked inputs.
• $|A\rangle = \frac{1}{\sqrt{N-k}}\sum_{x \notin M}|x\rangle$ — uniform superposition over unmarked (“bad”) states.

The initial state is:

$$|\psi\rangle = \sqrt{\tfrac{k}{N}}\,|B\rangle + \sqrt{\tfrac{N-k}{N}}\,|A\rangle.$$

Define $\sin\theta = \sqrt{k/N}$. Then $|\psi\rangle = \sin\theta|B\rangle + \cos\theta|A\rangle$ — a point on a 2D plane at angle $\theta$ from the $|A\rangle$ axis.

Key realization: everything Grover does stays in this 2D plane. The whole $2^n$-dimensional Hilbert space is irrelevant; only the angle matters.

The Grover iteration

Each iteration consists of two reflections:

Step 1: Oracle reflection. The phase oracle $O$ flips the sign of marked states. In the 2D picture, this is a reflection across the $|A\rangle$ axis:

$$O\,(\alpha|B\rangle + \beta|A\rangle) = -\alpha|B\rangle + \beta|A\rangle.$$

Step 2: Diffuser (reflection about the uniform superposition). Define $D = 2|\psi\rangle\langle\psi| - I$. This reflects any state across the $|\psi\rangle$ axis.

The product $G = DO$ is a rotation by angle $2\theta$ in the 2D plane. Two reflections = one rotation.

After $t$ iterations, the state is at angle $(2t+1)\theta$ from $|A\rangle$. When this angle reaches $\pi/2$, the state is at $|B\rangle$ and a measurement gives a marked element with probability 1.

Solve: $(2t+1)\theta \approx \pi/2$, so

$$t_{\text{opt}} \approx \tfrac{\pi}{4\theta} - \tfrac{1}{2} \approx \tfrac{\pi}{4}\sqrt{N/k}\quad (\text{for small } \theta = \sqrt{k/N}).$$

For $k = 1$, $N = 16$: $t_\text{opt} \approx \pi/4 \cdot 4 = \pi \approx 3.14$ → use 3 iterations.

Implementing the diffuser

The diffuser $D = 2|\psi\rangle\langle\psi| - I$ can be decomposed as:

$$D = H^{\otimes n}\,(2|0^n\rangle\langle 0^n| - I)\,H^{\otimes n}.$$

The middle operator “reflect about $|0^n\rangle$” is implemented as: flip all qubits (X gates) so that $|0^n\rangle$ becomes $|1^n\rangle$; apply a multi-controlled Z (which flips the sign only of $|1^n\rangle$); flip back. Concretely:

def grover_diffuser(n: int) -> QuantumCircuit:
    qc = QuantumCircuit(n, name="diffuser")
    qc.h(range(n))
    qc.x(range(n))
    # Multi-controlled Z via H-CCZ-H pattern
    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

Full Grover circuit

import numpy as np
from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

def phase_oracle(n: int, marked: list[int]) -> QuantumCircuit:
    """Phase oracle that flips the sign of every `x` in `marked`."""
    qc = QuantumCircuit(n, name="oracle")
    for x in marked:
        bits = format(x, f"0{n}b")
        # Flip zeros so the marked state becomes |11...1⟩
        for i, b in enumerate(reversed(bits)):
            if b == "0":
                qc.x(i)
        qc.h(n - 1)
        qc.mcx(list(range(n - 1)), n - 1)
        qc.h(n - 1)
        for i, b in enumerate(reversed(bits)):
            if b == "0":
                qc.x(i)
    return qc

def grover(n: int, marked: list[int], iterations: int | None = None) -> QuantumCircuit:
    N = 2**n
    k = len(marked)
    if iterations is None:
        theta = np.arcsin(np.sqrt(k / N))
        iterations = max(1, round((np.pi / (4 * theta)) - 0.5))

    qc = QuantumCircuit(n, n)
    qc.h(range(n))                                     # uniform superposition
    for _ in range(iterations):
        qc.compose(phase_oracle(n, marked), inplace=True)
        qc.compose(grover_diffuser(n), inplace=True)
    qc.measure(range(n), range(n))
    return qc

# --- Run ---
n = 4
marked = [0b1011]          # find the state |1011⟩ = 11
qc = grover(n, marked)
counts = AerSimulator().run(qc, shots=2048).result().get_counts()
top = sorted(counts.items(), key=lambda kv: -kv[1])[:3]
for bits, count in top:
    print(f"|{bits}⟩ → {count} shots ({count/2048:.1%})")
# |1011⟩ → 1997 shots (97.5%)
# |0000⟩ → 7 shots (0.3%)
# ...

For $n = 4$, $k = 1$, optimal iterations = 3, success probability ≈ 96%. The remaining 4% is spread over the 15 unmarked states.

→ Try the 3-qubit Grover in the playground — select “Grover (3 qubits)” from the examples dropdown.

Multiple marked items

If $k > 1$, amplitude amplification still works; the optimal iteration count just scales differently:

# Find one of {|1011⟩, |0110⟩} among 16
marked = [0b1011, 0b0110]
qc = grover(n, marked)
counts = AerSimulator().run(qc, shots=4096).result().get_counts()
hits = counts.get(format(marked[0], f"0{n}b"), 0) + counts.get(format(marked[1], f"0{n}b"), 0)
print(f"Found a marked state in {hits/4096:.1%} of shots")
# Found a marked state in ~99% of shots

With $k = 2$, $\sin\theta = \sqrt{2/16} = 0.354$, $\theta = 0.361$. Optimal iterations: $(\pi/4)/\theta - 0.5 \approx 1.67$ → 2 iterations.

Amplitude amplification: the general pattern

Grover is a special case of a broader technique called amplitude amplification. The general setup:

• You have a quantum algorithm $\mathcal{A}$ that produces $\mathcal{A}|0\rangle = \sin\theta\,|B\rangle + \cos\theta\,|A\rangle$, where $|B\rangle$ is a “good” subspace and $|A\rangle$ is “bad.”
• You have an oracle $P_B$ that reflects about $|B\rangle$ (flips the sign of good states).
• You want to amplify the good-state amplitude from $\sin\theta$ to near 1.

The recipe is exactly Grover’s: repeatedly apply $Q = -\mathcal{A}(2|0\rangle\langle 0| - I)\mathcal{A}^\dagger P_B$, which is a rotation by $2\theta$ in the same 2D plane. After $\sim \pi/(4\theta)$ iterations, the good-state amplitude is near 1.

Why this matters in practice: any classical Monte Carlo algorithm with success probability $p$ becomes a quantum algorithm with success probability near 1 after $O(1/\sqrt{p})$ repetitions — a quadratic speedup, for free. This shows up in:

• SAT solving: quadratic speedup over backtracking
• Hash preimage search: SHA-256 preimage in $2^{128}$ instead of $2^{256}$, forcing post-quantum protocol design
• Machine learning: quadratic speedup for Monte-Carlo-style estimators
• Optimization: quantum minimum finding in $O(\sqrt{N})$

Exercises

1. Iteration-count intuition

For $N = 100$ and $k = 1$, how many Grover iterations are optimal? What’s the success probability after that many iterations?

Show answer

$\sin\theta = 1/10$, $\theta \approx 0.1002$ rad. Optimal iterations: $(\pi/(4 \cdot 0.1002)) - 0.5 \approx 7.34$ → round to 7. After 7 iterations, the angle from $|A\rangle$ is $(2 \cdot 7 + 1) \cdot 0.1002 = 15 \cdot 0.1002 = 1.503$ rad, so $\sin(1.503)^2 \approx 0.996$ → 99.6% success.

2. Over-iterating

Implement a 4-qubit Grover search for a single marked state and measure the success probability as a function of iteration count from 0 to 10. Verify you see the rotation pattern predicted by the geometric picture.

Show expected shape

For $N = 16$, $k = 1$, $\theta = \arcsin(1/4) \approx 0.2527$. Success probability at iteration $t$: $\sin^2((2t+1)\theta)$.

• t=0: 6.25% (sanity check — 1/16 = baseline)
• t=1: 47.3%
• t=2: 90.9%
• t=3: 96.1% (peak)
• t=4: 58.0% (over-rotated past the target)
• t=5: 11.2%
• t=6: 0.3% (almost back to $|A\rangle$)

3. Grover as hash preimage attack

Given a hash function $h: \{0,1\}^{16} \to \{0,1\}^{16}$ and a target digest $d$, how many Grover iterations do you need to find a preimage $x$ with $h(x) = d$, assuming 1 preimage exists? How does this scale to SHA-256?

Show answer

For 16-bit preimage: $N = 2^{16}$, $k = 1$, iterations $\approx \tfrac{\pi}{4}\sqrt{N} \approx 201$. For SHA-256 preimage: $N = 2^{256}$, iterations $\approx 2^{127}$ — still astronomical, but “only” the square root of $2^{256}$. This is the reason NIST recommends 256-bit hashes for post-quantum security: to retain 128-bit effective security against Grover attacks.

4. Amplitude amplification beyond search

Suppose you have a classical algorithm that samples a value from a distribution and returns “success” with probability $p = 0.01$. How many Grover-style amplifications turn this into a near-certain success, assuming you can run the algorithm reversibly as a quantum subroutine?

Show answer

$\sin\theta = \sqrt{0.01} = 0.1$, $\theta \approx 0.1$ rad. Optimal iterations: $\pi/(4 \cdot 0.1) - 0.5 \approx 7.4$ → 7 iterations. Classical would need $\sim 100$ tries for the same confidence. The quadratic $\sqrt{100} \approx 10$ vs actual 7 matches theory.

What you should take away

• Grover finds a marked element in $O(\sqrt{N/k})$ queries. Classical unstructured search is $\Theta(N/k)$. The quadratic speedup is optimal — you cannot do better on unstructured problems.
• Geometric picture: Grover lives in a 2D plane, rotates by $2\theta$ per iteration, hits $|B\rangle$ after $\sim \pi/(4\theta)$ iterations.
• The diffuser is a Hadamard-sandwiched multi-controlled-Z. Same structure for every $n$.
• Amplitude amplification generalizes Grover: any quantum algorithm with success probability $p$ gets amplified to near-1 in $O(1/\sqrt{p})$ iterations.
• Implications for crypto: forces 256-bit hashes and $\geq 256$-bit symmetric keys for post-quantum security. Doesn’t threaten public-key crypto — that’s Shor’s territory.

Next: Quantum Fourier Transform and Phase Estimation. The last two primitives you need before we tackle Shor.

---

Weekly dispatch

Quantum, for people who already code.

One serious tutorial per week, plus the industry moves that actually matter. No hype, no hand-waving.

Email Subscribe

Free. Unsubscribe anytime. We will never sell your email.