Quantum algorithms for SCS and text assembling problems

In this paper, we consider two versions of the Text Assembling problem. We are given a sequence of strings s¹, , sⁿ of total length L that is a dictionary, and a string t of length m that is a text. The first version of the problem is assembling t from the dictionary. The second version is the ``Shortest Superstring Problem'' (SSP) or the ``Shortest Common Superstring Problem'' (SCS). In this case, t is not given, and we should construct the shortest string (we call it superstring) that contains each string from the given sequence as a substring. These problems are connected with the sequence assembly method for reconstructing a long DNA sequence from small fragments. For both problems, we suggest new quantum algorithms that work better than their classical counterparts. In the first case, we present a quantum algorithm with O (m+ mnL) query complexity. In the case of SSP, we present a quantum algorithm with O (n³ 1. 728ⁿ +L +n^1. 5L) query complexity. Here O hides not only constants but logarithms of L and n also.