Grover's Algorithm Explained with Python Code

The Search Problem

Imagine you have an unsorted database of N items and you need to find a specific one. Classically, the best you can do is check items one at a time, which takes N/2 checks on average and N checks in the worst case. Grover's algorithm, published by Lov Grover in 1996, solves the same problem in roughly √N steps. For a database of one million items, that comes to about 800 quantum iterations instead of 500,000 classical checks.

This quadratic speedup looks modest beside the exponential speedup Shor's algorithm offers for factoring. What makes Grover's interesting is its generality. It applies to any problem you can frame as searching for an input that satisfies a condition, which covers optimization, constraint satisfaction and NP-complete problems.

The comparison deserves one caveat. Grover gives a quadratic speedup over brute-force search, and serious classical solvers rarely use brute force. A SAT solver with good heuristics already beats exhaustive search by an enormous margin, so the honest benchmark is Grover against the best classical method for your problem rather than against checking every possibility in turn.

How It Works

Grover's algorithm repeats two operations: the oracle and the diffusion operator.

The oracle marks the target item by flipping the sign of its amplitude. If you are searching for item |w⟩ in a superposition of all items, the oracle makes the amplitude of |w⟩ negative and leaves every other amplitude exactly as it was.

The diffusion operator then performs an inversion about the mean: it computes the average of all amplitudes and reflects each amplitude about that average. Getting the sequence right matters here, because the oracle changed the mean. One amplitude has gone negative, so the average drops below where it started. Every unmarked amplitude now sits slightly above that lower average and the reflection nudges it down. The marked amplitude sits far below the average, so the same reflection throws it a long way up.

Repeat the pair and the marked amplitude climbs toward 1. How many times you repeat it is the parameter most implementations get wrong, and the code below comes back to it.

Implementation in Qiskit

Let's implement Grover's algorithm to search for the state |11⟩ among four possible states (|00⟩, |01⟩, |10⟩, |11⟩):

from qiskit import QuantumCircuit, transpile
from qiskit_aer import AerSimulator

SHOTS = 4096


def grovers_algorithm():
    qc = QuantumCircuit(2, 2)

    # Step 1: Initialize superposition
    qc.h([0, 1])

    # Step 2: Oracle. CZ flips the phase of |11>
    qc.cz(0, 1)

    # Step 3: Diffusion operator. Z on both qubits followed by CZ gives
    # diag(1, -1, -1, -1), the reflection about |00>. The H layers move
    # that reflection to the uniform superposition.
    qc.h([0, 1])
    qc.z([0, 1])
    qc.cz(0, 1)
    qc.h([0, 1])

    # For N=4, one iteration is enough
    qc.measure([0, 1], [0, 1])
    return qc


simulator = AerSimulator()
qc = grovers_algorithm()
counts = simulator.run(transpile(qc, simulator), shots=SHOTS).result().get_counts()

print(f"Results: {counts}")
assert max(counts, key=counts.get) == "11"
assert counts["11"] == SHOTS   # exact here, not merely likely

Running it prints:

Results: {'11': 4096}

Every shot lands on the target. For N = 4 a single iteration rotates the state exactly onto |11⟩, so the algorithm finds it with probability 1 rather than high probability. Treat this as the special case it is. For larger N the success probability oscillates, and the iteration count has to be chosen with care.

Scaling Up

For practical problems, the oracle is the challenging part. The textbook version assumes a black-box oracle, but in practice you build a circuit that recognises the target. For structured problems such as SAT solving, the oracle implements the constraint-checking function reversibly using ancilla qubits.

Here is a general implementation, searching for any target over any number of qubits:

import math


def optimal_iterations(n_qubits: int) -> int:
    """floor(pi/4 * sqrt(N)). Use floor here, never round."""
    return math.floor(math.pi / 4 * math.sqrt(2 ** n_qubits))


def grovers_search(target: str):
    n = len(target)
    zeros = [q for q in range(n) if target[n - 1 - q] == "0"]
    qc = QuantumCircuit(n, n)

    # Initialize superposition
    qc.h(range(n))

    for _ in range(optimal_iterations(n)):
        # Oracle: flip the phase of the target state
        if zeros:
            qc.x(zeros)
        qc.h(n - 1)
        qc.mcx(list(range(n - 1)), n - 1)   # Multi-controlled X
        qc.h(n - 1)
        if zeros:
            qc.x(zeros)

        # Diffusion operator. The outer H and X layers cover every qubit.
        # The two H gates around the MCX cover the last qubit only, because
        # their job is to turn the multi-controlled X into a controlled Z.
        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))

    qc.measure(range(n), range(n))
    return qc


counts = simulator.run(transpile(grovers_search("101"), simulator),
                       shots=SHOTS).result().get_counts()

print(f"Results: {counts}")
print(f"Found '101' in {counts['101'] / SHOTS:.2%} of shots")
assert max(counts, key=counts.get) == "101"

Running it prints:

Results: {'000': 41, '001': 35, '010': 39, '011': 27, '100': 40, '101': 3840, '110': 45, '111': 29}
Found '101' in 93.75% of shots

Theory predicts 94.53% for three qubits at two iterations, and the run lands within sampling error of it. Notice that the other seven outcomes still appear. Grover gives you a high probability rather than a guarantee, so production use measures, checks the result against the oracle condition, and runs again when the check fails.

One detail in that diffuser catches people out. It looks like the Hadamards should sit on every qubit for symmetry. Make that change and the algorithm stops working entirely: all eight outcomes come back at 1/8, exactly as if you had guessed at random. The inner Hadamards belong on a single qubit because they convert a controlled X into a controlled Z.

Choosing the Iteration Count

Amplitude amplification is a rotation. Each iteration turns the state a fixed angle toward the target, and once past the optimum it keeps turning and moves away again. Running more iterations eventually makes the answer worse.

The correct count is the floor of π/4 × √N. Rounding instead looks harmless and quietly costs accuracy. At two qubits, π/4 × √4 is 1.571, so rounding gives two iterations and a 25% success rate where flooring gives one iteration and certainty. At three qubits both give 2, which is how the mistake survives the example everyone writes first. At seven and eight qubits they diverge again, with rounding costing roughly a percentage point of success probability each time.

Practical Significance

Grover's algorithm provides a provably optimal quantum speedup for unstructured search. No quantum algorithm can do better than O(√N) for this problem, a lower bound proved by Bennett, Bernstein, Brassard and Vazirani. That result describes the limits of quantum computing as much as its power, since it rules out an exponential speedup for search.

The algorithm also serves as a subroutine in more complex work. Amplitude amplification, the generalization of Grover's technique, appears in quantum counting, quantum minimum finding, quantum walks and several quantum optimization algorithms. Most algorithms you meet later assume you already know this rotation.

One caution before reaching for it. Grover assumes an oracle that recognises the target, and building that oracle as a reversible circuit costs gates that count toward the total. Searching stored data also requires loading that data into quantum memory, which remains an unsolved engineering problem. The √N scaling is real; the constant factors are where the difficulty lives.

Run the Code

Every snippet here lives in the Towards Quantum studies repository, pinned to the package versions it was tested against, alongside a test suite that checks the diffuser against the reflection operator it is supposed to equal.

git clone https://github.com/TowardsQuantum/studies
cd studies/grovers-algorithm-explained
pip install -r requirements.txt
python grover.py
pytest test_grover.py -v

github.com/TowardsQuantum/studies. Issues and corrections are welcome.