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