What is Grover's algorithm and how much speedup does it really give?

Status as of: August 2026. Grover's algorithm is the second most famous quantum algorithm and probably the most misquoted. What it gives is precise and proven: for unstructured search, about √N calls to an oracle instead of N — a quadratic speedup, in the query model. What it is routinely sold as — a way to search your database, a parallel brute-forcer, a near-term threat to AES — it is not. The ceiling is also a theorem: nothing quantum beats √N for this task. And the largest better-than-classical Grover run published to date used 5 qubits, a search space of 32 items.

What does Grover actually do?

Take a function that marks exactly one of N candidates, with no structure to exploit. Classically you evaluate candidates until you hit the marked one — about N/2 tries on average. Grover (1996) prepares a superposition over all N candidates and applies roughly (π/4)·√N iterations; each iteration calls the function as a quantum circuit — the oracle — and rotates amplitude toward the marked state. It is choreography by interference, not parallel testing: measure too early and you get a random candidate (how a qubit actually computes).

Two properties make this class unusually honest. The speedup is proven — no asymptotic conjecture, no heuristic. And the limit is proven too: Bennett, Bernstein, Brassard and Vazirani (1997) showed that no quantum algorithm can solve unstructured search in fewer than on the order of √N queries. Grover is optimal. In a field where most claims live on estimates, this is one of the few corners bounded by theorems in both directions (the proven-advantage shortlist).

Does Grover speed up searching my database?

No — and this is the most common misreading. The oracle is not a lookup; it is a computation. Grover assumes you can evaluate the marking function on a superposition of candidates. If your N items are stored, unstructured data, something has to load them into that circuit first, and loading N items costs on the order of N operations — the advantage evaporates before the algorithm starts (Aaronson, Nature Physics 2015). This is the same fine print that dequantization exploited to take down a generation of quantum machine learning claims (the QML verdict).

Where Grover legitimately applies is search spaces defined by a function rather than stored in memory: satisfying assignments of a formula, preimages of a hash, cryptographic keys. There the candidate is computed, not fetched, and the √N count stands. Grover's core also generalizes into amplitude amplification (Brassard, Høyer, Mosca & Tapp, 2002) — a subroutine that quadratically boosts the success probability of other quantum algorithms, which is where most of its serious use lives.

How much speedup is "quadratic" in practice?

Quadratic means square root of the query count — not of the wall-clock time. For AES-128 key search, 2^128 classical guesses become about 2^64 Grover queries, and each query runs the full AES circuit coherently. The standard costing (Grassl, Langenberg, Roetteler & Steinwandt, PQCrypto 2016) puts the attack at 2,953 logical qubits and a total circuit depth of about 1.16·2^81, with roughly 1.19·2^86 T-gates. Later work refined the estimates downward (Jaques et al., EUROCRYPT 2020 — revised once after tooling bugs; the arithmetic moves, the conclusion does not).

Depth is the killer, because Zalka (1999) proved the iterations must run in series to get the full speedup. Our arithmetic on the cited depth: 1.16·2^81 is about 2.8×10^24 sequential logical steps. At a 1 GHz logical clock — which no roadmap promises; today's logical cycles run on the order of microseconds — that is roughly 89 million years. Parallelizing does not rescue it: Zalka's bound says S machines buy only a √S speedup, so cutting 89 million years to one year would take on the order of 8×10^15 full quantum computers. This is why "AES-128 drops to 64-bit security under Grover" is true only in the query model, and why NIST's own FAQ (accessed August 2026) concludes it is "quite likely that Grover's algorithm will provide little or no advantage in attacking AES, and AES 128 will remain secure for decades to come" (NIST PQC FAQ).

The general version of this arithmetic is already on the record: quadratic speedups, as a class, do not deliver advantage on early fault-tolerant machines once error-correction overhead is priced in (Babbush et al., PRX Quantum 2021 — where a crossover point comes from). Grover is the canonical member of that class.

What has actually run on hardware?

Small, careful, and honest demos. The record for better-than-classical Grover success probability is 5 qubits — a 32-item search space — on IBM 7-qubit devices, using error detection and dynamical decoupling (Pokharel & Lidar, npj Quantum Information 2024). On current 100+ qubit IBM machines, a 3-qubit Grover instance succeeds 51–64% of the time against a 25% random-guessing baseline, and published 8-qubit attempts had not beaten classical guessing (AbuGhanem, Scientific Reports 2025). The highest-fidelity small run is 3 nuclear-spin qubits in silicon at 93.5% success without error correction (Nature Nanotechnology 2024; SQC, Feb 2025) — a genuine fidelity result that its own authors present as a small-scale proof of concept, not an advantage claim. None of this is a criticism: these papers state their scope plainly. Every one of those shots also bills by task and shot on rented hardware (what a run actually costs).

Measured end-to-end advantage from Grover on a useful problem, on any hardware: zero, as of August 2026 (the scoreboard).

Claims about Grover, one by one

What we know / what we don't know

What we know. The √N query count is proven, and BBBV proved no quantum algorithm beats it — for pure unstructured search, the ceiling is a theorem, so no future cleverness raises it in the query model. The published fault-tolerant costings put Grover-on-AES at astronomical serial depth, and NIST's public position reflects that. The hardware record for better-than-classical success is 5 qubits.

What we don't know. Whether cheaper magic-state factories and better oracle synthesis bend the constants enough to matter someday — the estimates have been revised more than once, always astronomical so far. Whether Grover-as-subroutine inside larger fault-tolerant algorithms ever delivers measured end-to-end value on a useful instance — nothing measured to date. Where the crossover size N* would sit on real fault-tolerant hardware — no such machine exists to measure it on. Rosetta Q has no sealed runs in this class: our sealed series are small optimization and quantum-walk experiments where the classical baseline remains unbeaten — we have no Grover measurements of our own and claim none.

Rosetta Q publishes verdicts with reproducible raw data. This is educational content, not a product claim.