Grover's Algorithm

Definition

Grover's algorithm, discovered by Lov Grover in 1996, solves the unstructured search problem: given an oracle that recognises a marked state among $N$ unsorted items, find the marked state using $O(\sqrt{N})$ oracle queries. Classically, this requires $O(N)$ queries in the worst case. Grover's algorithm is provably optimal — no quantum algorithm can beat $O(\sqrt{N})$ for unstructured search (Bennett et al., 1997).

The algorithm works by amplitude amplification: it iteratively flips the sign of the marked state's amplitude (via the oracle) and then inverts the amplitudes about the mean (via the Grover diffusion operator), causing the marked state's probability to grow quadratically faster than random chance.

Algorithm Outline

Setup

Let $N = 2^n$ be the number of items, and define:

Oracle $O$ : A unitary that marks the target state $\ket{\omega}$ :

$\displaystyle O \ket{x} = \begin{cases} -\ket{x} & \text{if } x = \omega \\ \ket{x} & \text{otherwise} \end{cases}$

Implemented as a phase-flip on the target — often constructed from a classical Boolean function $f(x)$ that returns 1 for the target and 0 otherwise.
Diffusion operator $D$ :

$\displaystyle D = 2\ket{\psi}\bra{\psi} - I$

where $\ket{\psi} = H^{\otimes n} \ket{0}^{\otimes n}$ (the uniform superposition). $D$ inverts amplitudes about the mean.

Steps

Initialise: Apply Hadamard gates to all $n$ qubits:

$\displaystyle \ket{\psi_0} = H^{\otimes n} \ket{0}^{\otimes n} = \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} \ket{x}$
Grover iteration (repeat $\approx \frac{\pi}{4}\sqrt{N}$ times):
1. Apply oracle $O$ (flip sign of target amplitude).
2. Apply diffusion operator $D$ (invert about the mean).
Measure all qubits. The outcome is $\omega$ with high probability ( $> 1/2$ for optimal iteration count).

Iteration Count and Success Probability

The optimal number of iterations is:

$\displaystyle R = \left\lfloor \frac{\pi}{4} \sqrt{\frac{N}{M}} \right\rceil$

where $M$ is the number of marked items. After $R$ iterations, the success probability is $\sin^2((2R+1)\theta)$ where $\theta = \arcsin(\sqrt{M/N})$ .

$N$	$\sqrt{N}$	Iterations $R$	Success probability
4	2	1	100%
100	10	8	~95%
10,000	100	79	~99%
$10^6$	1,000	785	~100%

Circuit Diagram

|0⟩ — H —●———H─────────●———H──●——— ⋯ — M
|0⟩ — H —●———H─────────●———H──●——— ⋯ — M
|0⟩ — H —●———H─────────●———H──●——— ⋯ — M
         │         │         │
         │    ┌────┴────┐    │    ─
         │    │Diffusion│    │    ⋮
         │    └─────────┘    │
        Oracle            Oracle

Applications

Beyond database search, Grover's algorithm provides quadratic speedups for any problem reducible to unstructured search:

Application	Classical complexity	Quantum complexity	Speedup factor (at $N=10^6$ )
Unstructured search	$O(N)$	$O(\sqrt{N})$	×1,000
SAT (Boolean satisfiability)	$O(2^n)$	$O(2^{n/2})$	×32,768 (at $n=30$ )
Collision finding (hash functions)	$O(2^{n/2})$	$O(2^{n/3})$	×32,768 (at $n=60$ )
Graph connectivity	$O(N + E)$	$O(\sqrt{NE})$	×1,000 (at $N=10^6$ )
Minimum finding	$O(N)$	$O(\sqrt{N})$	×1,000
Mean/median estimation	$O(N)$	$O(\sqrt{N})$	×1,000

Grover's Algorithm and Cryptography

Grover's algorithm halves the effective key length of symmetric ciphers:

Symmetric cipher	Key length	Effective security against Grover	Required post-Grover key length
AES-128	128 bits	64 bits	AES-256
AES-256	256 bits	128 bits	AES-256 (already sufficient)
SHA-256 (collision)	256-bit output	85 bits (Grover + Brassard)	SHA-512

Important caveat: Grover's algorithm requires a serial quantum circuit — each iteration depends on the previous one. Running $2^{64}$ iterations for AES-128 on a single quantum processor would take an impractically long time. Parallelising Grover across many quantum processors reduces runtime but increases total physical qubit requirements by the parallelisation factor. Most estimates place the quantum resource needed to break AES-128 well beyond any plausible near-term hardware.

Amplitude Amplification (Generalised Grover)

Grover's algorithm is a special case of amplitude amplification — a framework that amplifies the amplitude of any "good" subspace. Given a unitary $A$ that prepares an initial state $\ket{\psi} = A\ket{0}$ with probability $p$ of the good subspace, amplitude amplification finds a good state with $O(1/\sqrt{p})$ iterations.

This generalisation underpins:

Quantum counting: Estimate the number of solutions $M$ without enumerating them (uses quantum phase estimation + Grover iterations).
Quantum Monte Carlo: Quadratic speedup for estimating expectation values of random variables — $O(1/\epsilon)$ classical vs. $O(1/\epsilon)$ quantum.
Quantum optimisation: QAOA (Quantum Approximate Optimisation Algorithm) can be viewed as a continuous-time analogue of amplitude amplification.

Hardware Requirements

Grover's algorithm is shallower than Shor's — it requires roughly $O(\sqrt{N})$ sequential operations. For $N = 10^{12}$ (40 qubits), that is ~ $10^6$ sequential gates. Current NISQ devices with $\sim 10^{-3}$ per-gate error would produce essentially random results at this depth. Grover's algorithm therefore requires fault-tolerant qubits (error-corrected logical qubits) to reach useful problem sizes.

Resources and References

Grover, "A fast quantum mechanical algorithm for database search" (1996), STOC 1996, 212–219. [Original paper]
Bennett et al., "Strengths and weaknesses of quantum computing" (1997), SIAM J. Comput. 26, 1510–1523. [Optimality proof]
Brassard et al., "Quantum amplitude amplification and estimation" (2002), Quantum Computation and Quantum Information, 160–176.
Boyer et al., "Tight bounds on quantum searching" (1998), Fortschritte der Physik 46, 493–505.
Quantum circuit implementations: qiskit.org/textbook/ch-algorithms/grover.html — Qiskit textbook implementation.