A General Quantum Circuit for String Matching: Unleashing Quantum Path Parallelism

Text searching is a fundamental problem in computer science, and it finds applications in several scientific fields. The string matching problem is the common framework for the class of text searching problems where the objective is to find all, possibly approximate, occurrences of a given pattern of length m within a larger text of length n. This paper introduces the quantum path parallelism approach, that is, a general strategy based on quantum computation, which is easily adapted to a variety of nonstandard text-searching problems. Our method translates a text-searching problem into an automata-based string-recognition problem, associating each possible approximation of the pattern with a different path accepted by the automaton. Under favorable conditions, our algorithm solves an approximate search problem in -time, yielding a quadratic speed-up over classical solutions. In other cases, such a speed-up is achieved only for short patterns, i.e. whenever . We show the flexibility of our method, giving explicit adaptations to some specific approximate string matching problems.