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

arXiv:2306.10572 · Quantum Information and Computation

Quantum algorithms for SCS and text assembling problems

Kamil Ravilevich Khadiev, Carlos Manuel Bosch Machado, Zeyu Chen, Junde Wu

Published Mar 1, 2024• 2 citations
arXivHTMLPDF

Abstract

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.

DOI
10.26421/qic24.3-4-4

Related papers

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

Classical and Quantum Algorithms for Assembling a Text from a Dictionary

Kamil Ravilevich Khadiev, Vladislav Remidovskii

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.

Nonlinear Phenomena in Complex Systems•Oct 12, 2021•6 citations

Quantum Circuits for Fixed Substring Matching Problems

Domenico Aldo Cantone, Simone Faro, Arianna Pavone +1 more

Quantum computation represents a computational paradigm whose distinctive attributes confer the ability to devise algorithms with asymptotic performance levels significantly superior to those achievable via classical computation. Recent strides have been taken to apply this computational framework in tackling and resolving various issues related to text processing. The resultant solutions demonstrate marked advantages over their classical counterparts. This study employs quantum computation to efficaciously surmount text processing challenges, particularly those involving string comparison. The focus is on the alignment of fixed-length substrings within two input strings. Specifically, given two input strings, $x$ and $y$, both of length $n$, and a value $d \leq n$, we want to verify the following conditions: the existence of a common prefix of length $d$, the presence of a common substring of length $d$ beginning at position $j$ (with $0 \leq j < n$) and, the presence of any common substring of length $d$ beginning in both strings at the same position. Such problems find applications as sub-procedures in a variety of problems concerning text processing and sequence analysis. Notably, our approach furnishes polylogarithmic solutions, a stark contrast to the linear complexity inherent in the best classical alternatives.

arXiv:2308.11758•Aug 22, 2023•2 citations

Quantum Speed-ups for String Synchronizing Sets, Longest Common Substring, and k -mismatch Matching

Ce Jin, Jakob Nogler

Longest Common Substring (LCS) is an important text processing problem, which has recently been investigated in the quantum query model. The decisional version of this problem, LCS with threshold d, asks whether two length-n input strings have a common substring of length d. The two extreme cases, d = 1 and d = n, correspond respectively to Element Distinctness and Unstructured Search, two fundamental problems in quantum query complexity. However, the intermediate case 1 ≪ d ≪ n was not fully understood.

arXiv:2211.15945•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2023•23 citations

Near-Optimal Quantum Algorithms for String Problems

Shyan Akmal, Ce Jin

We study quantum algorithms for several fundamental string problems, including Longest Common Substring, Lexicographically Minimal String Rotation, and Longest Square Substring. These problems have been widely studied in the stringology literature since the 1970s, and are known to be solvable by near-linear time classical algorithms. In this work, we give quantum algorithms for these problems with near-optimal query complexities and time complexities. Specifically, we show that: Longest Common Substring can be solved by a quantum algorithm in Õ(n2/3) time, improving upon the recent Õ(n5/6)-time algorithm by Le Gall and Seddighin (2020). Our algorithm uses the MNRS quantum walk framework, together with a careful combination of string synchronizing sets (Kempa and Kociumaka, 2019) and generalized difference covers. Lexicographically Minimal String Rotation can be solved by a quantum algorithm in n1/2 + o(1) time, improving upon the recent Õ(n3/4)-time algorithm by Wang and Ying (2020). We design our algorithm by first giving a new classical divide-and-conquer algorithm in near-linear time based on exclusion rules, and then speeding it up quadratically using nested Grover search and quantum minimum finding. Longest Square Substring can be solved by a quantum algorithm in time. Our algorithm is an adaptation of the algorithm by Le Gall and Seddighin (2020) for the Longest Palindromic Substring problem, but uses additional techniques to overcome the difficulty that binary search no longer applies. Our techniques naturally extend to other related string problems, such as Longest Repeated Substring, Longest Lyndon Substring, and Minimal Suffix.

arXiv:2110.09696•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2022•30 citations

Near-Optimal Quantum Algorithms for String Problems

Shyan Akmal, Ce Jin

Abstract We study quantum algorithms for several fundamental string problems, including Longest Common Substring, Lexicographically Minimal String Rotation, and Longest Square Substring. These problems have been widely studied in the stringology literature since the 1970s, and are known to be solvable by near-linear time classical algorithms. In this work, we give quantum algorithms for these problems with near-optimal query complexities and time complexities. Specifically, we show that: Longest Common Substring can be solved by a quantum algorithm in $$\tilde{O}(n^{2/3})$$ O ~ ( n 2 / 3 ) time, improving upon the recent $$\tilde{O}(n^{5/6})$$ O ~ ( n 5 / 6 ) -time algorithm by Le Gall and Seddighin (in: Proceedings of the 13th innovations in theoretical computer science conference (ITCS 2022), pp 97:1–97:23, 2022. https://doi.org/10.4230/LIPIcs.ITCS.2022.97 ). Our algorithm uses the MNRS quantum walk framework, together with a careful combination of string synchronizing sets (Kempa and Kociumaka, in: Proceedings of the 51st annual ACM SIGACT symposium on theory of computing (STOC 2019), ACM, pp 756–767, 2019. https://doi.org/10.1145/3313276.3316368 ) and generalized difference covers. Lexicographically Minimal String Rotation can be solved by a quantum algorithm in $$n^{1/2 + o(1)}$$ n 1 / 2 + o ( 1 ) time, improving upon the recent $$\tilde{O}(n^{3/4})$$ O ~ ( n 3 / 4 ) -time algorithm by Wang and Ying (in: Quantum algorithm for lexicographically minimal string rotation. CoRR, 2020. arXiv:2012.09376 ). We design our algorithm by first giving a new classical divide-and-conquer algorithm in near-linear time based on exclusion rules, and then speeding it up quadratically using nested Grover search and quantum minimum finding. Longest Square Substring can be solved by a quantum algorithm in $$\tilde{O}(\sqrt{n})$$ O ~ ( n ) time. Our algorithm is an adaptation of the algorithm by Le Gall and Seddighin (2022) for the Longest Palindromic Substring problem, but uses additional techniques to overcome the difficulty that binary search no longer applies. Our techniques naturally extend to other related string problems, such as Longest Repeated Substring, Longest Lyndon Substring, and Minimal Suffix.

Algorithmica•Jan 27, 2023•19 citations
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 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.
Quantum computation represents a computational paradigm whose distinctive attributes confer the ability to devise algorithms with asymptotic performance levels significantly superior to those achievable via classical computation. Recent strides have been taken to apply this computational framework in tackling and resolving various issues related to text processing. The resultant solutions demonstrate marked advantages over their classical counterparts. This study employs quantum computation to efficaciously surmount text processing challenges, particularly those involving string comparison. The focus is on the alignment of fixed-length substrings within two input strings. Specifically, given two input strings, xxx and yyy, both of length nnn, and a value d≤nd \leq nd≤n, we want to verify the following conditions: the existence of a common prefix of length ddd, the presence of a common substring of length ddd beginning at position jjj (with 0≤j<n0 \leq j < n0≤j<n) and, the presence of any common substring of length ddd beginning in both strings at the same position. Such problems find applications as sub-procedures in a variety of problems concerning text processing and sequence analysis. Notably, our approach furnishes polylogarithmic solutions, a stark contrast to the linear complexity inherent in the best classical alternatives.
Longest Common Substring (LCS) is an important text processing problem, which has recently been investigated in the quantum query model. The decisional version of this problem, LCS with threshold d, asks whether two length-n input strings have a common substring of length d. The two extreme cases, d = 1 and d = n, correspond respectively to Element Distinctness and Unstructured Search, two fundamental problems in quantum query complexity. However, the intermediate case 1 ≪ d ≪ n was not fully understood.
We study quantum algorithms for several fundamental string problems, including Longest Common Substring, Lexicographically Minimal String Rotation, and Longest Square Substring. These problems have been widely studied in the stringology literature since the 1970s, and are known to be solvable by near-linear time classical algorithms. In this work, we give quantum algorithms for these problems with near-optimal query complexities and time complexities. Specifically, we show that: Longest Common Substring can be solved by a quantum algorithm in Õ(n2/3) time, improving upon the recent Õ(n5/6)-time algorithm by Le Gall and Seddighin (2020). Our algorithm uses the MNRS quantum walk framework, together with a careful combination of string synchronizing sets (Kempa and Kociumaka, 2019) and generalized difference covers. Lexicographically Minimal String Rotation can be solved by a quantum algorithm in n1/2 + o(1) time, improving upon the recent Õ(n3/4)-time algorithm by Wang and Ying (2020). We design our algorithm by first giving a new classical divide-and-conquer algorithm in near-linear time based on exclusion rules, and then speeding it up quadratically using nested Grover search and quantum minimum finding. Longest Square Substring can be solved by a quantum algorithm in time. Our algorithm is an adaptation of the algorithm by Le Gall and Seddighin (2020) for the Longest Palindromic Substring problem, but uses additional techniques to overcome the difficulty that binary search no longer applies. Our techniques naturally extend to other related string problems, such as Longest Repeated Substring, Longest Lyndon Substring, and Minimal Suffix.
Abstract We study quantum algorithms for several fundamental string problems, including Longest Common Substring, Lexicographically Minimal String Rotation, and Longest Square Substring. These problems have been widely studied in the stringology literature since the 1970s, and are known to be solvable by near-linear time classical algorithms. In this work, we give quantum algorithms for these problems with near-optimal query complexities and time complexities. Specifically, we show that: Longest Common Substring can be solved by a quantum algorithm in O~(n2/3)\tilde{O}(n^{2/3})O~(n2/3) O ~ ( n 2 / 3 ) time, improving upon the recent O~(n5/6)\tilde{O}(n^{5/6})O~(n5/6) O ~ ( n 5 / 6 ) -time algorithm by Le Gall and Seddighin (in: Proceedings of the 13th innovations in theoretical computer science conference (ITCS 2022), pp 97:1–97:23, 2022. https://doi.org/10.4230/LIPIcs.ITCS.2022.97 ). Our algorithm uses the MNRS quantum walk framework, together with a careful combination of string synchronizing sets (Kempa and Kociumaka, in: Proceedings of the 51st annual ACM SIGACT symposium on theory of computing (STOC 2019), ACM, pp 756–767, 2019. https://doi.org/10.1145/3313276.3316368 ) and generalized difference covers. Lexicographically Minimal String Rotation can be solved by a quantum algorithm in n1/2+o(1)n^{1/2 + o(1)}n1/2+o(1) n 1 / 2 + o ( 1 ) time, improving upon the recent O~(n3/4)\tilde{O}(n^{3/4})O~(n3/4) O ~ ( n 3 / 4 ) -time algorithm by Wang and Ying (in: Quantum algorithm for lexicographically minimal string rotation. CoRR, 2020. arXiv:2012.09376 ). We design our algorithm by first giving a new classical divide-and-conquer algorithm in near-linear time based on exclusion rules, and then speeding it up quadratically using nested Grover search and quantum minimum finding. Longest Square Substring can be solved by a quantum algorithm in O~(n)\tilde{O}(\sqrt{n})O~(n​) O ~ ( n ) time. Our algorithm is an adaptation of the algorithm by Le Gall and Seddighin (2022) for the Longest Palindromic Substring problem, but uses additional techniques to overcome the difficulty that binary search no longer applies. Our techniques naturally extend to other related string problems, such as Longest Repeated Substring, Longest Lyndon Substring, and Minimal Suffix.