量子傅里叶变换：从叠加到频谱
一句话定义
量子傅里叶变换（QFT）是计算基上的离散傅里叶变换的酉版本：|x⟩ → 2−n/2Σy e2πixy/2ⁿ|y⟩，且对 n 个量子比特只需 O(n²) 个门即可实现。
为什么重要
QFT 是 Shor 算法的发动机（kp-017），也是相位估计的骨架——后者又支撑着量子化学（kp-027）中的能量估计。它的存在证明了一件深刻的事：一类"全振幅"的线性变换（经典 FFT 需要 O(N log N)、N=2n）在量子硬件上可以指数级省门。同时它也是练习"振幅几何"的最佳对象：看懂 QFT，就真正看懂了相位如何编码数字。
前置知识
kp-012（通用门集，受控相位门的角色）、kp-015（相位回踢与 H⊗n 的用法）。需要复数指数 eiθ = cos θ + i·sin θ 与求和记号。
核心概念
- 定义（N = 2n）：|x⟩ → 1√NΣy e2πixy/N|y⟩——把"数字 x"变成"频率相位均匀铺开的叠加"。
- 直觉：QFT 把数域换成频域；若输入是周期 r 的叠加，输出谱峰位于 k·N/r 处——"找周期"变成"测峰位"。
- 线路结构：每个比特一个 H，加若干受控相位门 Rk（角度 π/2k−1），末端比特反序（SWAP 网络）。
- 与经典 FFT 的对比：经典对 N 个数需 O(N log N) 次运算并读出全部系数；QFT 用 O(n²) 门完成同样映射，但输入输出都是量子态、谱峰无法整体读出——加速"隐含"在读出限制里。
- 相位估计：给定本征态与 U，用 QFT 反演读出 U 的相位——Shor 与化学模拟的共同底层。
直观类比
音乐调音师不必逐个听每个泛音，一次听感就能判断"基频是多少"——耳朵做了傅里叶变换。QFT 是量子版的耳朵：给一串按周期重复的振幅，它一次变换就把周期信息集中到少数"频率峰"上。区别在于：调音师能报出所有频率，而量子耳朵一次测量只报一个峰（以高概率命中正确峰位，见 kp-017 的后处理）。
原理与机制
两级递推看清线路。第一步，把 |x⟩ 写成二进制展开并代入定义式，可证 QFT 分解为 |x₁…xₙ⟩ → (|0⟩+e2πi0.xₙ|1⟩)⊗( |0⟩+e2πi0.xₙ₋₁xₙ|1⟩)⊗…——每个输出比特恰是一个"相位由输入比特从低位读出"的等幅叠加。第二步，该结构对应的电路：对第 1 位加 H（造叠加），再依次受控加来自后续输入位的相位门 R2, R3, …（角度 π/2, π/4, …），对下一位重复；k 级深度共 n(n+1)/2 个门，末端 SWAP 翻转比特序。门数 O(n²)、深度 O(n)，远小于经典 FFT 的 O(2ⁿ·n)。二比特实例：输入 |10⟩（x=2，N=4），输出 = ¼Σy eπiy|y⟩ = ½(|0⟩−|1⟩+|2⟩−|3⟩)——相位以 2 为周期交替，可在纸上逐项验证。
公式或模型
定义：QFT|x⟩ = 1√NΣy=0N−1 e2πixy/N|y⟩。
谱峰定位：输入 1√rΣj|x₀+jr⟩ 时，输出集中在 |kN/r⟩（k=0…r−1），峰宽 ±1——kp-017 的周期 r 由此读出。
门复杂度：n(n+1)/2 + O(n) ≈ O(n²)。
图示
实例或案例
纸面复算二比特 QFT（如上 |10⟩ 例）后，在 kp-030 平台运行 3 比特 QFT 并输入 |011⟩，直方图应显示测量结果均匀分布于 8 个基态——因为输出各振幅模长均为 1/√8。再构造周期输入（用受控相位模拟），观察分布向少数峰聚集。这两个实验分别展示"QFT 不直接给答案"与"谱峰如何浮现"，正是读出限制与周期检测两个知识点的实物教具。
与其他知识点的关系
kp-015 的三段式（叠加-写相位-干涉读出）在此升级为"傅里叶版"；kp-017 直接消费"谱峰定位"结论；kp-027 的相位估计用 QFT 估化学基态能量；kp-019 的 NISQ 变分算法正是为了绕开QFT 深度而生的替代路线。
常见误区
- "QFT 让量子计算机快速做所有傅里叶分析"：谱系数无法全部读出；只有当谱高度集中（少数峰）时，重复测量才有意义。
- "QFT 是指数加速的 FFT，所以能加速信号处理"：输入必须先以量子态存在；把 N 个经典数载入量子态本身就需要 O(N) 操作（输入瓶颈，kp-033）。
- "QFT 输出可以直接读出频率"：输出是叠加态，峰位要靠重复采样与后处理（连分数展开，kp-017）提取。
自测题
- 计算 QFT 作用在 |0⟩ 的输出。
- 为什么 QFT 只需 O(n²) 门而经典 FFT 是 O(N log N)？
- 周期 r 的均匀叠加输入，QFT 输出分布长什么样？
答案要点：x=0 时所有相位为 1，输出 = 均匀叠加态（全部基态等幅）。
答案要点：QFT 是作用在 2ⁿ 维态上的酉变换，门作用"整体"操纵所有振幅；经典 FFT 必须逐个处理 N 个数——量子并行在读出限制内的代价优势。
答案要点：集中于 kN/r（k=0,1,…,r−1）的 r 个峰，各峰宽约 ±1；这正是从测量反推 r 的依据。
延伸阅读
M. A. Nielsen、I. L. Chuang《Quantum Computation and Quantum Information》5.1–5.2 节（含相位估计全推导）。