Grover’s algorithm, discovered by Lov Grover in 1996, searches an unsorted database of $N$ items in $O(\sqrt{N})$ time — a quadratic speedup over the classical $O(N)$.

The Problem¶

Given a function $f: \{0, 1, \ldots, N-1\} \to \{0, 1\}$ that returns 1 for exactly one “marked” item $w$, find $w$.

Classically, this requires $O(N)$ function evaluations. Grover’s algorithm requires only $O(\sqrt{N})$.

The Algorithm¶

Grover’s algorithm has three main steps, repeated approximately $\frac{\pi}{4}\sqrt{N}$ times:

1. Initialize in Uniform Superposition¶

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

2. Oracle Query¶

The oracle flips the phase of the marked item:

$$O|x\rangle = \begin{cases} -|x\rangle & \text{if } x = w \\ |x\rangle & \text{otherwise} \end{cases}$$

Mathematically: $O = I - 2|w\rangle\langle w|$

3. Diffusion Operator (Amplitude Amplification)¶

$$D = 2|s\rangle\langle s| - I$$

This reflects all amplitudes about their mean, amplifying the marked item’s amplitude while suppressing others.

Qiskit Implementation¶

from qiskit import QuantumCircuit
from qiskit.quantum_info import Statevector
import numpy as np

def grovers_search(n_qubits=3, target=5):
    """
    Grover's algorithm for searching n_qubits.
    target: the integer to search for (0 to 2^n - 1)
    """
    N = 2**n_qubits
    iterations = int(np.pi / 4 * np.sqrt(N))

    qc = QuantumCircuit(n_qubits)

    # Step 1: Initialize superposition
    qc.h(range(n_qubits))

    for _ in range(iterations):
        # Step 2: Oracle — mark the target
        target_bits = format(target, f'0{n_qubits}b')
        for i, bit in enumerate(reversed(target_bits)):
            if bit == '0':
                qc.x(i)
        qc.h(n_qubits - 1)
        qc.mcx(list(range(n_qubits - 1)), n_qubits - 1)
        qc.h(n_qubits - 1)
        for i, bit in enumerate(reversed(target_bits)):
            if bit == '0':
                qc.x(i)

        # Step 3: Diffusion operator
        qc.h(range(n_qubits))
        qc.x(range(n_qubits))
        qc.h(n_qubits - 1)
        qc.mcx(list(range(n_qubits - 1)), n_qubits - 1)
        qc.h(n_qubits - 1)
        qc.x(range(n_qubits))
        qc.h(range(n_qubits))

    return qc

circuit = grovers_search(n_qubits=3, target=5)
sv = Statevector.from_instruction(circuit)
probs = sv.probabilities()
print(f"Probability of finding target |101⟩: {probs[5]:.4f}")

Why Only Quadratic?¶

It has been proven (by Bennett, Bernstein, Brassard, and Vazirani) that Grover’s algorithm is optimal — no quantum algorithm can search an unstructured database faster than $O(\sqrt{N})$. This is significant because it shows that quantum computers do not provide exponential speedups for all problems.

Applications¶

Despite being “only” quadratic, the speedup is transformative for:

• Cryptography: Grover’s algorithm halves the effective key length of symmetric ciphers (AES-256 becomes AES-128 security)
• Optimization: Amplitude amplification techniques extend to constraint satisfaction
• Machine Learning: Speeding up nearest-neighbor search in high-dimensional spaces