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

arXiv: https://arxiv.org/abs/2010.02174 · HTML: https://mlsanity.com/paper/2010.02174/

## Key facts

- Cited by 271 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Oct 2020.

## Built on by (most cited first, 30 of 271)

- [Generalization in quantum machine learning from few training data](https://mlsanity.com/paper/2111.05292/) (2021)
- [Challenges and Opportunities in Quantum Machine Learning](https://mlsanity.com/paper/2303.09491/) (2023)
- [Supervised quantum machine learning models are kernel methods](https://mlsanity.com/paper/2101.11020/) (2021)
- [Barren Plateaus in Variational Quantum Computing](https://mlsanity.com/paper/2405.00781/) (2024)
- [Quantum machine learning beyond kernel methods](https://mlsanity.com/paper/2110.13162/) (2021)
- [The Inductive Bias of Quantum Kernels](https://mlsanity.com/paper/2106.03747/) (2021)
- [Parametrized quantum policies for reinforcement learning](https://mlsanity.com/paper/2103.05577/) (2021)
- [Exponential concentration in quantum kernel methods](https://mlsanity.com/paper/2208.11060/) (2022)
- [Encoding-dependent generalization bounds for parametrized quantum circuits](https://mlsanity.com/paper/2106.03880/) (2021)
- [Training Quantum Embedding Kernels on Near-Term Quantum Computers](https://mlsanity.com/paper/2105.02276/) (2021)
- [Theory for Equivariant Quantum Neural Networks](https://mlsanity.com/paper/2210.08566/) (2022)
- [A Survey on Quantum Reinforcement Learning](https://mlsanity.com/paper/2211.03464/) (2022)
- [Out-of-distribution generalization for learning quantum dynamics](https://mlsanity.com/paper/2204.10268/) (2022)
- [Understanding quantum machine learning also requires rethinking generalization](https://mlsanity.com/paper/2306.13461/) (2023)
- [Quantum federated learning through blind quantum computing](https://mlsanity.com/paper/2103.08403/) (2021)
- [Quantum Self-Attention Neural Networks for Text Classification](https://mlsanity.com/paper/2205.05625/) (2022)
- [Representation Learning via Quantum Neural Tangent Kernels](https://mlsanity.com/paper/2111.04225/) (2021)
- [When BERT Meets Quantum Temporal Convolution Learning for Text Classification in Heterogeneous Computing](https://mlsanity.com/paper/2203.03550/) (2022)
- [Representation Theory for Geometric Quantum Machine Learning](https://mlsanity.com/paper/2210.07980/) (2022)
- [Experimental quantum adversarial learning with programmable superconducting qubits](https://mlsanity.com/paper/2204.01738/) (2022)
- [Classical surrogates for quantum learning models](https://mlsanity.com/paper/2206.11740/) (2022)
- [Recent advances for quantum classifiers](https://mlsanity.com/paper/2108.13421/) (2021)
- [Subtleties in the trainability of quantum machine learning models](https://mlsanity.com/paper/2110.14753/) (2021)
- [Bandwidth Enables Generalization in Quantum Kernel Models](https://mlsanity.com/paper/2206.06686/) (2022)
- [Towards provably efficient quantum algorithms for large-scale machine-learning models](https://mlsanity.com/paper/2303.03428/) (2023)
- [A survey on the complexity of learning quantum states](https://mlsanity.com/paper/2305.20069/) (2023)
- [A comprehensive review of Quantum Machine Learning: from NISQ to Fault Tolerance](https://mlsanity.com/paper/2401.11351/) (2024)
- [Importance of Kernel Bandwidth in Quantum Machine Learning](https://mlsanity.com/paper/2111.05451/) (2021)
- [Shadows of quantum machine learning](https://mlsanity.com/paper/2306.00061/) (2023)
- [Quantum machine learning of large datasets using randomized measurements](https://mlsanity.com/paper/2108.01039/) (2021)

## Abstract (arXiv)

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.