⚛️ quantum physics

The cost of simulating classically tractable quantum circuits and dynamics

This paper demonstrates that the existence of polynomial-time classical algorithms for simulating certain quantum circuits does not guarantee practical efficiency, as specific regimes involving hardware costs, sampling overheads, and preprocessing can make direct execution on quantum hardware faster than classical simulation.

Original authors: Su Yeon Chang, Supanut Thanasilp, Zoë Holmes, M. Cerezo

Published 2026-09-11

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Su Yeon Chang, Supanut Thanasilp, Zoë Holmes, M. Cerezo

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the race to build useful quantum computers, scientists face a fundamental question: when a problem can be solved by a quantum machine, is it actually better to let the machine do the work, or to try to solve it on a regular computer? Quantum computers are famous for their ability to process information in ways that seem impossible for classical machines, but they are also fragile, expensive, and difficult to operate. For decades, researchers have known that certain types of quantum circuits—specific arrangements of quantum gates—can be simulated on ordinary computers without needing a quantum device at all. These are the "classically tractable" circuits, and for a long time, the assumption was that if a computer could simulate them, it should. The logic was simple: why pay for a rare, difficult-to-access quantum computer when a standard laptop can do the job?

However, this assumption relied on a mathematical idea called "polynomial time," which describes how the time needed to solve a problem grows as the problem gets bigger. While this tells us that a solution exists in theory, it does not tell us how long it will actually take in practice. A calculation that grows slowly enough to be considered "efficient" in math textbooks might still take years to run on a real machine if the starting numbers are large enough. Furthermore, simulating a quantum system on a classical computer often requires a massive amount of data about the starting state of the system, which itself must be gathered from the quantum world. This new research asks a more practical question: if we know a quantum process can be simulated classically, is it actually faster, cheaper, or more efficient to do so than to just run the process on the quantum hardware itself?

The researchers, working across several institutions including Los Alamos National Laboratory and the European Organization for Nuclear Research, set out to answer this by comparing two distinct paths. The first path is the direct approach: they take a quantum circuit, prepare the necessary quantum state, run the evolution on actual quantum hardware, and measure the result. This is the "Quantum Simulation." The second path is the "Classical Simulation," where they use a clever mathematical shortcut to replace the quantum evolution with a calculation on a standard computer. Crucially, they recognized that this shortcut often requires an initial step where they must gather information about the quantum state using the quantum hardware anyway. They analyzed several specific families of circuits that are known to be classically simulable, including those used in quantum chemistry and machine learning, and tracked three specific costs: how many times the quantum hardware had to be accessed, how long the quantum circuit took to run, and how long the classical computer took to crunch the numbers.

Their findings reveal that the answer is not a simple "yes" or "no." In many cases, the classical simulation is indeed the better choice, but only if the same circuit is run many times. If a researcher needs to test a quantum circuit just once or twice, the time and money spent gathering the initial data for the classical shortcut often outweigh the cost of simply running the circuit on the quantum computer. The classical method acts like a heavy investment: you pay a large upfront cost to build a model, but then you can run thousands of variations very cheaply. The quantum method has no upfront cost, but you pay a small fee every single time you run it. The researchers found that for certain types of circuits, the "break-even point" where the classical method becomes cheaper happens only after hundreds or thousands of runs. For other types of circuits, the classical method is so computationally heavy that the quantum computer remains faster and cheaper even for large numbers of runs.

One of the most surprising discoveries was that the cost of the classical simulation is not just about the speed of the computer, but also about the price of accessing the quantum hardware. In the current era of cloud-based quantum computing, users often pay per shot, or per measurement. The researchers calculated that for some circuits, the initial data gathering required for the classical simulation could cost more than running the entire experiment on the quantum computer, simply because the quantum hardware is so expensive to access right now. This creates a scenario where a method that is theoretically "efficient" is actually prohibitively expensive in the real world. The study also highlighted that the complexity of the problem matters immensely. For circuits involving simple interactions, the classical shortcut works well. But as the interactions become more complex, the classical computer's workload explodes, making the quantum hardware the more practical choice despite its reputation for being difficult to use.

The paper concludes that knowing a quantum process is "classically simulable" is not enough to decide how to run it. The decision depends entirely on the specific details of the problem: how many times the circuit needs to be run, the complexity of the interactions, and the current cost of accessing quantum hardware. The researchers emphasize that the boundary between what a quantum computer can do and what a classical computer can do is not a fixed line, but a shifting landscape that changes based on resources and scale. They suggest that for now, the existence of a classical algorithm does not automatically mean we should stop using quantum hardware. Instead, scientists must weigh the upfront costs of data gathering against the recurring costs of quantum access. In the end, the most efficient path is not determined by a mathematical proof alone, but by a careful accounting of time, money, and the specific demands of the task at hand.

Technical Summary: The Cost of Simulating Classically Tractable Quantum Circuits and Dynamics

Problem Statement
The central problem addressed in this work is the practical efficiency of simulating quantum evolutions that are theoretically classically simulable. While it is established that certain structured quantum processes (e.g., Clifford circuits, free-fermionic dynamics, low-entanglement systems) admit polynomial-time classical algorithms, polynomial-time complexity is an asymptotic statement. It does not inherently determine whether a classical simulation is practically preferable to direct execution on quantum hardware.

The authors identify a critical gap: different polynomial scalings can lead to vastly different computational costs, particularly when expensive preprocessing or quantum data acquisition is required. The paper asks: If a quantum evolution is classically simulable, is it actually more resource-efficient to simulate it classically than to run it on quantum hardware? This question is motivated by the fact that classical simulability is often an asymptotic guarantee that may not hold at finite system sizes, especially when the cost of acquiring information about unknown input states is factored in.

Methodology
The authors compare two computational routes for estimating expectation values $f_U(\rho, O) = \text{Tr}[U\rho U^\dagger O]$ for $T$ circuit instances:

Quantum Simulation (QS): Direct execution on quantum hardware. The quantum device prepares the state, evolves it, and measures it. The classical computer processes outcomes and updates parameters.
Classical Simulation (CS): A "quantum-inspired" approach where the quantum evolution is replaced by a polynomial-time classical computation (a surrogate). Crucially, if the initial state $\rho$ is unknown, CS may require an initial quantum data-acquisition stage (e.g., via classical shadows or tomography) to characterize $\rho$ . This data is then reused for subsequent circuit instances.

The comparison utilizes three resource metrics:

Quantum Sample Complexity: The number of copies of $\rho$ (circuit shots) required.
Quantum Time Complexity: The circuit depth required for a single sample.
Classical Time Complexity: The number of elementary classical operations.

The analysis covers seven families of classically simulable circuits:

Clifford circuits
Shallow local circuits (Hardware Efficient Ansatz)
Matchgate (free-fermionic) circuits
$S_n$ -equivariant circuits
$U(1)$ -equivariant circuits
Quantum Convolutional Neural Networks (QCNNs)
ADAPT-VQE circuits

For each family, the authors derive the resource complexities for both QS and CS, distinguishing between one-time costs (e.g., constructing a surrogate, acquiring state data) and per-instance costs (e.g., evaluating the surrogate for new parameters). They utilize frameworks such as Gottesman-Knill simulation, g-sim (Lie-algebraic simulation), Pauli Propagation, and Majorana Propagation.

Key Results
The paper translates theoretical complexity bounds into estimated wall-clock times and monetary costs using representative hardware specifications (IonQ, IBM, Google, Rigetti, Quantinuum) and cloud pricing models.

Polynomial Simulability $\neq$ Practical Advantage: The existence of a polynomial-time classical algorithm does not guarantee that CS is faster or cheaper than QS at finite system sizes. The relative advantage depends heavily on the number of circuit instances ( $T$ ) and the specific polynomial degree of the dominant cost.
Trade-off Between One-Time and Per-Instance Costs:
- QS incurs sampling and circuit-execution costs for every instance.
- CS often incurs a large one-time cost for quantum data acquisition and preprocessing, followed by a lower per-instance classical evaluation cost.
- A "crossover" point exists where CS becomes more efficient only after $T$ is sufficiently large to amortize the initial overhead.
Impact of Input State Knowledge:
- If the input state is known classically (e.g., Hartree-Fock in ADAPT-VQE), CS can be significantly faster and cheaper, as it avoids quantum data acquisition entirely.
- If the input state is unknown, the cost of characterizing it (via shadows) can make CS prohibitively expensive, even if the subsequent simulation is polynomial.
Fermionic Locality and System Size: For Matchgate circuits, the fermionic locality ( $\kappa$ ) of the observable drastically affects CS costs. Higher $\kappa$ (e.g., $\kappa=6$ ) increases the classical tensor-contraction cost ( $O(Tn^7)$ ) and the shadow sample complexity, often making QS faster than CS for moderate system sizes, despite CS having polynomial asymptotic scaling.
Wall-Clock vs. Monetary Cost: The approach that is faster in wall-clock time is not necessarily the least expensive.
- CS may reduce repeated quantum execution time but require a large one-time quantum data-acquisition budget.
- For small $T$ , QS is often cheaper; for large $T$ , CS may become cheaper, but the crossover point varies by hardware platform and circuit family.
Memory Constraints: The paper highlights that memory requirements (space complexity) can be a more severe bottleneck than time. For example, storing classical shadow data or intermediate tensors for large systems can require terabytes of memory, imposing a hard physical constraint that runtime estimates do not capture.

Significance and Claims
The paper concludes that guarantees of classical simulability with polynomial resources alone are insufficient to determine the preferred implementation.

Distinct Notions of Efficiency: Classical simulability, wall-clock advantage, and monetary advantage constitute distinct concepts. A method can be polynomially simulable but practically intractable due to large constant factors, high-degree polynomials, or expensive one-time overheads.
Context Dependence: The choice between QS and CS depends on the specific problem parameters: the number of circuit instances ( $T$ ), the knowledge of the input state, the locality of the observable, and the specific hardware access costs.
Practical Guidance: The work provides a framework for evaluating when a classically simulable quantum computation should actually be run classically. It suggests that for problems with unknown input states or high fermionic locality, direct quantum execution may remain the more resource-efficient option despite the existence of classical algorithms.

The authors emphasize that their analysis is a finite-resource comparison rather than a definitive hardware benchmark, noting that factors like error mitigation, fault tolerance, and parallelization could shift these quantitative crossovers. However, the fundamental mechanism—that one-time overheads vs. repeated sampling costs dictate practical efficiency—remains robust.

More like this