### Abstract

Over the past few years several quantum machine learning algorithms wereproposed that promise quantum speed-ups over their classical counterparts. Mostof these learning algorithms assume quantum access to data; and it is unclearif quantum speed-ups still exist without making these strong assumptions. Inthis paper, we establish a rigorous quantum speed-up for supervisedclassification using a quantum learning algorithm that only requires classicalaccess to data. Our quantum classifier is a conventional support vector machinethat uses a fault-tolerant quantum computer to estimate a kernel function. Datasamples are mapped to a quantum feature space and the kernel entries can beestimated as the transition amplitude of a quantum circuit. We construct afamily of datasets and show that no classical learner can classify the datainverse-polynomially better than random guessing, assuming the widely-believedhardness of the discrete logarithm problem. Meanwhile, the quantum classifierachieves high accuracy and is robust against additive errors in the kernelentries that arise from finite sampling statistics.