3. QFT的矩阵表示与酉性验证

量子傅里叶变换（QFT）在电路层面是一串受控相位门与Hadamard门的组合，但在代数层面，它就是一个作用在 2^n 维复向量空间上的线性算子。把 QFT 写成矩阵，是理解它“为什么可逆”“为什么保内积”“为什么能作为相位估计的核心”的最直接途径。本节先给出 QFT 矩阵的构造规则，再证明其酉性，最后用 N=2 与 N=4 两个小规模实例把矩阵完整写出来并逐项验证。

一、QFT 矩阵的构造规则

约定：基矢按整数二进制顺序排列，即对 n 个量子比特，基矢为 |0⟩, |1⟩, …, |N−1⟩，其中 N = 2^n。QFT 对基矢的作用定义为

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

注意指数上是正号，这是 QFT 的约定；逆 QFT 取负号。由此，QFT 矩阵的第 j 行第 k 列元素为

F[j][k] = (1/√N) · ω^{jk}，其中 ω = e^{2πi/N}

也就是说，矩阵的每一行是 ω^j 的幂次序列，第一行（j=0）全为 1，第一列（k=0）也全为 1。矩阵是对称的，因为 ω^{jk} = ω^{kj}。这个“行是等比序列、整体对称”的结构，是后面验证酉性时最方便利用的性质。

二、酉性证明

要证 QFT 是酉算子，即证 F†F = I。设 F† 的第 j 行第 k 列元素为 (F[k][j])* = (1/√N)·ω^{−kj}。于是乘积矩阵的第 a 行第 b 列元素为

(F†F)[a][b] = (1/N) Σ_{k=0}^{N−1} ω^{−ka} · ω^{kb} = (1/N) Σ_{k=0}^{N−1} ω^{k(b−a)}

这是一个等比级数求和。令 d = b − a，则求和为 Σ_k (ω^d)^k。当 d ≡ 0 (mod N) 时，每一项都是 1，和为 N，乘上 1/N 得 1；当 d ≢ 0 (mod N) 时，ω^d ≠ 1，由等比求和公式

Σ_{k=0}^{N−1} (ω^d)^k = (1 − ω^{dN}) / (1 − ω^d) = (1 − 1)/(1 − ω^d) = 0

因为 ω^{dN} = e^{2πi·d} = 1。所以 (F†F)[a][b] = δ_{ab}，即 F†F = I。又因 F 是方阵，左逆即右逆，故 F 可逆且 F† = F^{−1}，QFT 是酉算子。这个证明只用到了单位根的正交性，是离散傅里叶变换酉性的标准论证，也是 QFT 能保持量子态归一化、从而可作为合法量子门实现的根本原因。

三、N=2 实例：单量子比特 QFT

n=1 时 N=2，ω = e^{2πi/2} = e^{πi} = −1。按公式，矩阵元素为 (1/√2)·(−1)^{jk}，于是

F₂ = (1/√2) · [[1,  1],
                [1, −1]]

这正是 Hadamard 门 H 的矩阵。也就是说，单比特 QFT 就是 H，这与电路直觉一致：n=1 时没有受控相位门，只剩一个 H。验证酉性：F₂† = F₂（实对称），F₂·F₂ = (1/2)[[2,0],[0,2]] = I。同时 F₂|0⟩ = (|0⟩+|1⟩)/√2，F₂|1⟩ = (|0⟩−|1⟩)/√2，与 H 的作用完全吻合。

四、N=4 实例：两量子比特 QFT

n=2 时 N=4，ω = e^{2πi/4} = i。元素为 (1/2)·i^{jk}。把 i^{jk} mod 4 的取值列出来：j 或 k 为 0 时幂为 0 得 1；jk=1 得 i；jk=2 得 −1；jk=3 得 −i；jk=4 得 1，依此类推。于是

F₄ = (1/2) · [[ 1,  1,  1,  1],
              [ 1,  i, −1, −i],
              [ 1, −1,  1, −1],
              [ 1, −i, −1,  i]]

逐项核对：第 2 行 j=1，元素为 i^k，即 1, i, −1, −i；第 3 行 j=2，元素为 i^{2k} = (−1)^k，即 1, −1, 1, −1；第 4 行 j=3，元素为 i^{3k}，即 1, −i, −1, i。矩阵对称性可直接看出：F[1][3] = −i = F[3][1]。

验证酉性，取第 1 行与第 2 行的内积（即 (F†F)[0][1]）：

(1/4)·[1·1* + 1·(i)* + 1·(−1)* + 1·(−i)*] = (1/4)(1 − i − 1 + i) = 0

再取第 2 行与自身的模平方和：(1/4)(|1|² + |i|² + |−1|² + |−i|²) = (1/4)(1+1+1+1) = 1。其余行列同理，故 F₄†F₄ = I。这里的关键观察是：每一行的模长平方和恒为 1（归一化因子 1/√N 的作用），不同行之间因单位根正交而内积为 0。

五、用代码做数值验证

手算适合小规模，工程上更可靠的做法是写几行代码直接构造并检查。下面用 Python 与 NumPy 对 N=2、4、8 统一验证，判断依据是 F†F 与单位矩阵的最大偏差是否在浮点容差内。

import numpy as np

def qft_matrix(n):
    N = 2 ** n
    j, k = np.meshgrid(np.arange(N), np.arange(N), indexing='ij')
    omega = np.exp(2j * np.pi / N)
    return (omega ** (j * k)) / np.sqrt(N)

for n in (1, 2, 3):
    F = qft_matrix(n)
    err = np.max(np.abs(F.conj().T @ F - np.eye(2 ** n)))
    print(f"n={n}, N={2**n}, max|F†F - I| = {err:.2e}")

预期输出形如 n=1, N=2, max|F†F - I| = 0.00e+00、n=2, N=4, max|F†F - I| ≈ 2.2e-16、n=3, N=8, max|F†F - I| ≈ 4.4e-16。偏差量级在 10^{-16} 说明只是双精度舍入误差，可判定酉性成立。若偏差明显大于 10^{-12}，通常意味着指数符号写反、归一化因子漏乘或基矢顺序错位，应优先检查这三处。

六、从矩阵看 QFT 的结构性质

把 N=4 的矩阵与 N=2 的矩阵对照，可以看到一个递归结构：F₄ 的偶数列（第 0、2 列）构成 F₂ 的重复模式，奇数列（第 1、3 列）则带有 ±i 的相位因子。这正是 Coppersmith 分解 F_N = (F₂ ⊗ I_{N/2}) · D · (I₂ ⊗ F_{N/2}) · P 的矩阵体现，也是 QFT 电路能按 O(n²) 个门实现、而经典 FFT 需要 O(N log N) 次运算的代数根源。矩阵视角还直接说明：QFT 不改变测量概率分布的形状（酉变换保内积），它改变的是相位结构，这正是它在相位估计中把“相位信息”搬到“可测的振幅”上的原因。

小结本节的三条判断依据：矩阵元素由 ω^{jk}/√N 唯一确定；酉性由单位根正交性 Σ_k ω^{k(b−a)} = N·δ_{ab} 保证；小规模实例中 N=2 退化为 H、N=4 出现 ±1, ±i 四种相位，是检查实现是否正确的最小测试集。