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

There is an ongoing effort to find quantum speedups for learning problems. Recently [Y. Liu et al., Nat. Phys. 17, 1013 (2021)] proved 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.