# 量子算法基础4：Simon 算法

*前置阅读：[Deutsch-Jozsa 算法](deutsch-jozsa.md)（第 1 篇）、[量子傅里叶变换](quantum-fourier-transform.md)（第 2 篇）。本篇是通往第 4 章 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) \iff y = x \oplus s \quad \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)$ 次；然后做一步经典线性代数。

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

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

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

**Step 1：叠加。**

$$
|\psi_1\rangle = H^{\otimes n}|0\rangle^{\otimes n} \otimes |0\rangle^{\otimes n}
= \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^n} |x\rangle |0\rangle .
$$

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

$$
|\psi_2\rangle = \frac{1}{\sqrt{2^n}} \sum_x |x\rangle |f(x)\rangle .
$$

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

$$
|\psi_2\rangle = \frac{1}{\sqrt{2^{n-1}}} \sum_{u} \frac{|x_u\rangle + |x_u \oplus s\rangle}{\sqrt 2} |u\rangle ,
$$

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

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

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

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

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

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

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

## 3. 经典后处理：在 $\mathbb F_2$ 上解线性方程

把每次测得的 $z^{(1)}, z^{(2)}, \ldots$ 当作线性方程 $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 > \frac14 .
$$

这是一个与 $n$ 无关的常数（且随 $n$ 增大单调趋近 $\prod_{j\ge1}(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(g h) = f(g)\ \ \forall h \in H; \qquad 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 因数分解的核心步骤——第 4 章将看到，Shor 算法的量子部分几乎就是把本篇的 Hadamard 干涉换成上篇的 QFT 干涉。
- $G = \mathbb Z_N^2$（离散对数）：同样可解（第 4 章第二篇）。
- $G$ 为非交换群（如二面体群）：多数情形仍开放——这是"QFT 为什么对交换群特别有效"的深层边界。

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

## 本课总结

- Simon 问题承诺 $f(x)=f(y) \iff y = x \oplus s$；经典求解需 $\Theta(2^{n/2})$ 次查询（生日悖论）。
- 量子算法：叠加 → 查询 → 孪生态 $\frac{1}{\sqrt2}(|x\rangle + |x\oplus s\rangle)$ → 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\ne0$"（提示：秩）。
4. 思考题：把 Simon 算法中的 $H^{\otimes n}$ 换成 $\mathrm{QFT}_N$（$N = 2^n$），对 $\mathbb Z_N$ 上的周期函数 $f(x) = f(x \bmod r)$ 重演推导，写出测量分布（这是 Shor 算法量子部分的原型）。