Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Nonlinear Phenomena in Complex Systems

Classical and Quantum Algorithms for Assembling a Text from a Dictionary

Kamil Ravilevich Khadiev, Vladislav Remidovskii

Published Oct 12, 2021• 6 citations
Publisher

Abstract

We study algorithms for solving the problem of assembling a text (long string) from a dictionary (a sequence of small strings). The problem has an application in bioinformatics and has a connection with the sequence assembly method for reconstructing a long deoxyribonucleic-acid (DNA) sequence from small fragments. The problem is assembling a string t of length n from strings s1,...,sm. Firstly, we provide a classical (randomized) algorithm with running time Õ(nL0.5 + L) where L is the sum of lengths of s1,...,sm. Secondly, we provide a quantum algorithm with running time Õ(nL0.25 + √mL). Thirdly, we show the lower bound for a classical (randomized or deterministic) algorithm that is Ω(n+L). So, we obtain the quadratic quantum speed-up with respect to the parameter L; and our quantum algorithm have smaller running time comparing to any classical (randomized or deterministic) algorithm in the case of non-constant length of strings in the dictionary.

DOI
10.33581/1561-4085-2021-24-3-207-221

Related papers

Quantum algorithms for SCS and text assembling problems

Kamil Ravilevich Khadiev, Carlos Manuel Bosch Machado, Zeyu Chen +1 more

In this paper, we consider two versions of the Text Assembling problem. We are given a sequence of strings $s^1,\dots,s^n$ 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\sqrt{nL})$ query complexity. In the case of SSP, we present a quantum algorithm with $\tilde{O}(n^3 1.728^n +L +n^{1.5}\sqrt{L})$ query complexity. Here $\tilde{O}$ hides not only constants but logarithms of $L$ and $n$ also.

arXiv:2306.10572•Quantum Information and Computation•Mar 1, 2024•2 citations

Quantum algorithm for the shortest superstring problem

Kamil Ravilevich Khadiev, Carlos Manuel Bosch Machado

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

arXiv:2112.13319•International Conference on Micro- and Nano-Electronics (ICMNE)•Jan 31, 2022•6 citations

Quantum Algorithms for Some Strings Problems Based on Quantum String Comparator

Kamil Ravilevich Khadiev, Artem Ilikaev, Jevgēnijs Vihrovs

We study algorithms for solving three problems on strings. These are sorting of n strings of length k, “the Most Frequent String Search Problem”, and “searching intersection of two sequences of strings”. We construct quantum algorithms that are faster than classical (randomized or deterministic) counterparts for each of these problems. The quantum algorithms are based on the quantum procedure for comparing two strings of length k in O(k) queries. The first problem is sorting n strings of length k. We show that classical complexity of the problem is Θ(nk) for constant size alphabet, but our quantum algorithm has O˜(nk) complexity. The second one is searching the most frequent string among n strings of length k. We show that the classical complexity of the problem is Θ(nk), but our quantum algorithm has O˜(nk) complexity. The third problem is searching for an intersection of two sequences of strings. All strings have the same length k. The size of the first set is n, and the size of the second set is m. We show that the classical complexity of the problem is Θ((n+m)k), but our quantum algorithm has O˜((n+m)k) complexity.

Mathematics•Jan 26, 2022•13 citations

Quantum Algorithms for Genome Sequencing and Analysis

Josh Cudby, Sergii Strelchuk

The task of aligning DNA sequences has been pivotal in bioinformatics since the Needleman-Wunsch algorithm in 1970 [1]. Recent advances in sequencing technology have dramatically reduced the cost of DNA data acquisition, outpacing Moore's Law for computing costs. The COVID-19 pandemic further intensified data generation from viral and human samples, creating significant computational challenges. This study investigates the potential of near-term quantum computing to address these bottlenecks. We introduce two quantum algorithms tailored for crucial bioinformatics tasks. The first algorithm applies a quantum dynamic programming approach, inspired by Ambainis et al. [2], to pairwise Sequence Alignment, demonstrating minimal speedup. The second algorithm employs a quantum search via random walk, based on Magniez et al. [3], for the Center String problem, achieving a near-quadratic speedup over the best classical algorithm for unbounded alphabets and superior performance for bounded alphabets in key parameter regimes. Our findings suggest that while quantum computing offers promising speedups for certain bioinformatics problems, the extent of its benefits varies significantly across different tasks. Future work will investigate the potential of quantum computing in analysing graph-based representations of DNA data, such as pangenome models.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•3 citations

Genome assembly using quantum and quantum-inspired annealing

Aleksey S. Boev, Alexander Rakitko, Sergey R. Usmanov +5 more

Recent advances in DNA sequencing open prospects to make whole-genome analysis rapid and reliable, which is promising for various applications including personalized medicine. However, existing techniques for de novo genome assembly, which is used for the analysis of genomic rearrangements, chromosome phasing, and reconstructing genomes without a reference, require solving tasks of high computational complexity. Here we demonstrate a method for solving genome assembly tasks with the use of quantum and quantum-inspired optimization techniques. Within this method, we present experimental results on genome assembly using quantum annealers both for simulated data and the [Formula: see text]X 174 bacteriophage. Our results pave a way for a significant increase in the efficiency of solving bioinformatics problems with the use of quantum computing technologies and, in particular, quantum annealing might be an effective method. We expect that the new generation of quantum annealing devices would outperform existing techniques for de novo genome assembly. To the best of our knowledge, this is the first experimental study of de novo genome assembly problems both for real and synthetic data on quantum annealing devices and quantum-inspired techniques.

arXiv:2004.06719•Scientific Reports•Jun 23, 2021•72 citations

Quantum Pattern Matching in Generalised Degenerate Strings

Massimo Equi, Md Rabiul Islam Khan, Veli Mäkinen

A degenerate string is a sequence of sets of characters. A generalized degenerate (GD) string extends this notion to the sequence of sets of strings, where strings of the same set are of equal length. Finding an exact match for a pattern string inside a GD string can be done in $O(mn+N)$ time (Ascone et al., WABI 2024), where $m$ is the pattern length, $n$ is the number of strings and $N$ the total length of strings constituting the GD string. This is the best classical algorithm achieved so far, and no matching lower bound, neither unconditional nor conditional, has been shown. We make progress on this problem proposing a quantum algorithm that achieves running time $\tilde{O}(\sqrt{mnN})$, thus beating the current best classical solution. To the best of our knowledge, this is the first quantum algorithm proposed in the context of GD strings. We present our results starting from the framework of classical parallel computing, which we believe makes them intuitive to understand and possibly easy to generalise to other similar structures.

quant-pharXiv:2603.16297•Mar 18, 2026•1 citation
We study algorithms for solving the problem of assembling a text (long string) from a dictionary (a sequence of small strings). The problem has an application in bioinformatics and has a connection with the sequence assembly method for reconstructing a long deoxyribonucleic-acid (DNA) sequence from small fragments. The problem is assembling a string t of length n from strings s1,...,sm. Firstly, we provide a classical (randomized) algorithm with running time Õ(nL0.5 + L) where L is the sum of lengths of s1,...,sm. Secondly, we provide a quantum algorithm with running time Õ(nL0.25 + √mL). Thirdly, we show the lower bound for a classical (randomized or deterministic) algorithm that is Ω(n+L). So, we obtain the quadratic quantum speed-up with respect to the parameter L; and our quantum algorithm have smaller running time comparing to any classical (randomized or deterministic) algorithm in the case of non-constant length of strings in the dictionary.
In this paper, we consider two versions of the Text Assembling problem. We are given a sequence of strings s1,…,sns^1,\dots,s^ns1,…,sn of total length LLL that is a dictionary, and a string ttt of length mmm that is a text. The first version of the problem is assembling ttt from the dictionary. The second version is the ``Shortest Superstring Problem''(SSP) or the ``Shortest Common Superstring Problem''(SCS). In this case, ttt 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⁡mnL)O(m+\log m\sqrt{nL})O(m+logmnL​) query complexity. In the case of SSP, we present a quantum algorithm with O~(n31.728n+L+n1.5L)\tilde{O}(n^3 1.728^n +L +n^{1.5}\sqrt{L})O~(n31.728n+L+n1.5L​) query complexity. Here O~\tilde{O}O~ hides not only constants but logarithms of LLL and nnn also.
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, . . . , 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.
We study algorithms for solving three problems on strings. These are sorting of n strings of length k, “the Most Frequent String Search Problem”, and “searching intersection of two sequences of strings”. We construct quantum algorithms that are faster than classical (randomized or deterministic) counterparts for each of these problems. The quantum algorithms are based on the quantum procedure for comparing two strings of length k in O(k) queries. The first problem is sorting n strings of length k. We show that classical complexity of the problem is Θ(nk) for constant size alphabet, but our quantum algorithm has O˜(nk) complexity. The second one is searching the most frequent string among n strings of length k. We show that the classical complexity of the problem is Θ(nk), but our quantum algorithm has O˜(nk) complexity. The third problem is searching for an intersection of two sequences of strings. All strings have the same length k. The size of the first set is n, and the size of the second set is m. We show that the classical complexity of the problem is Θ((n+m)k), but our quantum algorithm has O˜((n+m)k) complexity.
The task of aligning DNA sequences has been pivotal in bioinformatics since the Needleman-Wunsch algorithm in 1970 [1]. Recent advances in sequencing technology have dramatically reduced the cost of DNA data acquisition, outpacing Moore's Law for computing costs. The COVID-19 pandemic further intensified data generation from viral and human samples, creating significant computational challenges. This study investigates the potential of near-term quantum computing to address these bottlenecks. We introduce two quantum algorithms tailored for crucial bioinformatics tasks. The first algorithm applies a quantum dynamic programming approach, inspired by Ambainis et al. [2], to pairwise Sequence Alignment, demonstrating minimal speedup. The second algorithm employs a quantum search via random walk, based on Magniez et al. [3], for the Center String problem, achieving a near-quadratic speedup over the best classical algorithm for unbounded alphabets and superior performance for bounded alphabets in key parameter regimes. Our findings suggest that while quantum computing offers promising speedups for certain bioinformatics problems, the extent of its benefits varies significantly across different tasks. Future work will investigate the potential of quantum computing in analysing graph-based representations of DNA data, such as pangenome models.
Recent advances in DNA sequencing open prospects to make whole-genome analysis rapid and reliable, which is promising for various applications including personalized medicine. However, existing techniques for de novo genome assembly, which is used for the analysis of genomic rearrangements, chromosome phasing, and reconstructing genomes without a reference, require solving tasks of high computational complexity. Here we demonstrate a method for solving genome assembly tasks with the use of quantum and quantum-inspired optimization techniques. Within this method, we present experimental results on genome assembly using quantum annealers both for simulated data and the [Formula: see text]X 174 bacteriophage. Our results pave a way for a significant increase in the efficiency of solving bioinformatics problems with the use of quantum computing technologies and, in particular, quantum annealing might be an effective method. We expect that the new generation of quantum annealing devices would outperform existing techniques for de novo genome assembly. To the best of our knowledge, this is the first experimental study of de novo genome assembly problems both for real and synthetic data on quantum annealing devices and quantum-inspired techniques.
A degenerate string is a sequence of sets of characters. A generalized degenerate (GD) string extends this notion to the sequence of sets of strings, where strings of the same set are of equal length. Finding an exact match for a pattern string inside a GD string can be done in O(mn+N)O(mn+N)O(mn+N) time (Ascone et al., WABI 2024), where mmm is the pattern length, nnn is the number of strings and NNN the total length of strings constituting the GD string. This is the best classical algorithm achieved so far, and no matching lower bound, neither unconditional nor conditional, has been shown. We make progress on this problem proposing a quantum algorithm that achieves running time O~(mnN)\tilde{O}(\sqrt{mnN})O~(mnN​), thus beating the current best classical solution. To the best of our knowledge, this is the first quantum algorithm proposed in the context of GD strings. We present our results starting from the framework of classical parallel computing, which we believe makes them intuitive to understand and possibly easy to generalise to other similar structures.