第5章：量子傅里叶变换、相位估计与 Shor

傅里叶变换

对 N 维计算基，量子傅里叶变换定义为

|x\rangle\mapsto\frac1{\sqrt N}\sum_{y=0}^{N-1}e^{2\pi ixy/N}|y\rangle.

当 $N=2^n$ ，它可以用关于 n 的多项式规模门电路实现。输入若是任意经典长度 N 的数组，仍需考虑装载成本；测量也不会输出全部傅里叶系数。因此不能直接与输出全部系数的经典 FFT 比较而忽略输入输出差异。

若 $U|u\rangle=e^{2\pi i\phi}|u\rangle$ ，通过受控 $U^{2^j}$ 与逆 QFT，可估计 $\phi$ 的二进制位。若相位恰能用有限位表示，在理想模型下可精确读取；一般相位则得到邻近估计，需要分析误差概率。

受控幂 $U^{2^j}$ 的实现成本必须计入。用二进制写出指数很短，不意味着执行该幂一定只需很少门。

整数分解可归约到求 $a^r\equiv1\pmod N$ 的最小正周期 r，其中 $\gcd(a,N)=1$ 。量子部分构造模指数关系并利用傅里叶结构得到接近 $s/r$ 的相位信息，再用连分数恢复周期候选并经典验证。

若 r 偶数且 $a^{r/2}\not\equiv-1\pmod N$ ，则

(a^{r/2}-1)(a^{r/2}+1)\equiv0\pmod N,

求两因子与 N 的 gcd 可能得到非平凡因数。失败时需重选 a 或重新采样，不能把每次运行都视为必然成功。

取 a=2，周期 r=4，因为 $2^4\equiv1\pmod{15}$ ，且更小正指数不满足。于是 $2^{r/2}=4$ ，得到 $\gcd(4-1,15)=3$ 、 $\gcd(4+1,15)=5$ 。

这个计算验证经典后处理。真正算法还要实现模乘电路、辅助位清理、相位估计和采样，不能把“已知 r=4”的演示当作已完成量子周期寻找。