量子计算科普系列 · 第 15 篇

量子傅里叶变换：Shor 的心脏

2026年8月23日

前情提要：第 9 篇《Shor：动摇互联网根基的因式分解》里，我们说到 Shor 算法把"分解大数"变成"找一个周期"。但"找周期"这句话本身并不产生魔法——真正让经典计算机望尘莫及的加速，藏在一个你当时没见过的变换里。它就是量子傅里叶变换（QFT）。

量子傅里叶变换概念图：波干涉化作频谱，叠加相位旋转门线路

一、钩子：魔法不在"找周期"这句话里

第 9 篇留了一个悬念：经典计算机反复试周期要指数时间，Shor 凭什么"一次"就能摸到周期？

答案是——Shor 并没有真的"一次找到周期"。它做的是更聪明的事：先把所有可能周期同时摆上台面，再让一个特殊变换把"正确答案对应的频率"放大成一座尖峰，最后轻轻一测，就读出了周期。

这个"把频率放大成尖峰"的变换，就是量子傅里叶变换。它才是 Shor 真正的心脏。

二、先复习：经典傅里叶变换在干什么

量子版之前，先想清楚经典版。

你听到一段音乐，耳朵能分辨出里面同时有 440Hz 的 A 音、330Hz 的 E 音……这是因为任何复杂声音，都能被拆成一堆不同频率的正弦波叠加。傅里叶变换干的事，就是把一段"随时间变化的波形"，翻译成"由哪些频率、各占多少"的清单。

它在日常里无处不在：MP3 压缩（丢掉人耳不敏感的频率）、JPEG 图片压缩、医疗 CT 成像，背后都是它。而让它飞起来的，是 1965 年发明的 FFT（快速傅里叶变换）算法——把原本 O(N²) 的计算压到 O(N log N)，计算机才得以实时处理信号。

关键点：经典傅里叶变换，是把"一个信号"变成"它的频率分布"。

三、量子版：对"振幅"做频率分析

经典傅里叶变换作用在一串数字（信号采样点）上。量子傅里叶变换作用的，是一个量子态的振幅上。

回忆第 2 篇：n 个量子比特的叠加态长这样

|ψ⟩ = α₀|0⟩ + α₁|1⟩ + … + α_{2ⁿ−1}|2ⁿ−1⟩

那些 α 就是各个基态的振幅。QFT 接收这样一组振幅，输出另一组振幅——本质上，它把"输入态在哪些编号上强、哪些弱"的周期模式，编码进输出态的相位里。

一句话：经典 FFT 分析信号的频率；QFT 分析"振幅排列"里的周期。

这就是为什么它能服务 Shor——分解大数的难点恰恰是"找周期"，而 QFT 天然是个"周期探测器"。

四、QFT 长什么样：一串受控旋转门

在线路里，QFT 不是某个神秘黑箱，而是一段很规整的结构：对每一个比特，先来一个 H 门把它变成叠加，再接上一串受控旋转门（记作 R₂、R₃、…），让后面的比特去"转动"前面的比特的相位；把所有比特处理完后，最后交换一下顺序，就得到了 QFT 的输出。

flowchart LR A["输入: n 个量子比特的叠加态"] --> B["对第 1 个比特加 H 门"] B --> C["后面比特对它施加 R2,R3,... 受控旋转"] C --> D["对第 2 个比特加 H 门 + 受控旋转"] D --> E["依此类推, 处理到第 n 个比特"] E --> F[交换比特顺序] F --> G["输出: 周期信息藏在相位中"] G --> H["逆 QFT = 把整条旋转链反向"]

注意它的"代价"：作用在 2ⁿ 维的态上，QFT 只用了 O(n²) 个量子门。这是一个惊人的事实——它一次性地处理了指数多个振幅，而资源只是量子比特数的平方。经典计算机想做同等规模，连把 2ⁿ 个数写下来都不可能。

五、相位估计：QFT 真正登场的舞台

光有 QFT 还不够，得有人把"要找的周期"先印到相位上。这件前置工作叫量子相位估计（Quantum Phase Estimation, QPE）。

想象一个黑盒 U，它作用在某个态上只是乘一个相位：U|ψ⟩ = e^{2πiφ}|ψ⟩。φ 就是要找的数（比如周期相关的某个分数）。相位估计的做法是：

1. 准备一串"上寄存器"比特，用 H 门制造全叠加； 2. 用受控 U^{2ᵏ} 把不同倍数的相位，分别印到上寄存器各个比特的振幅里； 3. 对上寄存器做 QFT； 4. 测量上寄存器，读出一个整数，它编码了 φ 的二进制近似。

flowchart LR U["黑盒幺正 U, 特征态, 本征相位 phi"] --> E["目标: 读出 phi"] E --> Q["上寄存器: H 门制造全叠加"] Q --> C["受控 U^{2^k}: 把 phi 的二进制位印进振幅"] C --> F["对上寄存器做 QFT"] F --> M["测量 -> 读出的整数约等于 phi 的二进制编码"]

回到 Shor：分解 N，先随机取 a，要找最小的 r 使得 aʳ ≡ 1 (mod N)。通过一种"阶查找（order-finding）"构造，r 恰好是某个相位 φ = k/r 的分母。相位估计把 φ 读出来，QFT 就是读出那一步的核心。最后用经典的数论（连分数展开）从 k/r 反推出 r，大功告成。

六、为什么出来的是"尖峰"而不是"噪声"

这是最该建立直觉的一步。

QFT 之后，输出态在"正确频率"附近会发生相长干涉——所有路径的振幅同相叠加，堆成一座高高的尖峰；而在"错误频率"处，振幅正负相消，塌成接近零。于是当你测量时，有压倒性概率落在这座尖峰对应的编号上。

相长与相消干涉：错误答案相互抵消，正确答案被放大

把"找周期"翻译成一句话：Shor 让所有候选周期同时参与一次干涉实验，而 QFT 负责把对的那个周期变成干涉图里最亮的那条纹。

graph LR subgraph C["经典 FFT"] I1["时域 / 空间信号 N 个点"] --> T1["离散傅里叶变换"] --> O1["频域表示"] end subgraph Q["量子 QFT"] I2["振幅向量, 维数 2^n"] --> T2["受控旋转门链 O(n^2) 门"] --> O2["相位编码的叠加态"] end C -->|资源| X["O(N log N), N 点逐一存储"] Q -->|资源| Y["O(n^2) 门, 一次处理 2^n 个振幅"]

七、理性降温：QFT 不是万能钥匙

讲完 magic，必须泼点冷水——这也是第 10 篇"量子优势"里反复强调的：量子加速高度依赖任务结构。

它对噪声敏感。QFT 线路深度随比特数平方增长，每一个受控旋转门都必须足够精确。在噪声大的硬件上，误差会累积，尖峰被"抹平"。
它只是 Shor 的一环。完整的威力需要足够多的干净量子比特去表示那个大数，目前离实用规模还差量级。
它不加速所有事。QFT 擅长的是"周期 / 频率"类结构的问题；对没有这种结构的问题，它什么特别的好处都给不了。

换句话说，QFT 是 Shor 的心脏，但一颗强大的心脏，也得装在足够健康的身体（容错硬件）里才能跳动。

八、小结与预告

今天你拿到了第 9 篇留下的钥匙：

经典傅里叶变换分析信号的频率；量子傅里叶变换分析振幅排列里的周期。
QFT 由一串 H 门 + 受控旋转门构成，用 O(n²) 个门处理 2ⁿ 维态——这是它指数级效率的来源。
在 Shor 里，相位估计先把周期印成相位，QFT 再把对的频率放大成一座尖峰，一测即得。

下一篇，就回到第 2 篇那枚硬币：用 |ψ⟩ = α|0⟩ + β|1⟩ 重新看清叠加到底是什么，也顺便把"叠加=同时是 0 和 1"这个最常见的误读纠正过来。

至于"Shor 能破 RSA，我们怎么办"，那是抗量子密码学要回答的问题，后面再聊。

下次见。