How wrong answers cancel. Grover's search

On average it takes a little over two looks: 2.25 if you stop when one box is left, or 2.5 if you insist on opening the last box to see the cat. Either way an ordinary search needs about half as many looks as there are boxes. With a million boxes that is about half a million looks, and an unlucky search needs 999,999. No cleverness helps: the boxes give no clue, so each look rules out just one box.

For N boxes, opened in any order, stopping when one box is left:

For N = 4 that gives 2.25 and 3. Opening the last box too gives (N + 1) / 2 = 2.5 on average, and at worst N = 4.

Two qubits are enough to name four boxes: 00, 01, 10 and 11. Putting each qubit into an even both-ways wave gives every name the same ripple height. Ten qubits name 1,024 boxes, and twenty name more than a million. This is not yet useful. A look at this wave shows one box at random, no better than a blind guess. The real work is still to come.

One qubit in an even both-ways wave has height 1/√2 for 0 and for 1. For two qubits the heights multiply:

Each chance is (½)² = ¼, and the four chances add to 1. The animation turns each qubit smoothly from 0 to its even wave, so the chances add to 1 at every moment.

The check is a small circuit built to recognise the answer, and it acts on the whole both-ways wave at once. Drawn as one of Feynman's arrows from explainer 5, the mark is a half turn: the length, and so the chance, never changes, only the direction. That is how the animation shows it. Ordinary chances cannot be negative, so no ordinary machine can hide information like this. Here you choose where the cat hides. In a real search nobody knows, and only the check can tell.

The oracle multiplies the right box's height by −1 and leaves the others alone:

(−½)² = (½)² = ¼, so no single look can see the mark.

Like the mark, the mirror acts on all four ripples at once, and it needs no idea where the cat is. With exactly four boxes, one round of marking and mirroring gives certainty. Mark and mirror a second time and the cat's chance drops back to one in four: too many rounds overshoot. Lov Grover published the method in 1996, while working at Bell Labs.

Mirroring turns every height a into 2ā − a, where ā is the average height:

As one operation on the whole wave the mirror is D = 2|s⟩⟨s| − I, where |s⟩ is the even spread of section 2.

In 1997 Charles Bennett, Ethan Bernstein, Gilles Brassard and Umesh Vazirani proved that no quantum method can search unsorted boxes with fewer than about the square root of the number of boxes in checks. Grover's search reaches that limit, so it is the best possible. The gain is called a quadratic, or square-root, speed-up. It is real, but it is not the vast exponential leap that headlines often promise. For a million boxes it means several hundred times fewer checks.

Call θ the angle with sin θ = 1/√N. After k rounds the chance of the right box is:

For N = 1,000,000: θ ≈ 0.001 radians, k_best = 785 and P ≈ 0.99999996. For N = 4: θ = 30°, and one round gives sin²(90°) = 1.

This leaking is called decoherence, and it is the main enemy of every quantum computer. Many machines are cooled close to absolute zero, the coldest possible temperature, and shielded from stray light and magnetism. Even so, their waves last only a limited time. A search over a million boxes needs hundreds of rounds in a row, so the waves must survive all of them. Machines that catch and fix their own errors are a large part of the work today.

A record multiplies every cross term between two boxes by c, from 1 (no record) to 0 (a complete one). After one round with four boxes:

Grover's search weakens some secret codes without breaking them. Guessing a secret key would take about the square root of the usual effort, which roughly halves the key's effective length, so longer keys are the defence. The method shows the honest scale of quantum speed-ups: real, specific and often modest. Some other quantum methods, such as Peter Shor's of 1994 for finding the factors of large numbers, promise far bigger gains, but only for special problems with hidden patterns.