Grover's Limits

Grover's speedup is a square root, not an exponential one. It needs √N oracle queries instead of N. The BBBV theorem proves no quantum algorithm can do unstructured search with fewer. In practice, the gain is usually eaten up by two costs. Building the oracle circuit is costly. And each quantum query is tens of thousands of times slower than a CPU's memory check. So no Grover run so far has beaten a normal computer on a real search.

How big is Grover's speedup, really?

It is a square-root speedup, also called quadratic. It is not exponential. That difference decides everything that follows, so let us make it concrete.

Recall from chapter 1 that query complexity counts calls to the oracle, the yes/no test circuit. It ignores every other cost. Searching N choices with no clues takes a normal computer N/2 queries on average. Grover takes about (π/4)·√N.

Worked example: count the queries.

For N = 1,000,000: a normal search averages 500,000 queries. Grover needs ⌊0.785398 × √1,000,000⌋ = ⌊0.785398 × 1,000⌋ = 785 queries. That is about 637 times fewer.
For N = 10¹²: a normal search needs 5 × 10¹¹. Grover needs about 785,398.

The gap grows, but only as √N. Here is a handy rule for security: Grover halves the exponent. Searching 2⁸⁰ choices costs about 2⁴⁰ queries.

Compare that with an exponential speedup, like Shor's algorithm for factoring. Shor turns a problem believed to take longer than the age of the universe into one that takes hours or days. (That needs a machine that does not exist yet.) An exponential speedup changes what is possible. A square-root speedup changes how long you wait. And it only helps if each quantum query is not much slower than a normal one. That "if" is where Grover's real-world case falls apart, as we will count below. All the query-count statements here are proved theory.