先备导航：你需要 035（Simon 的筛子）、017（换轴母题）、021（H 门）、016（干涉）、014（门=表格）。
下一篇预告：037《王座上的算法：Shor I（问题与思路）》。

把周期变成频率：量子傅里叶变换

音乐软件里都见过那张图：左边的波形（声音随时间的抖动）与右边的频谱（一排高低不齐的柱子）。同一个声音，两种记法——时域记"什么时候振多大"，频域记"哪些频率在响"。中间那台翻译机，就是傅里叶变换：给它一段周期性的波形，它还你一根清晰的尖峰，峰的位置写着频率——周期的倒数。

这台翻译机是经典信号处理的心脏（快速傅里叶变换是算法史上最常用的例行公事之一）。本篇要造它的量子版——量子傅里叶变换（QFT）：输入不是声音波形，而是量子账本上的振幅分布；输出是同一份信息在"频率视角"下的振幅分布。017 篇立过的母题"换轴→干活→换回"，QFT 是它的威力加强版：最强换轴机。它也是 037~038 篇那台王座算法的心脏零件。

量子账本上，"周期"长什么样

先看输入。量子态就是一张振幅分布表（013/014 篇）。设想表里的振幅每 r 格重复一次图案——比如振幅只在 0、r、2r、3r…… 那些位置非零（035 篇 Simon 的孪生对，放大到整数世界就是这种形状）。

把这张表交给 QFT，输出表里发生什么？除极少数位置外，全部相消归零——016 篇的交叉项全表总动员：算某个输出位置 k 时，要把输入的每一格振幅"转一个与 k 成正比的角度"再加总。若输入有周期 r，这些角度在大多数 k 处转满一圈圈、箭头均匀摊开、加总为零；唯独 k 是 r 的整数倍附近时，所有箭头的角度对齐——同向相加，冲出一根振幅尖峰。

**周期 r 进，频率峰出。**这与"听和弦知音名"是同一个动作：时域里的重复结构，在频域里浓缩成一个位置。Simon 篇那台"生杀筛子"（第二个 H）就是 QFT 在比特串世界的分身——今天登场的是整数世界的正式版。

电路：相位当笔，画一台换轴机

QFT 的电路零件只有两样：一排 H 门，加一批受控相位门（CNOT 的表亲：控制比特为 1 时，给目标相位转一个特定角度——019 篇的相位语言上岗）。

n 个比特的 QFT 电路：每个比特过一个 H，再与后面所有比特各接一个角度递减的受控相位门，末尾对调比特顺序。门总数约 n²/2——n² 这个多项式，对 n 个比特的账本（2^n 格）来说是惊人的便宜。对比经典快速傅里叶变换要 O(N·n) = O(2^n·n) 步：QFT 把指数级的工作压成了多项式——这是量子电路第一次在"变换本身"上对经典算法形成指数级优势。

但这份便宜有条款，必须立刻读清（005 篇的老朋友"测量"会收税）：

QFT 便宜地"做"了变换，却不便宜地"给"结果。输入是叠加态，输出也是叠加态——测量只吐一个样本（一个随机的频率位置），整张频谱读不出来。想把 2^n 格的谱全读出来？得跑指数多次，指数优势瞬间蒸发光。

所以 QFT 的正确用法不是"读谱"，而是"瞥一眼"：在那些只需要一个（或少数几个）频率样本的场景里，一次测量就够——而这样的场景恰恰是金矿。头号金矿叫相位估计：估计一个量子操作自带的特征相位——下两篇 Shor 的全部戏份，都从这一个样本里展开。

与 Simon 对账：同一个招，两副拳架

把 035 篇和本篇并排放，你会看到同一招的两副拳架：

• Simon：周期藏在"比特串配对"里（x 与 x⊕s），筛子是比特串世界的 H 群；
• QFT：周期藏在"整数循环"里（x 与 x+r），换轴机是相位门编队。

两个都是"把隐藏的重复结构，翻译成可测量的尖峰/约束"。差别只在周期住在哪个数学世界里——这便是 034 篇谱系规律的下一级台阶：承诺"比特串周期"给指数加速，承诺"整数周期"同样给指数加速，而后者的现实化身（大数分解）值一座王座。

把类比拆掉

频谱类比借了哪里：

• 不像之一：音频频谱的柱子是能量（非负的实数）；QFT 输出的是振幅（带相位的复数箭头）——相位信息全程保留，直到测量那一刻才被平方规则"收税"（016/019 篇）。
• 不像之二：均衡器展示的是"已录好的整段声音"，随时可看全谱；QFT 的输入是叠加态，测量即坍缩——全谱在原理上不可一次读出，只有单样本。类比负责"周期变尖峰"的画面，别负责"随便看谱"。

带走的行李

1. QFT=对振幅分布做傅里叶变换：输入表里每 r 格重复的周期结构，输出表里坍缩成频率尖峰——017 篇"换轴"母题的威力加强版。
2. 电路 n² 门，便宜得惊人；但测量只给一个样本——QFT 的正确用法是"peek 一眼"（相位估计），不是"读全谱"。
3. 与 Simon 同宗：都是"隐藏重复结构 → 可测尖峰/约束"；Simon 的 H 群是比特串版分身，整数版 QFT 将在 Shor 手里对准密码学。

下一站的钩子：零件终于凑齐——H 铺开（021）、黑箱回踢（031）、QFT 换轴（本篇）、模运算黑箱（下篇现造）。把它们装进一台机器，去拆解大数分解——那个 RSA 密码整个地基压着的问题。037《王座上的算法：Shor I（问题与思路）》。

#量子计算 #从硬币到纠错 #量子傅里叶变换 #相位估计