# Information-theoretic bounds on quantum advantage in machine learning

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

## Key facts

- Cited by 96 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 86 references that are in the map.
- First posted on arXiv 7 Jan 2021.

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

- [Supervised learning with quantum enhanced feature spaces](https://mlsanity.com/paper/1804.11326/) (2018)
- [Power of data in quantum machine learning](https://mlsanity.com/paper/2011.01938/) (2020)
- [Quantum Machine Learning](https://mlsanity.com/paper/1611.09347/) (2016)
- [Predicting Many Properties of a Quantum System from Very Few Measurements](https://mlsanity.com/paper/2002.08953/) (2020)
- [A quantum-inspired classical algorithm for recommendation systems](https://mlsanity.com/paper/1807.04271/) (2018)
- [Deep autoregressive models for the efficient variational simulation of many-body quantum systems](https://mlsanity.com/paper/1902.04057/) (2019)
- [On the Quantum versus Classical Learnability of Discrete Distributions](https://mlsanity.com/paper/2007.14451/) (2020)
- [Active learning machine learns to create new quantum experiments](https://mlsanity.com/paper/1706.00868/) (2017)
- [Machine learning & artificial intelligence in the quantum domain](https://mlsanity.com/paper/1709.02779/) (2017)
- [Optimal Quantum Sample Complexity of Learning Algorithms](https://mlsanity.com/paper/1607.00932/) (2016)
- [Reformulation of the No-Free-Lunch Theorem for Entangled Data Sets](https://mlsanity.com/paper/2007.04900/) (2020)
- [Entanglement is Necessary for Optimal Quantum Property Testing](https://mlsanity.com/paper/2004.07869/) (2020)
- [Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension](https://mlsanity.com/paper/1811.04909/) (2018)
- [Quantum-inspired algorithms in practice](https://mlsanity.com/paper/1905.10415/) (2019)
- [Sample Efficient Algorithms for Learning Quantum Channels in PAC Model and the Approximate State Discrimination Problem](https://mlsanity.com/paper/1810.10938/) (2018)
- [Experimental learning of quantum states](https://mlsanity.com/paper/1712.00127/) (2017)
- [Fast graph operations in quantum computation](https://mlsanity.com/paper/1510.03742/) (2015)

## Built on by (most cited first, 30 of 96)

- [Generalization in quantum machine learning from few training data](https://mlsanity.com/paper/2111.05292/) (2021)
- [Challenges and Opportunities in Quantum Machine Learning](https://mlsanity.com/paper/2303.09491/) (2023)
- [Quantum advantage in learning from experiments](https://mlsanity.com/paper/2112.00778/) (2021)
- [Theory of overparametrization in quantum neural networks](https://mlsanity.com/paper/2109.11676/) (2021)
- [Quantum machine learning beyond kernel methods](https://mlsanity.com/paper/2110.13162/) (2021)
- [The Inductive Bias of Quantum Kernels](https://mlsanity.com/paper/2106.03747/) (2021)
- [Exponential concentration in quantum kernel methods](https://mlsanity.com/paper/2208.11060/) (2022)
- [Does provable absence of barren plateaus imply classical simulability?](https://mlsanity.com/paper/2312.09121/) (2023)
- [Exponential separations between learning with and without quantum memory](https://mlsanity.com/paper/2111.05881/) (2021)
- [Out-of-distribution generalization for learning quantum dynamics](https://mlsanity.com/paper/2204.10268/) (2022)
- [Recent Advances for Quantum Neural Networks in Generative Learning](https://mlsanity.com/paper/2206.03066/) (2022)
- [Recent advances for quantum classifiers](https://mlsanity.com/paper/2108.13421/) (2021)
- [Learning to predict arbitrary quantum processes](https://mlsanity.com/paper/2210.14894/) (2022)
- [Subtleties in the trainability of quantum machine learning models](https://mlsanity.com/paper/2110.14753/) (2021)
- [Towards provably efficient quantum algorithms for large-scale machine-learning models](https://mlsanity.com/paper/2303.03428/) (2023)
- [On quantum backpropagation, information reuse, and cheating measurement collapse](https://mlsanity.com/paper/2305.13362/) (2023)
- [A comprehensive review of Quantum Machine Learning: from NISQ to Fault Tolerance](https://mlsanity.com/paper/2401.11351/) (2024)
- [Speeding up Learning Quantum States through Group Equivariant Convolutional Quantum Ans"atze](https://mlsanity.com/paper/2112.07611/) (2021)
- [Entangled Datasets for Quantum Machine Learning](https://mlsanity.com/paper/2109.03400/) (2021)
- [Structural risk minimization for quantum linear classifiers](https://mlsanity.com/paper/2105.05566/) (2021)
- [Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrix](https://mlsanity.com/paper/2212.04471/) (2022)
- [Improved machine learning algorithm for predicting ground state properties](https://mlsanity.com/paper/2301.13169/) (2023)
- [Analytic theory for the dynamics of wide quantum neural networks](https://mlsanity.com/paper/2203.16711/) (2022)
- [The dilemma of quantum neural networks](https://mlsanity.com/paper/2106.04975/) (2021)
- [Problem-Dependent Power of Quantum Neural Networks on Multi-Class Classification](https://mlsanity.com/paper/2301.01597/) (2022)
- [Quantum-Noise-Driven Generative Diffusion Models](https://mlsanity.com/paper/2308.12013/) (2023)
- [On the Sample Complexity of Quantum Boltzmann Machine Learning](https://mlsanity.com/paper/2306.14969/) (2023)
- [Variational inference with a quantum computer](https://mlsanity.com/paper/2103.06720/) (2021)
- [A Hierarchy for Replica Quantum Advantage](https://mlsanity.com/paper/2111.05874/) (2021)
- [The Complexity of NISQ](https://mlsanity.com/paper/2210.07234/) (2022)

## Abstract (arXiv)

We study the performance of classical and quantum machine learning (ML) models in predicting outcomes of physical experiments. The experiments depend on an input parameter x and involve execution of a (possibly unknown) quantum process E. Our figure of merit is the number of runs of E required to achieve a desired prediction performance. We consider classical ML models that perform a measurement and record the classical outcome after each run of E, and quantum ML models that can access E coherently to acquire quantum data; the classical or quantum data is then used to predict outcomes of future experiments. We prove that for any input distribution D(x), a classical ML model can provide accurate predictions on average by accessing E a number of times comparable to the optimal quantum ML model. In contrast, for achieving accurate prediction on all inputs, we prove that exponential quantum advantage is possible. For example, to predict expectations of all Pauli observables in an n-qubit system ρ, classical ML models require 2Omega(n) copies of ρ, but we present a quantum ML model using only O(n) copies. Our results clarify where quantum advantage is possible and highlight the potential for classical ML models to address challenging quantum problems in physics and chemistry.