Grover’s Algorithm

A quantum search algorithm providing quadratic speedup for finding items in unsorted databases.

Grover’s algorithm (1996) searches an unsorted database of $N$ items in $O(\sqrt{N})$ queries, compared to $O(N)$ classically. It’s one of the foundational quantum algorithms.

The Problem

Given a function $f(x)$ that returns 1 for exactly one “marked” item and 0 otherwise, find the marked item.

• Classical: Check items one by one → $O(N)$ queries on average
• Quantum (Grover): $O(\sqrt{N})$ queries

The Algorithm

Grover’s algorithm repeatedly applies two operations:

1. Oracle $O$

Marks the solution by flipping its sign: $$O|x⟩=\{\begin{array}{ll}-|x⟩& \text{if }f(x)=1\\ |x⟩& \text{otherwise}\end{array}$$

2. Diffusion $D$

Reflects amplitudes about their average (amplitude amplification): $$D=2|s⟩⟨s|-I$$ where $|s⟩=H^{\otimes n}|0{⟩}^{\otimes n}$ is the uniform superposition.

The Circuit

|0⟩^n ── H^⊗n ──┬── O ── D ──┬── ... ── Measure
                │            │
            (repeat √N times)

Geometric Intuition

Think of the state as a vector in a 2D plane:

• One axis: the marked state $|w⟩$
• Other axis: superposition of unmarked states $|s^{\prime }⟩$

Each Grover iteration rotates the state vector toward $|w⟩$ by angle $\approx 2/\sqrt{N}$.

After $\approx \frac{\pi }{4}\sqrt{N}$ iterations, the state points at (or very close to) $|w⟩$.

Example: N = 4

• 4 items, need to find 1 marked item
• Classical: 2.25 queries on average
• Grover: ~1 iteration (plus setup)

Starting state: $\frac{1}{2}(|00⟩+|01⟩+|10⟩+|11⟩)$

If $|10⟩$ is marked:

1. Oracle: $\frac{1}{2}(|00⟩+|01⟩-|10⟩+|11⟩)$
2. Diffusion: $|10⟩$ (exactly the answer!)

Key Properties

Optimal

Grover’s algorithm is provably optimal. No quantum algorithm can do better than $O(\sqrt{N})$ for unstructured search.

Works with Multiple Solutions

If $k$ items are marked, the algorithm finds one in $O(\sqrt{N/k})$ queries.

Requires Knowing When to Stop

Over-iterating causes the amplitude to “rotate past” the solution. You need to know approximately how many iterations to run.

Applications

• Database search: Searching unsorted data
• Cryptography: Speed up brute-force attacks (effectively halving key lengths)
• Satisfiability: Search for satisfying assignments
• Amplitude amplification: Generalization used in many algorithms

Practical Considerations

Quadratic speedup is significant but not transformative:

• $10^{12}$ → $10^6$ queries (meaningful)
• But requires a quantum oracle for $f$, and building this can be expensive

See also: Quantum Algorithm, Quantum Speedup