Simon 算法

前置阅读：Deutsch-Jozsa 算法、量子傅里叶变换。本词条是通往 Shor 算法的最后一级台阶。

本词条要点：

1. 理解 Simon 问题（寻找”隐藏掩码”）的设定，以及为什么经典算法需要指数级查询。
2. 走通算法推导：相位回踢 + Hadamard 干涉，得到 $z\cdot s=0$ 的随机方程。
3. 掌握最后一步经典线性代数：在 ${\mathbb{F}}_2$ 上解齐次线性方程组，并分析采样多少条方程才够。
4. 理解 Simon 算法的真正历史地位：它是隐子群问题的最小完整样本，Shor 算法是它的”连续群”版本。

1. 问题设定：寻找隐藏掩码

给定一个黑盒函数 $f:\{0,1{\}}^n\to \{0,1{\}}^m$（为简单起见设 $m=n$）。我们被承诺：存在一个非零比特串 $s\in \{0,1{\}}^n$，使得

$$f(x)=f(y)⟺y=x\oplus s\text{（对所有 }x,y\text{），}$$

其中 $\oplus$ 表示按位模 2 加法。任务：找出 $s$。

直观地说，$f$ 把 $\{0,1{\}}^n$ 划分成 $2^{n-1}$ 对 $\{x,x\oplus s\}$，每一对映到同一个输出，不同对映到不同输出。$f$ 是”以 $s$ 为周期折叠”的二对一函数；特殊情形 $s=0^n$ 时退化为单射。

经典难度：要确定 $s$，经典算法必须找到一个”碰撞”——两个不同输入 $x\ne y$ 使 $f(x)=f(y)$。随机查询 $k$ 个输入，由生日悖论，出现碰撞的概率约为 $k^2/2^n$；要大概率找到碰撞需要 $k=\Theta (2^{n/2})$ 次查询。而且碰撞本身还不够——找到 $O(n)$ 个碰撞才能解出 $s$。这是指数级（虽然”只是” $2^{n/2}$）复杂度。

2. 量子算法：三步走

Simon 算法的量子部分与 D-J 算法几乎一样短：Hadamard、预言机、Hadamard、测量，重复 $O(n)$ 次；然后做一步经典线性代数。

预言机照旧用相位回踢形式（辅助比特置 $|-⟩$）：

$$U_f|x⟩|-⟩=(-1{)}^{\text{（此处不用）}}\cdots$$

不过 Simon 算法里更方便的写法是直接保留输出寄存器。我们从头推一遍。

Step 1：叠加。

$$|{\psi }_1⟩=H^{\otimes n}|0{⟩}^{\otimes n}\otimes |0{⟩}^{\otimes n}=\frac{1}{\sqrt{2^n}}\sum _{x\in \{0,1{\}}^n}|x⟩|0⟩.$$

Step 2：查询预言机（一次！）。

$$|{\psi }_2⟩=\frac{1}{\sqrt{2^n}}\sum _x|x⟩|f(x)⟩.$$

现在把求和按 $f$ 的取值重新分组：对每个输出值 $u$，恰有两个原像 $x_u$ 与 $x_u\oplus s$。于是

$$|{\psi }_2⟩=\frac{1}{\sqrt{2^{n-1}}}\sum _u\frac{|x_u⟩+|x_u\oplus s⟩}{\sqrt{2}}|u⟩,$$

关键观察：只要不测量输出寄存器，数据寄存器就处在”孪生态” $\frac{1}{\sqrt{2}}(|x_u⟩+|x_u\oplus s⟩)$ 与 $|u⟩$ 的纠缠叠加中；而每一对孪生态都是只依赖两个基矢与 $s$ 的叠加。周期 $s$ 已经”藏”进了这些孪生态的结构里。

Step 3：对数据寄存器做 Hadamard 干涉并测量。

利用推导的恒等式 $H^{\otimes n}|x⟩=\frac{1}{\sqrt{2^n}}{\sum }_z(-1{)}^{x\cdot z}|z⟩$，孪变态变为

$$\frac{1}{\sqrt{2}}\left(H^{\otimes n}|x_u⟩+H^{\otimes n}|x_u\oplus s⟩\right)=\frac{1}{\sqrt{2^{n+1}}}\sum _z(-1{)}^{x_u\cdot z}\left(1+(-1{)}^{s\cdot z}\right)|z⟩.$$

测量数据寄存器，得到特定 $z$ 的概率正比于 ${\left|1+(-1{)}^{s\cdot z}\right|}^2$：

• 若 $s\cdot z=1$：两项相消，概率为 0——这些 $z$ 被干涉彻底抹掉；
• 若 $s\cdot z=0$：两项相长，概率为 $\frac{2}{2^n}=\frac{1}{2^{n-1}}$，且在 $\{z:z\cdot s=0\}$ 上均匀分布。

结论：每一次运行，我们均匀采到一个满足 $z\cdot s=0(\mathrm{mod}2)$ 的随机比特串 $z$。注意测量输出寄存器（得到随机的 $u$）不影响这一分布，可以顺便测掉。

3. 经典后处理：在 ${\mathbb{F}}_2$ 上解线性方程

把每次测得的 $z^{(1)},z^{(2)},\dots$ 当作线性方程 $z^{(i)}\cdot s=0$ 的系数。所有满足条件的 $z$ 构成 ${\mathbb{F}}_2^n$ 中一个 $n-1$ 维子空间 $s^{\perp }$（因为 $s\ne 0$，线性泛函 $z\mapsto z\cdot s$ 的秩为 1）。于是问题化为：收集足够多 $s^{\perp }$ 中的均匀随机向量，张成整个 $s^{\perp }$，其正交补就是 $\{0,s\}$，非零元即答案。

需要多少个样本？ 逐个考察：已有 $k$ 个线性无关的向量时，它们张成 $2^k$ 维子空间；下一个均匀随机向量落入该子空间的概率是 $2^{k-(n-1)}$，从而”线性无关”的概率是 $1-2^{k-(n-1)}$。取 $n-1$ 个样本全部线性无关的概率为

$$\prod _{k=0}^{n-2}\left(1-2^{k-(n-1)}\right)=\prod _{j=1}^{n-1}\left(1-2^{-j}\right)\approx 0.2887>\frac{1}{4}.$$

这是一个与 $n$ 无关的常数（且随 $n$ 增大单调趋近 ${\prod }_{j\ge 1}(1-2^{-j})\approx 0.2888$）！所以重复整个流程 $O(1)$ 轮、共 $O(n)$ 次预言机查询，即可大概率凑齐 $n-1$ 条独立方程，用高斯消元解出 $s$。

复杂度对比：量子 $O(n)$ 次查询 + 多项式经典后处理；经典 $2^{n/2}$ 级别。这是第一个在**查询复杂度**上证明出指数分离的问题（Simon, 1994）。

4. 为什么 Simon 算法重要：隐子群问题的预告

把 Simon 问题抽象一下：函数 $f$ 在群 $G={\mathbb{Z}}_2^n$ 上”隐藏”了一个子群 $H=\{0,s\}$，$f$ 在 $H$ 的每个陪集上取常值、在不同陪集上取不同值。这类设定统称隐子群问题 (Hidden Subgroup Problem, HSP)：

$$f(gh)=f(g)\forall h\in H;f(g_1)\ne f(g_2)\text{若 }{g}_1,g_2\text{ 属于不同陪集}.$$

• $G={\mathbb{Z}}_2^n$：HSP 就是 Simon 问题，用量子方法已解决。
• $G=\mathbb{Z}$（整数加法群）：HSP 就是**周期查找**，而周期查找正是 Shor 因数分解的核心步骤——将看到，Shor 算法的量子部分几乎就是把本词条的 Hadamard 干涉换成上篇的 QFT 干涉。
• $G={\mathbb{Z}}_N^2$（离散对数）：同样可解（第二篇）。
• $G$ 为非交换群（如二面体群）：多数情形仍开放——这是”QFT 为什么对交换群特别有效”的深层边界。

Simon 算法用最小的技术含量（相位回踢 + Hadamard）完整展示了”周期结构 → 相位回踢 → 傅里叶干涉 → 线性方程”这条量子算法主生产线。读懂了它，Shor 算法里真正新的东西就只剩下数论部分（连分数与阶的提取）。

本词条总结

• Simon 问题承诺 $f(x)=f(y)⟺y=x\oplus s$；经典求解需 $\Theta (2^{n/2})$ 次查询（生日悖论）。
• 量子算法：叠加 → 查询 → 孪生态 $\frac{1}{\sqrt{2}}(|x⟩+|x\oplus s⟩)$ → Hadamard 干涉，测得均匀随机的 $z\in s^{\perp }$，即方程 $z\cdot s=0$。
• 采 $n-1$ 个独立方程的成功率是常数（$\approx 0.29$），故总查询次数 $O(n)$，指数优于经典。
• Simon 算法是隐子群问题在 ${\mathbb{Z}}_2^n$ 上的实例，也是 Shor 算法（$\mathbb{Z}$ 上的 HSP）的直接模板。

习题

1. 补全 Step 3 中测量概率的归一化：证明 $z$ 在 $s^{\perp }$ 上均匀分布，即 $P(z)=1/2^{n-1}$。
2. 设 $n=3,s=101$。写出 $s^{\perp }$ 的全部元素；若采样得到 $z^{(1)}=110,z^{(2)}=011$，用高斯消元求出 $s$（答案不唯一时说明如何再采一次）。
3. 证明：若允许 $s=0^n$（$f$ 单射），原算法测得的 $z$ 将在全体 $\{0,1{\}}^n$ 上均匀分布；设计一个判据区分"$s=0$"与"$s\ne 0$"（提示：秩）。
4. 思考题：把 Simon 算法中的 $H^{\otimes n}$ 换成 ${\mathrm{QFT}}_N$（$N=2^n$），对 ${\mathbb{Z}}_N$ 上的周期函数 $f(x)=f(x\mathrm{mod}r)$ 重演推导，写出测量分布（这是 Shor 算法量子部分的原型）。

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch03-algo-basics/simon
• 内容遵循 CC BY-NC-SA 4.0 许可协议