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.
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.
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.
Restricted models of quantum computation are ones that have less power than a universal quantum computer. We studied the consequences of removing particular properties from a universal quantum computer to discover whether those resources were important.In the first part of the thesis we studied universal quantum computers which are implemented using Clifford gates, adaptive measurements, and magic states. The Gottesman–Knill theorem shows that circuits in this form which do not use magic states can be simulated by a classical computer. We extended this result to show that all circuits in this form can be partially simulated; the same computation can be implemented using a smaller quantum computer with the assistance of some polynomial time classical computation. We also identified a subclass of these computations that can be shown to not be entirely classically simulated by any method, given certain complexity theoretic assumptions are true.In the next part of the thesis we examine the role of entanglement in noisy quantum computations. Entanglement is necessary for noiseless quantum computers to have any quantum advantage, but it is not known whether the same is true for mixed state quantum computers. We show that entanglement, unexpectedly, does play a crucial role in the most well known mixed state computer: the one clean qubit model.Finally, we investigate how closely classical simulation is related to another idea of classicality.This notion captures how easily the final state of a computation can be learnt, given samples of measurements from it. We find an extra condition under which a circuit that is classically simulable is also efficiently learnable.
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.
Given a dataset of input states, measurements, and probabilities, is it possible to efficiently predict the measurement probabilities associated with a quantum circuit? Recent work of Caro and Datta \cite{2020Caro} studied the problem of PAC learning quantum circuits in an information theoretic sense, leaving open questions of computational efficiency. In particular, one candidate class of circuits for which an efficient learner might have been possible was that of Clifford circuits, since the corresponding set of states generated by such circuits, called stabilizer states, are known to be efficiently PAC learnable \cite{rocchetto2018stabiliser}. Here we provide a negative result, showing that proper learning of CNOT circuits with 1/ poly( n ) error is hard for classical learners unless RP = NP , ruling out the possibility of strong learners under standard complexity theoretic assumptions. As the classical analogue and subset of Clifford circuits, this naturally leads to a hardness result for Clifford circuits as well. Additionally, we show that if RP = NP then there would exist efficient proper learning algorithms for CNOT and Clifford circuits. By similar arguments, we also find that an efficient proper quantum learner for such circuits exists if and only if NP ⊆ RQP . We leave open the problem of hardness for improper learning or O(1) error to future work.
Traditional quantum state tomography requires a number of measurements that grows exponentially with the number of qubits n . But using ideas from computational learning theory, we show that one can do exponentially better in a statistical setting. In particular, to predict the outcomes of most measurements drawn from an arbitrary probability distribution, one needs only a number of sample measurements that grows linearly with n . This theorem has the conceptual implication that quantum states, despite being exponentially long vectors, are nevertheless ‘reasonable’ in a learning theory sense. The theorem also has two applications to quantum computing: first, a new simulation of quantum one-way communication protocols and second, the use of trusted classical advice to verify untrusted quantum advice.
The vast and complicated many-qubit state space forbids us to comprehensively capture the dynamics of modern quantum computers via classical simulations or quantum tomography. Recent progress in quantum learning theory prompts a crucial question: can linear properties of a many-qubit circuit with d tunable RZ gates and G − d Clifford gates be efficiently learned from measurement data generated by varying classical inputs? In this work, 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. To address this challenge, we propose a kernel-based method leveraging classical shadows and truncated trigonometric expansions, enabling a controllable trade-off between prediction accuracy and computational overhead. Our results advance two crucial realms in quantum computation: the exploration of quantum algorithms with practical utilities and learning-based quantum system certification. We conduct numerical simulations to validate our proposals across diverse scenarios, encompassing quantum information processing protocols, Hamiltonian simulation, and variational quantum algorithms up to 60 qubits. It is currently unclear whether machine learning model could efficiently learn the dynamics of many-qubit bounded-gate quantum circuits. This work reveals the learnability of predicting linear properties of large- scale quantum circuits and proposes a learning algorithm that enables resource-efficient solutions for many practical quantum applications.