Qisheng Wang, Mingsheng Ying. Quantum Algorithm for Lexicographically Minimal String Rotation (2022)
Abstract. 本文是 https://doi.org/10.1007/s00224-023-10146-8 的阅读笔记。他们提出了求字符串最小字典序后缀的 $O(n^{3/4})$ 量子算法,但感觉非常套路。文章还证明了这个问题的平均复杂度下界 $\Omega(n^{1/2} / \log^{1/2} n)$ 和最坏复杂度下界 $\Omega(n^{1/2})$,但他自己并没有达到这个界。