Quantum Algorithms for the Shortest Common Superstring and Text Assembling Problems

Abstract

In this paper, we consider two versions of the Text Assembling problem. We are given a sequence of strings $s^1,\dots ,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\sqrt{nL})$ running time. In the case of SSP, we present a quantum algorithm with running time $O(n^{3}1.728^n+L+\sqrt{L}{n}^{1.5}+\sqrt{L}n{\log }^{2}L{\log }^{2}n)$.

arXiv admin note: text overlap with arXiv:2112.13319

References in corpus (1)

• Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language

Cited by in corpus (1)

• Implementation of Quantum Fourier Transform and Quantum Hashing for a Quantum Device with Arbitrary Qubits Connection Graphs