We investigate the relationship between two distinct classical approaches to quantum systems: direct simulation from a classical description and sample-based learning from measurement data. While both tasks ultimately aim to reproduce Born-rule statistics, complexity-theoretic results suggest that simulability and learnability need not coincide in general. Here we study this relationship empirically using a fixed deep energy-based generative model trained on measurement samples from controlled families of quantum states. We independently tune two quantum resources associated with classical simulation cost: entanglement, through the bond dimension of random matrix product states, and non-stabilizerness, through the number of T gates in Clifford-dominated circuits. Learning difficulty is characterized using two probes of neural-network complexity: the largest Hessian eigenvalue at convergence and Random Subspace Optimization. For both quantum resources, increasing simulation hardness systematically correlates with sharper loss landscapes and degraded reconstruction performance under constrained capacity. Our results indicate that, within the regimes studied here, classical learnability tracks known simulation complexity measures, suggesting that neural-network training dynamics can provide an empirical probe of quantum computational hardness.
We investigate the relationship between two distinct classical approaches to quantum systems: direct simulation from a classical description and sample-based learning from measurement data. While both tasks ultimately aim to reproduce Born-rule statistics, complexity-theoretic results suggest that simulability and learnability need not coincide in general. Here we study this relationship empirically using a fixed deep energy-based generative model trained on measurement samples from controlled families of quantum states. We independently tune two quantum resources associated with classical simulation cost: entanglement, through the bond dimension of random matrix product states, and non-stabilizerness, through the number of T gates in Clifford-dominated circuits. Learning difficulty is characterized using two probes of neural-network complexity: the largest Hessian eigenvalue at convergence and Random Subspace Optimization. For both quantum resources, increasing simulation hardness systematically correlates with sharper loss landscapes and degraded reconstruction performance under constrained capacity. Our results indicate that, within the regimes studied here, classical learnability tracks known simulation complexity measures, suggesting that neural-network training dynamics can provide an empirical probe of quantum computational hardness.
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.
Abstract Quantum machine-learning models are only useful if a classical computer cannot cheaply imitate them. We test this directly for quantum Kolmogorov–Arnold networks (QKANs)—neural networks whose tunable “activation functions” are small quantum circuits—by asking whether each model can be contracted as an effcient tensor network (TN), the standard tool for classical quantum simulation. We make the test practical with a task-aware yardstick: the bond dimension a classical surrogate needs to copy the model’s output at the accuracy the model itself reaches. We find a clear ladder. The amplitude-encoded Chebyshev QKAN uses only logarithmically many qubits and is exactly classical. The variational QKAN, built from all-to-all controlled rotations, looks hard at random settings but, once trained to genuinely learn a smooth task (R2 = 0.30–0.62), is copied by a constant-bond-dimension surrogate at the sizes (n ≤ 10) we test. Noise pushes it toward classicality near p ≈ 0.03–0.05, echoing noisy random circuits. Every generic attempt to force hardness—a global measurement, a deeper entangler, or an interaction-based (IQP) feature map—instead destroys trainability through exponentially small gradients (a “barren plateau”). The escape is a discrete-logarithm feature map: its kernel variance is flat (0.07±0.01) from 4 to 14 qubits while a generic IQP kernel decays as 2 −n , and a support-vector machine with it learns a classically hard concept to ≥ 99% accuracy while generic and classical kernels stay at chance—hardness placed in number theory stays both classically hard and shot-effciently learnable. The work provides a concrete, measurement-based criterion for when a quantum model is reproducible by a low-bond- dimension surrogate, and a design rule: seek advantage in structured, provably hard encodings rather than in deep entanglement.
Given a quantum circuit, a quantum computer can sample the output distribution exponentially faster in the number of bits than classical computers. A similar exponential separation has yet to be established in generative models through quantum sample learning: given samples from an n-qubit computation, can we learn the underlying quantum distribution using models with training parameters that scale polynomial in n under a fixed training time? We study four kinds of generative models: Deep Boltzmann machine (DBM), Generative Adversarial Networks (GANs), Long Short-Term Memory (LSTM) and Autoregressive GAN, on learning quantum data set generated by deep random circuits. We demonstrate the leading performance of LSTM in learning quantum samples, and thus the autoregressive structure present in the underlying quantum distribution from random quantum circuits. Both numerical experiments and a theoretical proof in the case of the DBM show exponentially growing complexity of learning-agent parameters required for achieving a fixed accuracy as n increases. Finally, we establish a connection between learnability and the complexity of generative models by benchmarking learnability against different sets of samples drawn from probability distributions of variable degrees of complexities in their quantum and classical representations.
With increasing maturity of quantum computers, standard methods for characterizing global properties of their output quantum states via direct measurements and classical post-processing are becoming increasingly impractical due to large measurement costs. Although quantum neural networks could directly process quantum states to identify underlying characteristics with reduced measurement efforts, they often require deep quantum circuits that cannot be implemented on existing devices. To overcome these challenges, we introduce a hybrid quantum-classical neural network that consists of a shallow parameterized quantum circuit, measurements, and a classical neural network. The parameterized quantum circuit performs a nonlocal transformation of the measurement basis, which is jointly trained with the classical neural network to maximize the statistical distance between data obtained by measuring different quantum states. Using supervised learning, we demonstrate that the hybrid neural network distinguishes the topological phase of the surface code from a symmetry-enriched topological phase and random product states. Moreover, this hybrid neural network reduces both inference and training sample complexities of recognizing the topological phase by approximately one order of magnitude compared to a classical neural network trained on randomized Pauli measurements. As this hybrid neural network features a shallow quantum circuit that can be readily implemented on existing quantum computers, it enables the efficient characterization of complex quantum states.
Quantum machine learning models have shown successful generalization performance even when trained with few data. In this work, through systematic randomization experiments, we show that traditional approaches to understanding generalization fail to explain the behavior of such quantum models. Our experiments reveal that state-of-the-art quantum neural networks accurately fit random states and random labeling of training data. This ability to memorize random data defies current notions of small generalization error, problematizing approaches that build on complexity measures such as the VC dimension, the Rademacher complexity, and all their uniform relatives. We complement our empirical results with a theoretical construction showing that quantum neural networks can fit arbitrary labels to quantum states, hinting at their memorization ability. Our results do not preclude the possibility of good generalization with few training data but rather rule out any possible guarantees based only on the properties of the model family. These findings expose a fundamental challenge in the conventional understanding of generalization in quantum machine learning and highlight the need for a paradigm shift in the study of quantum models for machine learning tasks.
In the task of quantum state learning, one receives some data about measurements performed on a state, and using that, must make predictions on the outcomes of unseen measurements. Computing a prediction is generally hard but it has been shown that learning can be performed efficiently for states that are generated by Clifford circuits, which are known to be efficiently classically simulable. This naturally leads to the question, how does efficient state learnability compare with efficient classical simulation? In this work we introduce an extra condition on top of classical simulablity that guarantees efficiently learnability. To illustrate this we prove two new examples of efficient learnability: states with low (Schmidt rank) entanglement and states described by an 'efficient' ontological model.