量子算法基础4：Simon 算法¶
前置阅读：Deutsch-Jozsa 算法（第 1 篇）、量子傅里叶变换（第 2 篇）。本篇是通往第 4 章 Shor 算法的最后一级台阶。
课程目标：
理解 Simon 问题（寻找"隐藏掩码"）的设定，以及为什么经典算法需要指数级查询。
走通算法推导：相位回踢 + Hadamard 干涉，得到 \(z \cdot s = 0\) 的随机方程。
掌握最后一步经典线性代数：在 \(\mathbb{F}_2\) 上解齐次线性方程组，并分析采样多少条方程才够。
理解 Simon 算法的真正历史地位：它是隐子群问题的最小完整样本，Shor 算法是它的"连续群"版本。
1. 问题设定：寻找隐藏掩码¶
给定一个黑盒函数 \(f: \{0,1\}^n \to \{0,1\}^m\)（为简单起见设 \(m = n\)）。我们被承诺：存在一个非零比特串 \(s \in \{0,1\}^n\)，使得
其中 \(\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\)）：
不过 Simon 算法里更方便的写法是直接保留输出寄存器。我们从头推一遍。
Step 1：叠加。
Step 2：查询预言机（一次！）。
现在把求和按 \(f\) 的取值重新分组：对每个输出值 \(u\)，恰有两个原像 \(x_u\) 与 \(x_u \oplus s\)。于是
关键观察：只要不测量输出寄存器，数据寄存器就处在"孪生态" \(\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\)，孪变态变为
测量数据寄存器，得到特定 \(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\) 个样本全部线性无关的概率为
这是一个与 \(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)：
\(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）的直接模板。
习题¶
补全 Step 3 中测量概率的归一化：证明 \(z\) 在 \(s^\perp\) 上均匀分布，即 \(P(z) = 1/2^{n-1}\)。
设 \(n = 3, s = 101\)。写出 \(s^\perp\) 的全部元素；若采样得到 \(z^{(1)} = 110,\ z^{(2)} = 011\)，用高斯消元求出 \(s\)（答案不唯一时说明如何再采一次）。
证明：若允许 \(s = 0^n\)（\(f\) 单射），原算法测得的 \(z\) 将在全体 \(\{0,1\}^n\) 上均匀分布；设计一个判据区分"\(s=0\)"与"\(s\ne0\)"（提示：秩）。
思考题：把 Simon 算法中的 \(H^{\otimes n}\) 换成 \(\mathrm{QFT}_N\)（\(N = 2^n\)），对 \(\mathbb Z_N\) 上的周期函数 \(f(x) = f(x \bmod r)\) 重演推导，写出测量分布（这是 Shor 算法量子部分的原型）。