Grover's algorithm: √N queries and why that is optimal

Definition

Grover's algorithm searches an unstructured collection of N candidates for the items that satisfy a predicate. The predicate is an oracle: a black box that recognizes a marked item and does not otherwise reveal the list. For a unique marked item, the algorithm uses on the order of the square root of N queries. A classical algorithm that can only ask the same yes-or-no question needs on the order of N queries in the worst case.

The 1996 STOC paper is the conference account. The 1997 Physical Review Letters paper is the short telling with the phone-book picture. Both are about query cost. Neither is a gate count that ignores the cost of implementing the predicate.

Intuition

Start from the uniform superposition over all N candidates, which a layer of Hadamard gates prepares when N is a power of two. The oracle marks solutions by flipping their phase. A second reflection, often called the diffusion operator, reflects every amplitude about the mean. Marked amplitudes grow. Unmarked amplitudes shrink.

For one marked item, about (π/4) times the square root of N iterations drive the marked amplitude near 1. A measurement then returns that item with high probability. Too many iterations overshoot: the rotation does not stop at the solution by itself.

The phone book in the 1997 paper is an illustration of an oracle, not a design for a database. If the names have to be loaded into the quantum computer one by one, that loading is not free, and it can erase the quadratic improvement. The algorithm assumes the check is the expensive step you were going to pay for anyway.

Complexity

This is a query-complexity theorem. State it with the number of marked items in view. Boyer, Brassard, Høyer, and Tapp give a tight analysis: when t items are marked and t is known, the cost is on the order of the square root of N/t queries. They also give an algorithm for unknown t, so the search does not need the number of solutions in advance. Their lower bound puts Grover within about a factor of two of optimal in the number of probes.

Bennett, Bernstein, Brassard, and Vazirani prove a matching limitation. Relative to an oracle chosen uniformly at random, with probability 1, NP cannot be solved on a quantum Turing machine in time little-o of 2^(n/2). Grover's algorithm accepts NP relative to any oracle in time on the order of 2^(n/2), so the bound is tight. They are explicit that an oracle separation does not by itself prove NP is outside BQP with no oracle. It does rule out solving unstructured search, or NP-complete problems by brute force over an oracle, in fewer than about the square root of the search space queries.

Amplitude amplification, due to Brassard, Høyer, Mosca, and Tapp, keeps the quadratic improvement when the starting algorithm is any quantum procedure that already produces a solution with probability a. The expected number of uses of that procedure drops from about 1/a to about 1 over the square root of a. Grover's original algorithm is the case where the starting procedure is the uniform superposition and a is t/N.

The gate cost of one query is whatever the oracle circuit costs. Diffusion on N = 2^n basis states is a small circuit on n qubits, on the order of n gates, once the oracle is paid for. Totalling gates without a concrete oracle is not a complexity theorem.

Applications and limits

Exhaustive key search is the cryptographic reading. If the only attack is trying keys, a quadratic reduction in the number of trials changes the security level and does not collapse it. The usual engineering response discussed alongside this algorithm is a longer key, not a migration off the primitive. Shor's algorithm is the algorithm aimed at factoring and discrete logarithms. Mixing the two claims is how a quadratic search gets described as a break it is not.

Unstructured search is also a poor model of optimization problems that have structure. Classical solvers for satisfiability and for combinatorial optimization use that structure. Treating them as Grover instances throws the structure away and then proves a quadratic bound on what remains. QAOA is a different proposal: a shallow parameterized circuit for a cost function, with an approximation guarantee in one analyzed case, not a black-box search.

Amplitude amplification is the form that shows up as a subroutine, when a quantum routine already has a small success probability and the check is cheap. The hypothesis to test is still the cost of the routine being amplified, not the existence of the square-root symbol.

Reading the source

Read the STOC paper for the algorithm and the PRL for the short intuition. Read Boyer, Brassard, Høyer, and Tapp before quoting a bound for multiple solutions or for unknown t. Read Bennett, Bernstein, Brassard, and Vazirani before claiming a larger speedup, and read their own caution about what an oracle result does not prove. Brassard, Høyer, Mosca, and Tapp is the reference for amplitude amplification and for amplitude estimation.