Quantum Circuits for Fixed Matching Substring Problems.

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 < n) and, the presence of any common substring of length d starting at the same position of both strings. Such problems find applications as sub-procedures in a variety of problems concerning text processing and sequence analysis. Notably, our approach yields polylogarithmic solutions, a stark contrast to the linear complexity inherent in the best classical alternatives.