期刊
PHYSICAL REVIEW A
卷 102, 期 4, 页码 -出版社
AMER PHYSICAL SOC
DOI: 10.1103/PhysRevA.102.042414
关键词
-
资金
- 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
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据