1. 课程导入与量子计算基础回顾

量子傅里叶变换（Quantum Fourier Transform，QFT）是量子算法中最重要的线性变换之一，它把计算基下的振幅向量映射到频域表示，是 Shor 因数分解、量子相位估计、离散对数等算法的共同核心。要真正理解 QFT 为什么能带来指数级加速，必须先回到量子计算的基本语言：量子比特、叠加、纠缠、量子门与测量。本节作为全课程起点，先梳理这些基础概念之间的逻辑关系，再说明 QFT 在量子算法版图中的定位，并给出后续 30 章的学习路线。

一、量子比特：从经典位到二维复向量

经典比特只能取 0 或 1，而量子比特（qubit）的状态是一个二维复希尔伯特空间中的单位向量：

|ψ⟩ = α|0⟩ + β|1⟩，  其中 α, β ∈ ℂ，且 |α|² + |β|² = 1

这里 |0⟩ 与 |1⟩ 是计算基，α、β 称为概率幅。概率幅不是概率，它带有相位信息，这正是量子干涉能够发生的原因。例如 |+⟩ = (|0⟩+|1⟩)/√2 与 |−⟩ = (|0⟩−|1⟩)/√2 在测量时都以 1/2 概率得到 0 或 1，但它们的相对相位不同，经过 Hadamard 门后一个变回 |0⟩、另一个变成 |1⟩。QFT 的许多“魔法”正是通过精心安排相位，让某些路径相长、某些路径相消。

多量子比特系统的状态空间是各子系统张量积，n 个量子比特共有 2ⁿ 个基态：

|ψ⟩ = Σ<sub>x=0</sub><sup>2ⁿ−1</sup> α<sub>x</sub>|x⟩，  Σ|α<sub>x</sub>|² = 1

这意味着描述 n 比特的一般态需要 2ⁿ 个复数振幅，经典计算机无法高效存储，而量子计算机天然具备这一表示能力——这是量子并行性的物理基础，也是 QFT 能在 O(n²) 个门内完成经典 FFT 需要 O(n2ⁿ) 次运算之工作的根本原因。

二、叠加、纠缠与量子门

叠加指系统同时处于多个基态的线性组合。单个 Hadamard 门作用在 |0⟩ 上产生 (|0⟩+|1⟩)/√2，对 n 个比特分别作用 H 就得到均匀叠加态 (1/√2ⁿ)Σ|x⟩。QFT 的输入端往往就是这种均匀叠加态。

纠缠是叠加在多体系统中的特殊形式，指整体态不能写成各子系统态的直积。典型例子是 Bell 态 (|00⟩+|11⟩)/√2：测量第一个比特得到 0，第二个必为 0；得到 1，第二个必为 1。纠缠是量子相位估计中“把相位信息写入辅助寄存器”的关键资源，也是 QFT 逆变换能够提取相位的前提。

量子门是作用在量子态上的酉变换 U（满足 U†U = I），因此可逆且保内积。QFT 电路只用到三类门：Hadamard 门 H、受控相位门 R_k 和交换门 SWAP。其中

H = (1/√2)[[1, 1], [1, −1]]
R_k = [[1, 0], [0, e^{2πi/2^k}]]

受控相位门 R_k 在控制位为 1 时给目标位施加相位 e^{2πi/2^k}，它是 QFT 中产生“频率相关相位”的核心元件。理解 R_k 的相位累加方式，是后续手写 QFT 电路的第一步。

三、测量：把量子信息转成经典结果

测量是量子计算与经典世界之间的接口。在计算基下测量态 Σα_x|x⟩，得到结果 x 的概率为 |α_x|²，测量后态坍缩到 |x⟩。QFT 本身是酉变换，不直接给出答案；典型用法是“制备输入态 → 施加 QFT → 测量”，通过测量结果的概率分布反推频域信息。在量子相位估计中，则是对 QFT 后的寄存器测量，读出二进制小数表示的相位。因此，设计 QFT 时必须同时考虑“变换是否正确”和“测量后如何解读”，二者缺一不可。

四、QFT 在量子算法中的定位

QFT 不是“求某个函数的傅里叶变换”的独立算法，而是一个可复用的子程序。它的标准定义是作用在计算基 |x⟩ 上：

QFT|x⟩ = (1/√2ⁿ) Σ<sub>y=0</sub><sup>2ⁿ−1</sup> e^{2πi·x·y/2ⁿ} |y⟩

与经典 DFT 相比，QFT 的输入输出都是量子态，不能直接读出全部 2ⁿ 个振幅；它的价值在于把“周期信息”编码进相位，再通过后续测量或逆变换提取。例如 Shor 算法先用模幂运算制备周期态，再用 QFT 把周期 r 转化为测量结果中分母为 r 的分数；量子相位估计则用 QFT† 把本征相位 φ 转成寄存器中的二进制小数。因此，QFT 在算法版图中的位置可以概括为：它是连接“酉算子的相位结构”与“可测量经典信息”的桥梁。

从资源角度看，n 比特 QFT 只需约 n(n+1)/2 个门（含 H 与受控相位门）加若干 SWAP，门数 O(n²)，深度 O(n²)（在无全连接假设下可进一步优化到 O(n log n) 甚至 O(n) 的近似版本）。这一多项式资源与经典 FFT 的 O(n2ⁿ) 形成鲜明对比，也是 QFT 成为量子算法“基础设施”的原因。

五、本课程路线图与学习建议

后续章节按“概念—推导—电路—实现—应用—优化”推进：先给出 QFT 的严格定义与常用等价形式（张量积形式、二进制小数形式），再逐门推导电路，说明 H 与 R_k 如何逐位产生相位；随后进入实现环节，用状态向量模拟器手写 QFT 函数，并用小规模例子（如 n=3）验证输出振幅与理论值一致；再扩展到 QFT†、量子相位估计与 Shor 算法的周期查找；最后讨论门数优化、近似 QFT 与噪声影响。

学习本节时建议动手做两件事：其一，用纸笔写出 n=2 时 QFT 的 4×4 矩阵，确认每列都是单位向量且两两正交；其二，用任意量子模拟框架构造 |00⟩、|01⟩、|10⟩、|11⟩ 四个输入态，分别施加 QFT 并打印振幅，观察 |01⟩ 输入时输出相位是否按 e^{2πi·y/4} 变化。这两个练习能把“相位—频率”的抽象关系落到具体数字上，为后续电路实现打下直觉基础。