QFT：把相位摊成可读的刻度

「量子傅里叶变换」这个名字容易让人以为，它能在指数大的数据上做频谱分析。它做的事其实很朴素：把 $2^n$ 个振幅按相位重新排一遍，而且排得极省门。

定义：离散傅里叶变换的量子版

对 $N=2^n$ 维的计算基：

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

逐项和经典离散傅里叶变换一样，只是它作用在振幅上。经典 FFT 要在 N 个数上做 $O(N\log N)$ 次运算；QFT 只用 $O(n^2)$ 个门——因为 $N=2^n$ ，门数随比特数平方增长，随 N 只对数增长。

便宜的原因不神秘：它没有把 N 个系数写出来给你看，只是把这个态旋转了一下。

取 $n=1$ ： $H|0\rangle=|+\rangle$ ， $H|1\rangle=|-\rangle$ ，正好是两点 DFT 的两个输出，那个负号就是 $(-1)^{xy}$ 。

多比特的线路是同一件事的递归：对每个比特加 H，再用受控相位门把低位的信息累积到高位，最后用交换把顺序倒过来。写成乘积形式就是：

|x_1\cdots x_n\rangle\longmapsto\frac{1}{\sqrt{2^n}}\bigotimes_{k=1}^{n}\left(|0\rangle+e^{2\pi i\,0.x_k x_{k+1}\cdots x_n}|1\rangle\right)

每个因子只由一个 H 和若干受控相位构成， $O(n^2)$ 的门数就是从这里来的。线路里没有一步在做「求和」，求和是干涉自动完成的。

两点 QFT

默认是 2 比特。只按一个 H，看第一个比特变成 |0⟩ 与 |1⟩ 各一半——这就是最小规模的 QFT；再按 CZ、H，读数的变化就是相位被翻译成概率的样子。演示的档位只有 2–4 比特，1 比特的情形就是一个 H。

如果输入振幅带着周期 r 的相位，QFT 之后相长与相消会把概率挤到少数几个 y 上，位置由 N/r 决定。相位估计和 Shor 用的就是这一点：周期藏在相位里，QFT 把周期翻译成频率。

但 QFT 单独跑一次几乎不给你可读的答案：它没有读出 N 个系数，一次测量只给一个 y。要让答案浮现，得靠前后的线路把信息组织成「答案对应的振幅很大、其余相消」的形状。这就是为什么它通常作为子程序出现，而不是一个能直接输出结果的算法。

QFT 一次算出全部 N 个傅里叶系数，所以能指数加速任何频谱分析。

N 个振幅确实都在态里，但一次测量只读出一个 y；加速来自后续干涉把需要的答案集中到少数结果上，而不是把系数列出来。

把「态里含有全部信息」当成「能读出全部信息」，是量子算法科普里最普遍的一处越界。

一句话结论

QFT 是离散傅里叶变换的量子版本： $O(n^2)$ 个门把振幅按 $e^{2\pi ixy/N}$ 重排。一比特时它就是 H；多比特时是 H 加受控相位加交换。它把周期变成峰，但峰要被读出来，还得靠前后的线路——所以它永远是子程序。