WORLD SCIENTIFIC eBooks
Quantum Approximate String Matching for Large Alphabets
Jeffrey A. Aborot
Abstract
In this article we present a quantum algorithm for finding approximate copies of a pattern within a much longer text. The algorithm is based mainly on amplitude amplification technique used in Grover’s quantum search algorithm and is more suited for instances in which the size of the alphabet is at least twice as the number of distinct symbols of the pattern. The algorithm is composed of a filtering phase for trimming the search space and a verification phase for determining solution indices in the text. We present details of each subroutine used in the algorithm. The algorithm returns all solution indices within the text with number of iterations proportional to the ratio of the size of the text and the number of distinct symbols in the pattern with high probability. Overall, the time complexity of the algorithm is mainly influenced by the size of the text.