The cost of simulating classically tractable quantum circuits and dynamics
Abstract
Determining whether a quantum evolution can be efficiently simulated classically is central to understanding the boundary between classical and quantum computation. However, polynomial-time simulability is an asymptotic statement, and does not by itself determine whether the (quantum-inspired) classical simulation is actually practical. Indeed, different polynomial scalings can lead to vastly different computational costs, particularly when expensive preprocessing or quantum data acquisition is required. In this work, we ask whether classically simulable quantum dynamics are in practice more resource-efficient to simulate classically than to execute directly on quantum hardware. We analyze this question using three resource metrics, quantum sample, quantum time, and classical time complexity, for several widely studied classically simulable circuit families. Using representative hardware-level estimates, we identify regimes in which quantum simulation can be faster despite the existence of a polynomial-time classical algorithm, as well as regimes in which classical simulation remains more efficient. At the same time, the large quantum sampling cost needed to characterize unknown input states can make this polynomial-time classical simulation prohibitively expensive with current cloud-based hardware access prices. Ultimately, our work indicates that guarantees of classical simulability with polynomial resources alone are insufficient to determine the preferred implementation.
Related
- The cost of classically simulating quantum communication is as high as it could be
- Collective Dynamics in Spin Chains with Constrained Dissipation: Classically Fragile but Quantum Robust
- QuWARP: A Workload-Aware Reuse Planner for simulating Quantum Circuits
- Simulating and sampling from quantum circuits with 2D tensor networks
- Compile-Time Simplification of Classically Controlled Operations in Dynamic Circuits
BibTeX
@misc{chang2026cost,
title = {{The cost of simulating classically tractable quantum circuits and dynamics}},
author = {Su Yeon Chang and Supanut Thanasilp and Zoë Holmes and M. Cerezo},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.11847},
eprint = {2609.11847},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.11847},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The cost of simulating classically tractable quantum circuits and dynamics
AU - Su Yeon Chang
AU - Supanut Thanasilp
AU - Zoë Holmes
AU - M. Cerezo
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2609.11847
UR - https://arxiv.org/abs/2609.11847
AB - Determining whether a quantum evolution can be efficiently simulated classically is central to understanding the boundary between classical and quantum computation. However, polynomial-time simulability is an asymptotic statement, and does not by itself determine whether the (quantum-inspired) classical simulation is actually practical. Indeed, different polynomial scalings can lead to vastly different computational costs, particularly when expensive preprocessing or quantum data acquisition is required. In this work, we ask whether classically simulable quantum dynamics are in practice more resource-efficient to simulate classically than to execute directly on quantum hardware. We analyze this question using three resource metrics, quantum sample, quantum time, and classical time complexity, for several widely studied classically simulable circuit families. Using representative hardware-level estimates, we identify regimes in which quantum simulation can be faster despite the existence of a polynomial-time classical algorithm, as well as regimes in which classical simulation remains more efficient. At the same time, the large quantum sampling cost needed to characterize unknown input states can make this polynomial-time classical simulation prohibitively expensive with current cloud-based hardware access prices. Ultimately, our work indicates that guarantees of classical simulability with polynomial resources alone are insufficient to determine the preferred implementation.
ER -