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.
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.
Magic states are essential for universal quantum computation and are widely viewed as a key source of quantum advantage, yet in realistic devices they are inevitably noisy. In this work, we characterize how noise on injected magic resources changes the classical simulability of quantum circuits and when it induces a transition from classically intractable behavior to efficient classical simulation. We adopt a resource-centric noise model in which only the injected magic components are noisy, while the baseline states, operations, and measurements belong to an efficiently simulable family. Within this setting, we develop an approximate classical sampling algorithm with controlled error and prove explicit noise-dependent conditions under which the algorithm runs in polynomial time. Our framework applies to both qubit circuits with Clifford baselines and fermionic circuits with matchgate baselines, covering representative noise channels such as dephasing and particle loss. We complement the analysis with numerical estimates of the simulation cost, providing concrete thresholds and runtime scaling across practically relevant parameter regimes.
Quantum resource theory has sharpened our understanding of the intrinsic complexity of quantum systems, particularly their classical simulability. However, it remains unclear which quantum resource governs the classical learnability of quantum circuits, especially beyond the regime of efficient classical simulation. Here we close this knowledge gap by studying the expectation-value functions of families of tunable quantum circuits, with many applications in digital quantum simulation, quantum metrology, and quantum-system characterization. Specifically, we introduce a new resource measure, the dynamical stabilizer entropy (\DSE), which quantifies how broadly an expectation-value function is distributed across its frequency modes. By relating \DSE to operator stabilizer entropy, we establish a computational phase diagram that compares classical simulators with quantum-data-assisted classical surrogates. We first determine the \DSE-dependent learnability boundary of this diagram by deriving bounds on the sample complexity and runtime of classical surrogates, and by developing a \DSE-guided surrogate. We then complete the diagram by proving, under standard complexity-theoretic assumptions, the existence of circuit families that can be efficiently learned by this surrogate but cannot be efficiently emulated from their circuit descriptions alone. Numerical experiments on random and structured circuits with up to 80 qubits support the predicted \DSE-dependent computational landscape. These results establish a quantitative resource-theoretic framework for delineating the boundary between classical simulation and learning, motivate resource measures linking quantum resources to learnability, and guide the design of learning-based algorithms for scalable quantum systems beyond the reach of direct classical simulation.
How well can quantum computers simulate classical dynamical systems? There is increasing effort in developing quantum algorithms to efficiently simulate dynamics beyond Hamiltonian simulation, but so far exact resource estimates are not known. In this work, we provide two significant contributions. First, we give the first non-asymptotic computation of the cost of encoding the solution to general linear ordinary differential equations into quantum states – either the solution at a final time, or an encoding of the whole history within a time interval. Second, we show that the stability properties of a large class of classical dynamics allow their fast-forwarding, making their quantum simulation much more time-efficient. From this point of view, quantum Hamiltonian dynamics is a boundary case that does not allow this form of stability-induced fast-forwarding. In particular, we find that the history state can always be output with complexity O(T1/2) for any stable linear system. We present a range of asymptotic improvements over state-of-the-art in various regimes. We illustrate our results with a family of dynamics including linearized collisional plasma problems, coupled, damped, forced harmonic oscillators and dissipative nonlinear problems. In this case the scaling is quadratically improved, and leads to significant reductions in the query counts after inclusion of all relevant constant prefactors.
Efficient classical simulation has matured to a critical component of the quantum computing stack, driving hardware validation, algorithm design, benchmarking, and the study of structured quantum dynamics. Lie-algebraic simulation (g-sim) offers a compelling approach: it represents Heisenberg-picture dynamics in the adjoint space whose dimension is set by the dynamical Lie algebra (DLA) governing the circuit, enabling efficient simulation of expectation values whenever the DLA grows only polynomially with system size. Despite this promise, existing applications of g-sim have been confined to free-fermionic settings. It has therefore remained unclear if the method can be applied to other structured circuit families, especially when their generators have large Pauli expansions, and hence whether Lie-algebraic simulability presents a genuinely broader paradigm than free fermions. In this work, we resolve this question by identifying additional non-trivial families of polynomial-dimensional DLAs and introducing symmetry-adapted bases that make the required adjoint-space preprocessing tractable. In particular, we develop an explicit Pauli orbit representation for permutation-equivariant dynamics, enabling efficient processing of cubic-dimensional algebras despite exponential Pauli support, and a modified generalized Gell--Mann representation for bounded Hamming-weight (U(1)-equivariant) dynamics, yielding polynomial simulation costs on fixed excitation sectors. Together with streamlined routines for free-fermionic algebras, these constructions significantly broaden the practical scope of g-sim as a unifying simulation tool for structured quantum circuits. Numerical benchmarks confirm favorable preprocessing scaling and validate large-scale proof-of-concept simulations beyond the reach of state-vector simulation.
Verifying quantum advantage for practical problems, particularly the ground state energy estimation (GSEE) problem, is one of the central challenges in quantum computing theory. For that purpose, dequantization algorithms play a central role in providing a clear theoretical framework to separate the complexity of quantum and classical algorithms. However, existing dequantized algorithms typically rely on sampling procedures, leading to prohibitively large computational overheads and hindering their practical implementation on classical computers. In this work, we propose a tensor network-based dequantization framework for GSEE that eliminates the sampling process while preserving the asymptotic complexity of prior dequantized algorithms. In our formulation, the overhead arising from sampling is replaced by the growth of the bond dimension required to represent Chebyshev vectors as tensor network states. Consequently, physical structure, such as entanglement and locality, is naturally reflected in the computational cost. By combining this approach with tensor network approximations, such as Matrix Product States (MPS), we construct a practical dequantization algorithm that is executable within realistic computational resources. Numerical simulations demonstrate that our method can efficiently construct high-degree polynomials up to d=104 for Hamiltonians with up to 100 qubits, explicitly revealing the crossover between classically tractable and quantum advantaged regimes. These results indicate that tensor network-based dequantization provides a crucial tool toward the rigorous, quantitative verification of quantum advantage in realistic many-body systems.
Quantum computational supremacy arguments, which describe a way for a quantum computer to perform a task that cannot also be done by a classical computer, typically require some sort of computational assumption related to the limitations of classical computation. One common assumption is that the polynomial hierarchy ( P H ) does not collapse, a stronger version of the statement that P ≠ N P , which leads to the conclusion that any classical simulation of certain families of quantum circuits requires time scaling worse than any polynomial in the size of the circuits. However, the asymptotic nature of this conclusion prevents us from calculating exactly how many qubits these quantum circuits must have for their classical simulation to be intractable on modern classical supercomputers. We refine these quantum computational supremacy arguments and perform such a calculation by imposing fine-grained versions of the non-collapse conjecture. Our first two conjectures poly3-NSETH( a ) and per-int-NSETH( b ) take specific classical counting problems related to the number of zeros of a degree-3 polynomial in n variables over F 2 or the permanent of an n × n integer-valued matrix, and assert that any non-deterministic algorithm that solves them requires 2 c n time steps, where c ∈ { a , b } . A third conjecture poly3-ave-SBSETH( a ′ ) asserts a similar statement about average-case algorithms living in the exponential-time version of the complexity class S B P . We analyze evidence for these conjectures and argue that they are plausible when a = 1 / 2 , b = 0.999 and a ′ = 1 / 2 .Imposing poly3-NSETH(1/2) and per-int-NSETH(0.999), and assuming that the runtime of a hypothetical quantum circuit simulation algorithm would scale linearly with the number of gates/constraints/optical elements, we conclude that Instantaneous Quantum Polynomial-Time (IQP) circuits with 208 qubits and 500 gates, Quantum Approximate Optimization Algorithm (QAOA) circuits with 420 qubits and 500 constraints and boson sampling circuits (i.e. linear optical networks) with 98 photons and 500 optical elements are large enough for the task of producing samples from their output distributions up to constant multiplicative error to be intractable on current technology. Imposing poly3-ave-SBSETH(1/2), we additionally rule out simulations with constant additive error for IQP and QAOA circuits of the same size. Without the assumption of linearly increasing simulation time, we can make analogous statements for circuits with slightly fewer qubits but requiring 10 4 to 10 7 gates.