The use of quantum computing for machine learning is among the most exciting
prospective applications of quantum technologies. However, machine learning
tasks where data is provided can be considerably different than commonly
studied computational tasks. In this work, we show that some problems that are
classically hard to compute can be easily predicted by classical machines
learning from data. Using rigorous prediction error bounds as a foundation, we
develop a methodology for assessing potential quantum advantage in learning
tasks. The bounds are tight asymptotically and empirically predictive for a
wide range of learning models. These constructions explain numerical results
showing that with the help of data, classical machine learning models can be
competitive with quantum models even if they are tailored to quantum problems.
We then propose a projected quantum model that provides a simple and rigorous
quantum speed-up for a learning problem in the fault-tolerant regime. For
near-term implementations, we demonstrate a significant prediction advantage
over some classical models on engineered data sets designed to demonstrate a
maximal quantum advantage in one of the largest numerical tests for gate-based
quantum machine learning to date, up to 30 qubits.

探讨了量子计算在机器学习中的应用和机器学习任务中存在的与传统计算不同之处，提出了一种用于评估量子学习任务潜在优势的方法，并提出了一种通过量子速度提高学习效率的量子机器学习模型。

量子机器学习中的数据力量

Power of data in quantum machine learning

Over the past few years several quantum machine learning algorithms were
proposed that promise quantum speed-ups over their classical counterparts. Most
of these learning algorithms either assume quantum access to data -- making it
unclear if quantum speed-ups still exist without making these strong
assumptions, or are heuristic in nature with no provable advantage over
classical algorithms. In this paper, we establish a rigorous quantum speed-up
for supervised classification using a general-purpose quantum learning
algorithm that only requires classical access to data. Our quantum classifier
is a conventional support vector machine that uses a fault-tolerant quantum
computer to estimate a kernel function. Data samples are mapped to a quantum
feature space and the kernel entries can be estimated as the transition
amplitude of a quantum circuit. We construct a family of datasets and show that
no classical learner can classify the data inverse-polynomially better than
random guessing, assuming the widely-believed hardness of the discrete
logarithm problem. Meanwhile, the quantum classifier achieves high accuracy and
is robust against additive errors in the kernel entries that arise from finite
sampling statistics.

本文提出一种量子支持向量机分类器模型，实现有监督分类并取得了明显的量子加速，要求仅具备经典数据访问能力。在构造的数据集中，基于普遍认为的离散对数问题的困难性假设，该量子分类器实现的分类效果均优于无法逆多项式地超越瞎猜的经典学习器。这个模型可以通过一个容错的量子计算机来估算内积核函数，并且将数据映射为一个量子特征空间。此外，该分类器对由有限采样误差产生的内积核函数的加性误差具有一定的鲁棒性。