Quantum Algorithm for the Shortest Superstring Problem

2021/12/26 by Kamil Khadiev, Khadiev, Kamil, Carlos Manuel Bosch Machado +1 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Coding theory and cryptography #Computation and Language (cs.CL) #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph)

paper · pdf · doi:10.48550/arxiv.2112.13319

openalex publication_date 2021/12/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper, we consider the ``Shortest Superstring Problem''(SSP) or the ``Shortest Common Superstring Problem''(SCS). The problem is as follows. For a positive integer n, a sequence of n strings S=(s¹,…,sⁿ) is given. We should construct the shortest string t (we call it superstring) that contains each string from the given sequence as a substring. The problem is connected with the sequence assembly method for reconstructing a long DNA sequence from small fragments. We present a quantum algorithm with running time O^*(1.728ⁿ). Here O^* notation does not consider polynomials of n and the length of t.

Cited by

• Quantum Algorithm for Searching for the Longest Segment and the Largest Empty Rectangle

Related

• Near-Optimal Quantum Algorithms for String Problems
• Classical and Quantum Algorithms for Constructing Text from Dictionary\n Problem
• Parameterized quantum algorithms for closest string problems
• Greedy Shortest Common Superstring Approximation in Compact Space
• Near-Optimal Quantum Algorithm for Finding the Longest Common Substring between Run-Length Encoded Strings