Grover's Search Algorithm

What You'll Learn: How a quantum computer can search an unstructured database of N items in just sqrt(N) steps — a quadratic speedup that is provably optimal.

Level: Intermediate | Time: 20 minutes | Qubits: 2 | Framework: Qiskit

Prerequisites

• Deutsch-Jozsa — Understanding oracle-based quantum algorithms and the Hadamard transform on multiple qubits

The Idea

Imagine you have a phonebook with 1,000,000 names but no alphabetical order. Classically, the only way to find a specific name is to check each entry one by one — on average, that takes 500,000 lookups.

Grover's algorithm is like asking the phonebook itself to glow on the right page. You prepare all pages in superposition (checked simultaneously), mark the target with a "phase kick," then amplify that mark until it dominates the measurement. For a million entries, this takes about 785 queries instead of 500,000 — a quadratic speedup.

In our 2-qubit version the "phonebook" has 4 entries (|00>, |01>, |10>, |11>). One Grover iteration is enough to find the marked entry with 100% probability.

How It Works

The Circuit (marked_state = "11")

CODECopy
     ┌───┐ ░       ░ ┌───┐┌───┐     ┌───┐┌───┐ ░ ┌───┐
q_0: ┤ H ├─░──■────░─┤ H ├┤ X ├──■──┤ X ├┤ H ├─░─┤ M ├
     ├───┤ ░  │    ░ ├───┤├───┤  │  ├───┤├───┤ ░ ├───┤
q_1: ┤ H ├─░──■────░─┤ H ├┤ X ├──■──┤ X ├┤ H ├─░─┤ M ├
     └───┘ ░  CZ   ░ └───┘└───┘  CZ └───┘└───┘ ░ └───┘
          init   oracle              diffusion        meas

Step 1: Initialization — Uniform Superposition

PYTHONCopy
qc.h(0)  # |0> -> (|0> + |1>) / sqrt(2)
qc.h(1)  # |0> -> (|0> + |1>) / sqrt(2)

Hadamard gates on both qubits create a uniform superposition over all 4 basis states, each with amplitude 1/2:

State: (|00> + |01> + |10> + |11>) / 2

Every item in our "database" now has equal weight. This is the quantum version of opening every page at once.

Step 2: Oracle — Phase-Flip the Target

PYTHONCopy
# For marked_state = "11": CZ marks it directly
qc.cz(0, 1)  # |11> -> -|11>, all others unchanged

The oracle recognizes the marked state and flips its phase (amplitude sign). The CZ gate naturally applies a -1 phase when both qubits are |1>. For other targets, X gates temporarily transform the target into |11>:

State after oracle (target = "11"): (|00> + |01> + |10> - |11>) / 2

Notice: the marked state has a negative amplitude (-1/2) while all others remain positive (+1/2). The mean amplitude is now 1/4 instead of 1/2.

Step 3: Diffusion — Inversion About the Mean

PYTHONCopy
qc.h([0, 1])    # To Hadamard basis
qc.x([0, 1])    # Map |00> to |11>
qc.cz(0, 1)     # Phase-flip |11> (was |00> in H basis)
qc.x([0, 1])    # Unmap
qc.h([0, 1])    # Back to computational basis

The diffusion operator reflects every amplitude about the mean. Since the marked state has a negative amplitude pulling the mean down, reflection boosts the marked state and suppresses the rest:

• Unmarked amplitudes: +1/2 -> reflected about mean 1/4 -> 0
• Marked amplitude: -1/2 -> reflected about mean 1/4 -> +1

State after diffusion: |11> (with amplitude 1.0)

The marked state now has all the probability. Measurement is certain.

Step 4: Measurement

PYTHONCopy
qc.measure(0, 0)  # Measure qubit 0
qc.measure(1, 1)  # Measure qubit 1

The Math

State Evolution

Starting from |00> with marked state |w> = |11>:

1. After initialization (H on both):

   |psi_0> = H|0> x H|0> = (1/2) * sum over all x in {0,1}^2 of |x>

   Every computational basis state has amplitude 1/2.

2. After oracle O_w (flips phase of |w>):

   |psi_1> = O_w |psi_0> = (1/2)(|00> + |01> + |10> - |11>)

   The oracle is a diagonal unitary: O_w = I - 2|w><w|.

3. After diffusion D = 2|s><s| - I (where |s> = H^n |0>^n):

   |psi_2> = D |psi_1> = |11>

   In the 2-qubit case, a single iteration rotates the state exactly onto |w>.

The Diffusion Operator

The diffusion operator D = 2|s><s| - I has the matrix form (for 2 qubits):

CODECopy
D = (1/2) [ -1   1   1   1 ]
          [  1  -1   1   1 ]
          [  1   1  -1   1 ]
          [  1   1   1  -1 ]

Geometrically, it reflects the state vector about the uniform superposition |s>. This is the "inversion about the mean" — each amplitude a_i is transformed to 2*mean - a_i.

Optimal Number of Iterations

The number of Grover iterations for maximum success probability is:

k = floor(pi/4 * sqrt(N))

where N = 2^n is the database size.

Over-iterating reduces the probability — the state rotates past the target. This is a key difference from classical search where more iterations never hurt.

Expected Output

When searching for marked_state = "11" with 1024 shots:

On a perfect simulator, you should see 1024/1024 for the marked state. On real hardware, gate errors will cause some "leakage" to other states — the ratio of correct to incorrect measurements is a direct measure of fidelity.

Running the Circuit

PYTHONCopy
from circuit import run_circuit, verify_grover

# Search for a specific state
counts = run_circuit(marked_state="11", shots=1024)
print(counts)  # {'11': 1024}

# Search for a different target
counts = run_circuit(marked_state="01", shots=1024)
print(counts)  # {'01': 1024}

# Verify all four targets
result = verify_grover(shots=4096)
print(result["passed"])  # True
for check in result["checks"]:
    print(f"  {check['name']}: {check['detail']}")

Try It Yourself

1. Count the iterations: Modify the circuit to apply 2 Grover iterations instead of 1 on 2 qubits. What happens to the probability? (Hint: you should see worse results — you've rotated past the target.)

2. Multiple solutions: Modify the oracle to mark two states (e.g., both |01> and |10>). With 2 out of 4 items marked, how many iterations are optimal? (Hint: pi/4 * sqrt(N/M) where M is the number of solutions.)

3. Scale to 3 qubits: Extend the algorithm to 3 qubits (8 items). You'll need a multi-controlled Z gate for the oracle and 2 Grover iterations for the best probability.

4. Classical comparison: Write a classical random search for 4 items. How many queries does it take on average to find the target? Compare with Grover's single query.

What's Next

• Quantum Fourier Transform — The key subroutine in Shor's algorithm and many other quantum speedups
• Phase Estimation — Uses QFT to estimate eigenvalues, a building block for quantum chemistry and optimization

Applications

References

• Grover, L.K. (1996). "A fast quantum mechanical algorithm for database search." Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pp. 212-219. arXiv:quant-ph/9605043
• Bennett, C.H., Bernstein, E., Brassard, G., Vazirani, U. (1997). "Strengths and Weaknesses of Quantum Computing." arXiv:quant-ph/9701001 (Proves Grover's algorithm is optimal.)
• Nielsen, M.A. & Chuang, I.L. Quantum Computation and Quantum Information, Section 6.1 (Grover's algorithm), Section 6.1.4 (Optimality of Grover's algorithm).
• IBM Quantum Learning: Grover's Algorithm