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

2023/09/25 by Till Muser, Muser, Till, Elias Zapusek +5 · 2 citations
Computer Science · #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography

paper · pdf · doi:10.48550/arxiv.2309.14406

Abstract

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.

Cited by

• Grover's algorithm is an approximation of imaginary-time evolution
• Guided Graph Compression for Quantum Graph Neural Networks

Related

• Quantum Machine Learning: Quantum Kernel Methods
• Machine Learning in the Quantum Age: Quantum vs. Classical Support Vector Machines
• An Exponential Separation Between Quantum and Quantum-Inspired Classical Algorithms for Linear Systems
• Quantum machine learning for multiclass classification beyond kernel methods
• Exploring an implementation of quantum learning pipeline for support vector machines