Grover's algorithm

In plain terms

Suppose one marked item is hidden somewhere in a long list with no structure to exploit, no sorting, no index and no pattern. The only way to find it classically is to check items one by one, so on average you look at half the list and in the worst case all of it, and it's natural to assume that's simply what unstructured search costs.

Grover showed that a quantum computer can do it in a number of steps proportional to the square root of the list size, so for a million items it takes roughly a thousand steps rather than half a million. The machine keeps one number for every item, called its amplitude, and the chance of reading out a given item at the end is the square of its amplitude. At the start all the amplitudes are equal, and each round of the algorithm does two things. First it flips the sign of the marked item's amplitude, which is the only step that uses any knowledge of which item is marked, and then it reflects every amplitude about the average of all of them, so the one entry that now stands out is pushed further from the crowd.

Seen geometrically, each round turns the machine's state through a small, fixed angle towards the marked item. After a number of rounds close to the square root of the list size the state is almost pointing at the answer, and a measurement reveals it with high probability. If you stop too early the answer is still unlikely, and if you carry on too long the rotation overshoots the target so the probability falls again, which means the algorithm comes with a timer as well as a result.

The unusual part is that the speedup is final. A separate theorem shows that no quantum algorithm, however ingenious, can find the item in fewer steps than this, up to a constant factor, so it isn't merely the best method known but the best method possible.

In CSD

Grover's algorithm is one of the algorithm witnesses in CSD's machine-checked corpus, a standard quantum algorithm formalised to show that the programme's account of quantum mechanics supports the working machinery of quantum computation. The relationship runs one way, and the corpus says so rather than leaving it implied. The algorithms depend on the programme's unitary pillar, its result establishing that quantum evolution is unitary, meaning reversible and probability-preserving, and they take that result as input and give no evidence for it. Their content is the meaning of circuits, with their amplitudes, iteration counts and success probabilities, and not foundations.

What this particular witness demonstrates, beyond the fact that the algorithm can be written down, is that the formalisation copes with genuinely quantitative reasoning. The bookkeeping of rotation angles and the schedule of how many rounds to run are exactly the details a fragile formal treatment would get wrong, and this one carries them through.

Mathematically

Amplitude amplification finds a marked element among N in order root-N oracle queries, versus order N classically. Optimality is a theorem, as the BBBV hybrid argument shows that no quantum algorithm beats order root-N queries for unstructured search.

The geometry is two-dimensional. The state stays in the plane spanned by the marked and unmarked components, and each double reflection (about the marked component, then about the mean) rotates it by a fixed angle, so the query count is a right angle divided by that angle, and running past it degrades the success probability.

The name

Lov Grover, born in 1961 in India, studied at IIT Delhi and Stanford and was at Bell Labs in New Jersey when he published the algorithm in 1996, in a paper three pages long whose title presented it as a database search result rather than a physics one.

The optimality half of the story is the strange half. The lower bound, due to Bennett, Bernstein, Brassard and Vazirani, was proved shortly before the algorithm existed, so the ceiling was known before anyone had built the thing that touches it, one of the rare cases in algorithms where the achievement and the proof that nothing better is possible arrived in the wrong order.

Related entries

• amplitude amplificationAmplitude amplification is the theorem of which Grover's algorithm is a shadow, as any quantum procedure with any success probability can have that probability raised by pure interference, quadratically faster than retrying.
• amplitude estimationPoint phase estimation at the rotation inside amplitude amplification and the success probability itself becomes measurable, quadratically faster than sampling could ever learn it.
• Shor's algorithmShor's algorithm factors large numbers in polynomial time on a quantum computer, and it turned quantum computing from a curiosity into a budget line and made every deployed cryptosystem provisional.
• Deutsch-Jozsa algorithmThe Deutsch-Jozsa algorithm settles a question with a single query where any exact classical method needs exponentially many, and the problem it solves is useless by design and historic for exactly that reason.
• Hadamard testThe Hadamard test turns a matrix element, a complex number buried inside an operator, into the bias of a single coin.