量子算法基础4：Simon 算法¶
前置阅读：Deutsch-Jozsa 算法（第 1 篇）、量子傅里叶变换（第 2 篇）。本篇是通往第 4 章 Shor 算法的最后一级台阶。
课程目标：
理解 Simon 问题（寻找"隐藏掩码"）的设定，以及为什么经典算法需要指数级查询。
走通算法推导：相位回踢 + Hadamard 干涉，得到 \(z \cdot s = 0\) 的随机方程。
掌握最后一步经典线性代数：在 \(\mathbb{F}_2\) 上解齐次线性方程组，并分析采样多少条方程才够。
理解 Simon 算法的真正历史地位：它是隐子群问题的最小完整样本，Shor 算法是它的"连续群"版本。
本课知识点
Simon 问题与二对一结构——能写出承诺条件 \(f(x)=f(y)\iff y=x\oplus s\)，并解释 \(f\) 为何把 \(\{0,1\}^n\) 划分成 \(2^{n-1}\) 个输入对 \(\{x,\ x\oplus s\}\)。
经典下界：生日悖论找碰撞——能用生日悖论估算 \(k\) 次随机查询出现碰撞的概率，并推导经典求解 Simon 问题需要 \(\Theta(2^{n/2})\) 次查询。
叠加、查询与孪生态——能逐步写出 Step 1–2 中两个寄存器的态演化，并把 \(|\psi_2\rangle\) 按输出值重新分组为孪生态 \(\frac{1}{\sqrt2}(|x_u\rangle+|x_u\oplus s\rangle)\) 的叠加。
Hadamard 干涉与测量分布——能推导孪变态经 \(H^{\otimes n}\) 后的测量分布，说明 \(s\cdot z=1\) 的分量被相消干涉抹掉、\(s\cdot z=0\) 的分量以概率 \(1/2^{n-1}\) 均匀出现。
经典后处理：解方程恢复 s——能把测得的每个 \(z\) 视为 \(\mathbb F_2\) 上的线性方程 \(z\cdot s=0\)，说明收集向量张成 \(s^\perp\) 后由正交补 \(\{0,s\}\) 恢复 \(s\) 的流程。
样本数分析：常数成功率——能计算 \(n-1\) 个样本线性无关的概率 \(\prod_{j=1}^{n-1}(1-2^{-j})\)，并比较量子 \(O(n)\) 与经典 \(2^{n/2}\) 的查询复杂度。
隐子群问题视角——能把 Simon 问题表述为 \(\mathbb Z_2^n\) 上隐藏子群 \(H=\{0,s\}\) 的实例，并说明它与周期查找、Shor 算法的对应关系。
1. 问题设定：寻找隐藏掩码¶
1.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\) 时退化为单射。
1.2 经典难度：生日悖论下界¶
经典难度：要确定 \(s\)，经典算法必须找到一个"碰撞"——两个不同输入 \(x \ne y\) 使 \(f(x) = f(y)\)；由承诺条件，这样一个碰撞直接给出 \(s = x \oplus y\)。随机查询 \(k\) 个输入，由生日悖论，出现碰撞的概率约为 \(k^2/2^n\)；要大概率找到碰撞需要 \(k = \Theta(2^{n/2})\) 次查询。这是指数级（虽然"只是" \(2^{n/2}\)）复杂度。
2. 量子算法：三步走¶
Simon 算法的量子部分与 D-J 算法几乎一样短：Hadamard、预言机、Hadamard、测量，重复 \(O(n)\) 次；然后做一步经典线性代数。
预言机照旧用相位回踢形式（辅助比特置 \(|-\rangle\)）：
不过 Simon 算法里更方便的写法是直接保留输出寄存器。我们从头推一遍。
2.1 Step 1–2：叠加、查询与孪生态¶
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\) 已经"藏"进了这些孪生态的结构里。
2.2 Step 3：Hadamard 干涉与测量分布¶
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\) 上解线性方程¶
3.1 把样本变成方程：张成 \(s^\perp\)¶
把每次测得的 \(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\}\)，非零元即答案。
3.2 样本数分析：常数成功率¶
需要多少个样本？ 逐个考察：已有 \(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）。
本课总结¶
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【Simon 问题与二对一结构】（→ 1.1 节）
设 \(n=2\)、\(s=11\)，写出 \(\{0,1\}^2\) 被承诺划分成的全部输入对 \(\{x,\ x\oplus s\}\)，数出共有几对并与 \(2^{n-1}\) 比较。
证明：满足承诺的掩码 \(s\) 是唯一的——若 \(s\) 与 \(s'\) 都满足承诺，对任意 \(x\)，由 \(f(x)=f(x\oplus s)\) 能推出什么？
提示：对 \(f(x)=f(x\oplus s)\) 用 \(s'\) 承诺的"仅当"方向，再两边与 \(x\) 异或。
练习 2【经典下界：生日悖论找碰撞】（→ 1.2 节）
固定输入 \(x\)，证明随机输入 \(y\ne x\) 与它碰撞的概率是 \(1/(2^n-1)\)；据此写出 \(k\) 个随机查询中期望碰撞对数的近似值，并推出找到一个碰撞需要 \(k=\Theta(2^{n/2})\)。
证明：随机查询 \(k=o(2^{n/2})\) 个输入时，出现碰撞的概率趋于 0，从而经典随机算法要以常数概率解出 \(s\) 需要 \(\Omega(2^{n/2})\) 次查询。
提示："至少一个碰撞"的概率不超过碰撞对数的期望（联合界）。
练习 3【叠加、查询与孪生态】（→ 2.1 节）
写出 Step 1 与 Step 2 结束时两个寄存器的态 \(|\psi_1\rangle\)、\(|\psi_2\rangle\)，并验证 \(|\psi_2\rangle\) 按输出值重新分组后的表达式是归一化的。
设测量输出寄存器得到某个值 \(u\)，写出数据寄存器此时坍缩到的态，并说明它正是孪生态 \(\frac{1}{\sqrt2}(|x_u\rangle+|x_u\oplus s\rangle)\)。
提示：对形如 \(\sum_u c_u|\varphi_u\rangle|u\rangle\) 的态，测量第二寄存器得 \(u\) 后第一寄存器坍缩为 \(|\varphi_u\rangle\)。
练习 4【Hadamard 干涉与测量分布】（→ 2.2 节）
设 \(n=3\)、\(s=111\)：计算单次运行测得 \(z=011\) 与 \(z=001\) 的概率，并列出所有可能被测到的 \(z\)。
补全 Step 3 中测量概率的归一化：证明 \(z\) 在 \(s^\perp\) 上均匀分布，即 \(P(z) = 1/2^{n-1}\)。
提示：对 \(s\cdot z=0\) 的 \(z\) 计算 \(\left|1+(-1)^{s\cdot z}\right|^2/2^{n+1}\)，再数一数 \(s^\perp\) 的元素个数。
练习 5【经典后处理：解方程恢复 s】（→ 3.1 节）
设 \(n = 3, s = 111\)。写出 \(s^\perp\) 的全部元素；若采样得到 \(z^{(1)} = 110,\ z^{(2)} = 011\)，用高斯消元求出 \(s\)（答案不唯一时说明如何再采一次）。
证明：若允许 \(s = 0^n\)（\(f\) 单射），原算法测得的 \(z\) 将在全体 \(\{0,1\}^n\) 上均匀分布；设计一个基于秩的判据区分"\(s=0\)"与"\(s\ne0\)"。
提示：考察采到的向量张成的子空间维数是 \(n-1\) 还是 \(n\)。
练习 6【样本数分析：常数成功率】（→ 3.2 节）
已有 \(k\) 个线性无关的样本时，写出下一个均匀随机样本落入它们张成子空间的概率，并导出"下一个样本仍线性无关"的概率 \(1-2^{k-(n-1)}\)。
计算 \(n=2,3,4\) 时 \(n-1\) 个样本全部线性无关的概率，验证其随 \(n\) 递减并趋于 \(\approx 0.2888\)，并解释为什么这意味着总共 \(O(n)\) 次预言机查询就够。
提示：每多采一个样本，乘积就多乘一个形如 \((1-2^{-j})\) 的因子。
练习 7【隐子群问题视角】（→ 第 4 节）
分别写出 Simon 问题与周期查找对应的群 \(G\) 和被隐藏的子群 \(H\)，并指出哪一个是 Shor 因数分解的核心步骤。
思考题：把 Simon 算法中的 \(H^{\otimes n}\) 换成 \(\mathrm{QFT}_N\)（\(N = 2^n\)），对 \(\mathbb Z_N\) 上的周期函数 \(f(x) = f(x \bmod r)\) 重演推导，写出测量分布（这是 Shor 算法量子部分的原型）。
提示：模仿孪生态的两项干涉，把 \((-1)^{x\cdot z}\) 换成 \(\omega^{xz}\)（\(\omega=e^{2\pi i/N}\)），考察两项何时相长。