| Форма представления | Статьи в зарубежных журналах и сборниках |
| Год публикации | 2024 |
| Язык | английский |
|
Хадиев Камиль Равилевич, автор
|
| Библиографическое описание на языке оригинала |
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. |
| Аннотация |
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. |
| Ключевые слова |
quantum algorithms, shortest common superstring, NP-complete problems |
| Название журнала |
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 |
| Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на эту карточку |
https://repository.kpfu.ru/?p_id=297969 |
Полная запись метаданных  |
| Поле DC |
Значение |
Язык |
| dc.contributor.author |
Хадиев Камиль Равилевич |
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/?p_id=297969 |
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 |
Статьи в зарубежных журналах и сборниках |
ru_RU |
|
EN 
中文 
ES 
Карта сайта
