Approximating Edit Distance
The edit distance of 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. In this work, we give the first quantum constant approximation algorithm for computing the edit distance in truly subquadratic time. More precisely, we give an O(n^{1.857}) 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 constant factor. This talk do not need any prior knowledge about quantum computing.

Download presentation from here.