  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". Our main result is a quantum constant approximation algorithm for
computing the edit distance in truly subquadratic time. More precisely, we give
an $O(n^{1.858})$ quantum algorithm that approximates the edit distance within
a factor of $7$. We further extend this result to an $O(n^{1.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 \textit{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.
