Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce
- 13 May 2021
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 68 (3), 1-41
- https://doi.org/10.1145/3456807
Abstract
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” [37]. Our main result is a quantum constant approximation algorithm for computing the edit distance in truly subquadratic time. More precisely, we give an \(\) quantum algorithm that approximates the edit distance within a factor of 3. We further extend this result to an \(\) 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 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 \(\), with sublinearly many machines and sublinear memory. Also, our algorithm runs in a logarithmic number of rounds.
Keywords
Funding Information
- NSF CAREER (CCF-1053605)
- NSF BIGDATA (IIS-1546108)
- NSF AF:Medium (CCF-1161365)
- DARPA GRAPHS/AFOSR (FA9550-12-1-0423)
- DARPA SIMPLEX
This publication has 40 references indexed in Scilit:
- On Exact Quantum Query ComplexityAlgorithmica, 2013
- The Computational Hardness of Estimating Edit DistanceSIAM Journal on Computing, 2010
- Improved Lower Bounds for Embeddings into $L_1$SIAM Journal on Computing, 2009
- Low distortion embeddings for edit distanceJournal of the ACM, 2007
- String matching inJournal of Discrete Algorithms, 2003
- Quantum amplitude amplification and estimationContemporary Mathematics, 2002
- Limit on the Speed of Quantum Computation in Determining ParityPhysical Review Letters, 1998
- Tight Bounds on Quantum SearchingFortschritte der Physik, 1998
- Algorithms for approximate string matchingInformation and Control, 1985
- A faster algorithm computing string edit distancesJournal of Computer and System Sciences, 1980