Journal
PHYSICAL REVIEW A
Volume 102, Issue 4, Pages -Publisher
AMER PHYSICAL SOC
DOI: 10.1103/PhysRevA.102.042414
Keywords
-
Categories
Funding
- National Science Foundation [NSF PHY-1748958]
- Heising-Simons Foundation
- Simons Foundation through It from Qubit: Simons Collaboration on Quantum Fields, Gravity, and Information
- Google Ph.D. Fellowship
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available