相位估计：Shor 的发动机

假设你有一个酉算符 $U$，也知道它的一个本征态 $|\psi\rangle$，但本征值 $e^{2\pi i\varphi}$ 里的 $\varphi$ 不知道。这个流程叫相位估计：把 $\varphi$ 的二进制位一位一位读出来，读几位由你愿意付多少比特决定。

先把相位摊到 n 个比特上

准备两个寄存器：上面 n 个比特全在 $|0\rangle$，下面放 $|\psi\rangle$。对上面每个比特加 H，它们变成从 0 到 $2^n-1$ 的均匀叠加。

接着做受控运算：第 j 个比特（j 从 0 数起）控制 $U^{2^j}$。因为 $U|\psi\rangle=e^{2\pi i\varphi}|\psi\rangle$，每作用一次，目标态不变，只把那个相位因子踢回控制位。这个动作叫相位回踢：你没有测量相位，只是让它落进了相对相位。全部做完，上面的寄存器变成

逆 QFT：把相位读成二进制

上面这条式子，正是 QFT 的输出形状：振幅等模，相位随 k 线性增长。对它做一次逆 QFT，这串相位就被整理成二进制小数。

如果 $\varphi$ 恰好是 n 位二进制小数，测量会确定地给出这 n 位。一般情况下它不是，逆 QFT 给出一个集中在最近值附近的分布，测到最接近的 n 位近似的概率很高：

想多读一位，就多一个比特；QFT 部分是 $O(n^2)$ 个门，受控 $U^{2^j}$ 的代价还要另算——那些幂通常靠反复平方构造，越往后越贵。

Shor 拿它做什么

Shor 算法 的量子部分只有一句：取 $U|y\rangle=|ay\bmod N\rangle$，它的本征相位满足 $\varphi\approx s/r$，而 r 正是模幂序列的周期。相位估计给出 $\varphi$ 的 n 位近似，连分数把它还原成 $s/r$，于是 r 有了；剩下的分解交给经典计算机。

所以「发动机」不是夸张：QFT 提供读法，相位估计提供接口，周期查找才是整台机器的用途。也正因为整条链路长，实际运行要靠纠错把每一步的错误压下去，否则读出的位全是噪声。