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+log m√nL) query complexity. In the case of SSP, we present a quantum algorithm with Õ(n³ 1.728ⁿ +L +n1.5√L) query complexity. Here Õ hides not only constants but logarithms of L and n also.