What is the "crossover point" in quantum advantage?
Status as of: July 2026. The estimates below are sourced and dated; the constant-factor argument is standard, and our own numbers are sealed and reproducible.
A speedup on paper is a statement about scaling — how a method's cost grows as the problem gets bigger. It says nothing about which machine is faster on the problem in front of you. The crossover point, written N*, is where those two things meet: the problem size at which a quantum method's better asymptotic scaling finally beats the best classical method on the same problem, after paying quantum's brutal constant-factor overhead. Below N*, classical is faster and cheaper. Above N*, quantum wins. Every honest claim of "quantum advantage" is, underneath, a claim about where N* sits and whether anyone can reach it.
What exactly is the crossover point?
Take any problem class and a quantum method with a proven asymptotic advantage — say Grover's quadratic speedup for unstructured search, or Shor's exponential speedup for factoring. Plot two curves against problem size: the runtime of the best classical algorithm, and the wall-clock runtime of the quantum method on real hardware, including error correction. The quantum curve almost always starts far above the classical one, because a single logical operation on an error-corrected qubit costs thousands to millions of physical operations. The crossover point N* is where the quantum curve — rising more slowly — finally dips below the classical one. It is not a property of the algorithm alone. It is a property of the algorithm, the hardware, the error-correction scheme, and the specific classical baseline, all at once. Change any of them and N* moves.
Why constant factors decide everything
The uncomfortable part: asymptotics hide the constants that determine whether N* is reachable in this universe. A quadratic speedup means quantum cost grows like the square root of classical cost — impressive on a slide. But error correction inflates every quantum operation by a large constant, and Babbush et al. showed in 2021 that for quadratic speedups this constant is so punishing that "quadratic speedups will not enable quantum advantage on early generations of fault-tolerant devices" — even a tenfold improvement in logical gate rates does not fix it. Their conclusion is blunt: only higher-degree polynomial speedups (quartic and up) or exponential ones push N* somewhere reachable. So the honest question is never "is there a speedup?" It is "where is the crossover, and can we build a machine big enough to pass it before the classical side improves and moves it further out?"
Where is the crossover, by problem class?
The crossover is knowable in principle but published for almost nothing. Here is the honest state, by class:
| Problem class | Speedup type | Where the crossover is estimated | Status | Source |
|---|---|---|---|---|
| Factoring (Shor) | Exponential | RSA-2048 breakable with under 1M noisy qubits | Estimated, hardware not built | Gidney 2025 |
| Fault-tolerant spin dynamics | Super-polynomial | ~100-site 1D Ising: ~2h quantum vs ~100y classical (~3.7×10⁵ physical qubits, p=10⁻³) | On paper (resource estimate) | arXiv:2607.16116 |
| Portfolio optimization (QAOA) | Heuristic | No crossover observed at n=12/16/20 | Measured; classical hit proven optimum 20/20 | V-0012 |
| Unstructured / quadratic (Grover-type) | Quadratic | Pushed out of reach by error-correction overhead | Theoretical caution | Babbush 2021 |
Two of these — factoring and fault-tolerant simulation — have crossover estimates only because someone did the resource accounting for hardware that does not yet exist. The estimate is a target, not a result. The simulation paper is explicit that its ~2-hour figure assumes 370,000 physical qubits at a 10⁻³ error rate; no machine on Earth is there today.
What our own data says
For the optimization problems businesses actually ask about, we stopped estimating and started measuring. In our sealed portfolio-optimization ladder (recipe RQ-0012, QAOA p=2 vs classical CP-SAT, 20 runs at 12, 16 and 20 assets) the classical solver reached the proven exact optimum in every single run, while QAOA sat 25–48% away — and the gap did not shrink monotonically with size. There is no crossover in that data because there is no trend pointing at one. That is not a failure of the experiment; it is the answer. A crossover you cannot see after 20 controlled runs is a crossover you are not allowed to assume exists.
What we don't know. The exact N* for any real optimization problem — it may sit at a size no hardware will reach for a decade, or it may not exist for heuristic quantum methods at all. Whether the fault-tolerant simulation and factoring estimates survive contact with real, noisy hardware and improved classical algorithms (both have a habit of moving N* the wrong way). And how much of any measured gap is the quantum method versus a classical baseline that simply was not tuned hard enough — separating those is the entire job of an honest referee.
Rosetta Q publishes verdicts with raw, reproducible data. This is educational content, not a product claim. Every external figure above is a sourced, dated public result read at face value; every internal number is sealed and reproducible.