Near-Optimal Quantum Algorithms for String Problems

Understand

We study quantum algorithms for several fundamental string problems, including Longest Common Substring, Lexicographically Minimal String Rotation, and Longest Square Substring.

• These problems have been widely studied in the stringology literature since the 1970s, and are known to be solvable by near-linear time classical algorithms.
• In this work, we give quantum algorithms for these problems with near-optimal query complexities and time complexities.
• Specifically, we show that: - Longest Common Substring can be solved by a quantum algorithm in $\tilde O(n^{2/3})$ time, improving upon the recent $\tilde O(n^{5/6})$-time algorithm by Le Gall and Seddighin (2020).