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

2020/10/05 by Yunchao Liu, Srinivasan Arunachalam, Kristan Temme · 1 voice · 5 citations
Computer Science · Physics and Astronomy · #cs.LG #quant-ph

paper · pdf · doi:10.1038/s41567-021-01287-z

published as Nature Physics, 2021 · 27 pages, 2 figures

arxiv published 2020/10/05 · arxiv created 2020/11/30 · arxiv updated 2021/07/14

Abstract

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.

Cited by

• Optimal Quantum Differential Privacy via Fisher Information Spectral Analysis
• Noise-enhanced quantum kernels on analog quantum computers
• Non-variational supervised quantum kernel methods: a review
• Quantum Doubly Stochastic Transformers
• Robust Decentralized Quantum Kernel Learning for Noisy and Adversarial Environment

Discussions

• There is work that demonstrates provable quantum speedups on artificial problems, based on the classical hardness and quantum efficiency of discrete log. This is interesting, but of course probably no [bsky, 0 points, 1 comments]

Related

• Supervised learning with quantum enhanced feature spaces
• Quantum Machine Learning For Classical Data
• An efficient quantum algorithm for generative machine learning
• Fully Quantum Classifier
• Supervised quantum machine learning models are kernel methods