A Quantum Circuit for the Cyclic String Matching Problem

The cyclic string matching problem aims to detect an occurrence of any cyclical shift of a given sequence of characters within a (usually larger) one. This variant of the (classical) string matching problem arises in several real-world problems, such as DNA analysis and spoken natural language recognition, in which it is necessary to deal with sequences that lack a precise beginning or end and are equivalent up to cyclical shifting. We present a quantum algorithm, in the form of a quantum circuit, for solving the cyclic string matching problem. This algorithm requires quadratically fewer time steps than the most efficient counterpart algorithm running on a classical machine. Additionally, we provide a p