Provable advantages of kernel-based quantum learners and quantum
  preprocessing based on Grover's algorithm
Till Muser Elias Zapusek Vasilis Belis Florentin Reiter
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.