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 commentarXiv admin note: text overlap with arXiv:2112.13319

References in corpus (11)

• A Quantum Algorithm for Finding the Minimum
• Quantum query complexity of state conversion
• Quantum Search on Bounded-Error Inputs
• Tradeoffs in the Quantum Search Algorithm
• 1-way quantum finite automata: strengths, weaknesses and generalizations
• Reordering Method and Hierarchies for Quantum and Classical Ordered Binary Decision Diagrams
• Quantum Meets Fine-grained Complexity: Sublinear Time Quantum Algorithms for String Problems
• An optimal quantum algorithm for the oracle identification problem
• Quantum Algorithms for String Processing
• Lecture Notes on Quantum Algorithms
• 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