# Provable advantages of kernel-based quantum learners and quantum preprocessing based on Grover's algorithm

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 67 references that are in the map.
- First posted on arXiv 25 Sep 2023.

## Builds on (most cited first, 23 of 23)

- [Supervised learning with quantum enhanced feature spaces](https://mlsanity.com/paper/1804.11326/) (2018)
- [The power of quantum neural networks](https://mlsanity.com/paper/2011.00027/) (2020)
- [Recent Advances in Convolutional Neural Networks](https://mlsanity.com/paper/1512.07108/) (2015)
- [Power of data in quantum machine learning](https://mlsanity.com/paper/2011.01938/) (2020)
- [Parameterized quantum circuits as machine learning models](https://mlsanity.com/paper/1906.07682/) (2019)
- [A rigorous and robust quantum speed-up in supervised machine learning](https://mlsanity.com/paper/2010.02174/) (2020)
- [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)
- [Data-centric Artificial Intelligence: A Survey](https://mlsanity.com/paper/2303.10158/) (2023)
- [Quantum advantage in learning from experiments](https://mlsanity.com/paper/2112.00778/) (2021)
- [Information-theoretic bounds on quantum advantage in machine learning](https://mlsanity.com/paper/2101.02464/) (2021)
- [The Inductive Bias of Quantum Kernels](https://mlsanity.com/paper/2106.03747/) (2021)
- [Feature Selection: A Data Perspective](https://mlsanity.com/paper/1601.07996/) (2016)
- [Universal Approximation Property of Quantum Machine Learning Models in Quantum-Enhanced Feature Spaces](https://mlsanity.com/paper/2009.00298/) (2020)
- [Is one annotation enough? A data-centric image classification benchmark for noisy and ambiguous label estimation](https://mlsanity.com/paper/2207.06214/) (2022)
- [Quantum Perceptron Models](https://mlsanity.com/paper/1602.04799/) (2016)
- [A Data-Centric Approach for Training Deep Neural Networks with Less Data](https://mlsanity.com/paper/2110.03613/) (2021)
- [Quantum anomaly detection in the latent space of proton collision events at the LHC](https://mlsanity.com/paper/2301.10780/) (2023)
- [On establishing learning separations between classical and quantum machine learning with classical data](https://mlsanity.com/paper/2208.06339/) (2022)
- [A Grover-search Based Quantum Learning Scheme for Classification](https://mlsanity.com/paper/1809.06056/) (2018)
- [A super-polynomial quantum-classical separation for density modelling](https://mlsanity.com/paper/2210.14936/) (2022)
- [Data-Centric AI Requires Rethinking Data Notion](https://mlsanity.com/paper/2110.02491/) (2021)
- [Quantum pattern matching fast on average](https://mlsanity.com/paper/1408.1816/) (2014)

## Built on by (most cited first, 3 of 3)

- [Machine Learning for Anomaly Detection in Particle Physics](https://mlsanity.com/paper/2312.14190/) (2023)
- [Can Geometric Quantum Machine Learning Lead to Advantage in Barcode Classification?](https://mlsanity.com/paper/2409.01496/) (2024)
- [Guided Graph Compression for Quantum Graph Neural Networks](https://mlsanity.com/paper/2506.09862/) (2025)

## Abstract (arXiv)

There is an ongoing effort to find quantum speedups for learning problems. Recently, [Y. Liu et al., Nat. Phys. 17, 1013--1017 (2021)] have proven an exponential speedup for quantum support vector machines by leveraging the speedup of Shor's algorithm. We expand upon this result and identify a speedup utilizing Grover's algorithm in the kernel of a support vector machine. To show the practicality of the kernel structure we apply it to a problem related to pattern matching, providing a practical yet provable advantage. Moreover, we show that combining quantum computation in a preprocessing step with classical methods for classification further improves classifier performance.