# 量子算法基础2：量子傅里叶变换（QFT）

*前置阅读：[Deutsch-Jozsa 算法](deutsch-jozsa.md)（本篇第 1 篇）。本篇是相位估计（第 3 篇）和 Shor 算法（第 4 章）的共同基石。*

**课程目标：**

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

## 1. 从经典 DFT 到量子 QFT

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

$$
\hat a_k = \sum_{j=0}^{N-1} a_j \, e^{2\pi i\, jk/N}.
$$

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

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

$$
\mathrm{QFT}_N |j\rangle = \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{2\pi i\, jk/N} |k\rangle .
$$

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

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

$$
\mathrm{QFT}_2 |0\rangle = \tfrac{1}{\sqrt2}(|0\rangle + |1\rangle), \qquad
\mathrm{QFT}_2 |1\rangle = \tfrac{1}{\sqrt2}(|0\rangle - |1\rangle),
$$

**单比特 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\rangle
= \bigotimes_{\ell=1}^{n} \frac{|0\rangle + e^{2\pi i\, 0.j_\ell j_{\ell+1}\cdots j_n}|1\rangle}{\sqrt 2}
= \frac{|0\rangle + e^{2\pi i\, 0.j_1 j_2\cdots j_n}|1\rangle}{\sqrt2}
\otimes \frac{|0\rangle + e^{2\pi i\, 0.j_2 \cdots j_n}|1\rangle}{\sqrt2}
\otimes \cdots \otimes
\frac{|0\rangle + e^{2\pi i\, 0.j_n}|1\rangle}{\sqrt2}.
$$

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

$$
e^{2\pi i\, jk/N} = e^{2\pi i\, j \sum_{\ell} k_\ell 2^{-\ell}} = \prod_{\ell=1}^{n} e^{2\pi i\, j\, k_\ell\, 2^{-\ell}}.
$$

注意每个因子只依赖**单个** $k_\ell \in \{0,1\}$：$k_\ell=0$ 时因子为 1，$k_\ell=1$ 时因子为 $e^{2\pi i\, j/2^\ell} = e^{2\pi i\, 0.j_{n-\ell+1}\cdots j_n}$（只有 $j$ 的低 $\ell$ 位进入这个相位——因为 $j/2^\ell \bmod 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 = \begin{pmatrix} 1 & 0 \\ 0 & e^{2\pi i/2^m} \end{pmatrix}\ \text{（作用在目标比特上，由控制比特决定是否执行）}.
$$

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

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

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

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

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

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

再按张量积公式（注意二进制小数 $0.j_1 j_2 = 0.01_2 = \tfrac14$、$0.j_2 = 0.1_2 = \tfrac12$）：

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

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

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

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

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

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

另一个容易忽略的事实：**QFT 作用在计算基矢上时，测量结果的分布完全不变**（$|j\rangle$ 等概率地变成所有 $|k\rangle$ 的均匀叠加）。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\rangle$ 的张量积形式，并化简每个相位因子（它们都是 $\pm1, \pm i$ 的 8 次单位根）。
2. 证明 $\mathrm{QFT}_N^{-1} = \mathrm{QFT}_N^\dagger$，并说明逆 QFT 线路与正 QFT 线路的关系（每个 $R_m$ 换成 $R_m^\dagger$，门的顺序倒排）。
3. 验证 QFT 把"平移"变成"相位"：证明对任意 $j, s$，$\mathrm{QFT}\left(\frac1{\sqrt N}\sum_j e^{2\pi i js/N}|j\rangle\right) = |s\rangle$（模归一化）。这正是相位估计最后一步能读出相位的原理。
4. 统计 QFT 线路中受控相位门的角度：证明若允许近似线路（丢弃所有角度小于 $\varepsilon/n^2$ 的受控旋转），门数可以降到 $O(n \log(n/\varepsilon))$。