Quantum Circuits for Fixed Matching Substring Problems

Abstract

Quantum computational models enable the design of algorithms that are often significantly more efficient than their most competitive counterpart classical solutions. Recently, strides have been made to take advantage of the quantum computational framework in tackling problems arising in the context of text processing. Our work fits in such a research direction. We focused on challenges arising from string comparison problems and, specifically, on the alignment of fixed-length substrings that are found within two input strings. To be precise, given two input strings, x and y, both of length n, and a value d⩽n, we want to verify the following conditions: the existence of a common prefix of length d, the presence of a common substring of length d starting at position j (with 0⩽j