论文标题
监督量子学习的统计限制
Statistical Limits of Supervised Quantum Learning
论文作者
论文摘要
在统计学习理论的框架内，可以束缚学习者达到目标准确性所需的最小样本数量。我们表明，如果考虑到准确性的界限，量子机器学习算法用于监督学习 - 对于哪些可用统计保证 - 无法实现输入维度中的polyrogarogarithmic runtimes。我们得出的结论是，如果没有对问题进行进一步的假设，即使在量子访问数据自然可用的情况下，对于有效的经典算法，用于监督学习的量子机学习算法也可以在高效的经典算法上具有最多的多项式加速。
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.
