Quantum Speed-ups for String Synchronizing Sets, Longest Common Substring, and k-mismatch Matching

Longest Common Substring (LCS) is an important text processing problem, which has recently been investigated in the quantum query model. The decisional version of this problem, LCS with threshold d, asks whether two length-n input strings have a common substring of length d. The two extreme cases, d = 1 and d = n, correspond respectively to Element Distinctness and Unstructured Search, two fundamental problems in quantum query complexity. However, the intermediate case 1 d n was not fully understood. We show that the complexity of LCS with threshold d smoothly interpolates between the two extreme cases up to n o(1) factors: