Prerequisite: Quantum Computing

The Unstructured Search Problem

Suppose you have a function $f : {0,1}^n \to {0,1}$ that equals $1$ on exactly one input $x^\ast \in {0,1}^n$. You can evaluate $f$ by querying an oracle, but you have no structural information about it. Classically, the only strategy is to query inputs one by one; on a database of $N = 2^n$ items you need $\Theta(N)$ queries in the worst case, and $\Theta(N)$ on average.

Grover’s algorithm (1996) solves this in $O(\sqrt{N})$ oracle queries. This is a provably optimal quantum algorithm for the task: the polynomial method establishes an $\Omega(\sqrt{N})$ lower bound on quantum query complexity for unstructured search.

The Oracle

The quantum oracle encodes $f$ as a unitary. Two equivalent formulations are standard.

Bit-flip oracle. Acts on a query register and one ancilla qubit:

$$U_f |x\rangle|y\rangle = |x\rangle|y \oplus f(x)\rangle$$

Phase oracle. Obtained by setting the ancilla to $|{-}\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$ and tracing over it. For any $|x\rangle$:

$$\mathcal{O}|x\rangle = (-1)^{f(x)}|x\rangle$$

The phase oracle flips the sign of the target state $|x^\ast\rangle$ while leaving all others unchanged. In the rest of this post we work exclusively with the phase oracle $\mathcal{O}$.

Geometric Picture

Define two normalised states in the $2^n$-dimensional Hilbert space:

$$|s\rangle = H^{\otimes n}|0\rangle^{\otimes n} = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}|x\rangle, \qquad |t\rangle = |x^\ast\rangle$$

Let $|\bar{t}\rangle$ be the unit vector in the span of ${|s\rangle, |t\rangle}$ that is orthogonal to $|t\rangle$:

$$|\bar{t}\rangle = \frac{1}{\sqrt{N-1}}\sum_{x \neq x^\ast}|x\rangle$$

The initial state $|s\rangle$ lies in the plane spanned by $|t\rangle$ and $|\bar{t}\rangle$. Define the angle $\theta$ by:

$$\sin\theta = \langle t | s \rangle = \frac{1}{\sqrt{N}}$$

For large $N$, $\theta \approx 1/\sqrt{N}$ is a small positive angle. The state $|s\rangle$ can be written:

$$|s\rangle = \cos\theta,|\bar{t}\rangle + \sin\theta,|t\rangle$$

The Grover Iterate

The Grover iterate $G$ is the composition of two reflections:

$$G = \underbrace{(2|s\rangle\langle s| - I)}{\text{diffusion operator}} \cdot \underbrace{\mathcal{O}}{\text{phase oracle}}$$

Step 1 - Phase oracle $\mathcal{O}$: Reflects the state about $|\bar{t}\rangle$ in the ${|\bar{t}\rangle, |t\rangle}$ plane:

$$\mathcal{O}(a|\bar{t}\rangle + b|t\rangle) = a|\bar{t}\rangle - b|t\rangle$$

Step 2 - Diffusion operator $2|s\rangle\langle s| - I$: Reflects about $|s\rangle$. This can be written as:

$$D = H^{\otimes n}(2|0\rangle\langle 0| - I)H^{\otimes n}$$

The gate $2|0\rangle\langle 0| - I$ flips the phase of every computational basis state except $|0\rangle$; conjugating by $H^{\otimes n}$ converts this into a reflection about $|s\rangle$.

The composition of two reflections in a plane is a rotation. Each application of $G$ rotates the state vector by angle $2\theta$ toward $|t\rangle$:

$$G^k|s\rangle = \cos!\big((2k+1)\theta\big)|\bar{t}\rangle + \sin!\big((2k+1)\theta\big)|t\rangle$$

Iteration Count and Success Probability

We want $(2k+1)\theta \approx \pi/2$, i.e., $k \approx \frac{\pi}{4\theta} - \frac{1}{2}$. Substituting $\theta = \arcsin(1/\sqrt{N}) \approx 1/\sqrt{N}$ gives:

$$k^\ast = \left\lfloor \frac{\pi}{4}\sqrt{N} \right\rfloor$$

After $k^\ast$ iterations, the probability of measuring $|t\rangle$ is:

$$P(\text{success}) = \sin^2!\big((2k^\ast+1)\theta\big) \geq 1 - \frac{1}{N}$$

The algorithm thus succeeds with probability close to $1$ using $O(\sqrt{N})$ oracle queries. The total gate count, assuming the oracle itself uses $O(\text{poly}(n))$ gates, is $O(\sqrt{N} \cdot \text{poly}(n))$.

Circuit Implementation

A complete $n$-qubit Grover circuit:

  1. Apply $H^{\otimes n}$ to $|0\rangle^{\otimes n}$ to prepare $|s\rangle$.
  2. Repeat $k^\ast$ times:
    • Apply the phase oracle $\mathcal{O}$.
    • Apply $H^{\otimes n}$.
    • Apply the conditional phase shift $2|0\rangle\langle 0| - I$ (one multi-controlled $Z$ gate).
    • Apply $H^{\otimes n}$.
  3. Measure all $n$ qubits.

The diffusion operator step uses one $n$-qubit controlled-$Z$ gate, which decomposes into $O(n)$ elementary gates using ancilla qubits and the standard Toffoli-based construction. Total circuit depth per iteration: $O(n)$ (plus oracle depth).

Amplitude Amplification

Grover’s algorithm generalises to amplitude amplification, which applies when the initial state $|\psi\rangle$ is not the uniform superposition but some other state prepared by a unitary $\mathcal{A}$, and the oracle marks a subset of “good” states with total probability $p$.

Define:

  • $|\psi_1\rangle$ = normalised projection onto good states, $|\psi_0\rangle$ = normalised projection onto bad states.
  • $\sin^2\theta = p$.

The iterate $G = \mathcal{A}(2|0\rangle\langle 0| - I)\mathcal{A}^\dagger \cdot \mathcal{O}$ again rotates by $2\theta$ per step, reaching near-$1$ success probability in $O(1/\sqrt{p})$ applications of $\mathcal{A}$.

This gives a generic recipe: if a classical randomised algorithm succeeds with probability $p$, its quantum counterpart (when the computation is reversible) succeeds in $O(1/\sqrt{p})$ trials rather than $O(1/p)$.

Optimality: The Polynomial Method

The $\Omega(\sqrt{N})$ lower bound follows from the polynomial method of Beals et al. (2001). Any $T$-query quantum algorithm computes, for each output bit, a multilinear polynomial of degree at most $2T$ in the input bits. The OR function on $N$ bits (which equals the search problem) requires degree $\Omega(\sqrt{N})$ to approximate, so $T = \Omega(\sqrt{N})$ queries are necessary.

Multiple Targets

If there are $M$ marked items ($M$ unknown), replace $\sin\theta = \sqrt{M/N}$, giving $O(\sqrt{N/M})$ iterations. For $M = N/2$ the algorithm terminates in $O(1)$ steps; for $M > N/2$ one Hadamard measurement already succeeds with constant probability.

When $M$ is unknown, quantum counting (using phase estimation on $G$) estimates $M$ in $O(\sqrt{N})$ queries, after which the iteration count is set appropriately.

Examples

Unsorted database search. Given $N$ records with no index, find the one satisfying a predicate (e.g., a specific name in a flat file). Classical cost: $O(N)$. Quantum cost: $O(\sqrt{N})$ oracle evaluations.

Satisfiability checking. For a 3-SAT formula on $n$ variables, build an oracle that evaluates the formula on a given assignment in $O(n)$ gates. Grover gives $O(2^{n/2} \cdot n)$ quantum time, versus the classical $O(2^n \cdot n)$ brute force. This halves the exponent but does not break NP-hardness (quantum polynomial time would require $O(\sqrt{N}) = O(1)$).

Collision finding. Given a function $f : [N] \to [N]$, find $x \neq y$ with $f(x) = f(y)$. Combining Grover with quantum walks yields $O(N^{1/3})$ queries, beating the classical birthday bound of $O(\sqrt{N})$.

Breaking symmetric ciphers. AES-128 has a $2^{128}$ key space. A Grover search reduces this to an effective $2^{64}$ quantum query complexity, which is why NIST recommends AES-256 for post-quantum security.

Read Next: Shor’s Algorithm