In supervised learning, an inductive learning algorithm extracts general rules from observed training instances, then the rules are applied to test instances. We show that this splitting of training and application arises naturally, in the classical setting, from a simple independence requirement with a physical interpretation of being nonsignaling. Thus, two seemingly different definitions of inductive learning happen to coincide. This follows from the properties of classical information that break down in the quantum setup. We prove a quantum de Finetti theorem for quantum channels, which shows that in the quantum case, the equivalence holds in the asymptotic setting, that is, for large numbers of test instances. This reveals a natural analogy between classical learning protocols and their quantum counterparts, justifying a similar treatment, and allowing us to inquire about standard elements in computational learning theory, such as structural risk minimization and sample complexity.
In supervised learning, an inductive learning algorithm extracts general rules from observed training instances, then the rules are applied to test instances. We show that this splitting of training and application arises naturally, in the classical setting, from a simple independence requirement with a physical interpretation of being nonsignaling. Thus, two seemingly different definitions of inductive learning happen to coincide. This follows from the properties of classical information that break down in the quantum setup. We prove a quantum de Finetti theorem for quantum channels, which shows that in the quantum case, the equivalence holds in the asymptotic setting, that is, for large numbers of test instances. This reveals a natural analogy between classical learning protocols and their quantum counterparts, justifying a similar treatment, and allowing us to inquire about standard elements in computational learning theory, such as structural risk minimization and sample complexity.
In supervised learning, an inductive learning algorithm extracts general rules from observed training instances, then the rules are applied to test instances. We show that this splitting of training and application arises naturally, in the classical setting, from a simple independence requirement with a physical interpretation of being non-signalling. Thus, two seemingly different definitions of inductive learning happen to coincide. This follows from very specific properties of classical information, which break down in the quantum setup. We prove a quantum de Finetti theorem for quantum channels, which shows that in the quantum case, the equivalence holds in the asymptotic setting (for large number of test instances). This reveals a natural analogy between classical learning protocols and their quantum counterparts, thus allowing to naturally enquire about standard elements in computational learning theory, such as structural risk minimization, model and sample complexity.
Abstract Learning problems involve settings in which an algorithm has to make decisions based on data, and possibly side information such as expert knowledge. This study has two main goals. First, it reviews and generalizes different results on the data and model complexity of quantum learning, where the data and/or the algorithm can be quantum, focusing on information‐theoretic techniques. Second, it introduces the notion of copy complexity, which quantifies the number of copies of a quantum state required to achieve a target accuracy level. Copy complexity arises from the destructive nature of quantum measurements, which irreversibly alter the state to be processed, limiting the information that can be extracted about quantum data. As a result, empirical risk minimization is generally inapplicable. The paper presents novel results on the copy complexity for both training and testing. To make the paper self‐contained and approachable by different research communities, an extensive background material is provided on classical results from statistical learning theory, as well as on the distinguishability of quantum states. Throughout, the differences between quantum and classical learning are highlighted by addressing both supervised and unsupervised learning, and extensive pointers are provided to the literature.
Statistical learning theory provides the mathematical foundations for understanding generalization from finite data. As quantum computing and quantum machine learning continue to develop, there is increasing interest in whether analogous principles can be formulated for learning settings involving quantum data, quantum models, or quantum computation. This paper offers an introductory perspective on quantum statistical learning theory. We begin by recalling the basic ideas of classical statistical learning theory, including empirical risk minimization, hypothesis classes, generalization, and sample complexity, and then discuss how these concepts must be adapted in the quantum setting. In particular, we distinguish between learning with classical data using quantum algorithms, learning with quantum models, and learning directly from quantum data. We then outline the central learning-theoretic objects in the quantum setting, including quantum hypotheses, measurement-based predictions, population and empirical risk, shot complexity, and information-extraction limitations. A simple illustrative example is used to highlight how finite measurements and quantum uncertainty affect learning performance. We conclude with a discussion of open problems and directions toward a more unified theory of generalization and learnability in quantum learning.
Machine learning is widely regarded as a promising application in which quantum computing could offer a computational advantage. However, general quantum machine learning models with provable guarantees on performance, trainability, and efficient inference remain limited. In this work, we introduce quantum Hamiltonian embeddings, a supervised learning framework in which a classical training dataset is encoded into a single effective, parameterized Hamiltonian. Training optimizes the parameters of this data-dependent Hamiltonian, whose approximate ground state defines the classification rule. Once the ground state has been approximated using a quantum algorithm, inference can be performed either classically using a classical representation of the learned state, or with a quantum representation of the state. We establish efficient methods for gradient estimation and prove favorable generalization guarantees. Furthermore, under standard cryptographic assumptions, we show that Hamiltonian embeddings can realize hypothesis functions beyond the reach of efficient classical algorithms. We then demonstrate the framework at scale on IBM Heron processors using a standard benchmark dataset. Together, these results establish Hamiltonian embeddings as a new framework for quantum machine learning, combining theoretical guarantees with a path for experimental investigations at scale on quantum hardware.
The widespread use of machine learning has raised the question of quantum supremacy for supervised learning as compared to quantum computational advantage. In fact, a recent work shows that computational and learning advantage are, in general, not equivalent, i.e., the additional information provided by a training set can reduce the hardness of some problems. This paper investigates under which conditions they are found to be equivalent or, at least, highly related. This relation is analyzed by considering two definitions of learning speed-up: one tied to the distribution and another that is distribution-independent. In both cases, the existence of efficient algorithms to generate training sets emerges as the cornerstone of such conditions, although, for the distribution-independent definition, additional mild conditions must also be met. Finally, these results are applied to prove that there is a quantum speed-up for some learning tasks based on the prime factorization problem, assuming the classical intractability of this problem.
Quantum machine learning models based on parametrized quantum circuits, also called quantum neural networks (QNNs), are considered to be among the most promising candidates for applications on near-term quantum devices. Here we explore the expressivity and inductive bias of QNNs by exploiting an exact mapping from QNNs with inputs x to classical perceptrons acting on x⊗x (generalised to complex inputs). The simplicity of the perceptron architecture allows us to provide clear examples of the shortcomings of current QNN models, and the many barriers they face to becoming useful general-purpose learning algorithms. For example, a QNN with amplitude encoding cannot express the Boolean parity function for n≥3, which is but one of an exponential number of data structures that such a QNN is unable to express. Mapping a QNN to a classical perceptron simplifies training, allowing us to systematically study the inductive biases of other, more expressive embeddings on Boolean data. Several popular embeddings primarily produce an inductive bias towards functions with low class balance, reducing their generalisation performance compared to deep neural network architectures which exhibit much richer inductive biases. We explore two alternate strategies that move beyond standard QNNs. In the first, we use a QNN to help generate a classical DNN-inspired kernel. In the second we draw an analogy to the hierarchical structure of deep neural networks and construct a layered non-linear QNN that is provably fully expressive on Boolean data, while also exhibiting a richer inductive bias than simple QNNs. Finally, we discuss characteristics of the QNN literature that may obscure how hard it is to achieve quantum advantage over deep learning algorithms on classical data.