KFU. Card publication. QUANTUM ALGORITHMS FOR THE SHORTEST COMMON SUPERSTRING AND TEXT ASSEMBLING PROBLEMS

KAZAN
FEDERAL UNIVERSITY

- RUS
- 中文
- ES

QUANTUM ALGORITHMS FOR THE SHORTEST COMMON SUPERSTRING AND TEXT ASSEMBLING PROBLEMS

Form of presentation

Articles in international journals and collections

Year of publication

2024

��

��

Authors, employees of KFU

Khadiev Kamil Ravilevich, author

Bibliographic description in the original language

Khadiev K, Bosch Machado C.M, Chen Z, Wu J, QUANTUM ALGORITHMS FOR THE SHORTEST COMMON SUPERSTRING AND TEXT ASSEMBLING PROBLEMS//Quantum Information and Computation. - 2024. - Vol.24, Is.3-4. - P.267-294.

Annotation

In this paper, we consider two versions of the Text Assembling problem. We are given a sequence of strings s1, …, sn of total length L that is a dictionary, and a string t of length m that is a text. The first version of the problem is assembling t from the dictionary. The second version is the “Shortest Superstring Problem”(SSP) or the “Shortest Common Superstring Problem”(SCS). In this case, t is not given, and we should construct the shortest string (we call it superstring) that contains each string from the given sequence as a substring. These problems are connected with the sequence assembly method for reconstructing a long DNA sequence from small fragments. For both problems, we suggest new quantum algorithms that work better than their classical counterparts. In the first case, we present a quantum algorithm with O(m+log m√nL) query complexity. In the case of SSP, we present a quantum algorithm with Õ(n^3*1.728^n + L + n^1.5√L) query complexity. Here Õ hides not only constants but logarithms of L and n also.

Keywords

quantum algorithms, shortest common superstring, NP-complete problems

The name of the journal

Quantum Information and Computation

URL

https://www.scopus.com/inward/record.uri?eid=2-s2.0-85188899281&doi=10.26421%2fQIC24.3-4-4&partnerID=40&md5=3d6712dd95d5d0ec6d918a0c95fd9bd4

Please use this ID to quote from or refer to the card

https://repository.kpfu.ru/eng/?p_id=297969&p_lang=2

Full metadata record

Field DC	Value	Language
dc.contributor.author	Khadiev Kamil Ravilevich	ru_RU
dc.date.accessioned	2024-01-01T00:00:00Z	ru_RU
dc.date.available	2024-01-01T00:00:00Z	ru_RU
dc.date.issued	2024	ru_RU
dc.identifier.citation	Khadiev K, Bosch Machado C.M, Chen Z, Wu J, QUANTUM ALGORITHMS FOR THE SHORTEST COMMON SUPERSTRING AND TEXT ASSEMBLING PROBLEMS//Quantum Information and Computation. - 2024. - Vol.24, Is.3-4. - P.267-294.	ru_RU
dc.identifier.uri	https://repository.kpfu.ru/eng/?p_id=297969&p_lang=2	ru_RU
dc.description.abstract	Quantum Information and Computation	ru_RU
dc.description.abstract	In this paper, we consider two versions of the Text Assembling problem. We are given a sequence of strings s1, …, sn of total length L that is a dictionary, and a string t of length m that is a text. The first version of the problem is assembling t from the dictionary. The second version is the “Shortest Superstring Problem”(SSP) or the “Shortest Common Superstring Problem”(SCS). In this case, t is not given, and we should construct the shortest string (we call it superstring) that contains each string from the given sequence as a substring. These problems are connected with the sequence assembly method for reconstructing a long DNA sequence from small fragments. For both problems, we suggest new quantum algorithms that work better than their classical counterparts. In the first case, we present a quantum algorithm with O(m+log m√nL) query complexity. In the case of SSP, we present a quantum algorithm with Õ(n^3*1.728^n + L + n^1.5√L) query complexity. Here Õ hides not only constants but logarithms of L and n also.	ru_RU
dc.language.iso	ru	ru_RU
dc.subject	quantum algorithms	ru_RU
dc.subject	shortest common superstring	ru_RU
dc.subject	NP-complete problems	ru_RU
dc.title	QUANTUM ALGORITHMS FOR THE SHORTEST COMMON SUPERSTRING AND TEXT ASSEMBLING PROBLEMS	ru_RU
dc.type	Articles in international journals and collections	ru_RU