Comparisons of Classic and Quantum String Matching Algorithms✱
Margaret Gao, Rachel Huang, Arul Rhik Mazumder, Fei Li · 2022
In this paper, we study the string matching problem. We design a quantum string-matching algorithm for noisy intermediate-scale quantum (NISQ) computers, given the current leading quantum processing units (QPUs) having no more than a few hundred qubits [16]. We also compare the performance of classic algorithms and quantum algorithms under various combinations. Our study provides a comprehensive and quantitative guide for users to choose appropriate classic or quantum algorithms for their string matching problems.