4. Simon算法与隐藏子群问题
Simon算法是量子计算史上第一个相对经典计算展现出指数级加速的算法，它比Shor算法更早出现，却奠定了后者乃至整个隐藏子群问题（Hidden Subgroup Problem, HSP）框架的核心思想。理解Simon算法，不只是记住一个电路，而是掌握“如何把函数的结构信息编码进量子相位，再用傅里叶采样把它提取出来”这一通用范式。
问题定义：周期函数识别
设有一个函数 f: {0,1}^n → {0,1}^n，它满足如下承诺：存在一个非零的隐藏串 s ∈ {0,1}^n，使得对所有 x, y，f(x) = f(y) 当且仅当 x = y 或 x ⊕ y = s。也就是说，函数在异或意义下以 s 为周期，每个输出值恰好被两个输入映射到，这两个输入相差 s。目标是找出 s。
经典确定性算法在最坏情况下需要 Ω(2^{n/2}) 次查询，因为随机取两个输入，它们恰好相差 s 的概率极低。而Simon算法只需 O(n) 次量子查询即可高概率求出 s，这是指数级分离。
量子线路：叠加、查询与傅里叶采样
算法使用两个n比特寄存器。第一步对第一个寄存器施加Hadamard变换，制备均匀叠加态 (1/√2^n) Σ_x |x⟩|0⟩。第二步用可逆的量子预言机 U_f: |x⟩|y⟩ → |x⟩|y ⊕ f(x)⟩，得到：
(1/√2^n) Σ_x |x⟩|f(x)⟩由于 f(x) = f(x ⊕ s)，测量第二个寄存器会得到某个输出值 f(x₀)，同时第一个寄存器坍缩为 (|x₀⟩ + |x₀ ⊕ s⟩)/√2。此时第一个寄存器中已经“编码”了 s：两个基态的异或正是 s。但直接测量只能得到 x₀ 或 x₀ ⊕ s，无法确定 s。
关键第三步：对第一个寄存器再次施加Hadamard变换。计算可得，测量结果 y 满足 y · s = 0 (mod 2)，且所有满足该条件的 y 等概率出现。也就是说，每次运行得到的是一个与 s 正交的n比特向量。重复 O(n) 次，收集到n个线性无关的方程 y₁·s = 0, …, yₙ·s = 0，用高斯消元在GF(2)上解出非零解，即得 s。
经典后处理：GF(2)上的线性代数
量子部分结束后，我们手中有若干向量 y，每个都满足 y · s ≡ 0 (mod 2)。把每个 y 看作一行，构造矩阵 A，问题转化为求 A s = 0 的非零解。由于 s ≠ 0，解空间至少是一维的。当收集到 n-1 个线性无关的向量时，解空间恰好是一维，s 被唯一确定（差一个非零标量，但在GF(2)上标量只有1，所以就是 s 本身）。
实际操作中，每次量子测量得到 y 是随机的，可能重复或线性相关。因此通常多跑几次，比如 n + c 次（c 为常数），以保证以高概率获得 n-1 个线性无关的向量。高斯消元的时间复杂度为 O(n³)，相对于量子查询次数 O(n) 来说，在多项式时间内可完成，不影响整体指数加速的结论。
s = 110。运行量子线路若干次，假设得到 y₁ = 101、y₂ = 011、y₃ = 110。检查：101·110 = 1⊕0⊕0 = 1 ≠ 0，说明 y₁ 不满足条件，应丢弃。实际有效向量必须满足点积为0。假设有效向量为 y₁ = 101（1⊕0⊕0=1，不对），重新取 y₁ = 011（0⊕1⊕0=1，不对），再取 y₁ = 000（平凡解，无信息）。正确例子：s = 110，则 y = 101 时 1·1⊕0·1⊕1·0 = 1，不满足；y = 011 时 0⊕1⊕0 = 1，不满足；y = 110 时 1⊕1⊕0 = 0，满足。所以有效向量是那些与 s 在偶数个位置同时为1的向量。收集到足够多这样的向量后，解方程即得 s。
复杂度下界与指数分离
Simon问题的一个重要理论贡献是给出了经典查询复杂度的下界。可以证明，任何经典随机算法在最坏情况下需要 Ω(2^{n/2}) 次查询才能确定 s。直观理解：在找到一对碰撞 x 和 x ⊕ s 之前，算法无法获得关于 s 的任何信息；而随机采样下，碰撞概率约为 2^{-n/2}。量子算法通过叠加和傅里叶采样，一次性获取全局相位信息，从而绕过了逐个查询的限制。
这个指数分离不仅是理论上的里程碑，还直接启发了Shor算法：Shor算法可以看作Simon算法在整数群上的推广，把异或周期替换为模运算周期，把Hadamard变换替换为量子傅里叶变换（QFT）。
隐藏子群问题（HSP）推广框架
Simon算法和Shor算法都可以纳入隐藏子群问题的统一框架。给定一个群 G 和一个函数 f: G → S，承诺 f 在某个子群 H ≤ G 的陪集上取常值，且在不同陪集上取值不同。目标是找出隐藏子群 H。
| 问题 | 群 G | 隐藏子群 H | 量子傅里叶变换 | 经典后处理 |
|---|---|---|---|---|
| Simon | (Z₂)ⁿ | {0, s} | Hadamard (即(Z₂)ⁿ上的QFT) | GF(2)高斯消元 |
| Shor (阶查找) | Z | rZ | QFT over Z | 连分数展开 |
| 离散对数 | Z × Z | {(x, y): x = ky mod r} | 二维QFT | 线性方程组 |
HSP框架的通用流程是：制备均匀叠加态 → 查询 f → 测量第二个寄存器 → 第一个寄存器坍缩到某个陪集 → 对第一个寄存器施加群 G 上的量子傅里叶变换 → 测量得到与隐藏子群正交的群特征标 → 重复采样并经典后处理求出 H。不同问题的区别在于群的结构、QFT的实现方式以及经典后处理的具体算法。
O(n) 次采样就足以确定整个隐藏结构。这种“量子采样 + 经典线性代数”的分工模式，是量子算法设计中反复出现的基本范式。
需要指出的是，HSP框架并非对所有群都已知高效量子算法。对于非阿贝尔群，HSP的量子算法设计仍然是开放难题，这也是量子算法理论中最活跃的研究方向之一。Simon算法作为阿贝尔群上HSP的最简单实例，为理解更复杂的群结构提供了清晰的起点。