# New Bounds on Quantum Sample Complexity of Measurement Classes

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 52 references that are in the map.
- First posted on arXiv 22 Aug 2024.

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

- [Predicting Many Properties of a Quantum System from Very Few Measurements](https://mlsanity.com/paper/2002.08953/) (2020)
- [TensorFlow Quantum: A Software Framework for Quantum Machine Learning](https://mlsanity.com/paper/2003.02989/) (2020)
- [Efficient quantum tomography II](https://mlsanity.com/paper/1612.00034/) (2016)
- [Entanglement is Necessary for Optimal Quantum Property Testing](https://mlsanity.com/paper/2004.07869/) (2020)
- [Quantum state certification](https://mlsanity.com/paper/1708.06002/) (2017)
- [A Survey of Quantum Learning Theory](https://mlsanity.com/paper/1701.06806/) (2017)
- [Transforming Bell's Inequalities into State Classifiers with Machine Learning](https://mlsanity.com/paper/1705.00813/) (2017)
- [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)
- [Learning k-qubit Quantum Operators via Pauli Decomposition](https://mlsanity.com/paper/2102.05209/) (2021)

## Abstract (arXiv)

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 C scales as 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 to O(VC^* log |C^*|), where C^* is the set of extreme points of the convex closure of C and VC^* 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(log |C^*|). Our approach is based on a new quantum empirical risk minimization (ERM) algorithm equipped with a shadow tomography method.