Mind the Gaps — Why "Quantum Advantage" Keeps Moving When You Reach for It.

Every few months there's a headline: a quantum computer did something a classical supercomputer supposedly can't. Google's Willow chip. IBM's "quantum utility." D-Wave's spin-glass simulation. Each time, a team of classical computer scientists shows up within weeks with a tensor-network trick that closes most of the gap. Each time, the quantum side quietly moves the goalposts and tries again.

This isn't a story about fraud or hype for its own sake. It's a story about a field that keeps conflating two very different questions: can a quantum computer do something a classical computer finds hard, and can a quantum computer do something useful that no classical computer can do at all, cheaper. The first question has been answered "yes" a few times now. The second question — the one that actually matters economically — is still open, and the honest answer is probably not yet, and maybe not for a while.

That's the argument in "Mind the gaps: The fraught road to quantum advantage" (arXiv:2510.19928), a perspective piece by Jens Eisert (Freie Universität Berlin) and John Preskill (Caltech) — the same Preskill who coined "NISQ" in 2018 and has spent a decade being the field's most trusted skeptic. This isn't a new algorithm or a new experiment. It's two of the most credentialed people in the field sitting down and writing, in plain language, exactly what still needs to happen before quantum computing is useful — and being unusually honest about how far away some of it still is.

The vocabulary problem: NISQ, FASQ, and the three "-quop" regimes

Before anything else, the paper fixes a vocabulary gap that's been quietly causing confused arguments for years.

NISQ (noisy intermediate-scale quantum) is what exists today: devices with roughly 50 to a few thousand physical qubits, no error correction, and gate error rates around $10^{-3}$ to $10^{-4}$. NISQ machines are real, they do impressive things, and they have never produced an economically useful result. FASQ — a term this paper is introducing — stands for fault-tolerant application-scale quantum: machines where error-corrected logical qubits run reliably enough, at large enough scale, to solve problems people actually care about. Nobody has built one. The entire paper is about the terrain between here and there.

The authors also give the field a shared unit system for talking about scale, borrowed from Preskill's own earlier writing: a megaquop machine reliably executes around $10^6$ quantum operations, a gigaquop machine around $10^9$, and a teraquop machine around $10^{12}$ — which the paper estimates is roughly the scale a "broadly useful" FASQ machine will need to reach. Today's best NISQ devices, even with heavy error mitigation, top out somewhere well short of that. The gap between NISQ and a megaquop machine is already daunting. The gap to teraquop is the real story.

With that vocabulary in hand, the paper structures the whole road ahead as four sequential hurdles. Not four independent problems you can parallelize across different teams — four gaps you cross in order, because each one is a prerequisite for the next.

Gap 1 — from mitigating errors to correcting them

Today's NISQ machines don't correct errors. They mitigate them: run the same noisy circuit many times, apply statistical postprocessing, and extract a usable signal from a mess. The two workhorse techniques are zero-noise extrapolation (deliberately amplify the noise, measure the trend, and extrapolate back to the zero-noise limit) and probabilistic error cancellation (characterize the noise channel experimentally, then invert it in postprocessing).

Quantum error mitigation (QEM) is genuinely useful right now — the paper credits it with extending the reachable circuit volume on today's hardware substantially, potentially enough for circuits with 10,000+ gates soon, and it will remain useful even into the fault-tolerant era for squeezing extra performance out of imperfect hardware. But QEM has a hard mathematical ceiling: the sampling overhead needed to extract a clean signal scales exponentially with circuit volume (depth times width). Under depolarizing noise specifically, once qubit count is large and circuit depth scales like $\log n$, efficient classical algorithms can already estimate the output accurately — which rules out any quantum advantage in that regime, mitigation or not.

Real quantum error correction (QEC) is different in kind, not just degree. Instead of statistically cleaning up noisy runs after the fact, you actively detect and fix errors during the computation, using redundant physical qubits to protect a smaller number of logical qubits. The overhead is real (more physical qubits, more physical gates) but it scales polylogarithmically in circuit volume rather than exponentially — which is exactly the trade that eventually has to happen. QEM buys you more circuit volume on today's hardware; QEC is the only path to circuits deep enough to matter.

What's actually new here isn't the theory — this insight is nearly 30 years old, dating to the first quantum error-correcting codes in 1995. What's new is that the experimental side is finally catching up. Google's superconducting processor recently demonstrated a protected quantum memory holding a single logical qubit through millions of consecutive rounds of surface-code syndrome measurement, and — this is the number worth remembering — the logical error rate improved by a factor of roughly $\Lambda \approx 2$ each time the code distance increased from 3 to 5, and again from 5 to 7. That's the first solid experimental evidence that scaling the code actually helps in practice, not just in theory. Separately, Rydberg tweezer arrays have run circuits with 48 logical qubits on a 280-qubit array, and ion traps have hit 12 logical qubits on a 56-qubit device — real progress, but both demonstrations are still limited to a handful of error-correction rounds and rely on postselection (discarding runs where errors are detected), a trick that flatly does not scale to the deep circuits FASQ will need.

Gap 2 — from "we corrected some errors" to actual fault tolerance

This is the gap most casual coverage of quantum computing skips entirely, and it's the one the paper spends the most technical effort unpacking, because the resource math is brutal.

The key theoretical result — the threshold theorem, established in the 1990s — says that if every physical operation's error rate is below some fixed threshold, and errors aren't too correlated, then you can drive the logical error rate arbitrarily low by adding more physical qubits per logical qubit. The catch is exactly how much overhead "arbitrarily low" costs you in practice.

optional read — the surface-code overhead formula, worked with real numbers

For the surface code — the leading near-term approach, because it only needs geometrically local operations in two dimensions — the paper gives the logical error rate per operation as:

$$P_{\text{logical}} \approx 0.1 \left(\frac{p_{\text{phys}}}{p_{\text{thresh}}}\right)^{(d+1)/2}$$

where $p_{\text{phys}}$ is the physical two-qubit gate error rate, $p_{\text{thresh}} \approx 10^{-2}$ is the accuracy threshold, and $d$ is the code distance. Each logical qubit in the surface code costs $n = d^2$ physical qubits.

Plug in real numbers. Suppose your hardware has $p_{\text{phys}} = 10^{-3}$ — roughly where today's best superconducting and trapped-ion platforms sit — and you need $P_{\text{logical}} = 10^{-11}$ to run a highly parallel algorithm on $10^3$ logical qubits for $10^8$ time steps without an error derailing the computation. Solving for $d$ gives $d \approx 19$, which means $n = 19^2 \approx 361$, or roughly $10^3$ physical qubits per logical qubit once you add ancilla and logical-gate overhead. Multiply by $10^3$ logical qubits and you land at roughly $10^6$ physical qubits total — far beyond the scale of any device that exists today.

That worked example is the entire "Gap 2" argument compressed into one number: even a modest useful computation — a thousand logical qubits, a hundred million time steps — needs on the order of a million physical qubits at today's error rates. Current devices top out around a few thousand physical qubits, period, error-corrected or not. That's not a small gap. It's three orders of magnitude, and closing it requires either dramatically better physical error rates, dramatically better codes, or both.

This is where the paper's most genuinely useful technical nugget shows up: quantum low-density parity-check (qLDPC) codes. The surface code protects exactly one logical qubit per code block; an emerging class of qLDPC codes does much better on that ratio — the paper cites a concrete $[[144, 12, 12]]$ code as an example, meaning 144 physical qubits protecting 12 logical qubits at the same code distance the surface code would need to protect just one. That's a real, order-of-magnitude improvement in encoding efficiency. The catch is that reading out error syndromes for these higher-rate codes needs geometrically non-local physical operations — hard to do in superconducting circuits, where qubits are wired in a fixed 2D grid, but a much more natural fit for platforms where qubits can be physically moved and rearranged, like Rydberg tweezer arrays or ion traps with shuttling. Plausible hardware-based estimates in the paper suggest qLDPC codes could reduce the physical qubit overhead of fault tolerance by orders of magnitude compared to nearest-neighbor-only architectures — if the connectivity problem gets solved.

There's a third cost the naive overhead math misses entirely: time. Even with enough physical qubits, you need many rounds of syndrome measurement to reliably diagnose errors, and you need to decode those syndromes fast enough to keep pace with the quantum processor's clock — or the whole computation slows down waiting on classical decoding. Rydberg platforms in particular have a logical cycle time orders of magnitude longer than superconducting processors, because moving atoms around physically is slow. Fast real-time decoding and fast qubit movement aren't optional nice-to-haves; they're load-bearing parts of whether fault tolerance is actually usable, not just theoretically achievable.

Gap 3 — from heuristics that look impressive to algorithms you can trust

Suppose the hardware problem gets solved. There's a separate, softer problem underneath it: for most of the algorithms people are actually excited about running on near-term or early fault-tolerant machines, nobody has proven they're actually faster than the best classical approach.

Take the quantum approximate optimization algorithm (QAOA), probably the most hyped near-term optimization algorithm. It's provably hard to simulate classically at sufficient depth — that much is established. But the paper is direct about the actual advantage question: log-depth QAOA has been shown to have no asymptotic quantum advantage for a large class of sparse combinatorial optimization problems. Classically hard to simulate and classically beatable are not the same claim, and QAOA at practical depths is squarely in the second category for a lot of the problems people want to throw it at. There are real bright spots — single-round QAOA has been rigorously proven to outperform any known classical algorithm for specific families of graphs, and there are results identifying graph families where polynomial-time QAOA finds cuts that provably beat what any known subexponential classical algorithm can achieve. But these are narrow, carefully constructed "proof pockets," not a general license to expect QAOA to beat classical solvers on your actual optimization problem.

Variational algorithms more broadly (QAOA and its cousin VQE, the variational quantum eigensolver) share a structural weakness the paper calls out directly: barren plateaus. As you make the parametrized quantum circuit more expressive — which is usually what you'd want for a harder problem — the cost-function gradient tends to vanish exponentially, which kills trainability. And the fix (reducing expressivity to keep gradients alive) tends to make the circuit easy enough to simulate classically that you've traded away the advantage you were trying to get in the first place. The paper is blunt about this: there's a fundamental tension between trainability and quantum advantage in this whole family of algorithms, and it remains genuinely unresolved.

The most interesting new idea in this section is decoded quantum interferometry (DQI) — a fresh paradigm, not a variational algorithm at all. DQI uses the quantum Fourier transform to map a problem that looks classically hard onto a decoding problem that's classically easy — the quantum part does the hard-to-classically-emulate transformation, and the classical part does cheap decoding on the result. For a specific structured problem called optimal polynomial intersection, DQI provably achieves a better approximation ratio than any currently known classical algorithm. That's genuinely exciting. But the paper is careful to flag two caveats that arrived almost immediately after DQI was proposed: directly simulating DQI has itself been shown to be classically hard (so you can't just fake it), but DQI has also been shown to provide no quantum advantage on unstructured combinatorial optimization problems. It only works on the structured problem class it was designed for, and whether that class contains anything anyone actually needs to solve is, per the paper, still under investigation.

Machine learning gets the same clear-eyed treatment. Rigorous quantum advantage has actually been established for a handful of learning tasks — generative modeling, density modeling, binary classification, and identification — but the paper's own assessment is that these are "mildly encouraging" and highly contrived results that don't yet point toward where a practically useful learning advantage might live. Quantum machine learning also inherits the barren-plateau problem from variational circuits generally, and a separate practical problem the paper flags clearly: loading a large classical dataset into a quantum device is itself expensive enough to potentially erase whatever advantage quantum processing would have provided on that data. And the field has already been burned once — an early hope that quantum computers could speed up certain linear-algebra-heavy ML tasks in exponentially large Hilbert spaces was "dequantized" when Ewin Tang and others found efficient classical sampling algorithms that matched the claimed quantum speedup. That's the "classical algorithms keep catching up" pattern from the very top of this article, showing up again inside the ML section specifically.

Algorithm family	Status per the paper
Random circuit sampling	Provably classically hard under standard complexity assumptions. Genuinely a scientific milestone. Not of practical interest — solves no useful problem.
QAOA (log-depth, general sparse problems)	No proven asymptotic advantage. Real advantage exists only in narrow, specifically constructed "proof pocket" instances.
VQE / variational algorithms generally	Barren plateaus create a direct tension between expressivity and trainability. Advantage on practical problems remains unresolved.
Grover's algorithm on NP-hard search	Real, provable quadratic speedup. Valuable eventually — but given FASQ's much slower clock speed vs. classical hardware, probably not for many decades.
DQI	Provable advantage on one structured problem (optimal polynomial intersection). Proven no advantage on unstructured combinatorial optimization.
Quantum ML (specific contrived tasks)	Rigorous advantage established for a few narrow learning tasks. "Mildly encouraging," not yet a guide to practical advantage.
Quantum linear systems solver	Real advantage in the FASQ regime for well-conditioned sparse matrices. Real applications remain an open problem — boundary conditions, preconditioners, output extraction all unresolved.

Gap 4 — from "we simulated something" to a credible simulation advantage

This is the gap the paper treats most optimistically — and it's worth understanding exactly why, because the optimism is narrow and specific, not general.

The argument starts from Dirac's famous 1929 lament: quantum mechanics gives you, in principle, the equation for all of chemistry, but it's "much too complicated to be soluble" for systems with more than a few electrons. Feynman's 1982 answer was that if nature is quantum mechanical, you should simulate it with a machine that's also quantum mechanical. The catch the paper spends real time on: Dirac's pessimism was in some ways misleading, because classical heuristics — density functional theory chief among them — have gotten remarkably good at exactly the problems he thought were hopeless, and they keep getting better. Quantum computing targets the genuinely, still-stubbornly-hard corner of chemistry and materials science: strongly correlated matter, where those classical heuristics break down.

The paper draws a sharp, useful distinction here that a lot of quantum-simulation coverage blurs: ground-state (equilibrium) simulation versus dynamical (far-from-equilibrium) simulation. For ground-state properties, powerful classical methods — density functional theory, tensor-network approaches — already perform well in practice for a huge range of physically relevant problems, especially in low dimensions. That makes it genuinely hard to argue convincingly that a ground-state problem of real physical interest is both classically hard and quantumly easy — you need both halves of that claim simultaneously, and finding real examples where both hold is rare. Simulating dynamics far from equilibrium is a different story: classical methods for dynamical simulation are generally much less effective, because entanglement grows rapidly during real-time evolution and classical descriptions choke on it — while a quantum computer can naturally realize that same dynamics through its own time evolution. That asymmetry is the paper's actual reason for optimism, and it's specific: dynamics, not equilibrium.

The paper is candid about how fast the classical side keeps closing gaps that looked closed. A 127-qubit two-dimensional kicked Ising simulation on IBM hardware was initially presented as demonstrating "quantum utility" — and was quickly matched by classical calculations using both tensor-network methods and sparse Pauli dynamics. D-Wave's claimed simulation of rapidly quenched spin-glass dynamics, also presented as beyond classical reach, has since been partially reproduced using classical tensor-network simulations too. The paper frames this back-and-forth as genuinely healthy for the field and stimulating for both sides — not evidence that quantum computing is fake, but evidence that the bar for a credible, durable advantage claim needs to be much higher than "nobody's matched it yet this month."

One recent result the paper does treat as a real, if qualified, positive data point: out-of-time-order correlators computed on a 103-qubit Google superconducting processor, in a regime the authors describe as arguably hard to simulate classically. The honest framing matters here — NISQ-era simulations may not have very high accuracy, but they can still be qualitatively informative, and this is offered as a state-of-the-art example of that category, not as a settled, unambiguous advantage claim.

There's a nice, concrete side note in this section on why quantum simulation matters even beyond the advantage question: a U.S. Department of Energy estimate cited in the paper says over 30% of compute cycles at a major HPC facility are spent on density functional theory calculations for chemistry and materials science, over 18% on lattice QCD, and roughly 2.6% more on other chemistry algorithms — a rough proxy for just how much classical compute is already being burned on exactly the kind of problems quantum simulation is aimed at.

The part I found most convincing: honesty as the actual contribution

What makes this paper worth reading isn't a new result — there isn't one, and it doesn't claim to have one. What makes it worth reading is that it's written by two people with every professional incentive to hype the field, choosing instead to write down exactly where the hard parts are, in public, with numbers attached.

The surface-code overhead example — a modest algorithm needing roughly a million physical qubits at today's error rates — is the single most useful number in the paper, because it converts a vague sense of "fault tolerance is hard" into a concrete distance you can actually reason about. The QAOA and DQI sections do the same job for algorithms: they replace "quantum computers can do optimization" with a precise map of exactly which narrow instances have been proven to work and which broad classes have been proven not to. And the repeated pattern of classical teams matching quantum simulation claims within weeks isn't presented as an embarrassment to paper over — it's presented as the actual scientific process working correctly, and as a standing challenge the next claimed advantage needs to survive.

The paper's closing move is also its most disarming: a 1945 John von Neumann quote about how the most important uses of any radically new computing technology are, by definition, the ones nobody can predict yet — because they're farthest removed from what's currently feasible. Eisert and Preskill apply that directly to quantum computing and essentially admit they can't tell you what the killer app will be. Given how carefully everything else in the paper is hedged, that admission reads as consistent rather than evasive.

What I'd want to see next

1. A standardized, adversarial benchmark for simulation-advantage claims. Given how reliably classical tensor-network teams have matched quantum simulation claims after the fact, the field would benefit from a claim only counting once it's survived a fixed challenge window against best-effort classical reproduction — rather than each new result getting its own round of post-hoc classical catch-up.
2. A sharper account of which qLDPC connectivity requirements are achievable on which hardware roadmaps. The paper flags qLDPC codes as a potentially order-of-magnitude overhead win, gated entirely on non-local connectivity. A concrete engineering roadmap — not just "atomic platforms are a better fit" — would make this gap's timeline much more legible.
3. More "proof pocket" mapping for near-term algorithms. The QAOA graph-family results are narrow but real. A systematic search for more such pockets — problem structures where a rigorous advantage can be proven even if the general case can't — seems like a higher-value use of near-term theory effort than more heuristic benchmarking.

The honest summary

Quantum computing has a real, demonstrated ability to do things classical computers find hard to simulate. It does not yet have a demonstrated ability to do something economically or scientifically useful that no classical approach can match or beat, cheaper. Those are different claims, and most of the public conversation about quantum advantage collapses them into one.

The road from here to there runs through four gaps, in order: mitigation has to give way to real correction, because mitigation's overhead grows exponentially and correction's doesn't; rudimentary correction has to become genuine fault tolerance, which today costs roughly a million physical qubits for a genuinely modest algorithm; near-term heuristics need to be replaced by algorithms with actual proofs behind them, because right now most of the exciting ones (QAOA chief among them) have been shown to lack a general advantage even where they're classically hard to simulate; and exploratory simulation needs to become credible simulation, which the paper argues is most plausible specifically for far-from-equilibrium dynamics, not equilibrium properties, because that's where classical methods are structurally weakest.

None of that is a reason to write off the field. It's a reason to be specific about what's actually been proven versus what's merely been demonstrated to be impressive, and specific about which gap any given headline is actually claiming to have crossed. Eisert and Preskill are optimistic about where this ends up. They're just refusing to pretend the road there is shorter than it is.

arXiv:2510.19928 — Mind the gaps: The fraught road to quantum advantage, Jens Eisert and John Preskill. Nine pages, four boxes, no new results, and probably the clearest single document on the actual state of quantum computing written this year.