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

Daniel Gibney, Ce Jin, Tomasz Kociumaka +1

Classically, the edit distance of two length-$n$ strings can be computed in $O(n^2)$ time, whereas an $O(n^{2-\epsilon })$-time procedure would falsify the Orthogonal Vectors Hypothesis. I…