Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE International Symposium on Information Theory (ISIT)

Empirical Risk Minimization and Uniform Convergence for Probabilistically Observed and Quantum Measurement Hypothesis Classes

Abram Magner, Arun Padakandla

Published Jul 7, 2024• 0 citations
Publisher

Abstract

We continue the study of the learnability of quantum measurement classes in the setting where the learner is given access only to prepared quantum states, aiming for necessary and sufficient conditions for PAC learnability, along with corresponding sample complexity bounds. In the quantum setting, in contrast with the classical probabilistically observed case, sampled states are perturbed when a quantum measurement is applied, according to the Born rule, so that distinct samples in the training data cannot be arbitrarily reused. We first probe the results from previous works on this setting. We show that the empirical risk defined in previous works and matching the definition in the classical theory can fail to satisfy the uniform convergence property enjoyed in the classical learning setting for classes that we can show to be PAC learnable. Moreover, we show that VC dimension generalization upper bounds in previous work are in many cases infinite, even for measurement classes defined on a finite-dimensional Hilbert space. We then show that, nonetheless, every measurement class defined on a finite-dimensional Hilbert space is PAC learnable via a modification of the ERM rule.

DOI
10.1109/isit57864.2024.10619236

Related papers

New Bounds on Quantum Sample Complexity of Measurement Classes

Mohsen Heidari, Wojciech Szpankowski A

This paper studies quantum supervised learning for classical inference from quantum states. In this model, a learner has access to a set of labeled quantum samples as the training set. The objective is to find a quantum measurement that predicts the label of the unseen samples. The hardness of learning is measured via sample complexity under a quantum counterpart of the well-known probably approximately correct (PAC). Quantum sample complexity is expected to be higher than classical one, because of the measurement incompatibility and state collapse. Recent efforts showed that the sample complexity of learning a finite quantum concept class$\mathcal{C}$scales as$O(\vert \mathcal{C}\vert)$. This is significantly higher than the classical sample complexity that grows logarithmically with the class size. This work improves the sample complexity bound to$O\left(V_{\mathcal{C}^*} \log \left\vert\mathcal{C}^*\right\vert\right)$, where$\mathcal{C}^*$is the set of extreme points of the convex closure of$\mathcal{C}$and$V_{\mathcal{C}^*}$is the shadow-norm of this set. We show the tightness of our bound for the class of bounded Hilbert-Schmidt norm, scaling as$O\left(\log \left\vert\mathcal{C}^*\right\vert\right)$. Our approach is based on a new quantum empirical risk minimization (ERM) algorithm equipped with a shadow tomography method.

arXiv:2408.12683•IEEE International Symposium on Information Theory (ISIT)•Jul 7, 2024•1 citation

A Theoretical Framework for Learning from Quantum Data

Mohsen Heidari, Arun Padakandla, Wojciech Szpankowski A

Over decades traditional information theory of source and channel coding advances toward learning and effective extraction of information from data. We propose to go one step further and offer a theoretical foundation for learning classical patterns from quantum data. However, there are several roadblocks to lay the groundwork for such a generalization. First, classical data must be replaced by a density operator over a Hilbert space. Hence, deviated from problems such as state tomography, our samples are i.i.d density operators. The second challenge is even more profound since we must realize that our only interaction with a quantum state is through a measurement which - due to no-cloning quantum postulate - loses information after measuring it. With this in mind, we present a quantum counterpart of the well-known probably approximately correct (PAC) framework. Based on that, we propose a quantum analogous of the Empirical Risk Minimization (ERM) algorithm for learning measurement hypothesis classes. Then, we establish upper bounds on the quantum sample complexity quantum concept classes.

arXiv:2107.06406•IEEE International Symposium on Information Theory (ISIT)•Jul 12, 2021•9 citations

Analysis of the sample complexity for PAC-learning functions defined over quantum states

Jordi Pérez-Guijarro

A fundamental question in PAC learning is determining the number of labeled examples required to learn a concept class to a desired accuracy and confidence. In classical learning theory, this quantity is characterized by the VC-dimension, while several quantum generalizations have established analogous results when examples are provided in quantum superposition. In this work, we study a distinct quantum PAC-learning model in which concepts are functions acting on quantum states. We demonstrate that the VC-dimension, although still relevant, fails to fully capture the sample complexity of this model. To further characterize this setting, we develop a new lower bound on the required number of samples and establish an upper bound when the states in the domain are linearly independent. Remarkably, this upper bound has a form similar to the classical PAC-learning bound. We further examine a setting in which the learner receives more informative data and show that the limitations of the VC-dimension persist in this extended model.

quant-pharXiv:2607.07572•Jul 9, 2026•0 citations

Advantage of Entangled Learning Rules in Quantum Measurement Class Learning

Arka Prabha Das, Abram Magner

Learning with data in the form of quantum states is of current interest and has led to a variety of problems that boil down to interaction with the available data via quantum measurement and classical post-processing of observed classical outcomes. In quantum measurement PAC learning, one is given a sequence of unknown, prepared quantum states and classical labels, along with a hypothesis class of candidate measurements. The task is to select a measurement from the hypothesis class that minimizes a fixed notion of error in prediction of the classical labels via measurement of a new state by the selected hypothesis. In this work, we consider the advantage of interacting with the given data in the measurement learning framework using learning rules given by measurements that cannot be implemented using local operations and classical communication (LOCC), as opposed to single-copy learning rules. We provide a construction showing that there exist learning scenarios wherein single-copy learning rules are asymptotically suboptimal compared to optimal ones. We then show that learning rules based on entangled measurements enjoy at most a polynomial sample complexity advantage over single-copy learning rules in the PAC learning setting (under a natural joint measurability covering assumption).

quant-pharXiv:2610.07328•Oct 7, 2026•0 citations

Optimal quantum sample complexity of learning algorithms

Srinivasan Arunachalam, Ronald de Wolf

In learning theory, the VC dimension of a concept class C is the most common way to measure its “richness.” A fundamental result says that the number of examples needed to learn an unknown target concept c∈C under an unknown distribution D, is tightly determined by the VC dimension d of the concept class C. Specifically, in the PAC model Θ(dϵ+log(1/δ)ϵ) examples are necessary and sufficient for a learner to output, with probability 1−δ, a hypothesis h that is ϵ-close to the target concept c (measured under D). In the related agnostic model, where the samples need not come from a c∈C, we know that Θ(dϵ2+log(1/δ)ϵ2) examples are necessary and sufficient to output an hypothesis h∈C whose error is at most ϵ worse than the error of the best concept in C. Here we analyze quantum sample complexity, where each example is a coherent quantum state. This model was introduced by Bshouty and Jackson (1999), who showed that quantum examples are more powerful than classical examples in some fixed-distribution settings. However, Atici and Servedio (2005), improved by Zhang (2010), showed that in the PAC setting (where the learner has to succeed for every distribution), quantum examples cannot be much more powerful: the required number of quantum examples is Ω(d1−ηϵ+d+log(1/δ)ϵ) for arbitrarily small constant η>0. Our main result is that quantum and classical sample complexity are in fact equal up to constant factors in both the PAC and agnostic models. We give two proof approaches. The first is a fairly simple information-theoretic argument that yields the above two classical bounds and yields the same bounds for quantum sample complexity up to a log(d/ϵ) factor. We then give a second approach that avoids the log-factor loss, based on analyzing the behavior of the “Pretty Good Measurement” on the quantum state-identification problems that correspond to learning. This shows classical and quantum sample complexity are equal up to constant factors for every concept class C.

Journal of Machine Learning Research•Oct 1, 2018•49 citations

A PAC-Bayesian approach to generalization for quantum models

Pablo Rodriguez-Grasa, Matthias C. Caro, Jens Eisert +3 more

Generalization is a central concept in machine learning theory, yet for quantum models, it is predominantly analyzed through uniform bounds that depend on a model's overall capacity rather than the specific function learned. These capacity-based uniform bounds are often too loose and entirely insensitive to the actual training and learning process. Previous theoretical guarantees have failed to provide non-uniform, data-dependent bounds that reflect the specific properties of the learned solution rather than the worst-case behavior of the entire hypothesis class. To address this limitation, we derive the first PAC-Bayesian generalization bounds for a broad class of quantum models by analyzing layered circuits composed of general quantum channels, which include dissipative operations such as mid-circuit measurements and feedforward. Through a channel perturbation analysis, we establish non-uniform bounds that depend on the norms of learned parameter matrices; we extend these results to symmetry-constrained equivariant quantum models; and we validate our theoretical framework with numerical experiments. This work provides actionable model design insights and establishes a foundational tool for a more nuanced understanding of generalization in quantum machine learning.

quant-pharXiv:2603.22964•Mar 25, 2026•0 citations
We continue the study of the learnability of quantum measurement classes in the setting where the learner is given access only to prepared quantum states, aiming for necessary and sufficient conditions for PAC learnability, along with corresponding sample complexity bounds. In the quantum setting, in contrast with the classical probabilistically observed case, sampled states are perturbed when a quantum measurement is applied, according to the Born rule, so that distinct samples in the training data cannot be arbitrarily reused. We first probe the results from previous works on this setting. We show that the empirical risk defined in previous works and matching the definition in the classical theory can fail to satisfy the uniform convergence property enjoyed in the classical learning setting for classes that we can show to be PAC learnable. Moreover, we show that VC dimension generalization upper bounds in previous work are in many cases infinite, even for measurement classes defined on a finite-dimensional Hilbert space. We then show that, nonetheless, every measurement class defined on a finite-dimensional Hilbert space is PAC learnable via a modification of the ERM rule.
This paper studies quantum supervised learning for classical inference from quantum states. In this model, a learner has access to a set of labeled quantum samples as the training set. The objective is to find a quantum measurement that predicts the label of the unseen samples. The hardness of learning is measured via sample complexity under a quantum counterpart of the well-known probably approximately correct (PAC). Quantum sample complexity is expected to be higher than classical one, because of the measurement incompatibility and state collapse. Recent efforts showed that the sample complexity of learning a finite quantum concept classC\mathcal{C}Cscales asO(∣C∣)O(\vert \mathcal{C}\vert)O(∣C∣). This is significantly higher than the classical sample complexity that grows logarithmically with the class size. This work improves the sample complexity bound toO(VC∗log⁡∣C∗∣)O\left(V_{\mathcal{C}^*} \log \left\vert\mathcal{C}^*\right\vert\right)O(VC∗​log∣C∗∣), whereC∗\mathcal{C}^*C∗is the set of extreme points of the convex closure ofC\mathcal{C}CandVC∗V_{\mathcal{C}^*}VC∗​is the shadow-norm of this set. We show the tightness of our bound for the class of bounded Hilbert-Schmidt norm, scaling asO(log⁡∣C∗∣)O\left(\log \left\vert\mathcal{C}^*\right\vert\right)O(log∣C∗∣). Our approach is based on a new quantum empirical risk minimization (ERM) algorithm equipped with a shadow tomography method.
Over decades traditional information theory of source and channel coding advances toward learning and effective extraction of information from data. We propose to go one step further and offer a theoretical foundation for learning classical patterns from quantum data. However, there are several roadblocks to lay the groundwork for such a generalization. First, classical data must be replaced by a density operator over a Hilbert space. Hence, deviated from problems such as state tomography, our samples are i.i.d density operators. The second challenge is even more profound since we must realize that our only interaction with a quantum state is through a measurement which - due to no-cloning quantum postulate - loses information after measuring it. With this in mind, we present a quantum counterpart of the well-known probably approximately correct (PAC) framework. Based on that, we propose a quantum analogous of the Empirical Risk Minimization (ERM) algorithm for learning measurement hypothesis classes. Then, we establish upper bounds on the quantum sample complexity quantum concept classes.
A fundamental question in PAC learning is determining the number of labeled examples required to learn a concept class to a desired accuracy and confidence. In classical learning theory, this quantity is characterized by the VC-dimension, while several quantum generalizations have established analogous results when examples are provided in quantum superposition. In this work, we study a distinct quantum PAC-learning model in which concepts are functions acting on quantum states. We demonstrate that the VC-dimension, although still relevant, fails to fully capture the sample complexity of this model. To further characterize this setting, we develop a new lower bound on the required number of samples and establish an upper bound when the states in the domain are linearly independent. Remarkably, this upper bound has a form similar to the classical PAC-learning bound. We further examine a setting in which the learner receives more informative data and show that the limitations of the VC-dimension persist in this extended model.
Learning with data in the form of quantum states is of current interest and has led to a variety of problems that boil down to interaction with the available data via quantum measurement and classical post-processing of observed classical outcomes. In quantum measurement PAC learning, one is given a sequence of unknown, prepared quantum states and classical labels, along with a hypothesis class of candidate measurements. The task is to select a measurement from the hypothesis class that minimizes a fixed notion of error in prediction of the classical labels via measurement of a new state by the selected hypothesis. In this work, we consider the advantage of interacting with the given data in the measurement learning framework using learning rules given by measurements that cannot be implemented using local operations and classical communication (LOCC), as opposed to single-copy learning rules. We provide a construction showing that there exist learning scenarios wherein single-copy learning rules are asymptotically suboptimal compared to optimal ones. We then show that learning rules based on entangled measurements enjoy at most a polynomial sample complexity advantage over single-copy learning rules in the PAC learning setting (under a natural joint measurability covering assumption).
In learning theory, the VC dimension of a concept class C is the most common way to measure its “richness.” A fundamental result says that the number of examples needed to learn an unknown target concept c∈C under an unknown distribution D, is tightly determined by the VC dimension d of the concept class C. Specifically, in the PAC model Θ(dϵ+log(1/δ)ϵ) examples are necessary and sufficient for a learner to output, with probability 1−δ, a hypothesis h that is ϵ-close to the target concept c (measured under D). In the related agnostic model, where the samples need not come from a c∈C, we know that Θ(dϵ2+log(1/δ)ϵ2) examples are necessary and sufficient to output an hypothesis h∈C whose error is at most ϵ worse than the error of the best concept in C. Here we analyze quantum sample complexity, where each example is a coherent quantum state. This model was introduced by Bshouty and Jackson (1999), who showed that quantum examples are more powerful than classical examples in some fixed-distribution settings. However, Atici and Servedio (2005), improved by Zhang (2010), showed that in the PAC setting (where the learner has to succeed for every distribution), quantum examples cannot be much more powerful: the required number of quantum examples is Ω(d1−ηϵ+d+log(1/δ)ϵ) for arbitrarily small constant η>0. Our main result is that quantum and classical sample complexity are in fact equal up to constant factors in both the PAC and agnostic models. We give two proof approaches. The first is a fairly simple information-theoretic argument that yields the above two classical bounds and yields the same bounds for quantum sample complexity up to a log(d/ϵ) factor. We then give a second approach that avoids the log-factor loss, based on analyzing the behavior of the “Pretty Good Measurement” on the quantum state-identification problems that correspond to learning. This shows classical and quantum sample complexity are equal up to constant factors for every concept class C.
Generalization is a central concept in machine learning theory, yet for quantum models, it is predominantly analyzed through uniform bounds that depend on a model's overall capacity rather than the specific function learned. These capacity-based uniform bounds are often too loose and entirely insensitive to the actual training and learning process. Previous theoretical guarantees have failed to provide non-uniform, data-dependent bounds that reflect the specific properties of the learned solution rather than the worst-case behavior of the entire hypothesis class. To address this limitation, we derive the first PAC-Bayesian generalization bounds for a broad class of quantum models by analyzing layered circuits composed of general quantum channels, which include dissipative operations such as mid-circuit measurements and feedforward. Through a channel perturbation analysis, we establish non-uniform bounds that depend on the norms of learned parameter matrices; we extend these results to symmetry-constrained equivariant quantum models; and we validate our theoretical framework with numerical experiments. This work provides actionable model design insights and establishes a foundational tool for a more nuanced understanding of generalization in quantum machine learning.