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 are established.
Abstract
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.
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.
S. Chang, Supanut Thanasilp, Zoe Holmes et al.· 0 citations
Classical simulability of quantum circuits plays a central role in characterizing and quantifying quantum computational advantage. Typically, the presence of non-Clifford gates introduces an exponential runtime overhead for classically estimating expectation values of observables. In this work, we introduce an efficient simulation framework that integrates the sum-over-Clifford method with quasi-probability-based stabilizer simulation to directly estimate expectation values. To optimize efficiency, we incorporate a circuit-adaptive reduction via variance estimation protocol, which terminates simulations once an empirical confidence bound is sufficient to guarantee the prescribed error tolerance. Our method circumvents overly conservative Hoeffding's inequality, thereby reducing the dependence on the gate-wise stabilizer extent from quadratic to linear in the low-variance regime, while maintaining the same space complexity as previous approaches. We explicitly prove the sample-complexity reduction for random quantum circuits and T-doped Clifford circuits and also empirically validate these advantages in the quantum approximate optimization algorithm and quantum kernel method.
Yunseo Hwang, Giwon Song, Kyoung Keun Park et al.· 0 citations
As IQP circuits produce remarkably low intermediate magic relative to phase-randomised states with the same sampling distributions, this renders IQP-based quantum generative models as promising candidates for resource-efficient demonstrations of quantum advantage on early fault-tolerant architectures.
It is shown that gradient-based PQCs can exhibit improved performance on unseen data as model size increases, displaying the phenomenon of double descent, which contrasts with the traditional view that larger models lead to degraded generalization.
Marie C. Kempkes, Elies Gil-Fuster, Carlos Bravo-Prieto et al.· arXiv.org· 0 citations
This paper develops a resource-bounded framework for evaluating practical controllability in open quantum systems using a trained graybox response model. Rather than treating controllability as a binary property of an idealised Hamiltonian model, the proposed approach evaluates the best-achievable process fidelity over a finite, hardware-realisable pulse family under explicit control constraints. The graybox model retains the known coherent dynamics while learning control-dependent open-system distortions from pulse-response data. The resulting surrogate predictions are used to reconstruct the implemented processes and compare them with Haar-random target gates. Practical controllability is then characterised through the distribution of best-achievable infidelities and an area-based summary metric. The framework is demonstrated for a driven qubit under closed-system, classical-noise, and combined quantum-plus-classical-noise dynamics, with pulse amplitude and inverse Gaussian width used as the control-resource coordinates. The results show how finite control resources and open-system noise jointly constrain the gate performance attainable by the chosen pulse family.
Yule Mayevsky, Akram Youssry, Alberto Peruzzo· 1 citation
We introduce Coherent Quantum Learning (CQL), a training framework for quantum learning models in which the model parameters are quantum degrees of freedom evolved under a Hamiltonian that encodes the loss function. Current quantum machine learning retains classical optimization: parameters are updated by a classical outer loop using gradient estimates from measurements, and quantum coherence has no role in the training dynamics, just as in any classical treatment of the same problem. In the quantum case, a parameter register initialized in superposition evolves unitarily, and probability amplitude concentrates near low-loss configurations through interference, without gradient computation or classical feedback. We give an explicit construction using block encodings and Hamiltonian simulation, applicable to arbitrary parameterized circuits. Numerical experiments on binary classification and interferometric phase estimation confirm that the evolved distribution peaks at the optimal parameters, matching gradient-based performance. The construction is compatible in principle with fault-tolerant implementations and extends to batched training via sequential Hamiltonian evolution.
Ignacio B. Acedo, Javier Gonzalez-Conde, Pablo Rodriguez-Grasa et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
