What Is Grover's Algorithm? From a 2-Qubit Model to the General Case

The Problem Grover's Algorithm Solves

Grover's algorithm (1996, Lov Grover) is a quantum algorithm that finds a single element satisfying a given condition within an unsorted (unstructured) database of N elements, using O(√N) oracle calls. Since a classical computation requires an average of O(N) checks, this is a quadratic speedup.

The role of "marking" the element being searched for is played by the oracle U_f, which flips the phase of the marked state (U_f|x⟩ = -|x⟩ if x is the marked target, and U_f|x⟩ = |x⟩ otherwise).

The Simplest Example: The Case of 2 Qubits (N=4)

The structure of Grover's algorithm is easiest to understand in the case of 2 qubits (N = 2² = 4). Here is the procedure.

1. Apply the Hadamard gate H⊗H to the two qubits to create a uniform superposition of the four basis states |00⟩, |01⟩, |10⟩, |11⟩
2. Apply the oracle U_f, flipping only the sign of the amplitude of the marked state (say, |10⟩)
3. Apply the diffusion operator, called "inversion about the mean," U_s = 2|s⟩⟨s| - I (where |s⟩ is the uniform superposition state)

Generalizing to n Qubits (N=2ⁿ)

In general, when handling N = 2ⁿ elements, one set of the oracle plus the diffusion operator is called a Grover iteration, and repeating it the optimal number of times

k ≈ (π/4)√N

maximizes the probability of detecting the marked state (in the case of N=4, as seen above, this comes out to k=1). Geometrically, this repetition can be understood as rotating the state vector by a fixed angle

θ = 2·arcsin(1/√N)

each time, within the two-dimensional plane spanned by the "marked state" and the "uniform superposition of unmarked states" (this corresponds to a special case of the general technique called amplitude amplification). Because the rotation angle θ is fixed, it's important to note that as the number of iterations moves away from the optimal value k, the probability of observing the marked state actually decreases (from rotating too far — overshoot).

The fact that the probability came out to exactly 100% in the N=4 case is a numerical coincidence: at N=4, θ happens to equal exactly π/3, letting a single rotation pass exactly (with no approximation error) through the angle (just under π/2) from the initial state to the marked state. For general N, the detection probability after the optimal number of iterations k comes out very close to 100%, but does not become exactly "1" in the strict sense that it does for N=4.

Implications for Cryptography: The Effective Key Length of Symmetric-Key Cryptography

Grover's algorithm can also be applied to key search against symmetric-key cryptography, where brute force is fundamentally what's being defended against. If the key space has size N = 2ⁿ (an n-bit key), a classical brute-force search requires an average of O(2ⁿ⁻¹) attempts, whereas Grover's algorithm needs only O(2^(n/2)). In other words, the effective security strength is halved in terms of key length. AES-128 would retain only an effective security strength equivalent to 64 bits against a quantum computer, which is why NIST's recommendation of AES-256 as the symmetric-key cipher for the post-quantum era is a decision that accounts for this halving effect from Grover's algorithm.

Summary

• Grover's algorithm solves unstructured search using O(√N) oracle calls, achieving a quadratic speedup
• In the case of N=4 (2 qubits), a single iteration finds the answer with 100% probability — a special case
• For general N, the optimal number of iterations (π/4)√N of amplitude amplification finds the answer with high probability
• Applied to symmetric-key cryptography, the effective key length is halved, which is why longer keys such as AES-256 are recommended for the post-quantum era