Abelian 隐藏子群：Simon、周期查找与离散对数的统一推导¶
许多著名量子算法都在做同一件事：一个黑盒函数把群元素按某个未知子群的陪集分组，量子傅里叶变换则把"平移不变性"变成关于对偶群的线性约束。本课完整推导有限 Abel 群上的隐藏子群（hidden subgroup problem, HSP）算法，并从通式逐一恢复 Simon、阶查找和离散对数。读完本课后，你应当能把这三个看似无关的算法看成同一个电路、同一段分析在不同群上的实例化。
本课知识点
HSP 统一框架——能把 Simon、周期查找与离散对数改写成"函数值相同当且仅当相差隐藏子群元素"的统一形式，写出各自对应的群与隐藏子群，并用生日悖论解释经典碰撞下界 \(\Omega(2^{n/2})\)。
问题定义与输入承诺——能写出有限 Abel 群上隐藏子群问题的承诺与任务目标，解释"当且仅当"承诺两个方向各自的作用，并写出相干 oracle \(U_f\) 的模型。
陪集态制备——能推导一次 \(U_f\) 调用加输出测量把第一寄存器坍缩为陪集态 \(|g+H\rangle\) 的全过程，并计算测量结果的概率 \(|H|/|G|\)。
特征与群上的 QFT——能写出乘积群特征 \(\chi_y(x)\) 的定义并验证其同态性，说明群 QFT 可逐分量实现为 \(F_G=F_{N_1}\otimes\cdots\otimes F_{N_m}\)。
特征正交关系——能用错位相消证明子群上的特征和引理（Lemma 1 的两分性），并说明它与几何级数求和恒等式 \(\sum_{h=0}^{N-1}e^{2\pi iyh/N}=N\delta_{y,0}\) 的联系。
正交补与均匀采样——能由特征和引理推出 \(F_G|g+H\rangle\) 的支撑恰为 \(H^\perp\)、测量结果在 \(H^\perp\) 上均匀分布，并解释陪集代表元 \(g\) 为何不影响分布。
从 Fourier 样本恢复子群——能把每个样本写成关于未知子群的线性同余约束，用子群阶翻倍论证证明 \(O(\log|G|)\) 个样本生成 \(H^\perp\)，并说明 Smith 标准形如何从 \(H^\perp\) 解出 \(H=(H^\perp)^\perp\)。
三个经典算法的实例化——能对 Simon、周期查找与离散对数写出各自的群、隐藏子群与样本方程，并完成高斯消元、连分数、模求逆三种经典后处理的具体计算。
1. 从 Simon 与 Shor 到隐藏子群问题¶
先看三个我们已经见过的具体问题。
Simon 问题（Simon, FOCS 1994，Zoo 编号 108）：黑盒函数 \(f:\{0,1\}^n\to\{0,1\}^n\) 承诺存在秘密串 \(s\)，使得 \(f(x)=f(y)\) 当且仅当 \(x=y\) 或 \(x=y\oplus s\)。任务是求 \(s\)。
周期查找（Shor 算法的核心子程序，见 Nielsen–Chuang 第 5 章，Zoo 编号 76）：给定 \(a\) 与 \(N\)，函数 \(f(x)=a^x\bmod N\) 是周期的，\(f(x)=f(x+r)\) 对某个未知最小周期 \(r\) 成立。任务是求 \(r\)（求出 \(r\) 就能分解 \(N\)）。
离散对数：给定循环群中 \(h=g^s\)，求 \(s\)。
这三个问题表面上差别很大：一个关于异或，一个关于模幂，一个关于循环群。但它们共享同一个代数骨架。Simon 问题中，\(\{0,s\}\) 是 \(\mathbb Z_2^n\) 的一个二阶子群，\(f\) 恰好在这个子群的每个陪集上取常值；周期查找中，\(r\mathbb Z\) 是 \(\mathbb Z\) 的子群，\(f\) 在每个陪集 \(x+r\mathbb Z\) 上取常值；离散对数也可以改写成某个二维群上的周期函数（见第 7 节）。换言之：函数值相同 \(\Longleftrightarrow\) 自变量相差隐藏子群的一个元素。把这句话当作定义，就得到隐藏子群问题。
为什么要专门研究这个统一框架？
第一，它解释了量子加速从哪里来。三个算法的量子部分本质上是同一个电路：制备均匀叠加、查询函数、做傅里叶变换、测量。把它们统一之后，我们只需要证明一次正确性，就能理解一整族算法；遇到新问题时，先问"它是不是某个群上的 HSP"，往往是最快的入手点。
第二，它标出了量子优势的边界。Abel 群上的 HSP 有高效量子算法，而许多重要问题（图同构、格上的最短矢量问题）可以归约为非 Abel 群上的 HSP，那里同样的电路仍然给出多项式次查询，但信息未必够用、后处理也未必高效。本章后续课程会专门讨论这种分离。因此，先把 Abel 情形彻底吃透，是理解"为什么有些 HSP 难"的前提。
第三，历史线索本身就是沿着这个框架展开的。Simon 1994 年的工作（Zoo 编号 108）第一次给出了指数级的量子–经典查询分离，直接启发了 Shor 的分解与离散对数算法；Boneh 与 Lipton（CRYPTO 1995，Zoo 编号 14）随即把同样的思想用于"隐藏线性函数"问题；de Beaudrap、Cleve 与 Watrous（Zoo 编号 30）进一步给出精确的量子–经典查询复杂度分离，说明在某些 HSP 变体中一次量子查询就足够；Hales–Hallgren（Zoo 编号 388）与 Shparlinski–Winterhof（Zoo 编号 389）则研究了当函数只近似周期、或只能观察到部分输出时，傅里叶采样是否仍然有效。本课第 8 节会回到这些放宽条件。
经典算法能做到什么程度？ 以 Simon 问题为代表：经典算法唯一能做的是不断查询 \(f\)，等待"碰撞"（两个不同输入给出相同输出）出现，因为一次碰撞 \(f(x)=f(y)\) 立刻泄露 \(s=x\oplus y\)。但由生日悖论，在约 \(2^{n/2}\) 次查询之前，碰到任何一对碰撞的概率都很小；可以证明经典随机算法需要 \(\Omega(2^{n/2})\) 次查询。这就是"最坏情况下需观察大量输入才能发现碰撞"的严格含义：经典算法的瓶颈在于它一次只能看到一个函数值，而量子算法可以把整个函数"叠加地"查询一次，再利用干涉把全局周期信息集中到可测量的位置上。HSP 框架下的量子算法只需 \(O(n)=O(\log|G|)\) 次查询——这就是指数级分离的来源。
2. 问题定义与输入承诺¶
由有限 Abel 群的结构定理，任何有限 Abel 群都可以分解为循环群的直积。因此不妨设
群运算按分量做模加法，元素写成 \(x=(x_1,\ldots,x_m)\)，\(x_j\in\mathbb Z_{N_j}\)，群的阶为 \(|G|=N_1N_2\cdots N_m\)。这个分解不是损失一般性，而是把"任意有限 Abel 群"具体化为"可以用 \(\sum_j\lceil\log_2 N_j\rceil\) 个量子比特表示的东西"。
隐藏子群问题（有限 Abel 群版本）。未知子群 \(H\le G\) 由黑盒函数 \(f:G\to S\)（\(S\) 是某个有限输出集合）隐藏，\(f\) 满足承诺
任务是：通过对 \(f\) 的（量子）查询，输出 \(H\) 的一组生成元。
把这个承诺拆开读。它包含两个方向：
"\(\Longleftarrow\)"：\(f\) 在每个陪集上常值。 \(H\) 的陪集（coset）指形如 \(g+H=\{g+h:h\in H\}\) 的子集；若 \(x-y\in H\)，则 \(x\) 与 \(y\) 落在同一个陪集中，\(f\) 取相同值。群论的基本事实：两个陪集要么完全相同、要么不相交，且每个陪集恰含 \(|H|\) 个元素，所以 \(G\) 被划分成恰好 \(|G|/|H|\) 个陪集。
"\(\Longrightarrow\)"：不同陪集取不同值。 即 \(f\) 不会"偶然碰撞"。
第二个方向常被忽视，但它很关键。下面的算法会把第一寄存器坍缩到单个陪集的均匀叠加态；如果两个不同陪集给出了相同的函数值，测量该值后第一寄存器将是两个陪集的叠加而不是一个陪集，后续傅里叶分析的结论就不再成立。所以本课所有推导都在这个"当且仅当"承诺下进行；承诺被放宽时会出什么问题，留到第 8 节讨论。
怎么才算"解出"了 \(H\)？ 子群可能有指数多个元素，逐个列举不现实。但有限 Abel 群的任何子群都可以由至多 \(\log_2|G|\) 个元素生成（每次加入一个不在已有子群中的元素，生成子群的阶至少翻倍），所以"输出一组生成元"是一个长度 \(O(\log|G|)\) 的输出，是合理的目标。
Oracle 模型。我们假设可以相干地查询 \(f\)，即存在酉变换
其中 \(\oplus\) 是输出寄存器上的某种可逆嵌入（例如按位异或）。这是标准的量子黑盒设定：一次调用 \(U_f\) 算一次查询。算法优劣首先按查询次数衡量，其次才讨论实现 \(U_f\) 与群运算的门复杂度（第 8 节）。
3. 核心直觉：平移不变性为什么变成线性约束¶
在进入公式之前，先用平实的语言把算法的骨架讲清楚。
困难在哪？ 查询 \(f\) 一次（经典地）只告诉我们一个函数值；\(H\) 的信息分散在全部函数值的全局结构里——哪些输入取相同的值。经典算法必须靠大量采样去"撞出"这个结构。
量子态天然能携带全局结构。 把 \(f\) 叠加地查询一遍，再测量输出寄存器，第一寄存器就坍缩成某个陪集 \(g+H\) 上的均匀叠加——一个"被 \(H\) 平移不变"的态：把它整体平移 \(h\in H\)，态不变（至多差相位）。问题变成：给定一个具有未知平移对称性的态，如何读出对称群 \(H\)？
傅里叶变换是"对称性检测器"。 这是整个算法最核心的一句直觉：在信号处理中，周期函数的傅里叶谱集中支撑在"与周期相容"的频率上——一个以 \(r\) 为周期的序列，其频谱只在 \(r\) 的整数倍对应的频率处非零。群上的傅里叶变换做的是同一件事：陪集态 \(|g+H\rangle\) 在 \(H\) 的所有平移下不变，所以它的傅里叶谱只可能支撑在那些"在 \(H\) 上恒等于 \(1\) 的特征（character）"上。这些特征的集合称为 \(H\) 的 annihilator（正交补） \(H^\perp\)。测量傅里叶谱，就等概率地得到 \(H^\perp\) 的一个元素。
为什么这够用？ 每个样本 \(y\in H^\perp\) 都是关于未知子群的一条线性约束："\(y\) 与 \(H\) 中所有元素配对得 \(1\)"。\(H^\perp\) 本身是一个阶为 \(|G|/|H|\) 的子群，\(O(\log|G|)\) 个随机样本就足以生成它；而知道了 \(H^\perp\)，\(H\) 由纯经典的线性代数（Smith 标准形）唯一确定。量子部分负责"把对称性变成随机约束"，经典部分负责"从约束解出子群"——这就是全部。
还要强调一个看似麻烦、实则无关紧要的点：每次制备陪集态时，陪集代表元 \(g\) 是随机的、不可控的。好在傅里叶谱中 \(g\) 只以相位 \(\chi_y(g)\) 的形式出现，测量时相位消失，所以每次实验得到的都是 \(H^\perp\) 上的同一个均匀分布。算法因此可以反复独立地运行，不必担心抽到"坏陪集"。
下面三节把这个故事逐行推出来。
4. 第一步：从函数查询得到陪集态¶
制备均匀叠加。 从 \(|0\rangle|0\rangle\) 出发，对第一寄存器的每个分量做相应的 Fourier/Hadamard 变换（对 \(\mathbb Z_{N_j}\) 分量做 \(\mathrm{QFT}_{N_j}\)，二进分量就是 Hadamard），得到 \(G\) 上的均匀叠加：
查询 oracle。 作用 \(U_f\)：
注意：这一步只用了一次 \(U_f\) 调用，却因为叠加原理，把 \(f\) 在全部 \(|G|\) 个输入上的值同时写进了寄存器。这是量子算法与经典"逐点查询"的根本区别。
测量第二寄存器。 设测量结果为 \(f\) 的某个取值 \(c\)。哪些 \(x\) 满足 \(f(x)=c\)？由承诺，\(f\) 在不同陪集上取不同值，所以满足条件的 \(x\) 恰好构成一个完整的陪集 \(g+H\)（其中 \(g\) 是任一满足 \(f(g)=c\) 的元素）。投影测量的规则说：测量后态由"把原态投影到与结果相容的子空间再归一化"得到。原态中与 \(c\) 相容的项是
共 \(|H|\) 项，每项振幅 \(1/\sqrt{|G|}\)，所以该结果出现的概率是 \(|H|\cdot(1/|G|)=|H|/|G|\)，归一化因子为 \(\sqrt{|G|/|H|}\)。于是第一寄存器坍缩为
这就是陪集态（coset state）：\(H\) 的某个陪集上的均匀叠加。哪个陪集？由测量结果决定，等价于在全部 \(|G|/|H|\) 个陪集上均匀随机——我们无法选择 \(g\)，也不必选择（第 5 节会说明原因）。
一个技术注记：可以不测量第二寄存器。 实际算法中，测量输出寄存器并非必要——直接把它丢弃（取部分迹）即可。原因是：第二寄存器处于各 \(|f(g)\rangle\) 的混合（不同陪集对应不同的函数值，由承诺这些输出串互不相同、对应的态正交），取部分迹后第一寄存器是各陪集态 \(|g+H\rangle\) 的等概率混合。而下一步（QFT 加测量）对第一寄存器的统计只取决于它是哪个陪集态，混合态的测量统计与"先随机抽一个陪集再测"完全相同——反正 \(g\) 本来就是随机的。这一点留作练习 3 第 2 题严格验证。
本步小结：一次查询（加一次可选的测量）制备出随机陪集态 \(|g+H\rangle\)。这个态携带着 \(H\) 的全部信息——它的平移不变群恰好是 \(H\)——但这些信息还不能直接测量出来，因为任意陪集态在计算基下测量都只给出均匀随机群元素，不含任何关于 \(H\) 的信息。需要换一个基，这就是下一步。
5. 第二步：QFT 为何只留下正交补¶
5.1 群上的特征与傅里叶变换¶
回忆 \(\mathbb Z_N\) 上的 Fourier 变换：\(F_N|x\rangle=\frac1{\sqrt N}\sum_y e^{2\pi ixy/N}|y\rangle\)。其中的相位因子 \(e^{2\pi ixy/N}\) 是 \(\mathbb Z_N\) 的特征——一个把群运算（加法）变成复数乘法的函数。对乘积群 \(G=\mathbb Z_{N_1}\times\cdots\times\mathbb Z_{N_m}\)，特征按分量相乘：对标签 \(y=(y_1,\ldots,y_m)\in G\)，定义
可以直接验证特征的两条基本性质：
同态性：\(\chi_y(x+x')=\chi_y(x)\chi_y(x')\)，因为指数上的和拆开，\(e^{a+b}=e^ae^b\)；
标签的同态性：\(\chi_{y+y'}(x)=\chi_y(x)\chi_{y'}(x)\)，同理。
群 \(G\) 上的量子傅里叶变换就是把计算基换成"特征基"：
它逐分量做 \(\mathrm{QFT}_{N_j}\) 即可实现：\(F_G=F_{N_1}\otimes\cdots\otimes F_{N_m}\)，因为总体相位因子 \(\chi_y(x)\) 正是各分量相位因子的乘积，而求和 \(\sum_y\) 也按分量分解。
5.2 QFT 作用在陪集态上¶
现在把 \(F_G\) 作用到 \(|g+H\rangle\) 上。推导分三步，每步只用上面列出的性质：
最后一步是关键：对固定的 \(y\)，相位 \(\chi_y(g)\) 不依赖于 \(h\)，可以从对 \(h\) 的求和中提出，剩下的括号只含关于 \(H\) 的量。整个表达式的结构于是非常清楚：\(|y\rangle\) 的振幅 =（只依赖 \(g\) 的相位）×（只依赖 \(H\) 的因子）。测量概率只与后者有关，这正解释了为什么随机陪集代表元 \(g\) 不影响结果。
5.3 特征正交关系：一个必须证明的引理¶
括号里的求和 \(\sum_{h\in H}\chi_y(h)\) 是全部推导的核心。它满足一个漂亮的两分性。
Lemma 1（子群上的特征和）. 设 \(H\) 是有限 Abel 群 \(G\) 的子群，\(\chi_y\) 是 \(G\) 的特征。则
证明。第一种情形是平凡的：若 \(\chi_y\) 在 \(H\) 上恒为 \(1\)，求和就是 \(|H|\) 个 \(1\) 相加。
第二种情形用"错位相消"。设存在 \(h_0\in H\) 使 \(\chi_y(h_0)\neq1\)。映射 \(h\mapsto h+h_0\) 是 \(H\) 到自身的双射（群对加法封闭，且平移可逆），所以对 \(h\) 求和与对 \(h+h_0\) 求和是同一个和，只是项的顺序不同：
对右端用同态性 \(\chi_y(h+h_0)=\chi_y(h)\chi_y(h_0)\)，并把不依赖 \(h\) 的因子提出：
于是 \((1-\chi_y(h_0))S=0\)。因为 \(\chi_y(h_0)\neq1\)，只能 \(S=0\)。Q.E.D.
这个证明的思想与"几何级数求和"完全一致：对一个非平凡的周期相位求和，各项绕单位圆均匀分布，恰好相消。事实上对 \(G=\mathbb Z_N\)、\(H=G\) 的特例，这就是恒等式 \(\sum_{h=0}^{N-1}e^{2\pi iyh/N}=N\delta_{y,0}\)。
5.4 annihilator 与最终的测量分布¶
Lemma 1 告诉我们：QFT 之后，只有那些在 \(H\) 上"平凡"的特征标签 \(y\) 才有非零振幅。给它们起个名字。
定义（annihilator / 正交补）。
\(H^\perp\) 本身也是 \(G\) 的子群：若 \(y,y'\in H^\perp\)，则由标签的同态性 \(\chi_{y-y'}(h)=\chi_y(h)\chi_{y'}(h)^{-1}=1\)，故 \(y-y'\in H^\perp\)。它的阶由 \(|H||H^\perp|=|G|\) 给出（练习 6 第 2 题），这与"频率分辨率等于周期长度的倒数"的直觉一致：\(H\) 越大（周期越短），相容的频率越少。
把 Lemma 1 代回 5.2 的表达式：\(y\notin H^\perp\) 的项全部消失，\(y\in H^\perp\) 的项括号等于 \(|H|\)，于是
验证归一化：右端共有 \(|H^\perp|=|G|/|H|\) 项，每项模方为 \(|H|/|G|\)，总模方 \(=|H^\perp|\cdot|H|/|G|=1\)，确实归一。
测量。在计算基下测量这个态，\(y\) 出现的概率为
即 \(H^\perp\) 上的均匀分布。这里用到了 \(|\chi_y(g)|=1\)（它是单位模复数）——陪集代表元 \(g\) 只贡献相位，测量时相位消失。这正是第 3 节预告的事实：未知陪集代表元完全不影响分布，算法能够反复使用随机陪集，每次独立地得到一个 \(H^\perp\) 的均匀随机样本。
5.5 一个可以手算的例子¶
取 \(G=\mathbb Z_{12}\)、\(H=\langle4\rangle=\{0,4,8\}\)（\(|G|=12\)，\(|H|=3\)）。特征为 \(\chi_y(x)=e^{2\pi ixy/12}\)。
先确定 \(H^\perp\)。条件 \(\chi_y(h)=1\) 对所有 \(h\in H\) 成立，只需对生成元 \(h=4\) 成立（其余元素是 \(4\) 的倍数，\(\chi_y(8)=\chi_y(4)^2\) 自动为 \(1\)）：
所以 \(H^\perp=\{0,3,6,9\}\)，\(|H^\perp|=4=12/3\)，与 \(|H||H^\perp|=|G|\) 一致。
再验证 Lemma 1 的相消情形。取 \(y=1\notin H^\perp\)：
因为这三个数恰好是单位圆上的三个三次单位根，和为零。取 \(y=3\in H^\perp\)：\(\chi_3(4)=e^{2\pi i\cdot12/12}=1\)，求和为 \(3=|H|\)。
最后看完整的陪集态演化。取陪集 \(1+H=\{1,5,9\}\)，即 \(g=1\)：
测量结果为 \(0,3,6,9\) 各以概率 \(1/4\) 出现。换一个陪集（比如 \(g=2\)），只是四个相位都乘以 \(e^{2\pi i\cdot2y/12}\)，概率分布不变。注意每个样本都给出关于 \(H\) 的约束：比如测到 \(y=3\) 就学到"\(H\) 中所有元素 \(h\) 满足 \(3h\equiv0\pmod{12}\)"，即 \(H\subseteq\{0,4,8\}\)；再测到一个非零样本（例如 \(6\)：\(6h\equiv0\)，即 \(h\) 偶）不足以缩小，但测到 \(3\) 与 \(9\)（等价地，生成 \(H^\perp\)）就完全确定了 \(H\)。下一节把这个"采样—求解"过程系统化。
6. 第三步：从 Fourier 样本恢复 \(H\)¶
6.1 每个样本是一条线性约束¶
重复"查询—QFT—测量"的循环，得到独立同分布的样本 \(y^{(1)},y^{(2)},\ldots\in H^\perp\)。每个样本的含义是：对所有 \(h\in H\)，
注意这是一条关于未知向量 \(h\) 的线性同余约束——这就是第 3 节所说的"平移不变性变成了线性约束"的精确形式。量子测量把求子群的问题化归为求解一族线性同余方程。
6.2 需要多少样本？¶
样本太少，约束不足以钉住 \(H\)；样本够多，\(H^\perp\) 就被完全生成。下面的引理给出定量答案。
Lemma 2（随机样本生成子群）. 设 \(K\) 是有限 Abel 群，从 \(K\) 上均匀独立地采样。则期望 \(2\log_2|K|\) 个样本即可生成 \(K\)；由 Markov 不等式，\(O(\log|K|)\) 个样本以常数成功率生成 \(K\)。
证明。设已采样本生成的子群为 \(L\le K\)。若 \(L\neq K\)，由 Lagrange 定理 \(|L|\) 整除 \(|K|\) 且 \(|L|\le|K|/2\)。下一个样本落在 \(L\) 外的概率为
而一旦 \(y\notin L\)，新生成的子群 \(\langle L,y\rangle\) 严格包含 \(L\)，其阶至少是 \(|L|\) 的两倍（因为 \(|\langle L,y\rangle|\) 是 \(|L|\) 的倍数且不等）。所以每"成功扩张"一次，子群的阶至少翻倍；从阶 \(1\) 到阶 \(|K|\) 至多需要 \(\log_2|K|\) 次扩张。每次扩张的等待时间是期望不超过 \(2\) 的几何随机变量，故总期望样本数不超过 \(2\log_2|K|\)。Q.E.D.
对 \(K=H^\perp\) 应用此引理：因为 \(|H^\perp|=|G|/|H|\le|G|\)，所以 \(O(\log|G|)\) 个样本以常数成功率生成整个 \(H^\perp\)；把成功率从常数提升到 \(1-\delta\) 只需再重复 \(O(\log\frac1\delta)\) 轮（标准的多数表决/重试放大）。
6.3 从 \(H^\perp\) 解出 \(H\)：Smith 标准形¶
设样本 \(y^{(1)},\ldots,y^{(t)}\) 生成了 \(H^\perp\)（这可以在经典侧随时检验：计算它们生成的子群是否稳定）。那么
第一个等号是有限 Abel 群对偶理论的标准事实（直观地说：\(H\subseteq(H^\perp)^\perp\) 由定义显然，而两者阶相等——\(|(H^\perp)^\perp|=|G|/|H^\perp|=|H|\)——故相等）。
剩下的工作是纯经典的整数线性代数。把第 \(i\) 个约束两边乘以 \(M=N_1N_2\cdots N_m\)（或各分母的最小公倍数）清除分母，得到整系数同余方程组；把 \(t\) 个样本写成矩阵的行，问题化为求这个矩阵的"模核"。标准工具是 Smith 标准形：任意整数矩阵 \(A\) 可以分解为 \(A=UDV\)，其中 \(U,V\) 是行列式 \(\pm1\) 的整数方阵（即可逆的整数行/列变换），\(D\) 是对角矩阵。可逆整数变换不改变方程组的解集结构，而对角矩阵的同余方程组可以逐行读出解。Smith 标准形有经典的多元多项式时间算法，其运行时间关于输入位数（即 \(\log|G|\)）是多项式的。求出解集的一组生成元，即为 \(H\) 的生成元。
6.4 复杂度逐项核算¶
把整条流水线的代价列清楚：
查询次数：每个样本需要一次 \(U_f\) 调用（第 4 节），共 \(O(\log|G|)\) 个样本（Lemma 2），所以量子查询次数为 \(O(\log|G|)\)。
每轮的量子电路：制备均匀叠加（逐分量 QFT/Hadamard，\(O(\log|G|)\) 个门）、一次 \(U_f\)、一次 \(F_G\)。\(F_G=F_{N_1}\otimes\cdots\otimes F_{N_m}\)，每个 \(\mathrm{QFT}_{N_j}\) 可用约 \(O((\log N_j)^2)\) 个基本门实现（本站 QFT 一课的标准构造），故每轮傅里叶部分的门数关于 \(\log|G|\) 是多项式。
经典后处理：Smith 标准形求解，关于 \(t=O(\log|G|)\) 个约束、每个约束 \(O(\log|G|)\) 比特的输入规模为多项式。
合起来：若群分解已知、群运算与各 \(\mathbb Z_{N_j}\) 的 QFT 均可高效实现，则总门复杂度关于 \(\log|G|\) 为多项式。对照经典算法的指数下界（第 1 节），这就是指数级的查询分离、以及（在 oracle 能有效实现的前提下）指数级的时间分离。第 8 节会仔细讨论这些"若"字。
7. 三个经典算法作为特例¶
现在把通式实例化。读者会看到一个统一的现象：三个算法用同一个电路，差别只在于群 \(G\) 与子群 \(H\) 的选择。
7.1 Simon 问题¶
取 \(G=\mathbb Z_2^n\)（每个 \(N_j=2\)），\(H=\{0,s\}\)。此时特征为
而 \(F_G=H^{\otimes n}\)——群 Fourier 变换就是 \(n\) 个 Hadamard。条件 \(\chi_y(s)=1\) 即
所以每次测量得到与 \(s\) 正交（\(\mathbb F_2\) 意义下）的均匀随机向量。收集 \(n-1\) 个线性无关的方程 \(y^{(i)}\cdot s=0\)，解空间就是一维的 \(\{0,s\}\)，高斯消元即得 \(s\)。由 Lemma 2（\(|H^\perp|=2^{n-1}\)，\(\log_2|H^\perp|=n-1\)），\(O(n)\) 次查询足够。
完整的小例子。取 \(n=2\)、\(s=11\)，即 \(H=\{00,11\}\)。设某轮测量输出寄存器后得到陪集态
作用 \(F_G=H^{\otimes2}\)。由 5.4 的通式，结果应为 \(\sqrt{|H|/|G|}\sum_{y\in H^\perp}\chi_y(0)|y\rangle\)，其中 \(H^\perp=\{y:y_1\oplus y_2=0\}=\{00,11\}\)，\(\sqrt{|H|/|G|}=\sqrt{2/4}=\frac1{\sqrt2}\)，故
直接验证：\(H^{\otimes2}|00\rangle=\frac12\sum_y|y\rangle\)，\(H^{\otimes2}|11\rangle=\frac12\sum_y(-1)^{y_1+y_2}|y\rangle\)，两者相加再除以 \(\sqrt2\)，\(y\in\{01,10\}\) 的项系数为 \(\frac{1}{2\sqrt2}(1-1)=0\)（相消干涉，正是 Lemma 1 的零情形），\(y\in\{00,11\}\) 的项系数为 \(\frac{1}{2\sqrt2}(1+1)=\frac1{\sqrt2}\)。测量以各 \(1/2\) 的概率得到 \(00\) 或 \(11\)；其中 \(11\) 给出约束 \(s_1\oplus s_2=0\)，与平凡样本 \(00\) 一起（或再抽到一个非平凡样本）即定出 \(s=11\)。整个 Simon 算法就是"重复 \(O(n)\) 次这个两轮电路，然后做 \(\mathbb F_2\) 上的高斯消元"。
7.2 阶与周期查找¶
Shor 分解算法的核心是对 \(f(x)=a^x\bmod N\) 求周期 \(r\)（\(a\) 与 \(N\) 互素）。在 HSP 语言中：\(f(x)=f(x')\) 当且仅当 \(x-x'\) 是 \(r\) 的倍数，即隐藏子群是 \(r\mathbb Z\le\mathbb Z\)。
这里有一个框架外的小麻烦：\(\mathbb Z\) 是无限群，不能直接放进有限寄存器。Shor 的处理是取一个足够大的 \(Q\)（2 的幂），在 \(\mathbb Z_Q\) 上计算：把 \(x\in\{0,\ldots,Q-1\}\) 上的函数 \(a^x\bmod N\) 当作"被截断的周期函数"。截断带来两个后果，都需要说明为什么无害：
陪集大小不再整齐。完整陪集有 \(\lfloor Q/r\rfloor\) 或 \(\lceil Q/r\rceil\) 个元素，不再是严格的等权叠加。但只要 \(Q\gg r\)（实际取 \(Q\approx N^2>r^2\)），每个陪集态仍然"近似均匀"，第 5.2 节的推导近似成立。
Fourier 峰不再精确落在格点上。理想情形下谱应集中在 \(Q/r\) 的整数倍处；有限 \(Q\) 下，测量值 \(k\) 以高概率落在某个峰附近，满足
对某个 \(j\in\{0,\ldots,r-1\}\) 成立。这正是"近似 Fourier 采样"的含义。
最后一步是纯经典的连分数算法：有理数逼近理论说，若 \(|\alpha-j/r|<1/(2r^2)\)，则 \(j/r\) 必出现在 \(\alpha\) 的连分数展开的渐近分数中。取 \(Q\ge 2r^2\)（由 \(r<N\)，\(Q\approx N^2\) 足够），误差 \(1/(2Q)\le1/(4r^2)<1/(2r^2)\) 满足条件，于是从 \(k/Q\) 的连分数中可以逐个检验出候选的 \(j/r\)，从而恢复 \(r\)（若 \(\gcd(j,r)=1\)，分母直接给出 \(r\)；否则少量重复即可）。连分数展开只需 \(O((\log Q)^3)\) 量级的经典运算。
要点：周期查找不是严格意义下的有限群 HSP，而是它的"连续化/截断版"。这解释了为什么它的分析比 Simon 多一步连分数——也解释了为什么第 8 节要说，承诺一旦放宽，傅里叶峰的稳健性必须重新论证。
7.3 离散对数¶
设 \(g\) 生成阶为 \(r\) 的循环群，\(h=g^s\)，求 \(s\)。把它包装成 HSP 需要一个技巧：定义二元函数
由循环群中的指数运算法则，第二个等号成立。现在验证 \(f\) 满足 HSP 承诺：
令 \(t=y-y'\)，则 \(x-x'\equiv-st\)，即差向量 \((x-x',\,y-y')=(-st,\,t)\)。所以隐藏子群为
由单个元素 \((-s,1)\) 生成——而求出这个生成元就求出了 \(s\)。
套用通式。\(G=\mathbb Z_r^2\) 的特征为 \(\chi_{(u,v)}(x,y)=e^{2\pi i(ux+vy)/r}\)，Fourier 样本 \((u,v)\) 满足
从样本解出 \(s\)。若抽到的样本中 \(u\) 在模 \(r\) 下可逆（\(\gcd(u,r)=1\)），两边乘以 \(u^{-1}\) 立即得到
一次成功。若 \(u\) 不可逆（\(r\) 为素数时只有 \(u=0\) 一种退化情形；\(r\) 合数时稍多），方程 \(us\equiv v\pmod r\) 有多个解，此时收集若干样本联立，用与第 6.3 节相同的线性同余方法联合处理，仍然可以钉住 \(s\)。由于样本在 \(H^\perp\) 上均匀，抽到"好用"样本的概率是常数级，期望 \(O(1)\) 轮即可。
数值小例子。取模 \(7\) 的原根 \(g=3\)，其阶 \(r=6\)（\(3^1=3,\,3^2=2,\,3^3=6,\,3^4=4,\,3^5=5,\,3^6=1\)）。设 \(h=5=3^5\)，即 \(s=5\)。则
隐藏子群 \(H=\langle(-5,1)\rangle=\langle(1,1)\rangle=\{(0,0),(1,1),\ldots,(5,5)\}\)（注意 \(-5\equiv1\pmod6\)）。Fourier 样本 \((u,v)\) 满足 \(-5u+v\equiv0\pmod6\)，即 \(v\equiv5u\pmod6\)。
测到 \((u,v)=(1,5)\)：\(u=1\) 可逆，\(s=v u^{-1}=5\)。直接命中。
测到 \((u,v)=(5,1)\)：\(5\cdot5=25\equiv1\pmod6\)，故 \(u^{-1}=5\)，\(s=1\cdot5=5\)。同样命中。
测到 \((u,v)=(2,4)\)：\(u=2\) 在模 \(6\) 下不可逆。方程 \(2s\equiv4\pmod6\) 的解为 \(s\in\{2,5\}\)（两边约去 \(\gcd(2,6)=2\)：\(s\equiv2\pmod3\)）。单此一样本不能定解；再与 \((1,5)\) 或 \((5,1)\) 联立即得 \(s=5\)。这就是"其余样本由线性同余联合处理"的具体含义。
7.4 对照表¶
算法 |
群 \(G\) |
隐藏子群 \(H\) |
样本约束 |
经典后处理 |
|---|---|---|---|---|
Simon |
\(\mathbb Z_2^n\) |
\(\{0,s\}\) |
\(y\cdot s=0\ (\mathrm{mod}\ 2)\) |
\(\mathbb F_2\) 高斯消元 |
周期查找 |
\(\mathbb Z_Q\)（\(\mathbb Z\) 的截断） |
\(r\mathbb Z\)（近似） |
\(k/Q\approx j/r\) |
连分数 |
离散对数 |
\(\mathbb Z_r^2\) |
\(\langle(-s,1)\rangle\) |
\(-su+v\equiv0\ (\mathrm{mod}\ r)\) |
模 \(r\) 求逆 / 联立同余 |
量子部分——均匀叠加、一次查询、傅里叶变换、测量——三者完全相同。
8. 承诺放宽与复杂度边界¶
本节把所有"免责条款"集中讲清楚。它们不是细节，而是理解"量子优势到底意味着什么"所必需的。
一次查询够吗？ 某些 HSP 变体只需一次查询即可产生足够信息——de Beaudrap、Cleve 与 Watrous（Zoo 编号 30）证明了对适当构造的问题，一次量子查询就能达到经典算法需要指数多次查询才能达到的效果，即精确的查询复杂度分离。但一般 Abel HSP 的算法使用对数多个陪集态（Lemma 2 的 \(O(\log|G|)\) 个样本），这不是缺陷而是常态：单个样本只给出一条约束，必须积累 \(\Omega(\log|H^\perp|)\) 条才能生成 \(H^\perp\)。
承诺不严格时会发生什么？ 第 2 节强调过"当且仅当"承诺的重要性。若 \(f\) 不是严格一一标记陪集——例如：
\(f\) 只是近似周期（在少量输入上破坏周期性）；
只能观察到 \(f(x)\) 的最高若干位（低位被截断）；
\(f\) 在小区间内多对一（碰撞不完全对齐陪集）；
那么第 5.3 节的特征正交关系不再严格成立：原本应为零的振幅会获得小的非零值，Fourier 峰会被"噪声底"包围。此时不能直接套用理想承诺下的结论，必须重新证明信号峰没有被噪声淹没——即峰值处的概率仍然以多项式因子压倒背景。Hales 与 Hallgren（Zoo 编号 388）发展了处理这类情形的改进 Fourier 采样技术，Shparlinski 与 Winterhof（Zoo 编号 389）研究了近似周期序列的周期重构。定性地说：只要"坏输入"的比例足够小、或泄露的信息足够多，算法仍然工作，但每个放宽都需要单独的稳健性分析。
"指数加速"的准确含义。本课证明的指数分离是 oracle 查询模型下的：经典算法最坏情形需指数多次查询才能发现碰撞，量子算法只需 \(O(\log|G|)\) 次。要把它升级为时间复杂度的分离，需要额外假设全部成立：
oracle \(U_f\) 可以被高效地相干实现（对 Shor 算法成立：模幂有经典多项式时间算法，故可做成多项式大小的可逆电路；对抽象黑盒这只是假设）；
群分解已知（第 2 节把 \(G\) 写成循环群直积是分析的起点，若分解本身难求，需另计代价）；
各 \(\mathbb Z_{N_j}\) 的 QFT 与群运算可高效实现（对标准表示成立）。
若这些条件不满足，完整运行时间可能包含远超查询次数的额外代价。本章下一课将看到，非 Abel 情形甚至会出现"查询是多项式、总时间仍指数"的明显分离：陪集态制备与弱 Fourier 采样都高效，但从测量统计中提取子群信息的经典/量子后处理可能困难。Abel 情形之所以"干净"，正是因为第 6.3 节的后处理只是线性代数。
9. 小结¶
本课的推导链可以浓缩为四句：
函数查询产生随机陪集态：一次 \(U_f\) 调用加（可选的）输出测量，把第一寄存器制备为 \(|g+H\rangle\)，\(g\) 均匀随机。
Abelian QFT 将陪集平移不变性变为 \(H^\perp\) 上的支撑：特征正交关系（Lemma 1）消灭了所有 \(y\notin H^\perp\) 的振幅，相位 \(\chi_y(g)\) 在测量时消失，样本分布与陪集无关。
多个 Fourier 样本给出同余方程：\(O(\log|G|)\) 个均匀样本以常数概率生成 \(H^\perp\)（Lemma 2），Smith 标准形恢复 \(H=(H^\perp)^\perp\)。
Simon、Shor 周期查找和离散对数只是群与子群选择不同：电路相同，后处理分别为高斯消元、连分数、模求逆。
练习题¶
练习 1【HSP 统一框架】（→ 1 节）
基础：分别写出 Simon 问题、周期查找与离散对数所对应的群 \(G\) 与隐藏子群 \(H\)。
进阶：解释经典随机算法求解 Simon 问题为什么需要 \(\Omega(2^{n/2})\) 次查询，而 HSP 框架下的量子算法只需 \(O(\log|G|)\) 次查询。
提示：经典算法只能逐点查询、等待碰撞，而一次碰撞 \(f(x)=f(y)\) 恰好泄露 \(s=x\oplus y\)；生日悖论说明约 \(2^{n/2}\) 次查询之前碰到碰撞的概率很小。
练习 2【问题定义与输入承诺】（→ 2 节）
基础：写出隐藏子群问题的承诺条件，并说明它把 \(G\) 划分成多少个陪集、每个陪集含多少个元素。
进阶：举例说明若承诺的"\(\Longrightarrow\)"方向失效（两个不同陪集取相同的函数值），测量输出寄存器后第一寄存器将坍缩成什么态，为什么第 5 节的傅里叶分析不再成立。
进阶：解释为什么"输出 \(H\) 的一组生成元"是合理的目标——有限 Abel 群的子群可以由多少个元素生成？
提示：两个陪集给出同一函数值时，测量后第一寄存器是两个陪集叠加的和，不再是任何单个陪集态；生成元个数可用"每添一个不在已有子群中的元素、生成子群的阶至少翻倍"论证。
练习 3【陪集态制备】（→ 4 节）
基础：从 \(|0\rangle|0\rangle\) 出发，写出经均匀叠加、一次 \(U_f\) 查询与输出测量后第一寄存器的态，并计算测得任一特定函数值的概率。
进阶：解释测量第二寄存器与直接丢弃它为什么给出相同的第一寄存器统计。
提示：把查询后的全局态按 \(f\) 的取值分块，写出丢弃第二寄存器后的密度矩阵，利用"不同陪集的函数值不同"说明各块之间无相干项。
练习 4【特征与群上的 QFT】（→ 5.1 节）
基础：写出乘积群 \(G=\mathbb Z_{N_1}\times\cdots\times\mathbb Z_{N_m}\) 上特征 \(\chi_y(x)\) 的定义，并验证 \(\chi_y(x+x')=\chi_y(x)\chi_y(x')\) 与 \(\chi_{y+y'}(x)=\chi_y(x)\chi_{y'}(x)\)。
进阶：证明 \(F_G=F_{N_1}\otimes\cdots\otimes F_{N_m}\)，并据此说明 \(\mathbb Z_2^n\) 上的群 QFT 就是 \(H^{\otimes n}\)。
提示：总体相位因子 \(\chi_y(x)\) 恰是各分量相位因子的乘积，求和 \(\sum_y\) 也按分量分解；\(N_j=2\) 时相位因子只有 \(\pm1\)。
练习 5【特征正交关系】（→ 5.3 节）
基础：对 \(G=\mathbb Z_{12}\)、\(H=\langle4\rangle\)、\(y=1\)，直接计算 \(\sum_{h\in H}\chi_1(h)\)，并说明三个相位为何恰好相消。
进阶：用"错位相消"完整证明 Lemma 1 的零情形，并说明当 \(G=\mathbb Z_N\)、\(H=G\) 时它退化为哪个熟悉的恒等式。
提示：映射 \(h\mapsto h+h_0\) 是 \(H\) 到自身的双射，故对 \(h\) 求和与对 \(h+h_0\) 求和是同一个和。
练习 6【正交补与均匀采样】（→ 5.4 节）
基础：解释为什么 QFT 后测量结果只能落在 \(H^\perp\) 中、且每个 \(y\in H^\perp\) 以相同概率 \(1/|H^\perp|\) 出现，而陪集代表元 \(g\) 不影响分布。
进阶：证明 \(|H||H^\perp|=|G|\)。
进阶：对 \(G=\mathbb Z_{12}\)、\(H=\langle4\rangle\) 写出全部 \(H^\perp\)，并对陪集 \(2+H\) 完整算出 \(F_{12}|2+H\rangle\) 与测量分布（可对照第 5.5 节自检）。
提示：考虑映射 \(G\to\{H\ \text{上的特征}\}\)，\(y\mapsto\chi_y|_H\)。证明它是满同态——有限 Abel 群上子群的特征总能延拓到全群——其核正是 \(H^\perp\)，再用同态基本定理与"\(H\) 的特征恰有 \(|H|\) 个"。
练习 7【从 Fourier 样本恢复子群】（→ 6 节）
基础：把样本 \(y\) 写成关于未知 \(h\in H\) 的线性同余约束；对 \(G=\mathbb Z_{12}\)、测得 \(y=3\) 的情形写出该约束，并求出它允许的 \(h\) 的集合。
进阶：第 6.2 节证明了期望 \(2\log_2|H^\perp|\) 个样本生成 \(H^\perp\)。用 Markov 不等式给出"以至少 \(3/4\) 的概率成功"所需样本数的显式上界，并说明如何以 \(O(\log\frac1\delta)\) 的额外重复把失败率压到 \(\delta\) 以下。
提示：对非负随机变量用 \(\Pr[X\ge a]\le E[X]/a\)，取 \(a\) 为期望的 \(4\) 倍；把整轮算法独立重复 \(O(\log\frac1\delta)\) 次即可放大成功率。
练习 8【三个经典算法的实例化】（→ 7 节）
基础：对照第 7.4 节的表格，写出 Simon、周期查找与离散对数各自的群 \(G\)、隐藏子群 \(H\)、样本约束与经典后处理方法。
进阶：从 \(f(x,y)=g^{x+sy}\) 推导离散对数样本方程 \(-su+v\equiv0\pmod r\)，并对第 7.3 节的例子（\(g=3\)、\(r=6\)、\(s=5\)）验证 \((u,v)=(3,3)\) 是合法样本；这个样本能否单独定出 \(s\)？为什么？
进阶：在 Simon 问题中取 \(n=3\)、\(s=110\)。写出 \(H^\perp\) 的全部元素；设两轮采样分别得到 \(y^{(1)}=001\) 与 \(y^{(2)}=111\)，验证它们给出的方程组的解空间恰为 \(\{000,110\}\)；再计算若第三轮得到 \(y^{(3)}=001\)，是否仍有足够信息确定 \(s\)。
提示：把样本方程 \(-su+v\equiv0\pmod r\)、\(y\cdot s=0\pmod2\) 分别代入具体数值，逐个解同余方程与线性方程组。
参考文献¶
Zoo 编号 14：D. Boneh 与 R. Lipton, Quantum Cryptanalysis of Hidden Linear Functions, CRYPTO 1995。
Zoo 编号 108：Daniel Simon, On the Power of Quantum Computation, FOCS 1994。
Zoo 编号 76：Michael Nielsen 与 Isaac Chuang, Quantum Computation and Quantum Information, 第 5 章。
Zoo 编号 30：J. Niel de Beaudrap、Richard Cleve 与 John Watrous, Sharp Quantum versus Classical Query Complexity Separations.
Zoo 编号 388：Lisa Hales 与 Sean Hallgren, An Improved Quantum Fourier Transform Algorithm and Applications, FOCS 2000。
Zoo 编号 389：Igor Shparlinski 与 Arne Winterhof, Quantum Period Reconstruction of Approximate Sequences, IPL 2007。