周期查找

给定在某加法结构上具有周期 $r$ 的函数（如 $f(x)=a^x\mathrm{mod}N$ 满足 $f(x+r)=f(x)$），周期查找的任务是求出 $r$。量子解法的骨架是”制备叠加 → 可逆计算函数值 → 测量 → QFT → 经典后处理”：

$\frac{1}{\sqrt{Q}}{\sum }_x|x⟩|f(x)⟩\stackrel{\text{丢函数值}}{\to }\frac{1}{\sqrt{Q/r}}{\sum }_j|x_0+jr⟩\stackrel{\mathrm{QFT}}{\to }\text{尖峰在 }kQ/r.$

从测得的 $k$ 经连分数恢复 $r$。

要点

• Shor 的引擎：因数分解（取 $f(x)=a^x\mathrm{mod}N$ 的阶 $r$）与离散对数都归约为周期查找，见 Shor 算法。
• 它是 Abelian 隐藏子群问题在最简单群 $\mathbb{Z}$ 上的实例；QFT 扮演”对偶群上的均匀采样”。
• 推广方向一：实数周期——Pell 方程 的调节子 $R$ 不是整数，需要处理近似周期与多对一映射；推广方向二：格上的周期——数域的单位群与类群 把一维周期升级为 $r$ 维对偶格。
• 经典对比：随机经典算法求周期需 $\Theta (\sqrt{r})$ 级别查询，量子为多项式对数——周期查找是少数有可证指数加速的自然问题。

关联词条

• 概念：量子傅里叶变换、相位估计、隐藏子群问题
• 算法：Shor 算法、Abelian 隐藏子群问题

取材：Shor 算法、Pell 方程与主理想问题。

参考文献

• P. W. Shor. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM J. Comput. 26, 1484 (1997). arXiv:quant-ph/9508027
• Nielsen & Chuang.《量子计算与量子信息》第 5 章（周期查找与连分数）.