# 量子算法基础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**。

:::{admonition} 本课知识点
:class: tip

1. **[QFT 的定义与 DFT 的关系](#qft-definition)**——能写出 QFT 作用在计算基矢 $|j\rangle$ 上的定义式，说明它与经典 DFT 矩阵仅差归一化因子 $\sqrt N$，并验证 $n=1$ 时退化为 Hadamard 门。
2. **[QFT 的张量积形式](#qft-tensor-product)**——能写出 QFT 输出态的逐比特张量积分解，并推导第 $\ell$ 个输出比特的相位 $2\pi\cdot 0.j_\ell j_{\ell+1}\cdots j_n$ 只由 $j$ 的低 $\ell$ 位决定。
3. **[QFT 线路实现与复杂度](#qft-circuit)**——能用 Hadamard 门、受控相位门 $R_m$ 与 SWAP 门搭出 $O(n^2)$ 规模的 QFT 线路，并与经典 FFT 的 $O(N\log N)$ 比较门数。
4. **[比特倒序与手算走查](#qft-bit-reversal-example)**——能对 $n=2$ 的实例分别按定义式与张量积公式计算 QFT，比较两个输出并解释线路末端需要 SWAP 的原因。
5. **[QFT 的能力边界与正确用法](#qft-capability-limits)**——能解释读出障碍与输入障碍为何使 QFT 无法加速经典傅里叶变换计算，并说明 QFT 作为干涉子程序服务于相位估计的用法。

:::

(qft-definition)=
## 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 把这套干涉工具推广到更细的相位分辨率。

(qft-tensor-product)=
## 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 的"复杂性"全部藏在相位里，而不藏在纠缠里。

(qft-circuit)=
## 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)$ 个基本操作——**就"实现这个酉变换"而言，量子线路有指数优势**。

(qft-bit-reversal-example)=
## 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$ 等相位的来源。

(qft-capability-limits)=
## 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【QFT 的定义与 DFT 的关系】**（→ [第 1 节](#qft-definition)）

1. 基础：写出 $\mathrm{QFT}_N$ 作用在计算基矢 $|j\rangle$ 上的定义式，并指出 QFT 矩阵与经典 DFT 矩阵在归一化上的差别。
2. 基础：对 $n=1$（$N=2$）分别计算 $\mathrm{QFT}_2|0\rangle$ 与 $\mathrm{QFT}_2|1\rangle$，验证单比特 QFT 就是 Hadamard 门。
3. 进阶：证明 $\mathrm{QFT}_N$ 是酉算子：对 $j\neq j'$ 计算和式 $\sum_{k=0}^{N-1}e^{2\pi i(j-j')k/N}$，并说明它为何等于 $0$。

> 提示：把和式看成公比为 $\omega=e^{2\pi i(j-j')/N}\neq 1$ 的等比级数，并利用 $\omega^N=e^{2\pi i(j-j')}=1$。

**练习 2【QFT 的张量积形式】**（→ [第 2 节](#qft-tensor-product)）

1. 基础：取 $j=6=(110)_2$，写出 $\mathrm{QFT}_8|110\rangle$ 的张量积形式，并把三个相位因子化简为具体的复数值。
2. 进阶：写出 $\mathrm{QFT}_8|111\rangle$ 的张量积形式并化简每个相位因子，验证它们都是 8 次单位根，且其中一个既不等于 $\pm 1$ 也不等于 $\pm i$。
3. 进阶：证明 $e^{2\pi i\,j/2^\ell}=e^{2\pi i\,0.j_{n-\ell+1}\cdots j_n}$，即 $j/2^\ell$ 的小数部分只由 $j$ 的低 $\ell$ 位决定（可把 $j$ 写成 $2^\ell q+r$，$r$ 为低 $\ell$ 位）。

> 提示：第 2 题的三个二进制小数依次为 $0.111_2=\tfrac78$、$0.11_2=\tfrac34$、$0.1_2=\tfrac12$。

**练习 3【QFT 线路实现与复杂度】**（→ [第 3 节](#qft-circuit)）

1. 基础：对 $n=3$ 统计标准 QFT 线路用到的 $H$ 门、受控相位门与 SWAP 门的个数，并验证总数与 $n+\tfrac{n(n-1)}{2}+\lfloor n/2\rfloor$ 一致。
2. 进阶：证明 $\mathrm{QFT}_N^{-1} = \mathrm{QFT}_N^\dagger$，并说明逆 QFT 线路与正 QFT 线路的关系（每个 $R_m$ 换成 $R_m^\dagger$，门的顺序倒排）。
3. 进阶：统计 QFT 线路中受控相位门的角度：证明若允许近似线路（丢弃所有角度小于 $\varepsilon/n^2$ 的受控旋转），门数可以降到 $O(n \log(n/\varepsilon))$。

> 提示：第 3 题中被保留的门满足 $2\pi/2^m\ge\varepsilon/n^2$，即 $m\le\log_2(2\pi n^2/\varepsilon)$，故每个比特只需 $O(\log(n/\varepsilon))$ 级旋转。

**练习 4【比特倒序与手算走查】**（→ [第 4 节](#qft-bit-reversal-example)）

1. 基础：按定义式与张量积公式分别计算 $\mathrm{QFT}_4|10\rangle$（$j=2$），对比两组振幅，指出哪两个基矢的振幅发生了互换。
2. 进阶：对一般的 $|j_1 j_2\rangle$，把第 3 节的 $n=2$ 线路（对比特 1 依次施加 $H$ 与受控 $R_2$、对比特 2 施加 $H$、最后 SWAP）逐步作用上去，验证输出与定义式逐项一致。

> 提示：受控 $R_2$ 恰好在 $j_2=1$ 时把比特 1 的 $|1\rangle$ 分量乘以 $e^{2\pi i/4}=i$，从而凑出相位 $e^{2\pi i\,0.j_1 j_2}$。

**练习 5【QFT 的能力边界与正确用法】**（→ [第 5 节](#qft-capability-limits)）

1. 基础：验证 QFT 作用在任意计算基矢 $|j\rangle$ 上时，所有输出振幅的模长都是 $1/\sqrt N$；据此说明 QFT 的一切作用都只通过改变相对相位实现。
2. 基础：分别用一句话说明"读出障碍"与"输入障碍"为什么都会带来 $O(N)$ 量级的代价。
3. 进阶：验证 QFT 把"相位梯度"变成"平移"：证明 $\mathrm{QFT}_N\left(\tfrac{1}{\sqrt N}\sum_j e^{-2\pi i js/N}|j\rangle\right) = |s\rangle$；再说明相位回踢产生的是 $e^{+2\pi i js/N}$ 型相位，因此相位估计的最后一步用的是逆 QFT。

> 提示：交换求和顺序后，内层 $\sum_j e^{2\pi ij(k-s)/N}$ 是公比非 1 的等比级数。