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

  • 2020-10-05 17:22:22
  • Yunchao Liu, Srinivasan Arunachalam, Kristan Temme
  • 26

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.

 

Quick Read (beta)

loading the full paper ...