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})$ time, improving upon the recent $\tilde O(n^{5/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 $n^{1/2 + o(1)}$ time, improving upon the recent $\tilde O(n^{3/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 $\tilde O(\sqrt{n})$ 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.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})$ time, improving upon the recent $\tilde O(n^{5/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 $n^{1/2 + o(1)}$ time, improving upon the recent $\tilde O(n^{3/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 $\tilde O(\sqrt{n})$ 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.09696Oct 19, 20211 citation

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

AlgorithmicaJan 27, 202311 citations

Quantum algorithms for longest common and palindromic substrings in the circuit model

Domenico Cantone, Simone Faro, Arianna Pavone +1 more

The Longest Common Substring (LCS) and Longest Palindromic Substring (LPS) problems are fundamental challenges in string processing, traditionally solved in linear time using classical computation through suffix trees. Recent breakthroughs by Le Gall and Seddighin [1] introduced sublinear quantum query algorithms, while Akmal and Jin [2] further improved the LCS complexity to O ˜ ( n 2 / 3 ) . While these results are remarkable in the quantum query model , their practical implementation on real quantum hardware remains elusive. In this paper, we bridge this gap by presenting the first O ˜ ( n ) quantum algorithms for both LCS and LPS in the circuit model of computation . Our circuits are explicitly constructed and analyzed in terms of size and depth, achieving polylogarithmic overheads while preserving the O ˜ ( n ) depth bound. This provides, for the first time, concrete circuit-level blueprints and resource estimates for quantum solutions to LCS and LPS.The Longest Common Substring (LCS) and Longest Palindromic Substring (LPS) problems are fundamental challenges in string processing, traditionally solved in linear time using classical computation through suffix trees. Recent breakthroughs by Le Gall and Seddighin [1] introduced sublinear quantum query algorithms, while Akmal and Jin [2] further improved the LCS complexity to O ˜ ( n 2 / 3 ) . While these results are remarkable in the quantum query model , their practical implementation on real quantum hardware remains elusive. In this paper, we bridge this gap by presenting the first O ˜ ( n ) quantum algorithms for both LCS and LPS in the circuit model of computation . Our circuits are explicitly constructed and analyzed in terms of size and depth, achieving polylogarithmic overheads while preserving the O ˜ ( n ) depth bound. This provides, for the first time, concrete circuit-level blueprints and resource estimates for quantum solutions to LCS and LPS.

Theoretical Computer ScienceDec 21, 20251 citation

Quantum Meets Fine-Grained Complexity: Sublinear Time Quantum Algorithms for String Problems

François Le Gall, Saeed Seddighin

Abstract Longest common substring (), longest palindrome substring (), and Ulam distance () are three fundamental string problems that can be classically solved in near linear time. In this work, we present sublinear time quantum algorithms for these problems along with quantum lower bounds. Our results shed light on a very surprising fact: Although the classic solutions for and are almost identical (via suffix trees), their quantum computational complexities are different. While we give an exact ${{\tilde{O}}}(\sqrt{n})$ O~(n) time algorithm for , we prove that needs at least time $\tilde{\Omega }(n^{2/3})$ Ω~(n2/3) even for 0/1 strings.Abstract Longest common substring (), longest palindrome substring (), and Ulam distance () are three fundamental string problems that can be classically solved in near linear time. In this work, we present sublinear time quantum algorithms for these problems along with quantum lower bounds. Our results shed light on a very surprising fact: Although the classic solutions for and are almost identical (via suffix trees), their quantum computational complexities are different. While we give an exact $${{\tilde{O}}}(\sqrt{n})$$ O~(n) time algorithm for , we prove that needs at least time $$\tilde{\Omega }(n^{2/3})$$ Ω~(n2/3) even for 0/1 strings.

arXiv:2010.12122AlgorithmicaDec 5, 202227 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\ll d\ll n$ was not fully understood. We show that the complexity of LCS with threshold $d$ smoothly interpolates between the two extreme cases up to $n^{o(1)}$ factors: LCS with threshold $d$ has a quantum algorithm in $n^{2/3+o(1)}/d^{1/6}$ query complexity and time complexity, and requires at least $Ω(n^{2/3}/d^{1/6})$ quantum query complexity. Our result improves upon previous upper bounds $\tilde O(\min \{n/d^{1/2}, n^{2/3}\})$ (Le Gall and Seddighin ITCS 2022, Akmal and Jin SODA 2022), and answers an open question of Akmal and Jin. Our main technical contribution is a quantum speed-up of the powerful String Synchronizing Set technique introduced by Kempa and Kociumaka (STOC 2019). It consistently samples $n/τ^{1-o(1)}$ synchronizing positions in the string depending on their length- $Θ(τ)$ contexts, and each synchronizing position can be reported by a quantum algorithm in $\tilde O(τ^{1/2+o(1)})$ time. As another application of our quantum string synchronizing set, we study the $k$ -mismatch Matching problem, which asks if the pattern has an occurrence in the text with at most $k$ Hamming mismatches. Using a structural result of Charalampopoulos, Kociumaka, and Wellnitz (FOCS 2020), we obtain a quantum algorithm for $k$ -mismatch matching with $k^{3/4} n^{1/2+o(1)}$ query complexity and $\tilde O(kn^{1/2})$ time complexity.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\ll d\ll n$ was not fully understood. We show that the complexity of LCS with threshold $d$ smoothly interpolates between the two extreme cases up to $n^{o(1)}$ factors: LCS with threshold $d$ has a quantum algorithm in $n^{2/3+o(1)}/d^{1/6}$ query complexity and time complexity, and requires at least $Ω(n^{2/3}/d^{1/6})$ quantum query complexity. Our result improves upon previous upper bounds $\tilde O(\min \{n/d^{1/2}, n^{2/3}\})$ (Le Gall and Seddighin ITCS 2022, Akmal and Jin SODA 2022), and answers an open question of Akmal and Jin. Our main technical contribution is a quantum speed-up of the powerful String Synchronizing Set technique introduced by Kempa and Kociumaka (STOC 2019). It consistently samples $n/τ^{1-o(1)}$ synchronizing positions in the string depending on their length-$Θ(τ)$ contexts, and each synchronizing position can be reported by a quantum algorithm in $\tilde O(τ^{1/2+o(1)})$ time. As another application of our quantum string synchronizing set, we study the $k$-mismatch Matching problem, which asks if the pattern has an occurrence in the text with at most $k$ Hamming mismatches. Using a structural result of Charalampopoulos, Kociumaka, and Wellnitz (FOCS 2020), we obtain a quantum algorithm for $k$-mismatch matching with $k^{3/4} n^{1/2+o(1)}$ query complexity and $\tilde O(kn^{1/2})$ time complexity.

arXiv:2211.15945Nov 29, 20220 citations

Longest Common Substring and Longest Palindromic Substring in $\tilde{\mathcal{O}}(\sqrt{n})$ TimeLongest Common Substring and Longest Palindromic Substring in $\tilde{\mathcal{O}}(\sqrt{n})$ Time

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

The Longest Common Substring (LCS) and Longest Palindromic Substring (LPS) are classical problems in computer science, representing fundamental challenges in string processing. Both problems can be solved in linear time using a classical model of computation, by means of very similar algorithms, both relying on the use of suffix trees. Very recently, two sublinear algorithms for LCS and LPS in the quantum query model have been presented by Le Gall and Seddighin~\cite{GallS23}, requiring $\tilde{\mathcal{O}}(n^{5/6})$ and $\tilde{\mathcal{O}}(\sqrt{n})$ queries, respectively. However, while the query model is fascinating from a theoretical standpoint, its practical applicability becomes limited when it comes to crafting algorithms meant for actual execution on real hardware. In this paper we present, for the first time, a $\tilde{\mathcal{O}}(\sqrt{n})$ quantum algorithm for both LCS and LPS working in the circuit model of computation. Our solutions are simpler than previous ones and can be easily translated into quantum procedures. We also present actual implementations of the two algorithms as quantum circuits working in $\mathcal{O}(\sqrt{n}\log^5(n))$ and $\mathcal{O}(\sqrt{n}\log^4(n))$ time, respectively.The Longest Common Substring (LCS) and Longest Palindromic Substring (LPS) are classical problems in computer science, representing fundamental challenges in string processing. Both problems can be solved in linear time using a classical model of computation, by means of very similar algorithms, both relying on the use of suffix trees. Very recently, two sublinear algorithms for LCS and LPS in the quantum query model have been presented by Le Gall and Seddighin~\cite{GallS23}, requiring $\tilde{\mathcal{O}}(n^{5/6})$ and $\tilde{\mathcal{O}}(\sqrt{n})$ queries, respectively. However, while the query model is fascinating from a theoretical standpoint, its practical applicability becomes limited when it comes to crafting algorithms meant for actual execution on real hardware. In this paper we present, for the first time, a $\tilde{\mathcal{O}}(\sqrt{n})$ quantum algorithm for both LCS and LPS working in the circuit model of computation. Our solutions are simpler than previous ones and can be easily translated into quantum procedures. We also present actual implementations of the two algorithms as quantum circuits working in $\mathcal{O}(\sqrt{n}\log^5(n))$ and $\mathcal{O}(\sqrt{n}\log^4(n))$ time, respectively.

arXiv:2309.01250Sep 3, 20230 citations

\tilde O(n^{2/3})

time, improving upon the recent

\tilde O(n^{5/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

n^{1/2 + o(1)}

time, improving upon the recent

\tilde O(n^{3/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

\tilde O(\sqrt{n})

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.

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

{{\tilde{O}}}(\sqrt{n})

O~(n) time algorithm for , we prove that needs at least time

\tilde{\Omega }(n^{2/3})

Ω~(n2/3) even for 0/1 strings.

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\ll d\ll n

was not fully understood. We show that the complexity of LCS with threshold

d

smoothly interpolates between the two extreme cases up to

n^{o(1)}

factors: LCS with threshold

d

has a quantum algorithm in

n^{2/3+o(1)}/d^{1/6}

query complexity and time complexity, and requires at least

Ω(n^{2/3}/d^{1/6})

quantum query complexity. Our result improves upon previous upper bounds

\tilde O(\min \{n/d^{1/2}, n^{2/3}\})

(Le Gall and Seddighin ITCS 2022, Akmal and Jin SODA 2022), and answers an open question of Akmal and Jin. Our main technical contribution is a quantum speed-up of the powerful String Synchronizing Set technique introduced by Kempa and Kociumaka (STOC 2019). It consistently samples

n/τ^{1-o(1)}

synchronizing positions in the string depending on their length-

Θ(τ)

contexts, and each synchronizing position can be reported by a quantum algorithm in

\tilde O(τ^{1/2+o(1)})

time. As another application of our quantum string synchronizing set, we study the

k

-mismatch Matching problem, which asks if the pattern has an occurrence in the text with at most

k

Hamming mismatches. Using a structural result of Charalampopoulos, Kociumaka, and Wellnitz (FOCS 2020), we obtain a quantum algorithm for

k

-mismatch matching with

k^{3/4} n^{1/2+o(1)}

query complexity and

\tilde O(kn^{1/2})

time complexity.

Longest Common Substring and Longest Palindromic Substring in

\tilde{\mathcal{O}}(\sqrt{n})

Time

\tilde{\mathcal{O}}(n^{5/6})

and

\tilde{\mathcal{O}}(\sqrt{n})

queries, respectively. However, while the query model is fascinating from a theoretical standpoint, its practical applicability becomes limited when it comes to crafting algorithms meant for actual execution on real hardware. In this paper we present, for the first time, a

\tilde{\mathcal{O}}(\sqrt{n})

quantum algorithm for both LCS and LPS working in the circuit model of computation. Our solutions are simpler than previous ones and can be easily translated into quantum procedures. We also present actual implementations of the two algorithms as quantum circuits working in

\mathcal{O}(\sqrt{n}\log^5(n))

and

\mathcal{O}(\sqrt{n}\log^4(n))

time, respectively.