Mind the gaps: The fraught road to quantum advantage

Jens Eisert; John Preskill

Source-linked AI summary

Mind the gaps: The fraught road to quantum advantage

Jens Eisert, John Preskill

arXiv:2510.19928v3Oct 22, 2025quant-phcond-mat.other

TL;DR

Quantum computing must bridge substantial gaps between NISQ devices and broadly useful FASQ machines, including transitions in error control, fault tolerance, algorithms, and simulation. This perspective identifies and organizes those hurdles, emphasizing technically reachable, classically hard, and useful applications. It concludes that early benefits will be primarily scientific, while credible quantum simulation may provide insights beyond classical methods despite continuing limits in demonstrating classically hard, quantumly easy tasks.

Problem
Substantial gaps separate today’s NISQ devices from FASQ machines, and it remains unclear when quantum computing will deliver broadly useful applications.
Method
The article organizes the path from NISQ to FASQ around four hurdles spanning error correction, fault tolerance, algorithms, and quantum simulation.
Results
The authors identify gradual progress toward scientific applications, with early benefits primarily scientific and quantum simulation offering potential insights beyond classical methods.
Takeaways & Limitations
Assessing and addressing these gaps clarifies a roadmap toward practical quantum utility and broadly useful quantum computing.

Abstract

from arXiv · show

Quantum computing is advancing rapidly, yet substantial gaps separate today's noisy intermediate-scale quantum (NISQ) devices from tomorrow's fault-tolerant application-scale quantum (FASQ) machines. We identify four related hurdles along the road ahead: (i) from error mitigation to active error detection and correction, (ii) from rudimentary error correction to scalable fault tolerance, (iii) from early heuristics to mature, verifiable algorithms, and (iv) from exploratory simulators to credible advantage in quantum simulation. Targeting these transitions will accelerate progress toward broadly useful quantum computing.

I. INTRODUCTION

Quantum computing has progressed from theory to capable NISQ hardware, but practical utility remains unachieved and the transition to FASQ faces major technical and knowledge gaps. The article frames a gradual roadmap centered on four hurdles and useful applications that are quantumly easy, classically hard, and practically useful.

NISQ computers now perform tasks too complex for leading conventional supercomputers, yet practically useful and economically viable quantum computations have not been achieved.
The NISQ-to-FASQ transition is likely arduous, expensive, prolonged, and highly uncertain because large-scale quantum computing poses a colossal engineering challenge.
The article highlights four gaps: error mitigation to correction, rudimentary correction to scalable fault tolerance, early heuristics to mature algorithms, and exploratory simulation to credible advantage.
Applications should combine efficiently reachable quantum resources, a persuasive case for greater classical runtime, and an intrinsically useful answer.
Early quantum-computing applications are expected to be primarily scientific, with broader economic impact following eventually.
Today’s NISQ machines execute fewer than 10^4 two-qubit operations, whereas broadly useful FASQ machines may require about 10^12 or more.

II. QUANTUM ERROR MITIGATION AND BEYOND

NISQ experiments demonstrate increasing circuit capability, while noise creates fundamental sampling costs that limit uncorrected circuits. Error mitigation extends usable circuit volume through postprocessing but becomes impractical as circuits deepen.

Current processors have demonstrated thousands of entangling operations, including 103-qubit, 40-layer random-circuit sampling and mirrored kicked Ising circuits with up to 5000 gates.
Under noise without quantum error correction, sampling overhead grows exponentially with circuit volume, fundamentally limiting informative results.
Quantum error mitigation samples related circuits and classically postprocesses outcomes, including through zero-noise extrapolation and probabilistic error cancellation.
QEM is essential when gate count times error per gate is about unity, but its sampling overhead scales unfavorably with circuit size.
QEM substantially increases accurately executable circuit volume but fails for very large circuits because sampling overhead grows exponentially.

Box 1 | Leading quantum-computing platforms and their trade-offs

Trapped ions, superconducting circuits, and neutral atoms have reached impressive control at the hundred-qubit scale, but their differing speed, connectivity, and engineering requirements shape applications and error-control strategies. Hardware progress may extend QEM and reduce fault-tolerance overhead, while QEM may enable marginal NISQ advantage.

Trapped ions: Trapped ions offer long coherence, high-fidelity operations, and non-local connectivity, but their entangling gates typically require tens of microseconds.
Superconducting circuits: Superconducting circuits provide entangling gates in tens of nanoseconds but use nearest-neighbor connectivity, a disadvantage relative to trapped-ion and neutral-atom platforms.
Neutral atoms: Neutral atoms provide flexible connectivity through reconfigurable geometries and sub-microsecond entangling gates, while motion, measurement latency, and reloading challenge deep circuits.
Cross-platform trade-offs: Across platforms, demonstrated circuits span tens to hundreds of qubits, with two-qubit gate error rates below 0.5% and approaching 0.1% in some cases.
Near-term reach: QEM may soon reach circuits with 10,000 or more gates and could support scientifically valuable simulations with width 100 and depth 100.
Prospects: Sufficiently low-error NISQ machines might achieve marginally useful quantum advantage, and QEM will remain useful in the FASQ era.
Error-control trade-offs: QEM overhead grows exponentially with circuit volume, whereas QEC overhead scales polylogarithmically but currently requires more physical qubits than available.

III. FROM PROTECTED QUANTUM MEMORY TO SCALABLE FAULT-TOLERANT QUANTUM COMPUTATION

Fault-tolerant quantum computing has a strong theoretical foundation, but scalable systems require major advances in hardware, error correction, logical gates, decoding, and architecture. Recent demonstrations and improving logical error rates mark progress, while billion-operation applications remain beyond current scale.

Theory and thresholds: If physical error probabilities lie below an accuracy threshold and errors are weakly correlated, fault-tolerant schemes can simulate L logical gates using O(L polylog L) physical gates.
Scaling requirements: Useful fault-tolerant computations may require billions of logical operations across thousands of logical qubits, demanding many more physical qubits, lower gate errors, or both.
Experimental progress: Logical error rates in a protected single-qubit memory improved by a factor Λ ≈2 as code distance increased from 3 to 5 and from 5 to 7.
Code and architecture trade-offs: Higher-rate codes reduce encoding overhead but require geometrically non-local syndrome measurements, favoring platforms with high connectivity such as Rydberg arrays and ion traps.
Demonstrations: Fault-tolerant demonstrations include 48 logical qubits on a 280-qubit Rydberg array and 12 logical qubits on a 56-qubit ion-trap device, but only a few syndrome-measurement rounds have been demonstrated.
Classical control: Fast real-time syndrome decoding is necessary because delayed decoding slows the logical clock, and decoding becomes harder as circuits and code blocks grow.

Box 2 | Why fault-tolerant quantum computing is expensive

Fault-tolerant quantum computing is expensive because protecting logical information requires substantial physical-qubit, processing, and engineering overhead. Although error correction can enable arbitrarily long reliable computations in principle, scaling from early devices to broadly useful machines remains uncertain and demanding.

Error correction: Quantum error correction encodes logical qubits into larger physical-qubit blocks or bosonic modes, enabling arbitrarily long reliable computations below an error threshold.This requires sufficiently weak error correlations in addition to physical error rates below threshold.
Error correction: Error correction repeatedly extracts noisy error syndromes, decodes them classically, applies recoveries, and uses mid-circuit measurement and feedforward for universal logical gates.Syndrome extraction must limit error propagation, while decoding must keep pace with the processor.
Resource overhead: For the surface code, each logical qubit requires n = d^2 physical qubits, while practical performance also depends on encoding rate, code distance, and implementation overhead.The surface code is attractive for early fault tolerance because it tolerates relatively strong physical noise and uses geometrically local two-dimensional operations.
Resource overhead: A logical error rate Plogical = 10^-11 at pphys = 10^-3 requires d ≈19 and roughly 10^3 physical qubits per logical qubit, or about 10^6 physical qubits in total.This example targets 10^3 logical qubits running for 10^8 time steps and is far beyond current device scale.
Scaling challenge: The large separation between physical and logical resources makes the transition from early error-corrected devices to scalable fault tolerance a daunting challenge.Reaching future machines may require advancing from hundreds to millions of physical qubits and improving encodings, hardware, and systems engineering.
Hardware uncertainty: The best hardware modality for scaling to broadly useful quantum computers remains unknown, despite progress in superconducting circuits, ion traps, and Rydberg tweezer arrays.Other approaches, including photonic and spin qubits, may become more competitive as the field develops.
Scaling challenge: Early fault-tolerant megaquop machines, capable of reliably executing one million or more quantum operations, could perform tasks beyond classical, NISQ, and analog quantum devices.Experience with these systems is expected to guide scaling toward more capable machines.

IV. FROM NEAR-TERM QUANTUM HEURISTICS TO MATURE QUANTUM ALGORITHMS

The path from near-term quantum heuristics to mature algorithms remains unsettled: demonstrations can exceed classical simulation without practical utility, while proposed optimization and learning advantages face substantial limitations. Progress includes new algorithmic paradigms and rigorous results in carefully chosen settings, but broad advantage is not established.

Near-term heuristics: NISQ quantum utility efforts have focused largely on variational quantum algorithms for potential applications in combinatorial optimization and machine learning.Quantum advantage over the best classical heuristics on practical problems remains an open question.
Optimization: Grover’s algorithm offers a quadratic speedup for exhaustive or heuristic search, but the benefit applies mainly to very large instances and may not become valuable for many decades.The slower clock speed expected for FASQ technology further limits near-term relevance.
New paradigms: Decoded quantum interferometry maps some seemingly hard problems to classically easy decoding, providing an efficient algorithm for optimal polynomial intersection.Its potential advantage for structured problems remains under investigation, while no advantage is reported for unstructured combinatorial optimization.

Box 3 | Why near-term quantum advantage is hard to establish

Near-term quantum advantage is difficult to establish because classical simulation can remain competitive, algorithmic training can be obstructed, and many demonstrated advantages rely on contrived or carefully selected problems. The paper surveys both these barriers and constructive results, while emphasizing that useful end-to-end advantages remain unresolved.

Evidence standards: Random circuit sampling can enter regimes infeasible for direct classical simulation, but it is mainly useful for benchmarking rather than practical applications.Hardness claims are asymptotic and rely on stringent distributional-closeness notions, while validation efforts have improved classical simulation methods.
Algorithmic obstacles: Variational quantum algorithms use hybrid quantum-classical optimization, but barren plateaus and numerous local minima can impede training.Reducing circuit expressivity can alleviate barren plateaus while making circuits easier to simulate classically.
Constructive strategies: Warm starts and hybrid workflows offer constructive strategies for improving variational optimization despite unresolved practical advantage.Classical heuristics can inform initial parameters or states, while classical computations can guide searches for nearby lower-cost states.
Constructive strategies: Rigorous proof pockets include concentrated optimal QAOA parameters, single-round QAOA advantages under suitable symmetries, and favorable cut fractions for certain graph families.Other work reduces expensive gradient estimation through dissipative optimization procedures.
Quantum machine learning: Quantum advantage has been rigorously established for some carefully chosen learning tasks, but these models are highly contrived and offer limited guidance for practical applications.Reported tasks include generative modeling, density modeling, binary classification, and identification.
Quantum machine learning: End-to-end quantum machine-learning advantage remains largely unknown because speedups are confined to cherry-picked examples and robust advantages for large instance families remain elusive.High data-loading costs and the uncertain efficiency limits of classical machine learning further complicate assessment.
Longer-term algorithms: Known FASQ algorithms include quantum linear systems methods for sparse, well-conditioned matrices, but useful real-life applications remain challenging.Applications to linear partial differential equations are possible using finite-difference and spectral methods.

V. TOWARD CREDIBLE QUANTUM ADVANTAGE IN QUANTUM SIMULATION

Quantum simulation may offer its most credible route to quantum advantage in nonequilibrium dynamics, where classical methods are less effective. Yet establishing advantage for physically relevant systems remains difficult, and near-term simulations may be scientifically useful even without high accuracy.

Ground-state problems for particular physically interesting Hamiltonians remain difficult to establish as both classically hard and quantumly easy.
Quantum simulations may provide abundant training data that enhances classical AI predictions for strongly correlated matter not yet observed in laboratories.
Classical heuristics often succeed for equilibrium properties, whereas nonequilibrium dynamics offers a more plausible route to quantum advantage.Rapidly growing entanglement can make classical descriptions inefficient.
A competition is increasingly under way between quantum teams running simulations and classical teams seeking to match or surpass them.Classical approaches include tensor-network, neural-network, and Pauli-path methods.
103 qubits were used to compute out-of-time-order correlators on a Google superconducting processor in a regime arguably hard to simulate classically.The result illustrates state-of-the-art NISQ quantum simulation, though quantitative usefulness will likely require fault tolerance.

Box 4 | Where quantum simulation may achieve credible advantage

Quantum simulation spans digital and analog platforms and targets equilibrium properties or nonequilibrium dynamics. The strongest prospects for credible advantage lie in dynamics, while scientific value is clearer than economic value and important platform limitations remain.

Scope and platforms: Quantum simulation can target static equilibrium properties or far-from-equilibrium dynamics using digital gate-based computers or analog programmable-Hamiltonian platforms.
Equilibrium versus dynamics: Classical methods often perform well for physically relevant equilibrium problems, particularly in low dimensions, making ground-state advantage difficult to establish.Quantum ground-state algorithms exist but typically depend on suitable initial states.
Equilibrium versus dynamics: Nonequilibrium dynamics is a more promising route because classical methods are generally less effective and growing entanglement can make classical descriptions inefficient.
Simulation workflow: Quantum simulation requires preparing an initial state, evolving under a target Hamiltonian, and repeatedly measuring observables to estimate expectation values.Digital methods may have favorable asymptotic scaling, but practical implementation can require deep circuits.
Limits of advantage claims: Complexity-theoretic mappings show that carefully constructed local-Hamiltonian models can be classically hard, but do not establish hardness for naturally occurring physical Hamiltonians.
Analog platforms: Analog simulators avoid some qubit-simulation overhead and are powerful near-term tools for scientific exploration, especially quantum dynamics.
Analog platforms: Imperfect control can make an analog simulator’s laboratory Hamiltonian differ significantly from the target system, though Hamiltonian learning may partially mitigate this issue.
Scientific and economic value: Quantum simulations are expected to yield scientific insights beyond classical methods, but their economic value remains less clear.Expected impact is described as arriving first in condensed matter physics, then chemistry and other fields.

VI. OUTLOOK

The paper argues that progress from NISQ devices to broadly useful FASQ machines requires attention to practical quantum advantage and scalable fault tolerance. It expects useful applications to expand gradually as quantum technology advances.

The paper highlights scalable fault-tolerant quantum computers and practical quantum advantages over conventional information processing as central challenges.
The portfolio of useful applications is likely to expand gradually through the megaquop, gigaquop, and teraquop regimes.
Predicting quantum technology’s long-term impact is difficult because limited imagination constrains efforts to envision its future benefits.The history of classical computing is offered as evidence that future information technology is hard to predict.