Quantum Algorithm for Lexicographically Minimal String Rotation

Abstract

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 to its $\Omega \left(\sqrt{n/\log n}\right)$ lower bound. Furthermore, we show that our quantum algorithm outperforms any (classical) randomized algorithms in both worst and average cases. As an application, it is used in benzenoid identification and disjoint-cycle automata minimization.

arXiv commentFinal version, with minor revision. 44 pages, 6 algorithms, 4 tables, 1 figure

References in corpus (9)

• Quantum algorithm for solving linear systems of equations
• Strengths and Weaknesses of Quantum Computing
• Tight bounds on quantum searching
• Structure, Stability, Edge States and Aromaticity of Graphene Ribbons
• Grover's quantum searching algorithm is optimal
• Quantum Search on Bounded-Error Inputs
• Nested quantum search and NP-complete problems
• Nested Quantum Walks with Quantum Data Structures
• Reconstructing Strings from Substrings with Quantum Queries

Cited by in corpus (3)

• A Note on Quantum Divide and Conquer for Minimal String Rotation
• Quantum Data Structure for Range Minimum Query
• Double-Ended Palindromic Trees in Linear Time