Quantum Algorithms for the Shortest Common Superstring and Text Assembling Problems
share
In this paper, we consider two versions of the Text Assembling problem. We are given a sequence of strings s^1,…,s^n of total length L that is a dictionary, and a string t of length m that is texts. 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)) running time. In the case of SSP, we present a quantum algorithm with running time O(n^3 1.728^n +L +√(L)n^1.5+√(L)nlog^2Llog^2n).
READ FULL TEXT