Quantum algorithm for the shortest superstring problem

Kamil Khadiev; Carlos Manuel Bosch Machado

doi:10.1117/12.2624618

30 January 2022 Quantum algorithm for the shortest superstring problem

Kamil Khadiev, Carlos Manuel Bosch Machado

Proceedings Volume 12157, International Conference on Micro- and Nano-Electronics 2021; 1215724 (2022) https://doi.org/10.1117/12.2624618
Event: International Conference on Micro- and Nano-Electronics 2021, 2021, Zvenigorod, Russian Federation

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.

Citation Download Citation

Kamil Khadiev and Carlos Manuel Bosch Machado "Quantum algorithm for the shortest superstring problem", Proc. SPIE 12157, International Conference on Micro- and Nano-Electronics 2021, 1215724 (30 January 2022); https://doi.org/10.1117/12.2624618

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available