# Statistical Limits of Supervised Quantum Learning

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jan 2020.

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

- [Generalization in Quantum Machine Learning: a Quantum Information Perspective](https://mlsanity.com/paper/2102.08991/) (2021)
- [Quantum Machine Learning For Classical Data](https://mlsanity.com/paper/2105.03684/) (2021)

## Abstract (arXiv)

Within the framework of statistical learning theory it is possible to bound the minimum number of samples required by a learner to reach a target accuracy. We show that if the bound on the accuracy is taken into account, quantum machine learning algorithms for supervised learning---for which statistical guarantees are available---cannot achieve polylogarithmic runtimes in the input dimension. We conclude that, when no further assumptions on the problem are made, quantum machine learning algorithms for supervised learning can have at most polynomial speedups over efficient classical algorithms, even in cases where quantum access to the data is naturally available.