Grover's Search Algorithm: Find a Needle in a Quantum Haystack

Suppose you have an unsorted list of a million entries and you need the one that matches. A classical computer has no choice but to check them one by one, half a million tries on average. Grover's algorithm finds it in about a thousand. This is the most intuitive quantum speedup there is, a real answer to a problem everyone understands, and it is a one-click template in the ZKSF console.

The problem: search with no structure

Grover's algorithm solves unstructured search: find the input that a black-box function marks as correct, when the function gives you no hints. Classically this needs on the order of N checks for N items. Grover needs about the square root of N. That quadratic speedup does not sound dramatic on small examples, but at scale it is the difference between a million steps and a thousand.

The engine behind it is amplitude amplification. Every possible answer starts equally likely. Grover then nudges probability away from the wrong answers and towards the right one, a little more with each round, until a measurement almost certainly returns the item you were looking for.

The circuit: mark, then amplify

Our template searches the four possible states of two qubits for the target 11. Two Hadamards spread the qubits into an equal superposition of all four candidates. The oracle, a controlled-Z, flips the phase of just the target. The diffusion step then reflects every amplitude about the average, which turns that hidden phase flip into a real jump in probability. For two qubits, a single round is enough to find the answer with certainty.

OPENQASM 2.0;
include "qelib1.inc";
qreg q[2];
creg c[2];
h q[0];
h q[1];
cz q[0],q[1];          // oracle: mark |11>
h q[0];
h q[1];
x q[0];
x q[1];
cz q[0],q[1];          // diffusion
x q[0];
x q[1];
h q[0];
h q[1];
measure q -> c;

In the diagram the two Hadamards on the left create the superposition. The emerald controlled-Z is the oracle that marks the target. The block that follows, Hadamards and X gates around a second controlled-Z, is the diffusion operator that amplifies whatever the oracle marked.

Running it live: found, every time

We ran this circuit on ZKSF at 1,000 shots. Every gate is Clifford, so the router used the exact stabilizer engine. The result:

counts:     {"11": 1000}
error_info: {"method": "stabilizer (Gottesman-Knill)",
             "truncation_error": 0.0,
             "shot_noise_only": true, "shots": 1000}

Every one of the 1,000 shots returned 11, the marked item. On two qubits a single Grover iteration is exact, so there is no scatter at all: the algorithm finds the needle on the first try. The run carries a public ZCC-v0.1 certificate.

Scaling up, and why it matters

Add qubits and the search space doubles with each one, but the number of Grover iterations you need only grows as the square root. Search a space of a million with twenty qubits and you need roughly 800 rounds instead of a million checks. The same shape of algorithm reaches into database lookup, constraint satisfaction, and cryptography, where it halves the effective key length of a symmetric cipher and is one reason the world is moving to longer keys. For the wider picture, see Grover and Shor, simulated and our post-quantum cryptography primer.

Try it yourself

Pick Grover search from the template menu in the console and run it. Then change the oracle to mark a different target, say 01 instead of 11, and confirm the algorithm follows. Grover pairs naturally with the Bernstein-Vazirani algorithm, another one-query quantum trick, and with QAOA for MaxCut when the thing you are searching for is the best answer, not just a marked one.