Grover's Limits

Grover's speedup is quadratic, not exponential — √N oracle queries instead of N — and the BBBV theorem proves no quantum algorithm can do unstructured search with fewer queries. In practice the advantage is usually consumed by the cost of building the oracle circuit and by quantum oracle queries that are tens of thousands of times slower than a CPU's memory checks, so no Grover run to date has beaten a classical computer on a real search.

How big is Grover's speedup, really?

Quadratic. Not exponential. The distinction decides everything downstream, so let's make it concrete.

Recall from chapter 1 that query complexity counts calls to the oracle — the yes/no test circuit — ignoring all other costs. Searching N unstructured candidates classically takes N/2 queries on average. Grover takes about (π/4)·√N.

Worked example: query counts. For N = 1,000,000: classical average 500,000 queries; Grover ⌊0.785398 × √1,000,000⌋ = ⌊0.785398 × 1,000⌋ = 785 queries — about 637 times fewer. For N = 10¹²: classical 5 × 10¹¹; Grover about 785,398. The gap grows, but only as √N. A useful mental model for security applications: Grover halves the exponent — searching 2⁸⁰ possibilities costs about 2⁴⁰ queries.

Compare that with an exponential speedup like Shor's algorithm for factoring, which turns a problem believed to need more than the age of the universe into one needing hours or days (given a machine that does not yet exist). An exponential speedup changes what is possible; a quadratic speedup changes how long you wait — and only if each quantum query is not too much slower than a classical one. That "if" is where Grover's practical case collapses, as we'll count below. All statements in this paragraph about query counts are proved theory in the query model.