Provable advantages of kernel-based quantum learners and quantum preprocessing based on Grover's algorithm
This work addresses the challenge of achieving quantum speedups in machine learning for researchers in quantum computing and AI, though it builds incrementally on existing results.
The paper tackles the problem of finding quantum speedups for learning by expanding on a prior exponential speedup for quantum support vector machines, identifying a speedup using Grover's algorithm in the kernel and applying it to pattern matching for a practical advantage, while also showing that quantum preprocessing combined with classical classification improves performance.
There is an ongoing effort to find quantum speedups for learning problems. Recently, [Y. Liu et al., Nat. Phys. $\textbf{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.