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

Algorithmica

Near-Optimal Quantum Algorithms for String Problems

Shyan Akmal, Ce Jin

Published Jan 27, 2023• 11 citations
Publisher

Abstract

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.

DOI
10.1007/s00453-022-01092-x

Related papers

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.

Society for Industrial and Applied Mathematics eBooks•Jan 1, 2022•18 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 $\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.09696•Oct 19, 2021•1 citation

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.

arXiv:2211.15945•Nov 29, 2022•0 citations

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.

arXiv:2010.12122•Algorithmica•Dec 5, 2022•27 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 decision 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 \(\Omega(n^{2/3}/d^{1/6})\) quantum query complexity. Our result improves upon previous upper bounds \(\widetilde{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/\tau^{1-o(1)}\) synchronizing positions in the string depending on their length- \(\Theta(\tau)\) contexts, and each synchronizing position can be reported by a quantum algorithm in \(\widetilde{O}(\tau^{1/2+o(1)})\) time. Our quantum string synchronizing set also yields a near-optimal LCE data structure in the quantum setting. 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 et al. (FOCS 2020), we obtain: — \(k\) -mismatch matching has a quantum algorithm with \(k^{3/4}n^{1/2+o(1)}\) query complexity and \(\widetilde{O}(kn^{1/2})\) time complexity. We also observe a non-matching quantum query lower bound of \(\Omega(\sqrt{kn})\) .

ACM Transactions on Algorithms•Jun 10, 2024•2 citations

A note on quantum divide and conquer for minimal string rotation

Qisheng Wang

Lexicographically minimal string rotation is a fundamental problem in string processing that has recently garnered significant attention in quantum computing. Near-optimal quantum algorithms have been proposed for solving this problem, utilizing a divide-and-conquer structure. In this note, we show that its quantum query complexity is n ⋅ 2 O ( log ⁡ n ) , improving the prior result of n ⋅ 2 ( log ⁡ n ) 1 / 2 + ε by Akmal and Jin (2022). Notably, this improvement is quasi-polylogarithmic, which is achieved by only logarithmic level-wise optimization using fault-tolerant quantum minimum finding.

arXiv:2210.09149•Theoretical Computer Science•Feb 12, 2025•1 citation
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.
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.
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) time, improving upon the recent O~(n5/6)\tilde O(n^{5/6})O~(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)n^{1/2 + o(1)}n1/2+o(1) time, improving upon the recent O~(n3/4)\tilde O(n^{3/4})O~(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 O~(n)\tilde O(\sqrt{n})O~(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.
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 ddd, asks whether two length-nnn input strings have a common substring of length ddd. The two extreme cases, d=1d=1d=1 and d=nd=nd=n, correspond respectively to Element Distinctness and Unstructured Search, two fundamental problems in quantum query complexity. However, the intermediate case 1≪d≪n1\ll d\ll n1≪d≪n was not fully understood. We show that the complexity of LCS with threshold ddd smoothly interpolates between the two extreme cases up to no(1)n^{o(1)}no(1) factors: LCS with threshold ddd has a quantum algorithm in n2/3+o(1)/d1/6n^{2/3+o(1)}/d^{1/6}n2/3+o(1)/d1/6 query complexity and time complexity, and requires at least Ω(n2/3/d1/6)Ω(n^{2/3}/d^{1/6})Ω(n2/3/d1/6) quantum query complexity. Our result improves upon previous upper bounds O~(min⁡{n/d1/2,n2/3})\tilde O(\min \{n/d^{1/2}, n^{2/3}\})O~(min{n/d1/2,n2/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)n/τ^{1-o(1)}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 O~(τ1/2+o(1))\tilde O(τ^{1/2+o(1)})O~(τ1/2+o(1)) time. As another application of our quantum string synchronizing set, we study the kkk-mismatch Matching problem, which asks if the pattern has an occurrence in the text with at most kkk Hamming mismatches. Using a structural result of Charalampopoulos, Kociumaka, and Wellnitz (FOCS 2020), we obtain a quantum algorithm for kkk-mismatch matching with k3/4n1/2+o(1)k^{3/4} n^{1/2+o(1)}k3/4n1/2+o(1) query complexity and O~(kn1/2)\tilde O(kn^{1/2})O~(kn1/2) time complexity.
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 O~(n){{\tilde{O}}}(\sqrt{n})O~(n​) O~(n) time algorithm for , we prove that needs at least time Ω~(n2/3)\tilde{\Omega }(n^{2/3})Ω~(n2/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 decision version of this problem, LCS with threshold ddd , asks whether two length- nnn input strings have a common substring of length ddd . The two extreme cases, d=1d=1d=1 and d=nd=nd=n , correspond, respectively to Element Distinctness and Unstructured Search, two fundamental problems in quantum query complexity. However, the intermediate case 1≪d≪n1\ll d\ll n1≪d≪n was not fully understood. We show that the complexity of LCS with threshold ddd smoothly interpolates between the two extreme cases up to no(1)n^{o(1)}no(1) factors: — LCS with threshold ddd has a quantum algorithm in n2/3+o(1)/d1/6n^{2/3+o(1)}/d^{1/6}n2/3+o(1)/d1/6 query complexity and time complexity, and requires at least Ω(n2/3/d1/6)\Omega(n^{2/3}/d^{1/6})Ω(n2/3/d1/6) quantum query complexity. Our result improves upon previous upper bounds O~(min⁡{n/d1/2,n2/3})\widetilde{O}(\min\{n/d^{1/2},n^{2/3}\})O(min{n/d1/2,n2/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)n/\tau^{1-o(1)}n/τ1−o(1) synchronizing positions in the string depending on their length- Θ(τ)\Theta(\tau)Θ(τ) contexts, and each synchronizing position can be reported by a quantum algorithm in O~(τ1/2+o(1))\widetilde{O}(\tau^{1/2+o(1)})O(τ1/2+o(1)) time. Our quantum string synchronizing set also yields a near-optimal LCE data structure in the quantum setting. As another application of our quantum string synchronizing set, we study the kkk -mismatch Matching problem, which asks if the pattern has an occurrence in the text with at most kkk Hamming mismatches. Using a structural result of Charalampopoulos et al. (FOCS 2020), we obtain: — kkk -mismatch matching has a quantum algorithm with k3/4n1/2+o(1)k^{3/4}n^{1/2+o(1)}k3/4n1/2+o(1) query complexity and O~(kn1/2)\widetilde{O}(kn^{1/2})O(kn1/2) time complexity. We also observe a non-matching quantum query lower bound of Ω(kn)\Omega(\sqrt{kn})Ω(kn​) .
Lexicographically minimal string rotation is a fundamental problem in string processing that has recently garnered significant attention in quantum computing. Near-optimal quantum algorithms have been proposed for solving this problem, utilizing a divide-and-conquer structure. In this note, we show that its quantum query complexity is n ⋅ 2 O ( log ⁡ n ) , improving the prior result of n ⋅ 2 ( log ⁡ n ) 1 / 2 + ε by Akmal and Jin (2022). Notably, this improvement is quasi-polylogarithmic, which is achieved by only logarithmic level-wise optimization using fault-tolerant quantum minimum finding.