2. 离散傅里叶变换与量子傅里叶变换的数学定义

要理解量子傅里叶变换（QFT）为什么重要，必须先把它和经典离散傅里叶变换（DFT）放在同一张数学“底片”上对照。两者处理的对象都是长度为 N 的复数序列，但一个作用在经典向量上，一个作用在量子态的振幅上；一个输出完整序列，一个把信息编码进量子相位。本节从定义出发，逐步建立归一化约定、基态变换规律，并给出复杂度的严格对比。

一、经典 DFT 的定义与约定

设输入序列为 x = (x₀, x₁, …, x_{N−1})，其中每个 x_j 为复数。经典离散傅里叶变换定义为：

X_k = Σ_{j=0}^{N-1} x_j · e^(−2πi·j·k / N),   k = 0, 1, …, N−1

令 ω_N = e^(−2πi/N)，则 X_k = Σ_j x_j · ω_N^{jk}。这里采用负指数约定，即正变换核为 e^(−2πi jk/N)，逆变换核为 e^(+2πi jk/N)。这一符号约定在后续 QFT 中必须保持一致，否则会出现相位共轭错误。DFT 是一个线性变换，可写成矩阵形式 X = F·x，其中 F_{kj} = ω_N^{jk}，F 为 N×N 的酉矩阵（乘以 1/√N 后）。

直接按定义计算，每个 X_k 需要 N 次复数乘加，共 N 个输出，复杂度为 O(N²)。快速傅里叶变换（FFT）利用 ω_N 的周期性与对称性做分治，把复杂度降到 O(N log N)，这是经典计算中实际使用的算法。

二、QFT 的定义与归一化

量子傅里叶变换作用在 n 个量子比特的计算基态 |j⟩ 上，其中 N = 2ⁿ，j ∈ {0, 1, …, N−1}。其定义为：

QFT: |j⟩ → (1/√N) · Σ_{k=0}^{N-1} e^(2πi·j·k / N) · |k⟩

注意两点关键差异。第一，QFT 的核是正指数 e^(+2πi jk/N)，与经典 DFT 的负指数相反；这并非错误，而是量子计算文献的通行约定，逆 QFT 才使用负指数。第二，系数 1/√N 是归一化因子，保证变换后态矢量的模长仍为 1。由于基态 |j⟩ 本身是正交归一的，QFT 矩阵 U_{kj} = (1/√N)·e^(2πi jk/N) 是酉矩阵，满足 U†U = I，这正是量子门可以实现它的前提。

对任意叠加态 |ψ⟩ = Σ_j α_j |j⟩，QFT 线性地作用于振幅：

QFT|ψ⟩ = Σ_k β_k |k⟩,   β_k = (1/√N) · Σ_j α_j · e^(2πi·j·k / N)

也就是说，QFT 把“振幅向量”做了一次与 DFT 同构的变换，只是指数符号相反、并带 1/√N 归一化。理解这一点，就能把经典 DFT 的许多性质（周期性、卷积定理、移位性质）平移到量子情形。

三、基态变换的具体形态

把定义展开到二进制表示，最能看清 QFT 的结构。设 j 的二进制为 j = j₁j₂…jₙ（j₁ 为最高位），定义小数记号 0.j₁j₂…jₙ = j₁/2 + j₂/4 + … + jₙ/2ⁿ。可以证明：

QFT|j⟩ = (1/√N) · (|0⟩ + e^(2πi·0.jₙ)|1⟩)
              ⊗ (|0⟩ + e^(2πi·0.j_{n-1}jₙ)|1⟩)
              ⊗ … ⊗ (|0⟩ + e^(2πi·0.j₁j₂…jₙ)|1⟩)

这个张量积形式是 QFT 电路设计的核心依据：每个输出比特对应一个单比特相位叠加态，相位由输入比特的“小数”决定。以 n = 3、N = 8 为例，输入 |j⟩ = |101⟩（即 j = 5），则：

• 第一个因子相位为 0.j₃ = 0.1 = 1/2，即 e^(2πi·1/2) = −1；
• 第二个因子相位为 0.j₂j₃ = 0.01 = 1/4，即 e^(2πi·1/4) = i；
• 第三个因子相位为 0.j₁j₂j₃ = 0.101 = 5/8，即 e^(2πi·5/8)。

于是 QFT|101⟩ = (1/√8)(|0⟩−|1⟩)⊗(|0⟩+i|1⟩)⊗(|0⟩+e^(5πi/4)|1⟩)。可以看到，输入比特的信息被“搬”到了各输出比特的相对相位上，而输出比特之间不再纠缠——这正是 QFT 能用 Hadamard 门加受控相位门高效实现的原因。

四、复杂度对比：为什么 QFT 是“指数级”优势

把两种变换的代价放在一起看，差异非常直观。经典 DFT 直接计算需要 O(N²) 次复数运算，FFT 优化后为 O(N log N)。而 QFT 在量子线路中只需 O(n²) 个基本门，其中 n = log₂N，因此门数为 O(log²N)。当 N = 2ⁿ 增大时，log²N 相对于 N log N 是多项式级对指数级的差距。

必须强调一个常见误解：QFT 并不能“一次性读出”傅里叶频谱。量子测量会以概率 |β_k|² 坍缩到某个基态 |k⟩，单次运行只给出一个样本。QFT 的真正价值在于它把周期性信息压缩进相位，使后续的相位估计或干涉测量能够以少量采样提取全局性质。这也是 Shor 算法能把因数分解从指数级降到多项式级的根本原因——它并不需要读出全部频谱，只需要提取一个周期。

五、从定义到实现的衔接

基于上面的张量积展开，QFT 的实现路径已经清晰：对每个输入比特先施加 Hadamard 门产生 |0⟩ 与 |1⟩ 的等幅叠加，再用受控相位门把其余比特的信息编码为相对相位，最后通过交换门调整比特顺序（因为展开式中相位因子的顺序与比特索引相反）。以 n = 3 为例，线路包含 3 个 H 门、3 个受控相位门（角度分别为 π/2、π/4、π/2）和若干 SWAP 门，总门数远小于经典 FFT 的运算量。下一节将据此给出具体的门级线路与矩阵验证方法。

总结本节要点：DFT 与 QFT 在数学上同构，差别在于作用对象、指数符号与归一化；QFT 的 1/√N 因子保证酉性，使其可由量子门实现；基态变换的张量积形式揭示了“信息搬移到相位”的机制；复杂度上 QFT 以 O(log²N) 门数取得对经典 O(N log N) 的显著优势，但这一优势必须配合测量策略与后续算法才能兑现。