Which problems actually have proven quantum advantage?

State as of: August 10, 2026. The Quantum Algorithm Zoo — the field's standard catalog — lists over 450 distinct quantum algorithms. Ask how many of those carry an advantage that is proven, in the mathematical sense of the word, and the catalog collapses to a handful. Ask how many have demonstrated that advantage end-to-end on hardware, on a useful problem, against a strong classical rival — and the number, as of today, is zero. This post is the map of that collapse: what "proven" actually means, which entries survive each definition, and why the gap between the catalog and the list is the real state of the art.

What counts as "proven"?

"Proven quantum advantage" gets used for at least three different things, and the difference is the whole story:

1. Unconditional theorem. A mathematical proof, resting on no unproven assumptions, that quantum beats classical at some task. This is the gold standard, and it has been achieved exactly once for a computational separation — and it is small.
2. Theorem in a restricted model. A proof that holds inside a formal model (usually query/oracle complexity: the algorithm counts calls to a black box, not wall-clock time). Real proofs — Grover's quadratic speedup is not only proven, it is proven optimal — but the model can hide the cost of building the box.
3. Conditional asymptotic advantage. The quantum runtime is proven; the claim that no fast classical algorithm exists is a conjecture. Shor's algorithm — the most famous "proven" advantage in the field — lives here: nobody has proven that factoring is classically hard.

And there is a fourth tier that none of the above confer: measured advantage — an end-to-end win on hardware, on a useful problem, same instance, against the strongest classical baseline. That tier is empty. The sampling-task demonstrations ("quantum supremacy") are real physics results on tasks with no known use — we drew that line in quantum advantage vs. quantum supremacy.

Which entries survive?

The honest list, one row per class, with what is proven and what is not:

Three notes the table forces:

Shor is conditional — and still the strongest card. The quantum side is a theorem; the classical side ("factoring has no fast classical algorithm") is a 50-year empirical observation, not a proof. Meanwhile the genuine hardware record is humbling: a 2024 survey of factoring on real quantum computers finds that "only very small integers N ≤ 35 have been successfully factored with Shor's algorithm on a digital QC," and notes that many larger claimed factorizations "rely on a certain kind of oversimplification that makes them equivalent to coin flipping" (Willsch et al., 2024). The threat to RSA is real and scheduled — but it lives in resource estimates and roadmaps, not in demonstrated factoring.

Grover is the only famous speedup that is provably optimal — and it may not pay. BBBV (1997) proved no quantum algorithm can search an unstructured space in fewer than ~√N queries, so Grover's quadratic gain is exact and final. But Babbush et al. (2021) showed quadratic speedups do not yield net advantage on the first generations of fault-tolerant machines once error-correction overhead is paid. A proven speedup can still lose on hardware — proof and payoff are different currencies.

HHL is the cautionary tale of the access model. The theorem is real (BQP-complete), but it prices in a state-preparation oracle. Aaronson's "Read the fine print" (2015) flagged the gap; Tang (2018) and successors then showed that for low-rank data, classical algorithms with matched sampling access close the exponential gap entirely. The theorem stands; the advantage it seemed to promise for machine-learning workloads mostly does not — the full post-mortem is in what dequantization took down.

Why is the honest list so short?

Because a quantum computer is not a parallel brute-forcer — measurement returns one outcome, and speedups only exist where interference structure can be engineered so wrong paths cancel (the qubit primer covers the mechanism). That structure is known to exist for a few problem shapes: period-finding (Shor), unstructured search (Grover, quadratically), and simulating quantum mechanics itself. For everything else in the catalog, the claim is asymptotic, conditional on an access model, or was matched classically once someone built the right baseline — the mechanism we documented in why a weak classical baseline ruins a quantum benchmark. The decade review on SSRN puts it flatly: quantum advantage "has been narrowed to a smaller and more clearly defined set of problems than the field imagined ten years ago" (Khan, Apr 2026).

What would move an entry up a tier?

Three observable events, in ascending order of difficulty: (1) a measured end-to-end win — same instance, strongest classical baseline, published costs — which is exactly the bar no useful problem has cleared (what the crossover point means); (2) hardware cheap and fast enough that polynomial speedups survive their constant factors — the Babbush bar; (3) a proof of classical hardness for factoring or simulation — which would be one of the deepest results in the history of computer science, and which nobody expects soon.

Where does Rosetta stand in this map? Nowhere flattering, and we publish it anyway: our sealed runs are in small-scale portfolio optimization — a class not on the proven list — and there the classical baseline has won every sealed comparison to date (the portfolio verdict). We have no runs in factoring, search, or quantum linear algebra, and we claim none.

What we know / what we don't know

We know: the Zoo lists 450+ algorithms (accessed Aug 2026); exactly one advantage theorem is unconditional (shallow circuits, Science 2018); Grover's quadratic speedup is proven optimal in the query model (BBBV 1997); Shor's runtime is proven polynomial (1994); the genuine hardware factoring record is N ≤ 35 (arXiv:2410.14397); low-rank quantum linear-algebra advantages were dequantized 2018–2020 (Tang 2018 and successors); quadratic speedups do not pay on early fault-tolerant hardware (PRX Quantum 2021).

We don't know: whether factoring is actually classically hard — no proof exists, and a classical breakthrough would erase Shor's advantage overnight; which polynomial speedups, if any, survive end-to-end costs on real machines — none has been measured; where the instance-level crossover sits for quantum simulation — every published number is a resource estimate on hardware that does not exist; whether more of the Zoo falls to future dequantization — the boundary is still moving; and whether the current "handful" is the final list or an artifact of what theorists have looked at hardest. Rosetta has no sealed runs in any class on the proven list; our only measured class is small-scale optimization, where the classical side is unbeaten.

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