Grover’s search algorithm

Grover’s search algorithm, also known as the quantum search algorithm, is a cornerstone of quantum computation, offering a quadratic speedup for unstructured search problems. It was introduced by Lov Kumar Grover in 1996 in his paper A fast quantum mechanical algorithm for database search [arXiv:quant-ph/9605043]. Whereas classical algorithms require $O(N)$ queries to search an unsorted database of $N$ elements, Grover’s algorithm achieves the same task with only $O(\sqrt{N})$ queries by exploiting quantum parallelism and amplitude amplification.

^{Fig. 1. Lov Kumar Grover, pioneer of algorithms for quantum computing. Photo is from this link.}

Searching an unstructured database is a fundamental task in many practical applications, such as finding the lowest-priced product, determining the shortest path to a destination via transfers, and solving other optimization problems. In this post, we begin with the simplest case of a single marked item and later consider the general case with multiple marked items. The core of Grover’s algorithm is the Grover iteration. The algorithm’s precision depends on the ratio $M/N$ , where $M$ is the number of marked items and $N$ is the total number of items.

Definition.(Unstructured search problem) The goal of Grover’s algorithm is to locate the marked element in an unsorted database. Given an oracle function

$f : \{0, 1\}^n \rightarrow \{0, 1\},$

where $f(x) = 1$ for the marked item $x'$ and $f(x') = 0$ for all other items$, the task is to find the marked elements $x'$ using fewer oracle queries than would be required classically.

Quantum oracle

To solve this problem quantumly, we also need to introduce a quantum oracle.

Recall that the classical oracle is a function $f : \{0, 1\}^n \rightarrow \{0, 1\},$ with $f(x) = 1$ for the marked item $x_{\text{marked}}$ and $f(x) = 0$ for all other items.

We can generalize this to a quantum oracle $U_f$ , which is a unitary operation that flips the sign of the amplitude of the marked state:

$U_f |x\rangle = (-1)^{f(x)} |x\rangle,$

where $|x\rangle = |x_1\rangle |x_2\rangle \cdots |x_n\rangle$ corresponds to the binary string $x$ .

This construction is the same as the oracles encountered in the Deutsch–Jozsa and Bernstein–Vazirani algorithms. By introducing an ancillary qubit initialized in the state $|-\rangle$ , we define the oracle

$\tilde{U}_f |x\rangle |y\rangle = |x\rangle |y \oplus f(x)\rangle,$

so that

$\tilde{U}_f |x\rangle (|0\rangle - |1\rangle) = (-1)^{f(x)} |x\rangle (|0\rangle - |1\rangle) = (U_f |x\rangle) (|0\rangle - |1\rangle).$

Dropping the ancillary qubit then recovers $U_f |x\rangle = (-1)^{f(x)} |x\rangle.$

In particular, for the marked state $x'$ , $f(x') = 1$ , so its phase is flipped: $U_f |x'\rangle = - |x'\rangle.$ For all unmarked elements, $f(x) = 0$ , so their amplitudes remain unchanged.

Grover iteration

The algorithm proceeds by repeatedly applying a procedure known as the Grover iteration or Grover operator to amplify the amplitude of the marked state. As we shall see, each Grover iteration corresponds to a rotation within a two-dimensional plane. The rotation angle at each step depends on the ratio $M/N$ between the number of marked items and the total number of items.

Suppose the search space contains $N=2^n$ items, of which $M$ are marked. Define the states

$|\alpha\rangle = \frac{1}{\sqrt{N-M}} \sum_{x: \text{ unmarked}} |x\rangle,$

representing an equal superposition of all unmarked items, and

$|\beta\rangle = \frac{1}{\sqrt{M}} \sum_{x: \text{ marked}} |x\rangle,$

representing an equal superposition of all marked items.

The uniform superposition over all items,

$|\psi\rangle = \frac{1}{\sqrt{N}} \sum_x |x\rangle = \frac{1}{\sqrt{2^n}} \sum_{x\in {0,1}^n} |x\rangle = H^{\otimes n} |0\rangle^{\otimes n},$

can be expressed as a superposition of $|\alpha\rangle$ and $|\beta\rangle$ :

$|\psi\rangle = \frac{\sqrt{N-M}}{\sqrt{N}} |\alpha\rangle + \frac{\sqrt{M}}{\sqrt{N}} |\beta\rangle.$

^{Fig. 2. Illustration of a Grover iteration. Each iteration rotates the state vector in the two-dimensional plane spanned by and , gradually increasing the amplitude of the marked state. Notice that for Grover’s search, the initial state is the uniform superposition over all items .}

We assume that $M/N$ is small. In this regime, the coefficient $c_{\alpha} = \frac{\sqrt{N-M}}{\sqrt{N}}$ corresponding to the unmarked states is much larger than the coefficient $c_{\beta} = \frac{\sqrt{M}}{\sqrt{N}}$ associated with the marked states. Consequently, the initial state $|\psi\rangle$ is predominantly aligned along $|\alpha\rangle$ , and the Grover iteration rotates the state vector slowly toward $|\beta\rangle$ , allowing gradual amplitude amplification of the marked state.

It is convenient to introduce an angle $\theta$ defined by

$\cos \frac{\theta}{2} = \frac{\sqrt{N-M}}{\sqrt{N}}, \qquad \sin \frac{\theta}{2} = \frac{\sqrt{M}}{\sqrt{N}}.$

This angle quantifies the initial projection of $|\psi\rangle$ onto the marked subspace and will be useful for understanding Grover iteration geometrically.

Each Grover iteration consists of two main steps:

Oracle Query (Phase Flip): Apply the oracle $U_f$ , which flips the phase of the marked state:
$U_f |x\rangle = (-1)^{f(x)} |x\rangle$ . Geometrically, this can be viewed as a reflection about the state $|\alpha\rangle$ . For any state in the two-dimensional subspace spanned by $|\alpha\rangle$ and $|\beta\rangle$ ,
$|\varphi\rangle = a |\alpha\rangle + b |\beta\rangle$ ,
the action of the oracle gives
$|\varphi'\rangle = U_f |\varphi\rangle = a |\alpha\rangle - b |\beta\rangle$ ,
showing that the $|\beta\rangle$ component is reflected.
Amplitude Amplification (Grover Diffusion Operator): Apply the diffusion operator
$D = 2 |\psi\rangle \langle \psi| - I$ ,
where $|\psi\rangle$ is the uniform superposition over all items as defined earlier. This operation can be interpreted as a reflection about $|\psi\rangle$ in the plane spanned by $|\alpha\rangle$ and $|\beta\rangle$ . To see this, define
$|\psi^\perp\rangle = -c_\beta |\alpha\rangle + c_\alpha |\beta\rangle$ ,
where $c_\alpha$ and $c_\beta$ are the coefficients of $|\psi\rangle$ in the $|\alpha\rangle$ , $|\beta\rangle$ basis, so that $|\psi^\perp\rangle$ is orthogonal to $|\psi\rangle$ in the plane. Any state in this plane can be expressed as
$|\chi\rangle = a |\psi\rangle + b |\psi^\perp\rangle$ . Acting with $D$ yields
$|\chi'\rangle = D |\chi\rangle = a |\psi\rangle - b |\psi^\perp\rangle$ ,
confirming that $D$ performs a reflection about $|\psi\rangle$ .

The combined Grover iteration operator is defined as

$G = D U_f = (2 |\psi\rangle\langle \psi| - I)\, U_f$ .

Within the two-dimensional subspace spanned by $|\alpha\rangle$ and $|\beta\rangle$ , consider an initial state

$|\Phi\rangle = \cos\frac{\theta}{2}\, |\alpha\rangle + \sin\frac{\theta}{2}\, |\beta\rangle$ ,

whose angle from $|\alpha\rangle$ is $\theta/2$ . Applying the oracle $U_f$ first reflects the state about $|\alpha\rangle$ , and subsequently applying $D$ reflects the resulting state about $|\psi\rangle$ . The composition of these two reflections produces a net rotation by an angle $3\theta/2$ toward $|\beta\rangle$ .

In Grover’s search, the initial state is the uniform superposition $|\psi\rangle$ , which lies at an angle $\theta/2$ from $|\alpha\rangle$ . Each application of $G$ therefore increases this angle by $\theta$ , gradually amplifying the amplitude of $|\beta\rangle$ and increasing the probability of measuring the marked state.

Exercise. Verify that $G |\psi\rangle$ performs the rotation illustrated in Fig. 2. Show explicitly that the Grover iteration acts as a rotation matrix in the basis ${|\alpha\rangle, |\beta\rangle}$ .

From Fig. 2, it is clear that $\theta$ becomes small when the ratio $M/N$ is small. Consequently, each Grover iteration corresponds to a small but precise rotation, making the algorithm particularly powerful for large databases with relatively few marked items.

The detailed procedure of Grover’s search algorithm is given below.

1. Initialization

Prepare $n$ qubits in the state $|0\rangle^{\otimes n}$ .

Apply the Hadamard transform $H^{\otimes n}$ to obtain the equal superposition
$|\psi\rangle = H^{\otimes n} |0\rangle^{\otimes n} = \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} |x\rangle$ .

2. Grover iterations

Apply the Grover iteration operator $G$ for $O(\sqrt{N})$ rounds. Each round consists of:

Oracle $U_f$ , flipping the phase of the marked state.

Diffusion operator $D$ , performing amplitude amplification.

3. Measurement

After approximately $O(\sqrt{N})$ iterations, the amplitude of the marked state is close to one. Measuring the qubits yields marked item $x'$ with high probability.

^{Fig. 3. Quantum circuit for Grover’s search algorithm.}

To analyze the behavior of the algorithm, let us assume for simplicity that there is exactly one marked item, $M=1$ . Initially, all basis states have amplitude $\frac{1}{\sqrt{N}}$ . After applying the oracle and the diffusion operator, the amplitude of the marked state increases, while the amplitudes of unmarked states decrease.

Each Grover iteration acts as a rotation in the two-dimensional subspace spanned by the unmarked-state superposition $|\alpha\rangle$ and the marked state $|\beta\rangle$ . The rotation angle is $\theta \approx 2 \sin^{-1}\left( \frac{1}{\sqrt{N}} \right)$ . After $k$ iterations, the state becomes
$G^k |\psi\rangle = \cos\left( \frac{2k+1}{2}\theta \right)|\alpha\rangle + \sin\left( \frac{2k+1}{2}\theta \right)|\beta\rangle$ .

Thus, repeated applications of $G$ rotate the initial state toward the marked state. The optimal number of iterations is
$k_{\mathrm{opt}} \approx \frac{\pi}{4}\sqrt{N}$ ,
which maximizes the probability of obtaining $|\beta\rangle$ upon measurement. Applying $G$ more times causes an overshoot and reduces the success probability.

M	T	W	T	F	S	S
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28