量子算法基础2：量子傅里叶变换（QFT）¶
前置阅读：Deutsch-Jozsa 算法（本篇第 1 篇）。本篇是相位估计（第 3 篇）和 Shor 算法（第 4 章）的共同基石。
课程目标：
理解量子傅里叶变换 (Quantum Fourier Transform, QFT) 的定义，以及它与经典离散傅里叶变换 (DFT) 的关系。
掌握 QFT 的张量积结构——它是整个线路实现的核心，也是最精妙的一步推导。
学会用受控相位门搭出 \(O(n^2)\) 规模的 QFT 线路，并与经典 FFT 的 \(O(N\log N)\) 比较。
弄清一个初学者最容易困惑的问题：为什么 QFT 不能用来"快速计算傅里叶变换"。
为第 3 篇（相位估计）做好准备：QPE 中真正被使用的是逆 QFT。
本课知识点
QFT 的定义与 DFT 的关系——能写出 QFT 作用在计算基矢 \(|j\rangle\) 上的定义式，说明它与经典 DFT 矩阵仅差归一化因子 \(\sqrt N\)，并验证 \(n=1\) 时退化为 Hadamard 门。
QFT 的张量积形式——能写出 QFT 输出态的逐比特张量积分解，并推导第 \(\ell\) 个输出比特的相位 \(2\pi\cdot 0.j_\ell j_{\ell+1}\cdots j_n\) 只由 \(j\) 的低 \(\ell\) 位决定。
QFT 线路实现与复杂度——能用 Hadamard 门、受控相位门 \(R_m\) 与 SWAP 门搭出 \(O(n^2)\) 规模的 QFT 线路，并与经典 FFT 的 \(O(N\log N)\) 比较门数。
比特倒序与手算走查——能对 \(n=2\) 的实例分别按定义式与张量积公式计算 QFT，比较两个输出并解释线路末端需要 SWAP 的原因。
QFT 的能力边界与正确用法——能解释读出障碍与输入障碍为何使 QFT 无法加速经典傅里叶变换计算，并说明 QFT 作为干涉子程序服务于相位估计的用法。
1. 从经典 DFT 到量子 QFT¶
回忆经典离散傅里叶变换：给定长度为 \(N\) 的复向量 \((a_0, a_1, \ldots, a_{N-1})\)，DFT 把它变成另一个长度为 \(N\) 的向量，第 \(k\) 个分量为
它是一个线性变换，写成矩阵就是 \(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\) 混用）映为
换句话说，QFT 的矩阵元素恰好是 DFT 矩阵的元素（差一个归一化因子 \(\sqrt N\)）。因为 DFT 矩阵是酉的，所以 QFT 是合法的量子操作。
一个立刻值得注意的事实：当 \(n=1\)（\(N=2\)）时，
单比特 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\)），则
为什么这个式子成立？ 把定义中的 \(k\) 写成二进制 \(k = k_1 k_2 \cdots k_n\)，则 \(jk/N = j \cdot 0.k_1 k_2 \cdots k_n\)（二进制小数乘法），于是
注意每个因子只依赖单个 \(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\) 拆回张量积，就得到上式。推导完毕。
这个形式告诉我们三件事：
第 \(\ell\) 个输出比特只依赖 \(j\) 的低 \(\ell\) 位所决定的相位 \(0.j_\ell j_{\ell+1}\cdots j_n\)（对第 1 个比特是全部 \(n\) 位）。
相位 \(2\pi \cdot 0.j_\ell \cdots j_n\) 是若干个 \(2\pi/2^m\) 型相位的和，而"给某比特加 \(2\pi/2^m\) 的相位"正是受控相位门能做的事。
整个变换无需任何纠缠残留——输出是乘积态（在正确的比特顺序下）。QFT 的"复杂性"全部藏在相位里，而不藏在纠缠里。
3. 线路实现¶
定义受控相位门
标准 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 门）。总门数为
而经典 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\)）：
再按张量积公式（注意二进制小数 \(0.j_1 j_2 = 0.01_2 = \tfrac14\)、\(0.j_2 = 0.1_2 = \tfrac12\)）：
对比两式：振幅的模完全一致，但 \(|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【QFT 的定义与 DFT 的关系】（→ 第 1 节）
基础：写出 \(\mathrm{QFT}_N\) 作用在计算基矢 \(|j\rangle\) 上的定义式，并指出 QFT 矩阵与经典 DFT 矩阵在归一化上的差别。
基础：对 \(n=1\)（\(N=2\)）分别计算 \(\mathrm{QFT}_2|0\rangle\) 与 \(\mathrm{QFT}_2|1\rangle\)，验证单比特 QFT 就是 Hadamard 门。
进阶：证明 \(\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 节）
基础：取 \(j=6=(110)_2\)，写出 \(\mathrm{QFT}_8|110\rangle\) 的张量积形式，并把三个相位因子化简为具体的复数值。
进阶：写出 \(\mathrm{QFT}_8|111\rangle\) 的张量积形式并化简每个相位因子，验证它们都是 8 次单位根，且其中一个既不等于 \(\pm 1\) 也不等于 \(\pm i\)。
进阶：证明 \(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 节）
基础：对 \(n=3\) 统计标准 QFT 线路用到的 \(H\) 门、受控相位门与 SWAP 门的个数，并验证总数与 \(n+\tfrac{n(n-1)}{2}+\lfloor n/2\rfloor\) 一致。
进阶：证明 \(\mathrm{QFT}_N^{-1} = \mathrm{QFT}_N^\dagger\)，并说明逆 QFT 线路与正 QFT 线路的关系（每个 \(R_m\) 换成 \(R_m^\dagger\)，门的顺序倒排）。
进阶：统计 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 节）
基础：按定义式与张量积公式分别计算 \(\mathrm{QFT}_4|10\rangle\)（\(j=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 作用在任意计算基矢 \(|j\rangle\) 上时，所有输出振幅的模长都是 \(1/\sqrt N\)；据此说明 QFT 的一切作用都只通过改变相对相位实现。
基础：分别用一句话说明"读出障碍"与"输入障碍"为什么都会带来 \(O(N)\) 量级的代价。
进阶：验证 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 的等比级数。