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

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

Daniel Gibney, Ce Jin, Tomasz Kociumaka, Sharma V. Thankachan

Published Nov 3, 2023• 0 citations
arXivHTMLPDF

Abstract

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})$.

DOI
10.48550/arxiv.2311.01793

Related papers

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

Daniel Gibney, Ce Jin, Tomasz Kociumaka +1 more

Measuring sequence similarity and compressing texts are among the most fundamental tasks in string algorithms. In this work, we develop near-optimal quantum algorithms for the central problems in these two areas: computing the edit distance of two strings [Levenshtein, 1965] and building the Lempel-Ziv factorization of a string [Ziv & Lempel, 1977], respectively.

Society for Industrial and Applied Mathematics eBooks•Jan 1, 2024•7 citations

Compressibility-Aware Quantum Algorithms on Strings

Daniel Gibney, Sharma V. Thankachan

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.

arXiv:2302.07235•Feb 14, 2023•1 citation

Quantum Linear Algorithm for Edit Distance Using the Word QRAM Model

Massimo Equi, Arianne Meijer-van de Griend, Veli Mäkinen

Many problems that can be solved in quadratic time have bit-parallel speed-ups with factor $w$, where $w$ is the computer word size. For example, edit distance of two strings of length $n$ can be solved in $O(n^2/w)$ time. In a reasonable classical model of computation, one can assume $w=Θ(\log n)$. There are conditional lower bounds for such problems stating that speed-ups with factor $n^ε$ for any $ε>0$ would lead to breakthroughs in complexity theory. However, these conditional lower bounds do not cover quantum models of computing. Indeed, Boroujeni et al. (J. ACM, 2021) showed that edit distance can be approximated within a factor $3$ in sub-quadratic time $O(n^{1.81})$ using quantum computing. They also showed that, in their chosen model of quantum computing, the approximation factor cannot be improved using sub-quadractic time. To break through the aforementioned classical conditional lower bounds and this latest quantum lower bound, we enrich the model of computation with a quantum random access memory (QRAM), obtaining what we call the word QRAM model. Under this model, we show how to convert the bit-parallelism of quadratic time solvable problems into quantum algorithms that attain speed-ups with factor $n$. The technique we use is simple and general enough to apply to many bit-parallel algorithms that use Boolean logics and bit-shifts. To apply it to edit distance, we first show that the famous $O(n^2/w)$ time bit-parallel algorithm of Myers (J. ACM, 1999) can be adjusted to work without arithmetic + operations. As a direct consequence of applying our technique to this variant, we obtain linear time edit distance algorithm under the word QRAM model for constant alphabet. We give further results on a restricted variant of the word QRAM model to give more insights to the limits of the model.

arXiv:2112.13005•Dec 24, 2021•0 citations

Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce

Mahdi Boroujeni, Soheil Ehsani, Mohammad Ghodsi +2 more

The edit distance between two strings is defined as the smallest number of insertions, deletions, and substitutions that need to be made to transform one of the strings to another one. Approximating edit distance in subquadratic time is “one of the biggest unsolved problems in the field of combinatorial pattern matching” [21]. Our main result is a quantum constant approximation algorithm for computing the edit distance in truly subquadratic time. More precisely, we give an O(n1.858) quantum algorithm that approximates the edit distance within a factor of 7. We further extend this result to an O(n1.781) quantum algorithm that approximates the edit distance within a larger constant factor. Our solutions are based on a framework for approximating edit distance in parallel settings. This framework requires as black box an algorithm that computes the distances of several smaller strings all at once. For a quantum algorithm, we reduce the black box to metric estimation and provide efficient algorithms for approximating it. We further show that this framework enables us to approximate edit distance in distributed settings. To this end, we provide a MapReduce algorithm to approximate edit distance within a factor of 3, with sublinearly many machines and sublinear memory. Also, our algorithm runs in a logarithmic number of rounds.

arXiv:1804.04178•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2018•69 citations

On the Quantum Complexity of Closest Pair and Related Problems

Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin +2 more

The closest pair problem is a fundamental problem of computational geometry: given a set of $n$ points in a $d$-dimensional space, find a pair with the smallest distance. A classical algorithm taught in introductory courses solves this problem in $O(n\log n)$ time in constant dimensions (i.e., when $d=O(1)$). This paper asks and answers the question of the problem's quantum time complexity. Specifically, we give an $\tilde{O}(n^{2/3})$ algorithm in constant dimensions, which is optimal up to a polylogarithmic factor by the lower bound on the quantum query complexity of element distinctness. The key to our algorithm is an efficient history-independent data structure that supports quantum interference. In $\mathrm{polylog}(n)$ dimensions, no known quantum algorithms perform better than brute force search, with a quadratic speedup provided by Grover's algorithm. To give evidence that the quadratic speedup is nearly optimal, we initiate the study of quantum fine-grained complexity and introduce the Quantum Strong Exponential Time Hypothesis (QSETH), which is based on the assumption that Grover's algorithm is optimal for CNF-SAT when the clause width is large. We show that the naïve Grover approach to closest pair in higher dimensions is optimal up to an $n^{o(1)}$ factor unless QSETH is false. We also study the bichromatic closest pair problem and the orthogonal vectors problem, with broadly similar results.

arXiv:1911.01973•Nov 5, 2019•2 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
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​).
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.
Many problems that can be solved in quadratic time have bit-parallel speed-ups with factor www, where www is the computer word size. For example, edit distance of two strings of length nnn can be solved in O(n2/w)O(n^2/w)O(n2/w) time. In a reasonable classical model of computation, one can assume w=Θ(log⁡n)w=Θ(\log n)w=Θ(logn). There are conditional lower bounds for such problems stating that speed-ups with factor nεn^εnε for any ε>0ε>0ε>0 would lead to breakthroughs in complexity theory. However, these conditional lower bounds do not cover quantum models of computing. Indeed, Boroujeni et al. (J. ACM, 2021) showed that edit distance can be approximated within a factor 333 in sub-quadratic time O(n1.81)O(n^{1.81})O(n1.81) using quantum computing. They also showed that, in their chosen model of quantum computing, the approximation factor cannot be improved using sub-quadractic time. To break through the aforementioned classical conditional lower bounds and this latest quantum lower bound, we enrich the model of computation with a quantum random access memory (QRAM), obtaining what we call the word QRAM model. Under this model, we show how to convert the bit-parallelism of quadratic time solvable problems into quantum algorithms that attain speed-ups with factor nnn. The technique we use is simple and general enough to apply to many bit-parallel algorithms that use Boolean logics and bit-shifts. To apply it to edit distance, we first show that the famous O(n2/w)O(n^2/w)O(n2/w) time bit-parallel algorithm of Myers (J. ACM, 1999) can be adjusted to work without arithmetic + operations. As a direct consequence of applying our technique to this variant, we obtain linear time edit distance algorithm under the word QRAM model for constant alphabet. We give further results on a restricted variant of the word QRAM model to give more insights to the limits of the model.
The edit distance between two strings is defined as the smallest number of insertions, deletions, and substitutions that need to be made to transform one of the strings to another one. Approximating edit distance in subquadratic time is “one of the biggest unsolved problems in the field of combinatorial pattern matching” [21]. Our main result is a quantum constant approximation algorithm for computing the edit distance in truly subquadratic time. More precisely, we give an O(n1.858) quantum algorithm that approximates the edit distance within a factor of 7. We further extend this result to an O(n1.781) quantum algorithm that approximates the edit distance within a larger constant factor. Our solutions are based on a framework for approximating edit distance in parallel settings. This framework requires as black box an algorithm that computes the distances of several smaller strings all at once. For a quantum algorithm, we reduce the black box to metric estimation and provide efficient algorithms for approximating it. We further show that this framework enables us to approximate edit distance in distributed settings. To this end, we provide a MapReduce algorithm to approximate edit distance within a factor of 3, with sublinearly many machines and sublinear memory. Also, our algorithm runs in a logarithmic number of rounds.
The closest pair problem is a fundamental problem of computational geometry: given a set of nnn points in a ddd-dimensional space, find a pair with the smallest distance. A classical algorithm taught in introductory courses solves this problem in O(nlog⁡n)O(n\log n)O(nlogn) time in constant dimensions (i.e., when d=O(1)d=O(1)d=O(1)). This paper asks and answers the question of the problem's quantum time complexity. Specifically, we give an O~(n2/3)\tilde{O}(n^{2/3})O~(n2/3) algorithm in constant dimensions, which is optimal up to a polylogarithmic factor by the lower bound on the quantum query complexity of element distinctness. The key to our algorithm is an efficient history-independent data structure that supports quantum interference. In polylog(n)\mathrm{polylog}(n)polylog(n) dimensions, no known quantum algorithms perform better than brute force search, with a quadratic speedup provided by Grover's algorithm. To give evidence that the quadratic speedup is nearly optimal, we initiate the study of quantum fine-grained complexity and introduce the Quantum Strong Exponential Time Hypothesis (QSETH), which is based on the assumption that Grover's algorithm is optimal for CNF-SAT when the clause width is large. We show that the naïve Grover approach to closest pair in higher dimensions is optimal up to an no(1)n^{o(1)}no(1) factor unless QSETH is false. We also study the bichromatic closest pair problem and the orthogonal vectors problem, with broadly similar results.
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.