A Note on Quantum Divide and Conquer for Minimal String Rotation

Abstract

Lexicographically minimal string rotation is a fundamental problem in string processing that has recently garnered significant attention in quantum computing. Near-optimal quantum algorithms have been proposed for solving this problem, utilizing a divide-and-conquer structure. In this note, we show that its quantum query complexity is $\sqrt{n}\cdot 2^{O(\sqrt{\log n})}$, improving the prior result of $\sqrt{n}\cdot 2^{(\log n{)}^{1/2+\epsilon }}$ due to Akmal and Jin (SODA 2022). Notably, this improvement is quasi-polylogarithmic, which is achieved by only logarithmic level-wise optimization using fault-tolerant quantum minimum finding.

16 pages, 1 table. v2: Decision version in v1 is removed due to a gap found in the proof