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:2302.07235

Compressibility-Aware Quantum Algorithms on Strings

Daniel Gibney, Sharma V. Thankachan

Published Feb 14, 2023• 1 citation
arXivHTMLPDF

Abstract

Sublinear time quantum algorithms have been established for many fundamental problems on strings. This work demonstrates that new, faster quantum algorithms can be designed when the string is highly compressible. We focus on two popular and theoretically significant compression algorithms -- the Lempel-Ziv77 algorithm (LZ77) and the Run-length-encoded Burrows-Wheeler Transform (RL-BWT), and obtain the results below. We first provide a quantum algorithm running in $\tilde{O}(\sqrt{zn})$ time for finding the LZ77 factorization of an input string $T[1..n]$ with $z$ factors. Combined with multiple existing results, this yields an $\tilde{O}(\sqrt{rn})$ time quantum algorithm for finding the RL-BWT encoding with $r$ BWT runs. Note that $r = \tildeΘ(z)$. We complement these results with lower bounds proving that our algorithms are optimal (up to polylog factors). Next, we study the problem of compressed indexing, where we provide a $\tilde{O}(\sqrt{rn})$ time quantum algorithm for constructing a recently designed $\tilde{O}(r)$ space structure with equivalent capabilities as the suffix tree. This data structure is then applied to numerous problems to obtain sublinear time quantum algorithms when the input is highly compressible. For example, we show that the longest common substring of two strings of total length $n$ can be computed in $\tilde{O}(\sqrt{zn})$ time, where $z$ is the number of factors in the LZ77 factorization of their concatenation. This beats the best known $\tilde{O}(n^\frac{2}{3})$ time quantum algorithm when $z$ is sufficiently small.

DOI
10.48550/arxiv.2302.07235

Related papers

Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization

Daniel Gibney, Ce Jin, Tomasz Kociumaka +1 more

Classically, the edit distance of two length-$n$ strings can be computed in $O(n^2)$ time, whereas an $O(n^{2-ε})$-time procedure would falsify the Orthogonal Vectors Hypothesis. If the edit distance does not exceed $k$, the running time can be improved to $O(n+k^2)$, which is near-optimal (conditioned on OVH) as a function of $n$ and $k$. Our first main contribution is a quantum $\tilde{O}(\sqrt{nk}+k^2)$-time algorithm that uses $\tilde{O}(\sqrt{nk})$ queries, where $\tilde{O}(\cdot)$ hides polylogarithmic factors. This query complexity is unconditionally optimal, and any significant improvement in the time complexity would resolve a long-standing open question of whether edit distance admits an $O(n^{2-ε})$-time quantum algorithm. Our divide-and-conquer quantum algorithm reduces the edit distance problem to a case where the strings have small Lempel-Ziv factorizations. Then, it combines a quantum LZ compression algorithm with a classical edit-distance subroutine for compressed strings. The LZ factorization problem can be classically solved in $O(n)$ time, which is unconditionally optimal in the quantum setting. We can, however, hope for a quantum speedup if we parameterize the complexity in terms of the factorization size $z$. Already a generic oracle identification algorithm yields the optimal query complexity of $\tilde{O}(\sqrt{nz})$ at the price of exponential running time. Our second main contribution is a quantum algorithm that achieves the optimal time complexity of $\tilde{O}(\sqrt{nz})$. The key tool is a novel LZ-like factorization of size $O(z\log^2n)$ whose subsequent factors can be efficiently computed through a combination of classical and quantum techniques. We can then obtain the string's run-length encoded Burrows-Wheeler Transform (BWT), construct the $r$-index, and solve many fundamental string processing problems in time $\tilde{O}(\sqrt{nz})$.

arXiv:2311.01793•Nov 3, 2023•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

A sublinear time quantum algorithm for longest common substring problem between run-length encoded strings

Tzu-Ching Lee, Han-Hsuan Lin

We give a sublinear quantum algorithm for the longest common substring (LCS) problem on the run-length encoded (RLE) inputs, under the assumption that the prefix-sums of the runs are given. Our algorithm costs $\tilde{O}(n^{5/6})\cdot O(\mathrm{polylog}(\tilde{n}))$ time, where $n$ and $\tilde{n}$ are the encoded and decoded length of the inputs, respectively. We justify the use of the prefix-sum oracles by showing that, without the oracles, there is a $Ω(n/\log^2n)$ lower-bound on the quantum query complexity of finding LCS given two RLE strings due to a reduction of $\mathsf{PARITY}$ to the problem.

arXiv:2310.00966•Oct 2, 2023•0 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

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•11 citations

Near-Optimal Quantum Algorithm for Finding the Longest Common Substring between Run-Length Encoded Strings

Tzu-Ching Lee, Han-Hsuan Lin

We give a near-optimal quantum algorithm for the longest common substring (LCS) problem between two run-length encoded (RLE) strings, with the assumption that the prefix-sums of the run-lengths are given. Our algorithm costs $\tilde{\mathcal{O}}(n^{2/3}/d^{1/6-o(1)}\cdot\mathrm{polylog}(\tilde{n}))$ time, while the query lower bound for the problem is $\tildeΩ(n^{2/3}/d^{1/6})$, where $n$ and $\tilde{n}$ are the encoded and decoded length of the inputs, respectively, and $d$ is the encoded length of the LCS. We justify the use of prefix-sum oracles for two reasons. First, we note that creating the prefix-sum oracle only incurs a constant overhead in the RLE compression. Second, we show that, without the oracles, there is a $Ω(n/\log^2n)$ lower bound on the quantum query complexity of finding the LCS given two RLE strings due to a reduction of $\mathsf{PARITY}$ to the problem. With a small modification, our algorithm also solves the longest repeated substring problem for an RLE string.

arXiv:2411.02421•Oct 21, 2024•0 citations
Sublinear time quantum algorithms have been established for many fundamental problems on strings. This work demonstrates that new, faster quantum algorithms can be designed when the string is highly compressible. We focus on two popular and theoretically significant compression algorithms -- the Lempel-Ziv77 algorithm (LZ77) and the Run-length-encoded Burrows-Wheeler Transform (RL-BWT), and obtain the results below. We first provide a quantum algorithm running in O~(zn)\tilde{O}(\sqrt{zn})O~(zn​) time for finding the LZ77 factorization of an input string T[1..n]T[1..n]T[1..n] with zzz factors. Combined with multiple existing results, this yields an O~(rn)\tilde{O}(\sqrt{rn})O~(rn​) time quantum algorithm for finding the RL-BWT encoding with rrr BWT runs. Note that r=Θ~(z)r = \tildeΘ(z)r=Θ~(z). We complement these results with lower bounds proving that our algorithms are optimal (up to polylog factors). Next, we study the problem of compressed indexing, where we provide a O~(rn)\tilde{O}(\sqrt{rn})O~(rn​) time quantum algorithm for constructing a recently designed O~(r)\tilde{O}(r)O~(r) space structure with equivalent capabilities as the suffix tree. This data structure is then applied to numerous problems to obtain sublinear time quantum algorithms when the input is highly compressible. For example, we show that the longest common substring of two strings of total length nnn can be computed in O~(zn)\tilde{O}(\sqrt{zn})O~(zn​) time, where zzz is the number of factors in the LZ77 factorization of their concatenation. This beats the best known O~(n23)\tilde{O}(n^\frac{2}{3})O~(n32​) time quantum algorithm when zzz is sufficiently small.
Classically, the edit distance of two length-nnn strings can be computed in O(n2)O(n^2)O(n2) time, whereas an O(n2−ε)O(n^{2-ε})O(n2−ε)-time procedure would falsify the Orthogonal Vectors Hypothesis. If the edit distance does not exceed kkk, the running time can be improved to O(n+k2)O(n+k^2)O(n+k2), which is near-optimal (conditioned on OVH) as a function of nnn and kkk. Our first main contribution is a quantum O~(nk+k2)\tilde{O}(\sqrt{nk}+k^2)O~(nk​+k2)-time algorithm that uses O~(nk)\tilde{O}(\sqrt{nk})O~(nk​) queries, where O~(⋅)\tilde{O}(\cdot)O~(⋅) hides polylogarithmic factors. This query complexity is unconditionally optimal, and any significant improvement in the time complexity would resolve a long-standing open question of whether edit distance admits an O(n2−ε)O(n^{2-ε})O(n2−ε)-time quantum algorithm. Our divide-and-conquer quantum algorithm reduces the edit distance problem to a case where the strings have small Lempel-Ziv factorizations. Then, it combines a quantum LZ compression algorithm with a classical edit-distance subroutine for compressed strings. The LZ factorization problem can be classically solved in O(n)O(n)O(n) time, which is unconditionally optimal in the quantum setting. We can, however, hope for a quantum speedup if we parameterize the complexity in terms of the factorization size zzz. Already a generic oracle identification algorithm yields the optimal query complexity of O~(nz)\tilde{O}(\sqrt{nz})O~(nz​) at the price of exponential running time. Our second main contribution is a quantum algorithm that achieves the optimal time complexity of O~(nz)\tilde{O}(\sqrt{nz})O~(nz​). The key tool is a novel LZ-like factorization of size O(zlog⁡2n)O(z\log^2n)O(zlog2n) whose subsequent factors can be efficiently computed through a combination of classical and quantum techniques. We can then obtain the string's run-length encoded Burrows-Wheeler Transform (BWT), construct the rrr-index, and solve many fundamental string processing problems in time O~(nz)\tilde{O}(\sqrt{nz})O~(nz​).
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.
We give a sublinear quantum algorithm for the longest common substring (LCS) problem on the run-length encoded (RLE) inputs, under the assumption that the prefix-sums of the runs are given. Our algorithm costs O~(n5/6)⋅O(polylog(n~))\tilde{O}(n^{5/6})\cdot O(\mathrm{polylog}(\tilde{n}))O~(n5/6)⋅O(polylog(n~)) time, where nnn and n~\tilde{n}n~ are the encoded and decoded length of the inputs, respectively. We justify the use of the prefix-sum oracles by showing that, without the oracles, there is a Ω(n/log⁡2n)Ω(n/\log^2n)Ω(n/log2n) lower-bound on the quantum query complexity of finding LCS given two RLE strings due to a reduction of PARITY\mathsf{PARITY}PARITY to the problem.
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.
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 give a near-optimal quantum algorithm for the longest common substring (LCS) problem between two run-length encoded (RLE) strings, with the assumption that the prefix-sums of the run-lengths are given. Our algorithm costs O~(n2/3/d1/6−o(1)⋅polylog(n~))\tilde{\mathcal{O}}(n^{2/3}/d^{1/6-o(1)}\cdot\mathrm{polylog}(\tilde{n}))O~(n2/3/d1/6−o(1)⋅polylog(n~)) time, while the query lower bound for the problem is Ω~(n2/3/d1/6)\tildeΩ(n^{2/3}/d^{1/6})Ω~(n2/3/d1/6), where nnn and n~\tilde{n}n~ are the encoded and decoded length of the inputs, respectively, and ddd is the encoded length of the LCS. We justify the use of prefix-sum oracles for two reasons. First, we note that creating the prefix-sum oracle only incurs a constant overhead in the RLE compression. Second, we show that, without the oracles, there is a Ω(n/log⁡2n)Ω(n/\log^2n)Ω(n/log2n) lower bound on the quantum query complexity of finding the LCS given two RLE strings due to a reduction of PARITY\mathsf{PARITY}PARITY to the problem. With a small modification, our algorithm also solves the longest repeated substring problem for an RLE string.