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

前置阅读：Deutsch-Jozsa 算法（本篇第 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. 线路实现

定义受控相位门

\[\begin{split} R_m = \begin{pmatrix} 1 & 0 \\ 0 & e^{2\pi i/2^m} \end{pmatrix}\ \text{（作用在目标比特上，由控制比特决定是否执行）}. \end{split}\]

标准 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))\)。