mlsanityData to 14 Oct 2026

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

arXiv 2309.14406 ↗First posted 25 Sep 2023quant-ph cs.LGcited by 3

Not on the map. Why?

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.

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

23 of 67 references.

References · 23

  1. 2018Supervised learning with quantum enhanced feature spacescited by 665
  2. 2020The power of quantum neural networkscited by 379
  3. 2015Recent Advances in Convolutional Neural Networkscited by 360
  4. 2020Power of data in quantum machine learningcited by 338
  5. 2019Parameterized quantum circuits as machine learning modelscited by 332
  6. 2020A rigorous and robust quantum speed-up in supervised machine learningcited by 271
  7. 2021Generalization in quantum machine learning from few training datacited by 216
  8. 2023Challenges and Opportunities in Quantum Machine Learningcited by 203
  9. 2023Data-centric Artificial Intelligence: A Surveycited by 203
  10. 2021Quantum advantage in learning from experimentscited by 188
  11. 2021Information-theoretic bounds on quantum advantage in machine learningcited by 96
  12. 2021The Inductive Bias of Quantum Kernelscited by 91
11 more
  1. 2016Feature Selection: A Data Perspectivecited by 50
  2. 2020Universal Approximation Property of Quantum Machine Learning Models in Quantum-Enhanced Feature Spacescited by 44
  3. 2022Is one annotation enough? A data-centric image classification benchmark for noisy and ambiguous label estimationcited by 43
  4. 2016Quantum Perceptron Modelscited by 28
  5. 2021A Data-Centric Approach for Training Deep Neural Networks with Less Datacited by 28
  6. 2023Quantum anomaly detection in the latent space of proton collision events at the LHCcited by 21
  7. 2022On establishing learning separations between classical and quantum machine learning with classical datacited by 15
  8. 2018A Grover-search Based Quantum Learning Scheme for Classificationcited by 12
  9. 2022A super-polynomial quantum-classical separation for density modellingcited by 9
  10. 2021Data-Centric AI Requires Rethinking Data Notioncited by 8
  11. 2014Quantum pattern matching fast on averagecited by 3

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 1; 2025: 1.

3 papers.

  1. 2023Machine Learning for Anomaly Detection in Particle Physicscited by 30
  2. 2024Can Geometric Quantum Machine Learning Lead to Advantage in Barcode Classification?cited by 0
  3. 2025Guided Graph Compression for Quantum Graph Neural Networkscited by 0