Quantum Path Parallelism: A Circuit-Based Approach to Text Searching

Abstract

Text searching problems are fundamental problems in computer science whose applications are found in a variety of 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. In this paper, we present the quantum path parallelism approach, a general strategy based on quantum computation that can be easily adapted to a variety of nonstandard text searching problems. Our method translates a text searching problem to an automata-based string recognition problem, associating each possible approximation of the pattern with a different path accepted by the automaton. Under favourable conditions, our proposed method solves the approximate search problem in O(nmlog2(n)) time, offering a quadratic speed-up over classical solutions. In other cases such speed-up is achieved only for short patterns, i.e. assuming m=O(log(n)). As a demonstration of the flexibility of our method, we show how it can be adapted for solving some approximate string matching problems, obtaining a significant quantum advantage.