A rigorous and robust quantum speed-up in supervised machine learning

Recently, several quantum machine learning algorithms have been proposed that may offer quantum speed-ups over their classical counterparts. Most of these algorithms are either heuristic or assume that data can be accessed quantum-mechanically, making it unclear whether a quantum advantage can be proven without resorting to strong assumptions. Here we construct a classification problem with which we can rigorously show that heuristic quantum kernel methods can provide an end-to-end quantum speed-up with only classical access to data. To prove the quantum speed-up, 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. Furthermore, we construct a family of parameterized unitary circuits, which can be efficiently implemented on a fault-tolerant quantum computer, and use them to map the data samples to a quantum feature space and estimate the kernel entries. The resulting quantum classifier achieves high accuracy and is robust against additive errors in the kernel entries that arise from finite sampling statistics. Many quantum machine learning algorithms have been proposed, but it is typically unknown whether they would outperform classical methods on practical devices. A specially constructed algorithm shows that a formal quantum advantage is possible.