# Fat Shattering, Joint Measurability, and PAC Learnability of POVM Hypothesis Classes

arXiv: https://arxiv.org/abs/2308.12304 · HTML: https://mlsanity.com/paper/2308.12304/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 55 references that are in the map.
- First posted on arXiv 21 Aug 2023.

## Builds on (most cited first, 12 of 12)

- [Generalization in quantum machine learning from few training data](https://mlsanity.com/paper/2111.05292/) (2021)
- [Efficient quantum tomography II](https://mlsanity.com/paper/1612.00034/) (2016)
- [Online Learning of Quantum States](https://mlsanity.com/paper/1802.09025/) (2018)
- [Sample-efficient learning of quantum many-body systems](https://mlsanity.com/paper/2004.07266/) (2020)
- [Optimal Quantum Sample Complexity of Learning Algorithms](https://mlsanity.com/paper/1607.00932/) (2016)
- [Quantum statistical query learning](https://mlsanity.com/paper/2002.08240/) (2020)
- [A Survey of Quantum Learning Theory](https://mlsanity.com/paper/1701.06806/) (2017)
- [The Learnability of Unknown Quantum Measurements](https://mlsanity.com/paper/1501.00559/) (2015)
- [A Theoretical Framework for Learning from Quantum Data](https://mlsanity.com/paper/2107.06406/) (2021)
- [Toward Physically Realizable Quantum Neural Networks](https://mlsanity.com/paper/2203.12092/) (2022)
- [Quantum Perceptron Revisited: Computational-Statistical Tradeoffs](https://mlsanity.com/paper/2106.02496/) (2021)
- [A learning theory for quantum photonic processors and beyond](https://mlsanity.com/paper/2209.03075/) (2022)

## Abstract (arXiv)

We characterize learnability for quantum measurement classes by establishing matching necessary and sufficient conditions for their PAC learnability, along with corresponding sample complexity bounds, in the setting where the learner is given access only to prepared quantum states. 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 fails to satisfy the uniform convergence property enjoyed in the classical setting for some learnable classes. Moreover, we show that VC dimension generalization upper bounds in previous work are frequently infinite, even for finite-dimensional POVM classes. To surmount the failure of the standard ERM to satisfy uniform convergence, we define a new learning rule -- denoised ERM. We show this to be a universal learning rule for POVM and probabilistically observed concept classes, and the condition for it to satisfy uniform convergence is finite fat shattering dimension of the class. We give quantitative sample complexity upper and lower bounds for learnability in terms of finite fat-shattering dimension and a notion of approximate finite partitionability into approximately jointly measurable subsets, which allow for sample reuse. We then show that finite fat shattering dimension implies finite coverability by approximately jointly measurable subsets, leading to our matching conditions. We also show that every measurement class defined on a finite-dimensional Hilbert space is PAC learnable. We illustrate our results on several example POVM classes.