A rigorous and robust quantum speed-up in supervised machine learning
A specially constructed algorithm shows that a formal quantum advantage is possible and is robust against additive errors in the kernel entries that arise from finite sampling statistics.
Abstract
Over the past few years several quantum machine learning algorithms were\nproposed that promise quantum speed-ups over their classical counterparts. Most\nof these learning algorithms either assume quantum access to data -- making it\nunclear if quantum speed-ups still exist without making these strong\nassumptions, or are heuristic in nature with no provable advantage over\nclassical algorithms. In this paper, we establish a rigorous quantum speed-up\nfor supervised classification using a general-purpose quantum learning\nalgorithm that only requires classical access to data. Our quantum classifier\nis a conventional support vector machine that uses a fault-tolerant quantum\ncomputer to estimate a kernel function. Data samples are mapped to a quantum\nfeature space and the kernel entries can be estimated as the transition\namplitude of a quantum circuit. We construct a family of datasets and show that\nno classical learner can classify the data inverse-polynomially better than\nrandom guessing, assuming the widely-believed hardness of the discrete\nlogarithm problem. Meanwhile, the quantum classifier achieves high accuracy and\nis robust against additive errors in the kernel entries that arise from finite\nsampling statistics.\n