周期藏在黑箱里：Simon 算法

先备导航：你需要 032（BV 与内积黑箱）、031（相位回踢）、016（干涉）、015（纠缠的长相）。

下一篇预告：036《把周期变成频率：量子傅里叶变换》。

周期藏在黑箱里：Simon 算法

一面鼓，鼓点里藏着节拍：音高每隔 s 秒重复一次。你只能"听"——每个时刻问一下音高——怎么敲出 s？

经典世界的笨办法是找重复：把听到的音高记下来，等同一个音高出现两次，两次的间隔就是 s。麻烦在于重复出现得太稀——n 比特的世界里，随机抽查要凑齐一对"孪生答案"，平均要听约 2^(n/2) 次：n=50 时，这个数比一千万亿还大。

1994 年，Simon 提出量子解法：约 n 次。五十比特的问题，五十次黑箱调用，指数级的悬崖被填成了缓坡。这篇算法本身不改密码（问题还是人造的），但它是本专栏的转折点——第一个指数级加速的黑箱算法，而且几个月后，Shor 站在它的肩膀上摘走了分解问题（037 篇）。批四的"谱系规律"（034 篇：承诺越强、加速越大）在此冲上顶格。

黑箱的承诺：孪生答案

设定：黑箱 f 保证——x 与 x 加上秘密 s（逐位异或），答案必然相同；反过来，不是孪生的两个输入，答案必然不同。用 2 比特、s=11 举例：f(00)=f(11)=A，f(01)=f(10)=B——四个输入，其实只有两个独立答案 A、B，每个答案背后站着一对"差 s"的孪生输入。任务：敲出 s。

对比 BV（032 篇）看承诺的分量：BV 的 f 每次泄露"s 与 x 的奇偶"——s 的 1 比特投影，问 n 次凑齐；Simon 的 f 更狡猾，答案根本不含 s 的直接投影，s 藏在"哪些输入共享答案"的配对结构里。承诺从"逐位奇偶"升级成"整体周期"，加速也从 n 倍跳到指数级——谱系规律分毫不差。

电路：纠缠配对，干涉筛子

输入寄存器: ──H──■──H──M
             │
答案寄存器: ──X──⊕────M   （第一步后先测它）

第一步，配对。输入寄存器过 H，铺开全部输入；黑箱调用一次，答案写进下面那条线。此刻账本上每个答案 A 背后拖着两个输入 |00⟩ 与 |11⟩——测量答案寄存器，坍缩出比如 A，输入寄存器立刻只剩 (|00⟩+|11⟩)/√2：一支孪生对（015 篇的纠缠判据现场生效：拆不开的叠加，两支差一个 s）。

第二步，筛。对这支孪生对再过一次 H（024 篇的图：第二个 H 就是干这个的）。2 比特、s=11 的例子可以手算到底：(1/√2)(|00⟩+|11⟩) 过 H⊗H，两支箭头在四个输出上重新分账——|01⟩ 和 |10⟩ 两格的振幅恰好抵消归零，只剩 (1/√2)(|00⟩+|11⟩)。换个坍缩结果 B（孪生对 (|01⟩+|10⟩)/√2），同样手算：剩下 (1/√2)(|00⟩−|11⟩)。

看两次结果的共同点：幸存的输出永远是 00 和 11——恰好是与 s=11"逐位乘积之和为偶"的那两个 y（00·11=0；11·11=1+1=2，偶）。这不是巧合，是干涉的筛选规则：孪生对的两支箭头，对某些输出同向相加、对另一些反向相消（016 篇的交叉项当筛子用），生死的判据是"y 与 s 正交"。

于是每次"配对-筛"，随机漏出一个与 s 正交的 y——s 的一个线性约束。重复约 n 次，收齐 n 个约束，解一个线性方程组，s 是唯一非零解。经典 2^(n/2) 次，量子约 n 次——指数与线性的对决，首秀告捷。

为什么这一步这么值钱

三件事值得单独钉住：

一，纠缠第一次当工具用（此前它都是研究对象）：答案寄存器一测，输入寄存器被"筛"成孪生对——纠缠是配对的传送带。

二，测量的位置是设计的一部分。第一处测量（答案寄存器）是主动的坍缩——故意把世界收窄到"某一个答案"，好让输入寄存器只剩干净的孪生对（002 篇的坍缩，第一次被当工序使用而非麻烦）。

三，第二个 H 是一次"傅里叶变换"。本篇可以提前揭底：把"比特串的世界"里的叠加换成"正交约束"，这一步 H 就是量子傅里叶变换在比特串世界的分身——把"周期结构"（孪生对）翻译成"频率信息"（与 s 正交的 y）。下一篇正式立传的 QFT，是这个动作在"普通整数周期"世界的加强版；再下一篇，Shor 把它对准了密码学的心脏。Simon 不是终点，是 QFT 的预告片。

把类比拆掉

鼓点类比借了哪里：

• 不像之一：鼓的周期是时间轴上的循环（每隔 s 秒重复）；Simon 的"周期"是比特串空间里的镜像孪生（x 与 x⊕s 共享答案）——不是循环，是平移对称。类比只负责"重复结构藏在输出里"。
• 不像之二：听鼓可以持续听、反复听同一段；黑箱每次调用都要现配一对——答案寄存器每次坍缩出的孪生对都是新的随机对，收 n 个约束就要调用 n 次，没有"录下来慢慢分析"。

带走的行李

1. Simon 承诺：f(x)=f(x⊕s)，答案共享构成"差 s"的孪生配对——承诺从 BV 的逐位奇偶升级为整体周期，加速从 n 倍跳到指数级。 2. 电路三步：H 铺开 → 黑箱+测量答案寄存器（纠缠当传送带、坍缩当工序）→ 第二个 H 当筛子（交叉项生杀，幸存者恰为与 s 正交的 y）；约 n 次收约束，解方程得 s。 3. 第二个 H=比特串世界的傅里叶变换——QFT 的预告片；谱系规律的顶格兑现：周期承诺换指数加速。

下一站的钩子：Simon 的"筛子"只在比特串世界好使，而真正的人间周期是普通整数的周期（比如"2 的 k 次方除以 N，余数每隔 r 步重复一次"）。把"换基显形"从比特串推广到整数频率——这台威力加强版换轴机，就是量子傅里叶变换。036《把周期变成频率：量子傅里叶变换》。

#量子计算 #从硬币到纠错 #Simon算法 #周期问题