Grover search

April 1, 2025

Grover’s algorithm finds a marked item in an unstructured database of size $N$ using $O(\sqrt{N})$ oracle queries, classically $O(N)$ in the worst case.

It is an oracle-based algorithm: you assume access to a black-box function that can recognize solutions, and you use quantum interference to amplify their probability.

Problem setup (oracle model)

You are given an oracle for a Boolean function $f(x)$ over $N=2^n$ inputs:

$f(x)=1$ for “good/marked” solutions
$f(x)=0$ otherwise

In the phase-oracle form, the oracle is a unitary $U_f$ that acts as:

U_f\lvert x\rangle = (-1)^{f(x)}\lvert x\rangle.

So marked states get a phase flip (a minus sign), while all other basis states stay unchanged.

If the word “oracle” feels mysterious, read What is an oracle in Grover?.

Oracle and diffusion

You implement an oracle that flips the phase of “good” states, then apply a diffusion operator that reflects amplitudes about the average.

The diffusion operator is often written as:

D = 2\lvert s\rangle\langle s\rvert - I,

where $\lvert s\rangle$ is the uniform superposition:

\lvert s\rangle = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}\lvert x\rangle.

The Grover iterate and iteration count

One Grover iteration (the “Grover operator”) is:

G = D\,U_f.

If there are $M$ marked items, the optimal number of Grover iterations is approximately:

k \approx \left\lfloor \frac{\pi}{4}\sqrt{\frac{N}{M}} \right\rceil.

The exact iteration count depends on the number of marked items. Too many Grover iterations can overshoot the desired state.

Minimal example in Qiskit (2 qubits, mark $\lvert 11\rangle$ )

Below is a tiny end-to-end circuit that searches among $N=4$ states and marks $\lvert 11\rangle$ . For $N=4$ and $M=1$ , a single Grover iteration is enough.

from qiskit import QuantumCircuit
from qiskit.quantum_info import Statevector

def grover_oracle_mark_11(qc: QuantumCircuit):
    # Phase flip on |11> using CZ
    qc.cz(0, 1)

def diffusion_2q(qc: QuantumCircuit):
    # D = H⊗H · (2|00><00| - I) · H⊗H
    qc.h([0, 1])
    qc.x([0, 1])
    qc.h(1)
    qc.cx(0, 1)
    qc.h(1)
    qc.x([0, 1])
    qc.h([0, 1])

qc = QuantumCircuit(2)

# 1) Prepare |s>
qc.h([0, 1])

# 2) Oracle
grover_oracle_mark_11(qc)

# 3) Diffusion
diffusion_2q(qc)

sv = Statevector.from_instruction(qc)
print(sv.probabilities_dict())

You should see most probability mass concentrated on '11'.

This example uses an ideal statevector simulation. On real hardware, noise reduces the achievable amplification; you typically repeat shots and use error mitigation strategies.

What Grover is really doing (geometric picture)

Grover iterations rotate the state in the 2D subspace spanned by:

$\lvert w\rangle$ : the uniform superposition over marked states
$\lvert w_\perp\rangle$ : the uniform superposition over unmarked states

Each iteration rotates the state closer to $\lvert w\rangle$ , increasing the chance of measuring a marked item.

Exercises

Modify the oracle to mark $\lvert 00\rangle$ instead of $\lvert 11\rangle$ . (Hint: use X gates to map the target state to $\lvert 11\rangle$ , apply the same phase flip, then undo the X gates.)
Try marking two states (so $M=2$ ) and observe how the “best” iteration count changes.

Learn the general technique behind Grover: Amplitude amplification.

Then continue to Shor’s algorithm.

Shor's algorithm