mlsanityData to 14 Oct 2026

Quantum Algorithm for the Shortest Superstring Problem

arXiv 2112.13319 ↗First posted 26 Dec 2021quant-ph cs.CL cs.DScited by 0

Not on the map. Why?

Abstract (arXiv)

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=(s1,dots,sn) 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.728n). Here O^* notation does not consider polynomials of n and the length of t.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 8 of its 32 references that are in the map. First posted on arXiv 26 Dec 2021.

Builds on

8 of 32 references.

References · 8

  1. 2018Quantum Speedups for Exponential-Time Dynamic Programming Algorithmscited by 6
  2. 2014Quantum pattern matching fast on averagecited by 3
  3. 2018Quantum Algorithm for Dynamic Programming Approach for DAGs. Applications for Zhegalkin Polynomial Evaluation and Some Problems on DAGscited by 2
  4. 2020Quantum-over-classical Advantage in Solving Multiplayer Gamescited by 2
  5. 2020Quantum Algorithms for the Most Frequently String Search, Intersection of Two String Sequences and Sorting of Strings Problemscited by 1
  6. 2020Classical and Quantum Algorithms for Constructing Text from Dictionary Problemcited by 1
  7. 2020Quantum Meets Fine-grained Complexity: Sublinear Time Quantum Algorithms for String Problemscited by 1
  8. 2021Near-Optimal Quantum Algorithms for String Problemscited by 1

Built on by

Not cited yet.