What is it about?
In this paper, we design a novel quantum algorithm to identify patterns in strings. This quantum algorithm is designed for the current era of quantum computers and can be applied to IBM quantum systems with less than a hundred qubits. We compare the novel algorithm abilities with the capabilities of the best classical algorithms in matching various patterns to different-sized strings. Our work serves as a guide for users to pick appropriate algorithms to solve their string-matching problems.
Featured Image
Photo by Christian Wiediger on Unsplash
Why is it important?
This work is crucial to understanding the potential and limitations of current-day quantum computers. We theoretically proved that our novel quantum algorithm could outperform the best classical algorithms. Although we discovered that the quantum algorithm is still slower than classical algorithms in this current era of NISQ technology, its capabilities will increase as quantum hardware improves. Our approach of combining quantum searching with classical memory can also be applied to solving other challenging problems in computer science.
Perspectives
This paper is a great way to learn about quantum computing and its ability to solve challenging problems in computer science. Our approach of intermingling the strengths of quantum and classical computing can be applied to other questions like the Travelling Salesman or Knapsack Problem. Although we find IBM quantum computers to be extremely limited, it is a good platform for anyone trying to learn about the field.
Arul Mazumder
Massachusetts Academy of Math and Science
Read the Original
This page is a summary of: Comparisons of Classic and Quantum String Matching Algorithms✱, November 2022, ACM (Association for Computing Machinery),
DOI: 10.1145/3573834.3574498.
You can read the full text:
Contributors
The following have contributed to this page
