Comparisons of Classic and Quantum String Matching Algorithms

Authors

  • Margaret Gao Aspiring Scientists’ Summer Internship Program Intern
  • Rachel Huang Aspiring Scientists’ Summer Internship Program Intern
  • Arul Mazumder Aspiring Scientists’ Summer Internship Program Intern
  • Dr. Fei Li Aspiring Scientists’ Summer Internship Program Primary Mentor

DOI:

https://doi.org/10.13021/jssr2022.3450

Abstract

In this project, 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. We also compare the performance of classic algorithms and quantum algorithms under various settings. Our study provides a comprehensive and quantitative guide for users to choose appropriate classic or quantum algorithms for their string-matching problems. 

Published

2022-12-13

Issue

Vol. 4 (2022)

Section

College of Engineering and Computing: Department of Computer Science

Categories

License

Creative Commons License

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.