论文标题
词素量算法旋转的量子算法
Quantum Algorithm for Lexicographically Minimal String Rotation
论文作者
论文摘要
词典最小的弦乐旋转（LMSR）是在词典顺序中找到弦的所有旋转中的最小旋转的问题，该弦的所有旋转曲线都广泛用于图形，多边形，自动机和化学结构的平等检查。在本文中，我们建议使用LMSR的$ O（N^{3/4}）$ Quantum查询算法。尤其是，该算法具有平均库查询复杂度$ O（\ sqrt n \ log n）$，与其$ω\ left相比，它在dopyogarithmithmit上均非最佳范围（\ sqrt {n/\ log n} \ right）$下限。此外，我们表明，在最坏情况和平均情况下，我们的量子算法的表现都优于任何（经典）随机算法。作为一种应用，它用于苯二鉴定和脱节周期自动机最小化。
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 $Ω\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.
