The cost of simulating classically tractable quantum circuits and dynamics

• URL: http://arxiv.org/abs/2609.11847v1
• Date: Thu, 10 Sep 2026 17:34:39 GMT
• Title: The cost of simulating classically tractable quantum circuits and dynamics
• Abstract summary: simulability is a statement, and does not by itself determine whether the (quantum-inspired) classical simulation is actually practical. Indeed, different scalings can ask whether classically simulable quantum dynamics are in practice more resource-efficient to simulate classically than to execute directly on quantum hardware.<n>Our work indicates that guarantees of classical simulability with resources alone are insufficient to determine the preferred implementation.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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 papers

• Learnable yet not simulable: a quantum resource theory of learning models [57.695822250391906]
  It remains unclear which quantum resource governs the classical learnability of quantum circuits.<n>We study the expectation-value functions of families of tunable quantum circuits.<n>These results establish a quantitative resource-theoretic framework for delineating the boundary between classical simulation and learning.
  arXiv  Detail & Related papers  (2026-08-03T14:48:03Z)
• Polyhedral Classical Simulators for Quantum Computation [0.0]
  We introduce polyhedral classical simulators, a framework for classical simulation grounded in polyhedral geometry.<n>We show how this framework unifies and extends existing simu- lation methods while at the same time providing a geometric roadmap for pushing the boundary of efficient classical simulation further.
  arXiv  Detail & Related papers  (2025-10-08T20:55:55Z)
• Evaluating classical simulations with a quantum processor [0.5592394503914488]
  Scaling predictions are based on local structure and assumptions.<n>We use a quantum annealing processor to produce a ground truth for evaluating classical tensor-network methods.<n>Our results demonstrate that the virtuous cycle of competition between classical and quantum simulations can lend insight in both directions.
  arXiv  Detail & Related papers  (2025-08-21T17:55:53Z)
• On the quantum computational complexity of classical linear dynamics with geometrically local interactions: Dequantization and universality [3.3083504598202733]
  A quantum algorithm offers an exponential speedup over any classical algorithm in simulating classical dynamics with long-range interactions.<n>Many real-world classical systems, such as those arising from partial differential equations, exhibit only local interactions.<n>This work offers new insights into the complexity of classical dynamics governed by partial differential equations.
  arXiv  Detail & Related papers  (2025-05-15T16:06:22Z)
• Operationally classical simulation of quantum states [41.94295877935867]
  A classical state-preparation device cannot generate superpositions and hence its emitted states must commute.<n>We show that no such simulation exists, thereby certifying quantum coherence.<n>Our approach is a possible avenue to understand how and to what extent quantum states defy generic models based on classical devices.
  arXiv  Detail & Related papers  (2025-02-03T15:25:03Z)
• Efficient quantum-enhanced classical simulation for patches of quantum landscapes [0.0]
  We show that it is always possible to generate a classical surrogate of a sub-region of an expectation landscape produced by a parameterized quantum circuit.<n>We provide a quantum-enhanced classical algorithm which, after simple measurements on a quantum device, allows one to classically simulate approximate expectation values of a subregion of a landscape.
  arXiv  Detail & Related papers  (2024-11-29T18:00:07Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [62.46800898243033]
  Recent progress in quantum learning theory prompts a question: can linear properties of a large-qubit circuit be efficiently learned from measurement data generated by varying classical inputs?<n>We prove that the sample complexity scaling linearly in $d$ is required to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d.<n>We propose a kernel-based method leveraging classical shadows and truncated trigonometric expansions, enabling a controllable trade-off between prediction accuracy and computational overhead.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Tensor Networks or Decision Diagrams? Guidelines for Classical Quantum Circuit Simulation [65.93830818469833]
  tensor networks and decision diagrams have independently been developed with differing perspectives, terminologies, and backgrounds in mind. We consider how these techniques approach classical quantum circuit simulation, and examine their (dis)similarities with regard to their most applicable abstraction level. We provide guidelines for when to better use tensor networks and when to better use decision diagrams in classical quantum circuit simulation.
  arXiv  Detail & Related papers  (2023-02-13T19:00:00Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model [68.8204255655161]
  Quantum algorithms for quantum dynamics simulations are traditionally based on implementing a Trotter-approximation of the time-evolution operator. variational quantum algorithms have become an indispensable alternative, enabling small-scale simulations on present-day hardware. We show that, despite providing a clear reduction of quantum gate cost, the variational method in its current implementation is unlikely to lead to a quantum advantage.
  arXiv  Detail & Related papers  (2021-08-09T18:00:05Z)
• Error mitigation and quantum-assisted simulation in the error corrected regime [77.34726150561087]
  A standard approach to quantum computing is based on the idea of promoting a classically simulable and fault-tolerant set of operations. We show how the addition of noisy magic resources allows one to boost classical quasiprobability simulations of a quantum circuit.
  arXiv  Detail & Related papers  (2021-03-12T20:58:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.