量子傅里叶变换（QFT）

前置阅读：Deutsch-Jozsa 算法。本词条是相位估计和 Shor 算法的共同基石。

本词条要点：

1. 理解量子傅里叶变换 (Quantum Fourier Transform, QFT) 的定义，以及它与经典离散傅里叶变换 (DFT) 的关系。
2. 掌握 QFT 的**张量积结构**——它是整个线路实现的核心，也是最精妙的一步推导。
3. 学会用受控相位门搭出 $O(n^2)$ 规模的 QFT 线路，并与经典 FFT 的 $O(N\log N)$ 比较。
4. 弄清一个初学者最容易困惑的问题：为什么 QFT 不能用来”快速计算傅里叶变换”。
5. 为（相位估计）做好准备：QPE 中真正被使用的是逆 QFT。

1. 从经典 DFT 到量子 QFT

回忆经典离散傅里叶变换：给定长度为 $N$ 的复向量 $(a_0,a_1,\dots ,a_{N-1})$，DFT 把它变成另一个长度为 $N$ 的向量，第 $k$ 个分量为

$${\hat{a}}_k=\sum _{j=0}^{N-1}{a}_j{e}^{2\pi ijk/N}.$$

它是一个线性变换，写成矩阵就是 $N\times N$ 的 DFT 矩阵。快速傅里叶变换 (FFT) 把计算它的时间从 $O(N^2)$ 压到 $O(N\log N)$。

量子版本的定义方式不同：QFT 不是作用在一个向量上的”计算”，而是一个作用在 $n={\log }_{2}N$ 个量子比特上的酉算子，它把基矢 $|j⟩$（这里把比特串 $|j_1{j}_2\cdots j_n⟩$ 与它表示的整数 $j$ 混用）映为

$${\mathrm{QFT}}_N|j⟩=\frac{1}{\sqrt{N}}\sum _{k=0}^{N-1}{e}^{2\pi ijk/N}|k⟩.$$

换句话说，QFT 的矩阵元素恰好是 DFT 矩阵的元素（差一个归一化因子 $\sqrt{N}$）。因为 DFT 矩阵是酉的，所以 QFT 是合法的量子操作。

一个立刻值得注意的事实：当 $n=1$（$N=2$）时，

$${\mathrm{QFT}}_2|0⟩=\frac{1}{\sqrt{2}}(|0⟩+|1⟩),{\mathrm{QFT}}_2|1⟩=\frac{1}{\sqrt{2}}(|0⟩-|1⟩),$$

单比特 QFT 就是 Hadamard 门。这提示我们：QFT 是 Hadamard 变换的”带相位”推广——我们在 D-J 算法里已经体会过 $H^{\otimes n}$ 配合相位回踢能做什么，QFT 把这套干涉工具推广到更细的相位分辨率。

2. 最重要的结构：张量积形式

直接看定义式，QFT 似乎把信息”搅”在一起。但一个优美的代数事实是：QFT 的输出态可以精确地写成逐比特的张量积。记 $0.j_{\ell }{j}_{\ell +1}\cdots j_n$ 为二进制小数（即 $j_{\ell }/2+j_{\ell +1}/4+\cdots$），则

$${\mathrm{QFT}}_N|j_1{j}_2\cdots j_n⟩=\underset{\ell =1}{\overset{n}{⨂}}\frac{|0⟩+e^{2\pi i0.j_{\ell }{j}_{\ell +1}\cdots j_n}|1⟩}{\sqrt{2}}=\frac{|0⟩+e^{2\pi i0.j_1{j}_2\cdots j_n}|1⟩}{\sqrt{2}}\otimes \frac{|0⟩+e^{2\pi i0.j_2\cdots j_n}|1⟩}{\sqrt{2}}\otimes \cdots \otimes \frac{|0⟩+e^{2\pi i0.j_n}|1⟩}{\sqrt{2}}.$$

为什么这个式子成立？ 把定义中的 $k$ 写成二进制 $k=k_1{k}_2\cdots k_n$，则 $jk/N=j\cdot 0.k_1{k}_2\cdots k_n$（二进制小数乘法），于是

$$e^{2\pi ijk/N}=e^{2\pi ij{\sum }_{\ell }{k}_{\ell }{2}^{-\ell }}=\prod _{\ell =1}^n{e}^{2\pi ij{k}_{\ell }{2}^{-\ell }}.$$

注意每个因子只依赖单个 $k_{\ell }\in \{0,1\}$：$k_{\ell }=0$ 时因子为 1，$k_{\ell }=1$ 时因子为 $e^{2\pi ij/2^{\ell }}=e^{2\pi i0.j_{n-\ell +1}\cdots j_n}$（只有 $j$ 的低 $\ell$ 位进入这个相位——因为 $j/2^{\ell }\mathrm{mod}1$ 恰好由低 $\ell$ 位决定）。把 ${\prod }_{\ell }$ 拆回张量积，就得到上式。推导完毕。

这个形式告诉我们三件事：

1. 第 $\ell$ 个输出比特只依赖 $j$ 的低 $\ell$ 位所决定的相位 $0.j_{\ell }{j}_{\ell +1}\cdots j_n$（对第 1 个比特是全部 $n$ 位）。
2. 相位 $2\pi \cdot 0.j_{\ell }\cdots j_n$ 是若干个 $2\pi /2^m$ 型相位的和，而”给某比特加 $2\pi /2^m$ 的相位”正是受控相位门能做的事。
3. 整个变换无需任何纠缠残留——输出是乘积态（在正确的比特顺序下）。QFT 的”复杂性”全部藏在相位里，而不藏在纠缠里。

3. 线路实现

定义受控相位门

$$R_m=\left(\begin{array}{cc}1& 0\\ 0& e^{2\pi i/2^m}\end{array}\right)\text{（作用在目标比特上，由控制比特决定是否执行）}.$$

标准 QFT 线路对第 1 个比特依次执行：$H$（产生 $\pm$ 相位 $0.j_1\cdots j_n$ 的叠加）、然后一串受控旋转（把 $0.0j_2\cdots ,0.00j_3\cdots$ 的精细相位逐级加到 $e^{2\pi i0.j_1\cdots }$ 上）；对第 2 个比特重复（少一级），以此类推。最后把比特顺序翻转（一排 SWAP 门）。总门数为

$$\underset{H\text{ 门}}{\underbrace{n}}+\underset{\text{受控相位门}}{\underbrace{\frac{n(n-1)}{2}}}+\underset{\text{SWAP}}{\underbrace{\lfloor n/2\rfloor }}=O(n^2).$$

而经典 FFT 计算同样大小的变换需要 $O(N\log N)=O(n{2}^n)$ 个基本操作——就”实现这个酉变换”而言，量子线路有指数优势。

4. 手算例子：$n=2$ 的完整走查

取 $N=4$，计算 ${\mathrm{QFT}}_4|01⟩$（即 $j=1=(01{)}_2$）。按定义（$k=0,1,2,3$）：

$${\mathrm{QFT}}_4|01⟩=\frac{1}{2}\left(|00⟩+i|01⟩-|10⟩-i|11⟩\right).$$

再按张量积公式（注意二进制小数 $0.j_1{j}_2=0.01_2=\frac{1}{4}$、$0.j_2=0.1_2=\frac{1}{2}$）：

$$\frac{|0⟩+e^{2\pi i/4}|1⟩}{\sqrt{2}}\otimes \frac{|0⟩+e^{2\pi i/2}|1⟩}{\sqrt{2}}=\frac{|0⟩+i|1⟩}{\sqrt{2}}\otimes \frac{|0⟩-|1⟩}{\sqrt{2}}=\frac{1}{2}\left(|00⟩-|01⟩+i|10⟩-i|11⟩\right).$$

对比两式：振幅的模完全一致，但 $|01⟩$ 与 $|10⟩$ 的位置互换了——这正是”最后要加 SWAP”的原因。张量积形式自然给出的是比特倒序 (bit-reversal) 的输出，交换比特顺序后才与定义式逐项吻合。建议读者动手验证 $j=2,3$ 的情形，体会 $e^{i\pi }=-1$ 等相位的来源。

5. 关键澄清：QFT 不是”快速傅里叶变换的量子版”

初学者最常见误解：有了 $O(n^2)$ 的 QFT，是不是就能比 FFT 更快地做信号处理？不能，原因有两层：

• 读出障碍：QFT 把 $a_j$ 的信息编码在振幅 $e^{2\pi ijk/N}/\sqrt{N}$ 中。若直接测量输出，得到 $|k⟩$ 的概率是 $|a_k{|}^2/N$ 级别的均匀混合——相位信息（DFT 结果里最有价值的部分）在一次测量中全部丢失。要恢复完整的 $\{{\hat{a}}_k\}$ 需要重复整个流程 $O(N)$ 次，指数优势荡然无存。
• 输入障碍：要把经典数据 $a_j$ 制备成叠加态 ${\sum }_j{a}_j|j⟩$ 本身一般就需要 $O(N)$ 量级的操作。

那 QFT 有什么用？它的正确用法是作为干涉子程序：先把相位信息回踢到一个基矢的相对相位上（比如经相位估计的受控演化，或 Simon/Shor 中周期函数的相位回踢），再用（逆）QFT 让不同相位的分量发生干涉，把”藏在相位里的周期性”转化为”测量结果中的可读模式”。相位估计正是这一模式最干净的范例。

另一个容易忽略的事实：QFT 作用在计算基矢上时，测量结果的分布完全不变（$|j⟩$ 等概率地变成所有 $|k⟩$ 的均匀叠加）。QFT 的一切作用都通过改变相对相位来实现——这与 D-J 算法中”干涉发生在最后一步 Hadamard”的图像一脉相承。

本词条总结

• QFT 是 DFT 矩阵对应的酉算子；$n=1$ 时退化为 Hadamard 门，可视为”带相位分辨率的 Hadamard 推广”。
• 核心结构是张量积形式：第 $\ell$ 个输出比特只带相位 $2\pi \cdot 0.j_{\ell }\cdots j_n$，这直接给出 $O(n^2)$ 的受控相位线路（输出为比特倒序，需 SWAP 翻转）。
• QFT 不能用来加速经典的傅里叶变换计算（读出障碍 + 输入障碍）；它的角色是干涉引擎，服务于相位估计与周期查找。
• 下一篇将看到：相位估计 = 受控幂 + 逆 QFT，请读者留意本词条的线路在彼处”反着用”的样子。

习题

1. 写出 ${\mathrm{QFT}}_8|111⟩$ 的张量积形式，并化简每个相位因子（它们都是 $\pm 1,\pm i$ 的 8 次单位根）。
2. 证明 ${\mathrm{QFT}}_N^{-1}={\mathrm{QFT}}_N^{†}$，并说明逆 QFT 线路与正 QFT 线路的关系（每个 $R_m$ 换成 $R_m^{†}$，门的顺序倒排）。
3. 验证 QFT 把”平移”变成”相位”：证明对任意 $j,s$，$\mathrm{QFT}\left(\frac{1}{\sqrt{N}}{\sum }_j{e}^{2\pi ijs/N}|j⟩\right)=|s⟩$（模归一化）。这正是相位估计最后一步能读出相位的原理。
4. 统计 QFT 线路中受控相位门的角度：证明若允许近似线路（丢弃所有角度小于 $\epsilon /n^2$ 的受控旋转），门数可以降到 $O(n\log (n/\epsilon ))$。

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch03-algo-basics/quantum-fourier-transform
• 内容遵循 CC BY-NC-SA 4.0 许可协议