Quantum Algorithm for the Shortest Superstring Problem
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^1,\dots,s^n)$ 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^n)$. Here $O^*$ notation does not consider polynomials of $n$ and the length of $t$.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
A supervised hybrid quantum machine learning solution to the emergency escape routing problem
Managing the response to natural disasters effectively can considerably mitigate their devastating impact. This work explores the potential of using supervised hybrid quantum machine learning to optimize emergency evacua…
Quantum Machine LearningChallenges in Applying Variational Quantum Algorithms to Dynamic Satellite Network Routing
Applying near-term variational quantum algorithms to the problem of dynamic satellite network routing represents a promising direction for quantum computing. In this work, we provide a critical evaluation of two major ap…
Reinforcement LearningReverse Annealing for Nonnegative/Binary Matrix Factorization
It was recently shown that quantum annealing can be used as an effective, fast subroutine in certain types of matrix factorization algorithms. The quantum annealing algorithm performed best for quick, approximate answers…
Domain-Informed Representation for Evolutionary Sieving in Integral and Module Lattices
Traditional cryptography, rooted in problems, e.g., integer factorisation or discrete log, is inevitably vulnerable to a fully operational quantum computer. Although it remains an engineering frontier, the looming threat…
Novel algorithm to generate shortest edit script using Levenshtein distance algorithm
String similarity, longest common subsequence and shortest edit scripts are the triplets of problem that related to each other. There are different algorithms exist to generate edit script by solving longest common subse…
Edit script generationFile difference