论文标题
关于量子划分和征服的注释，以最小的弦旋转
A Note on Quantum Divide and Conquer for Minimal String Rotation
论文作者
论文摘要
词素最小的弦乐旋转是弦处理中的一个基本问题，最近在量子计算中引起了极大的关注。已经提出了近距离的量子算法，该算法是利用分裂和串联结构来解决此问题的。在此注释中，我们表明其量子查询复杂性为$ \ sqrt {n} \ cdot 2^{o（\ sqrt {\ sqrt {\ log n}）} $，改善了$ \ sqrt {n} \ cdot 2^{（\ cdot 2^{（\ log n）^{\ log n）^{1/2+\ v vareps的先前结果（苏打水2022）。值得注意的是，这种改进是准螺旋载体，仅使用耐断层量子量的最小发现仅通过对数水平优化来实现。
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 $\sqrt{n} \cdot 2^{O(\sqrt{\log n})}$, improving the prior result of $\sqrt{n} \cdot 2^{(\log n)^{1/2+\varepsilon}}$ due to Akmal and Jin (SODA 2022). Notably, this improvement is quasi-polylogarithmic, which is achieved by only logarithmic level-wise optimization using fault-tolerant quantum minimum finding.
