4. 量子傅里叶变换的定义

经典离散傅里叶变换（DFT）处理的是一个长度为 N 的复数向量 x = (x₀, x₁, …, x_N−1)，输出向量 y = (y₀, y₁, …, y_N−1)，其定义为

y_k = (1/√N) Σ_j=0^N−1 x_j · e^2πijk/N，  k = 0, 1, …, N−1。

这里 N 通常取 2 的幂，即 N = 2ⁿ，因为量子傅里叶变换（QFT）最自然的实现规模就是 n 个量子比特。经典 DFT 的输入是 N 个复数，输出也是 N 个复数，计算复杂度为 O(N²)，快速傅里叶变换（FFT）可降到 O(N log N)。而 QFT 的输入是 n 个量子比特的量子态，输出是同一组量子比特上的另一个量子态，线路深度约为 O(n²)，相对于 N = 2ⁿ 是指数级加速。理解这一映射的关键，是把“向量分量”换成“计算基态的振幅”。

从向量分量到计算基振幅

设量子态 |x⟩ = Σ_j=0^N−1 x_j |j⟩，其中 {|j⟩} 是 n 比特计算基，x_j 是满足归一化条件 Σ|x_j|² = 1 的复振幅。QFT 定义为线性算符

QFT: |j⟩ ↦ (1/√N) Σ_k=0^N−1 e^2πijk/N |k⟩。

对任意叠加态作用，得到 QFT|x⟩ = Σ_k y_k |k⟩，其中 y_k 正是经典 DFT 的输出分量。也就是说，QFT 就是把经典 DFT 的系数矩阵作用在量子态的振幅向量上。区别在于：经典 DFT 把结果写进内存，可以逐个读出；QFT 把结果编码进振幅，测量只能以概率 |y_k|² 得到某个基态 |k⟩，无法直接读出全部 y_k。这正是 QFT 不能单独用来“求傅里叶变换”的原因，它必须嵌入相位估计、因子分解等算法中，让后续干涉把相位信息提取出来。

基变换视角：从计算基到傅里叶基

QFT 也可以看作一次基变换。定义傅里叶基

|k⟩_F = (1/√N) Σ_j=0^N−1 e^2πijk/N |j⟩。

那么 QFT 就是把计算基下的态 |x⟩ = Σ_j x_j|j⟩ 重新用傅里叶基展开：|x⟩ = Σ_k y_k|k⟩_F。从矩阵角度看，QFT 矩阵 F_N 的元素为 (F_N)_kj = (1/√N) e^2πijk/N，它是一个酉矩阵，满足 F_N^†F_N = I。逆 QFT 就是 F_N^†，元素为 (1/√N) e^−2πijk/N。酉性保证了 QFT 可以用量子线路可逆地实现，这是它区别于一般线性变换的根本性质。

二进制展开与乘积形式

把 j 和 k 写成二进制 j = j₁j₂…j_n，k = k₁k₂…k_n（j₁ 为最高位），利用 jk/N = Σ_l=1ⁿ j_l k / 2^l，可以把 QFT 写成张量积形式：

QFT|j⟩ = (1/√2)(|0⟩ + e^2πi0.j_n|1⟩) ⊗ (1/√2)(|0⟩ + e^{2πi0.j_n−1j_n}|1⟩) ⊗ … ⊗ (1/√2)(|0⟩ + e^{2πi0.j₁j₂…j_n}|1⟩)。

这里 0.j₁j₂…j_n 表示二进制小数。这个乘积形式直接给出了线路构造：每个输出比特是一个单比特叠加态，其相对相位由输入比特的二进制小数决定。注意输出比特的顺序与输入相反，第 l 个输出比特携带的是输入第 n−l+1 位及更低位的相位信息，因此标准线路最后需要一组交换门把顺序翻转回来。

量子线路符号表示

QFT 的标准线路由三类门组成：Hadamard 门 H 和受控相位门 R_m。受控相位门 R_m 的定义为

R_m = [[1, 0],
       [0, e^{2πi / 2^m}]]

其中 m 是整数，R₂ 即受控 S 门（相位 π/2），R₃ 即受控 T 门（相位 π/4），依此类推。对 n 个量子比特，线路按如下方式作用：对第 1 个比特施加 H，然后依次以第 2、3、…、n 个比特为控制位施加 R₂、R₃、…、R_n；接着对第 2 个比特施加 H，再以第 3、…、n 个比特为控制位施加 R₂、…、R_n−1；如此继续，直到最后一个比特只施加 H。最后用 n/2 个交换门（SWAP）把比特顺序反转。整个线路使用 n(n+1)/2 个门，深度 O(n²)。

下面这张图给出 n = 4 时 QFT 线路的结构示意，同时标出输入比特、输出比特与相位门的控制关系，便于对照上面的乘积形式理解“哪个输出比特携带哪一段相位”。

图中虚线表示控制关系：R₂ 由相邻低位比特控制，R₃ 由次低位控制，R₄ 由最低位控制。可以看到，越靠上的输出比特，其相位中保留的输入位越多，这正是乘积形式中“第 l 个输出比特相位为 0.j_n−l+1…j_n”的线路体现。

一个可手算的示例

取 n = 2，N = 4，输入 |j⟩ = |2⟩ = |10⟩，即 j₁ = 1，j₂ = 0。按定义：

QFT|2⟩ = (1/2) Σ_k=0³ e^2πi·2k/4|k⟩ = (1/2)(|0⟩ + e^πi|1⟩ + e^2πi|2⟩ + e^3πi|3⟩) = (1/2)(|0⟩ − |1⟩ + |2⟩ − |3⟩)。

用乘积形式验证：第一个输出比特相位为 0.j₂ = 0.0 = 0，故为 (|0⟩+|1⟩)/√2；第二个输出比特相位为 0.j₁j₂ = 0.10 = 1/2，故为 (|0⟩ + e^πi|1⟩)/√2 = (|0⟩−|1⟩)/√2。两者张量积为 (1/2)(|00⟩ − |01⟩ + |10⟩ − |11⟩)，与定义式一致。这个例子说明：QFT 对计算基态的作用，就是把每个输入比特的二进制值“翻译”成对应输出比特的相对相位，相位大小由二进制小数决定。

与经典 DFT 的对照

最后强调一个容易混淆的点：QFT 的“指数加速”指的是线路规模相对于输入规模 N 的多项式化，而不是说它能像经典 FFT 那样输出完整频谱。真正把 QFT 用起来，靠的是后续算法对相位信息的干涉提取。理解这一点，才能在相位估计章节中看清 QFT 的角色：它把“未知相位”转换成“可测量的比特串”，而不是直接给出答案。