A note on quantum divide and conquer for minimal string rotation
Qisheng Wang · Theoretical Computer Science · 2025
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 n ⋅ 2 O ( log n ) , improving the prior result of n ⋅ 2 ( log n ) 1 / 2 + ε by Akmal and Jin (2022). Notably, this improvement is quasi-polylogarithmic, which is achieved by only logarithmic level-wise optimization using fault-tolerant quantum minimum finding.