Quantum Algorithm for Lexicographically Minimal String Rotation

Lexicographically minimal string rotation (LMSR) is a problem to find the minimal one among all rotations of a string in the lexicographical order, which is widely used in equality checking of graphs, polygons, automata and chemical structures. In this paper, we propose an $O(n^{3/4})$ quantum query algorithm for LMSR. In particular, the algorithm has average-case query complexity $O(\sqrt n \log n)$, which is shown to be asymptotically optimal up to a polylogarithmic factor, compared with its $\Omega\left(\sqrt{n/\log n}\right)$ lower bound. Furthermore, we claim that our quantum algorithm outperforms any (classical) randomized algorithms in both worst-case and average-case query complexities by showing that every (classical) randomized algorithm for LMSR has worst-case query complexity $\Omega(n)$ and average-case query complexity $\Omega(n/\log n)$. Our quantum algorithm for LMSR is developed in a framework of nested quantum algorithms, based on two new results: (i) an $O(\sqrt{n})$ (optimal) quantum minimum finding on bounded-error quantum oracles; and (ii) its $O\left(\sqrt{n \log(1/\varepsilon)}\right)$ (optimal) error reduction. As a byproduct, we obtain some better upper bounds of independent interest: (i) $O(\sqrt{N})$ (optimal) for constant-depth MIN-MAX trees on $N$ variables; and (ii) $O(\sqrt{n \log m})$ for pattern matching which removes $\operatorname{polylog}(n)$ factors.