# Quantum Algorithm for the Shortest Superstring Problem

arXiv: https://arxiv.org/abs/2112.13319 · HTML: https://mlsanity.com/paper/2112.13319/

## 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 (most cited first, 8 of 8)

- [Quantum Speedups for Exponential-Time Dynamic Programming Algorithms](https://mlsanity.com/paper/1807.05209/) (2018)
- [Quantum pattern matching fast on average](https://mlsanity.com/paper/1408.1816/) (2014)
- [Quantum Algorithm for Dynamic Programming Approach for DAGs. Applications for Zhegalkin Polynomial Evaluation and Some Problems on DAGs](https://mlsanity.com/paper/1804.09950/) (2018)
- [Quantum-over-classical Advantage in Solving Multiplayer Games](https://mlsanity.com/paper/2006.06965/) (2020)
- [Quantum Algorithms for the Most Frequently String Search, Intersection of Two String Sequences and Sorting of Strings Problems](https://mlsanity.com/paper/2001.01914/) (2020)
- [Classical and Quantum Algorithms for Constructing Text from Dictionary Problem](https://mlsanity.com/paper/2005.14335/) (2020)
- [Quantum Meets Fine-grained Complexity: Sublinear Time Quantum Algorithms for String Problems](https://mlsanity.com/paper/2010.12122/) (2020)
- [Near-Optimal Quantum Algorithms for String Problems](https://mlsanity.com/paper/2110.09696/) (2021)

## 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.