# Statistical Complexity of Quantum Learning

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 120 references that are in the map.
- First posted on arXiv 20 Sep 2023.

## Builds on (most cited first, 30 of 35)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [The power of quantum neural networks](https://mlsanity.com/paper/2011.00027/) (2020)
- [Power of data in quantum machine learning](https://mlsanity.com/paper/2011.01938/) (2020)
- [The effect of data encoding on the expressive power of variational quantum machine learning models](https://mlsanity.com/paper/2008.08605/) (2020)
- [Quantum Machine Learning](https://mlsanity.com/paper/1611.09347/) (2016)
- [Size-Independent Sample Complexity of Neural Networks](https://mlsanity.com/paper/1712.06541/) (2017)
- [Deep learning: a statistical viewpoint](https://mlsanity.com/paper/2103.09177/) (2021)
- [Predicting Many Properties of a Quantum System from Very Few Measurements](https://mlsanity.com/paper/2002.08953/) (2020)
- [Generalization in quantum machine learning from few training data](https://mlsanity.com/paper/2111.05292/) (2021)
- [Supervised quantum machine learning models are kernel methods](https://mlsanity.com/paper/2101.11020/) (2021)
- [Quantum advantage in learning from experiments](https://mlsanity.com/paper/2112.00778/) (2021)
- [Generalization and Equilibrium in Generative Adversarial Nets (GANs)](https://mlsanity.com/paper/1703.00573/) (2017)
- [Quantum generative adversarial networks](https://mlsanity.com/paper/1804.08641/) (2018)
- [Theory of overparametrization in quantum neural networks](https://mlsanity.com/paper/2109.11676/) (2021)
- [Information-theoretic bounds on quantum advantage in machine learning](https://mlsanity.com/paper/2101.02464/) (2021)
- [Quantum machine learning: a classical perspective](https://mlsanity.com/paper/1707.08561/) (2017)
- [Provably efficient machine learning for quantum many-body problems](https://mlsanity.com/paper/2106.12627/) (2021)
- [Encoding-dependent generalization bounds for parametrized quantum circuits](https://mlsanity.com/paper/2106.03880/) (2021)
- [On the Discrimination-Generalization Tradeoff in GANs](https://mlsanity.com/paper/1711.02771/) (2017)
- [Representation Theory for Geometric Quantum Machine Learning](https://mlsanity.com/paper/2210.07980/) (2022)
- [Experimental quantum adversarial learning with programmable superconducting qubits](https://mlsanity.com/paper/2204.01738/) (2022)
- [Quantum Wasserstein Generative Adversarial Networks](https://mlsanity.com/paper/1911.00111/) (2019)
- [Capacity and quantum geometry of parametrized quantum circuits](https://mlsanity.com/paper/2102.01659/) (2021)
- [Bandwidth Enables Generalization in Quantum Kernel Models](https://mlsanity.com/paper/2206.06686/) (2022)
- [Approximability of Discriminators Implies Diversity in GANs](https://mlsanity.com/paper/1806.10586/) (2018)
- [Structural risk minimization for quantum linear classifiers](https://mlsanity.com/paper/2105.05566/) (2021)
- [An Introduction to Quantum Machine Learning for Engineers](https://mlsanity.com/paper/2205.09510/) (2022)
- [Adversarial quantum circuit learning for pure state approximation](https://mlsanity.com/paper/1806.00463/) (2018)

## Built on by (most cited first, 11 of 11)

- [Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits](https://mlsanity.com/paper/2408.12199/) (2024)
- [Quantum Adversarial Learning for Kernel Methods](https://mlsanity.com/paper/2404.05824/) (2024)
- [Quantum computing and artificial intelligence: status and perspectives](https://mlsanity.com/paper/2505.23860/) (2025)
- [Analysis of Quantum Image Representations for Supervised Classification](https://mlsanity.com/paper/2507.22039/) (2025)
- [Learning to Classify Quantum Phases of Matter with a Few Measurements](https://mlsanity.com/paper/2409.05188/) (2024)
- [Uncertainty Quantification and Data Efficiency in AI: An Information-Theoretic Perspective](https://mlsanity.com/paper/2512.05267/) (2025)
- [Accuracy vs Memory Advantage in the Quantum Simulation of Stochastic Processes](https://mlsanity.com/paper/2312.13473/) (2023)
- [Separable Power of Classical and Quantum Learning Protocols Through the Lens of No-Free-Lunch Theorem](https://mlsanity.com/paper/2405.07226/) (2024)
- [On the Generalization of Adversarially Trained Quantum Classifiers](https://mlsanity.com/paper/2504.17690/) (2025)
- [Few measurement shots challenge generalization in learning to classify entanglement](https://mlsanity.com/paper/2411.06600/) (2024)
- [Learning Topological Quantum Phases from Limited Subsystems](https://mlsanity.com/paper/2607.10656/) (2026)

## Abstract (arXiv)

Recent years have seen significant activity on the problem of using data for the purpose of learning properties of quantum systems or of processing classical or quantum data via quantum computing. As in classical learning, quantum learning problems involve settings in which the mechanism generating the data is unknown, and the main goal of a learning algorithm is to ensure satisfactory accuracy levels when only given access to data and, possibly, side information such as expert knowledge. This article reviews the complexity of quantum learning using information-theoretic techniques by focusing on data complexity, copy complexity, and model complexity. 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. For example, in a quantum system, unlike in classical machine learning, it is generally not possible to evaluate the training loss simultaneously on multiple hypotheses using the same quantum data. To make the paper self-contained and approachable by different research communities, we provide extensive background material on classical results from statistical learning theory, as well as on the distinguishability of quantum states. Throughout, we highlight the differences between quantum and classical learning by addressing both supervised and unsupervised learning, and we provide extensive pointers to the literature.