2. 数学基础

量子傅里叶变换（QFT）并不是凭空出现的算法，它建立在四块数学基石之上：复数运算、单位根、离散傅里叶变换（DFT）以及张量积与量子态表示。理解这四者的关系，才能看清 QFT 为什么能用 H 门和受控相位门高效实现，而不是像经典 DFT 那样需要 O(N²) 次运算。本节按“从数到变换、从变换到量子表示”的顺序展开，并在关键处给出可直接手算的示例。

一、复数：量子振幅的通用语言

量子态的振幅是复数，写作 z = a + bi，其中 a 为实部，b 为虚部，i² = -1。复数有两种常用表示：直角坐标 (a, b) 与极坐标 z = r·e^{iθ}，其中 r = √(a²+b²) 是模长，θ = atan2(b, a) 是辐角。量子测量只关心模长平方 |z|²，而相位 e^{iθ} 虽然不直接可测，却决定了干涉结果——这正是 QFT 的核心资源。

两个关键运算必须熟练：乘法对应“模长相乘、辐角相加”，即 r₁e^{iθ₁}·r₂e^{iθ₂} = r₁r₂e^{i(θ₁+θ₂)}；共轭 z* = a - bi，用于计算内积 ⟨ψ|φ⟩。例如 z = 1 + i，则 r = √2，θ = π/4，可写成 √2·e^{iπ/4}。在量子线路中，相位门 R_k 的作用就是给指定基态乘上 e^{i2π/2^k}，本质是一次复数乘法。

二、单位根：DFT 的骨架

N 次单位根定义为 ω_N = e^{2πi/N}，满足 ω_N^N = 1。它的 N 个幂 ω_N^0, ω_N^1, …, ω_N^{N-1} 均匀分布在复平面单位圆上，构成一个循环群。以 N = 4 为例：ω₄ = i，四个根为 1, i, -1, -i，分别对应角度 0、π/2、π、3π/2。

单位根有三条常用性质：ω_N^{j+k} = ω_N^j·ω_N^k（指数可加）、ω_N^{N-j} = ω_N^{-j}（共轭对称）、以及正交性 Σ_{j=0}^{N-1} ω_N^{j(k-l)} = N·δ_{kl}。正交性是 DFT 可逆的根本原因，也是 QFT 作为酉变换的数学保证。手算时记住：ω₈ = e^{iπ/4} = (1+i)/√2，它的 8 个幂依次旋转 45°，这在分析 3 量子比特 QFT 的相位时非常有用。

三、离散傅里叶变换：从时域到频域

对长度 N 的复数序列 x₀, x₁, …, x_{N-1}，DFT 定义为：

X_k = (1/√N) · Σ_{j=0}^{N-1} x_j · ω_N^{jk},   k = 0, 1, …, N-1

归一化因子 1/√N 使变换成为酉变换，保证能量守恒 Σ|X_k|² = Σ|x_j|²。逆变换只需把 ω_N^{jk} 换成 ω_N^{-jk}。DFT 的矩阵形式为 F_N[j,k] = ω_N^{jk}/√N，是一个 N×N 的对称酉矩阵。

以 N = 4、输入 x = [1, 0, 0, 0] 为例，计算得 X_k = 1/2（对所有 k），即直流分量均匀分布；若输入 x = [1, 1, 1, 1]，则 X₀ = 2，其余为 0。这两个例子说明 DFT 把“位置信息”转换为“频率信息”。经典计算 DFT 需要 O(N²) 次复数乘法，而 FFT 降到 O(N log N)；QFT 则更进一步，用 O(n²) 个门处理 N = 2ⁿ 维态矢量，但输出是量子叠加态，不能直接读出全部 X_k。

四、张量积与量子态表示

多量子比特系统的态空间是各子系统态空间的张量积。若单比特基态为 |0⟩ 和 |1⟩，则两比特计算基为 |00⟩, |01⟩, |10⟩, |11⟩，写作 |a⟩⊗|b⟩ = |ab⟩。张量积满足双线性：(α|0⟩+β|1⟩)⊗|0⟩ = α|00⟩+β|10⟩。n 个量子比特的态可表示为：

|ψ⟩ = Σ_{j=0}^{2ⁿ-1} c_j |j⟩,   其中 Σ|c_j|² = 1

这里 j 的二进制展开 j = j₁j₂…jₙ 直接对应计算基下标。QFT 正是作用在这 2ⁿ 个基态上：|j⟩ → (1/√N) Σ_k ω_N^{jk}|k⟩。注意 ω_N^{jk} 中的 jk 是整数乘积，而 j 和 k 都是 0 到 N-1 的整数——这与经典 DFT 完全一致，只是输入从复数序列变成了量子振幅。

五、四块基石如何拼成 QFT

把上述内容串起来：复数提供振幅与相位；单位根提供正交基与旋转因子；DFT 给出变换的数学定义；张量积把单比特操作扩展到 n 比特空间。QFT 的线路实现正是这三者的直接翻译——对第 k 个量子比特施加 H 门，再对后续比特施加受控 R_k 相位门，最后做比特反转。每一步都对应一次单位根乘法，整体复杂度 O(n²)，远优于经典 FFT 的 O(N log N)（当 N = 2ⁿ 时，n² 远小于 n·2ⁿ）。

上图的依赖关系可以这样理解：复数定义了振幅的“数”，单位根提供了旋转的“角”，DFT 规定了变换的“式”，张量积搭建了多比特的“场”。四者缺一不可。在后续相位估计中，我们会把 QFT 作用在寄存器上，利用 ω_N^{jk} 的相位累加特性，把 φ 的二进制小数位逐位“提取”到测量结果中。建议读者亲手用 N = 4 验证一次 QFT 矩阵：F₄ = 1/2 · [[1,1,1,1],[1,i,-1,-i],[1,-1,1,-1],[1,-i,-1,i]]，并检查 F₄†F₄ = I，这能帮助你在进入算法细节前建立可靠的直觉。