Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization
Daniel Gibney, Ce Jin, Tomasz Kociumaka, Sharma V. Thankachan · Society for Industrial and Applied Mathematics eBooks · 2024
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.