Solving the exact pattern matching problem constrained to single occurrence of pattern p in string s using Grover's quantum search algorithm
College
College of Computer Studies
Department/Unit
Computer Science
Document Type
Conference Proceeding
Source Title
Proceedings in Information and Communications Technology
Volume
7
First Page
124
Last Page
142
Publication Date
2013
Abstract
In this paper we present an application of Grover’s Quantum Search Algorithm in solving the Exact Pattern Matching Problem. We discuss the details of each step of the algorithm, from the preparation, initialization, evolution and measurement of the final state of the quantum memory registers and the verification of the measurement result. We also discuss the inner workings of the Oracle in identifying the solution state |ix> from among the other superpositioned states |i>s. Analysis of the running time of the algorithm will lead us to the worst-case running time of O(√N) (such that N is the length of the string) proportional to the length of the pattern we are searching for within the string. Some basic concepts in quantum mechanics necessary for understanding the topic are also presented.
html
Recommended Citation
de Jesus, B. A., Aborot, J. A., & Adorna, H. N. (2013). Solving the exact pattern matching problem constrained to single occurrence of pattern p in string s using Grover's quantum search algorithm. Proceedings in Information and Communications Technology, 7, 124-142. Retrieved from https://animorepository.dlsu.edu.ph/faculty_research/13740
Disciplines
Computer Engineering | Engineering
Keywords
Quantum computing
Upload File
wf_no
