黑盒群的阶与成员关系

Shor 算法解决的是整数乘法群里一个元素的阶；本词条把它推广到最一般的有限群计算模型——黑盒群 (black-box group)。在黑盒群模型中，群元素只是不透明的比特串标签，我们唯一能做的事情是调用乘法与求逆 oracle：连”这个群有多少个元素""某个标签是否落在给定子群里”这类最基本的问题，经典算法都可能需要指数次查询。量子算法的关键原语是均匀子群态 $|H⟩$：一旦能制备它，元素 $g$ 在商结构中的阶就表现为陪集态序列 $|H⟩,|gH⟩,|g^{2}H⟩,\dots$ 的周期，而周期正是量子傅里叶变换最擅长读取的信息。Mosca 在其博士论文中把这一思路纳入隐藏子群问题框架，Watrous 则进一步沿可解群的循环因子逐层扩张均匀态，给出了可解黑盒群的群阶、成员判定、子群相等与正规性测试的多项式时间量子算法。

本词条的组织如下：先形式化黑盒群模型与四个核心任务，说明经典算法的瓶颈与算法史；再用 Abelian 群做热身（关系格 + Smith 标准形）；然后建立核心引理”均匀子群态把商阶变成周期”；接着解释为什么可解群恰好允许逐层执行这个操作，给出 Watrous 算法的结构；逐项分析复杂度；最后用 $S_3$ 完整手算一遍。阅读本词条前，建议先完成 Abelian 隐藏子群问题；其中用到的相位估计与连分数提取周期技术见相位估计。

1. 黑盒群模型与四个任务

1.1 输入模型

有限黑盒群 $G$ 的元素由 $n$ 比特字符串（标签）编码。注意标签总数 $2^n$ 是群阶的上界，因此

$$|G|\le 2^n,\text{即}{\log }_2|G|\le n.$$

这个不等式在后面做复杂度分析时会反复用到：以 $n$ 为参数的多项式自动是以 $\log |G|$ 为参数的多项式。

我们不掌握标签与群元素之间的任何对应规律，只能调用两个可逆 oracle：

$$|x,y⟩\mapsto |x,xy⟩,|x,y⟩\mapsto |x,x^{-1}y⟩,$$

其中 $x,y$ 是群元素的标签，第二个寄存器中的运算”乘到目标寄存器上”保证了映射是置换，从而是合法的酉操作。由于映射可逆，这两个 oracle 可以在量子叠加态上相干地执行——这是全部后续算法的基础。

问题的输入是 $k$ 个生成元 $g_1,\dots ,g_k$ 的标签。我们关心的四个典型任务是：

1. 群阶 (order)：计算 $|⟨g_1,\dots ,g_k⟩|$；
2. 成员判定 (membership)：给定标签 $x$，判断 $x$ 是否属于该子群；
3. 构造性成员 (constructive membership)：在 yes 情形给出 $x$ 的生成元乘积表达（即把 $x$ 写成 $g_i$ 及其逆的乘积）；
4. 子群比较：判断两个生成子群是否相等，或判断一个子群在另一个子群中是否正规 (normal)。

1.2 编码的唯一性

编码有两种情形，难度差别很大：

• 唯一编码 (unique encoding)：每个群元素恰好有一个标签。此时比较两个元素只需比较比特串，单位元可直接辨认。
• 非唯一编码 (non-unique encoding)：同一群元素可以有多个标签（例如矩阵的某种冗余表示）。此时标签相等不蕴含元素相等，模型必须额外提供 identity/equality oracle——给定标签判断它是否表示单位元，或判断两个标签是否表示同一元素。

复杂度一律以 $n$（标签长度）、$k$（生成元个数）和 $\log |G|$ 为参数衡量，而不把规模高达 $|G{|}^2$ 的 Cayley 表（乘法表）当作输入——如果允许读乘法表，求群阶就是平凡的，整个问题也就失去了意义。

2. 经典算法能做什么，瓶颈在哪里

2.1 为什么经典方法撞墙

给定 $k$ 个生成元，最 naive 的经典策略是从单位元出发不断用生成元右乘、记录遇到的所有标签，直到不再产生新元素——即显式枚举整个群。这需要 $\Omega (|G|)$ 步。由于 $|G|$ 可以达到 $2^n$，这是输入规模的指数，不可接受。

有没有更聪明的经典算法？对具体表示的群，答案有时是肯定的：例如置换群（$S_n$ 的子群，元素直接给成置换）有 Sims 基与强生成元理论，可以多项式时间求阶与成员。但黑盒模型故意抹掉了这些表示信息：算法只能通过 oracle 与群交互。Babai 与 Szemerédi 在引入黑盒群模型时就已经指出其固有的困难：在非唯一编码下，连”这个标签是否表示单位元”都可能无法有效判定；对一般的黑盒群，群阶与成员判定对经典（即使随机化）算法存在指数级查询下界。直觉上的原因是：经典算法每调用一次乘法 oracle 只能得到一个新标签，信息以加法速度积累；而 $k$ 个生成元生成的群却可能以乘法速度膨胀——没有可资利用的结构时，经典算法无法在多项式次查询内区分”群已经探索完了”和”还有一大片没碰到”。

量子算法绕开这堵墙的方式与 Shor 算法一脉相承：不是逐个收集元素，而是制备全体元素的均匀叠加，再用傅里叶变换从干涉图样中读出整体性的不变量（周期、阶）。单个标签你永远看不完，但叠加态的相位结构多项式次查询就能探明。

2.2 算法史

• Mosca（1999，Zoo 编号 74）：其博士论文 Quantum Computer Algorithms 系统地把 Simon、Shor 的算法统一为隐藏子群问题（HSP），并将 HSP 方法应用于黑盒群计算，给出了 Abelian 黑盒群的多项式量子算法。
• Watrous（2000，Zoo 编号 91）：在 Quantum Algorithms for Solvable Groups 中，Watrous 把适用面从 Abelian 群推进到可解群：对可解黑盒群，群阶、成员判定、构造性成员、子群相等与正规性测试都有 $\mathrm{poly}(n,k,\log |G|)$ 时间的量子算法。核心技巧就是本词条的主线——沿循环因子逐层制备均匀子群态，把每一层的商阶转化为周期查找。
• Babai–Beals–Seress（STOC 2009，Zoo 编号 124）：对矩阵群（元素显式给成有限域上的矩阵，而非黑盒标签），把经典矩阵群结构理论与量子因数分解、离散对数子程序结合，在更广的参数范围内解决群阶与构造性成员问题。

这三个结果的关系是：Mosca 建立了”HSP 解决群计算”的范式，Watrous 在黑盒模型内把范式推到可解群的边界，Babai–Beals–Seress 则跳出黑盒模型、利用矩阵表示的显式结构走得更远。本词条重点是 Watrous 的结果。

3. 核心直觉：把”商群里的阶”翻译成”态序列的周期”

在正式进入推导之前，先用平实语言把整个算法想做什么讲清楚。

回忆 Shor 求阶：给定元素 $g$，函数 $a\mapsto g^a$ 是周期的，周期就是 $g$ 的阶 $r$；把叠加 ${\sum }_a|a⟩|g^a⟩$ 制备出来，对第一个寄存器做 QFT，干涉相消后只有满足”$cr$ 接近 $M$ 的整数倍”的频率 $c$ 存活，于是 $r$ 被读了出来。整个技巧成立的前提是：序列 $|g^a⟩$ 只依赖 $a\mathrm{mod}r$，且不同剩余类给出正交的态——这样第二个寄存器才能把第一个寄存器”筛”成等差数列。

现在把单元素生成的循环群 $⟨g⟩$ 换成”子群 $H$ 再添一个元素 $g$“。自然的类比对象是陪集序列

$$H,gH,g^{2}H,\dots$$

设 $r$ 是使 $g^r$ 回到 $H$ 的最小正整数。那么陪集序列从第 $r$ 项起重复：$g^{r}H=H$，$g^{r+1}H=gH$，依此类推。换句话说，$a\mapsto g^{a}H$ 是以 $r$ 为周期的函数，而 $r$ 正是 $gH$ 在商群中的阶。如果我们能把每个陪集 $g^{a}H$ 替换成一个量子态 $|g^{a}H⟩$，并且保证不同陪集对应正交态，那么 Shor 的周期查找机器可以原封不动地搬过来，读出的周期乘以 $|H|$ 就是新群 $⟨H,g⟩$ 的阶。

哪个量子态能”代表”陪集且自动满足上述要求？答案是均匀子群态

$$|H⟩=\frac{1}{\sqrt{|H|}}\sum _{h\in H}|h⟩.$$

它有一条决定一切的性质：对任意 $h^{\prime }\in H$，右乘 $h^{\prime }$ 只是把求和中的各项重新排列，因此

$$|H{h}^{\prime }⟩=\frac{1}{\sqrt{|H|}}\sum _{h\in H}|h{h}^{\prime }⟩=|H⟩.$$

也就是说，这个态无法区分 $H$ 内部的元素——$H$ 内部的右乘作用在它上面是恒等的。它唯一能”看见”的信息是陪集本身。这正是我们想要的：一个把商结构（而不是群内部细节）编码进量子态的数据结构。不同陪集作为集合互不相交，所以对应态的支撑集不交，自动正交。于是”商群里的阶 $=$ 态序列的周期”这条翻译就完成了。

剩下的问题只有一个：怎样从 $|H⟩$ 出发制备 $|⟨H,g⟩⟩$，从而把构造逐层推进下去？这一步对一般群做不到，但 Watrous 发现：可解群的正规列恰好提供了一座塔，塔的第 $j$ 层到第 $j+1$ 层恰好是”添一个元素”的形状，于是上述原语可以从 $\{e\}$ 开始逐层执行，直到塔顶 $G$。

4. 热身：Abelian 群由关系格完全决定

先看 Abelian 情形。它是 Abelian 隐藏子群问题 的直接应用，也为后面一般情形提供了”关系数据”的样板。

4.1 第一步：求每个生成元的阶

对每个生成元 $g_i$，函数 $a\mapsto g_i^a$ 在 $\mathbb{Z}$ 上以 $g_i$ 的阶 $r_i$ 为周期，且一个周期内 $g_i^a$ 互不相同（否则阶更小）。这正是 Shor 求阶问题的形状：制备

$$\frac{1}{\sqrt{M}}\sum _{a=0}^{M-1}|a⟩|g_i^a⟩,$$

对第一寄存器做 QFT 并测量，用连分数从测量结果中提取 $r_i$。每个 $r_i$ 的代价是关于 $n$ 的多项式（详见第 7 节的精度分析），$k$ 个生成元共 $k$ 次。

4.2 第二步：关系映射与它的核

定义映射

$$\Phi :{\mathbb{Z}}_{r_1}\times \cdots \times {\mathbb{Z}}_{r_k}\to G,(a_1,\dots ,a_k)\mapsto g_1^{a_1}\cdots g_k^{a_k}.$$

由于 $g_1,\dots ,g_k$ 生成 $G$，$\Phi$ 是满射：每个群元素至少有一个指数向量作为原像。当 $G$ 是 Abelian 群时，$\Phi$ 还是群同态——直接验证：对 $a=(a_1,\dots ,a_k)$、$b=(b_1,\dots ,b_k)$，

$$\Phi (a+b)=\prod _i{g}_i^{a_i+b_i}=\prod _i{g}_i^{a_i}\prod _i{g}_i^{b_i}=\Phi (a)\Phi (b),$$

其中第二个等号把所有 $g_i^{a_i}$ 归拢到左边、$g_i^{b_i}$ 归拢到右边，这一步用到了元素两两交换；对非交换群该等式一般不成立，这就是”关系格”方法限于 Abelian 群的根本原因。

同态基本定理给出

$$G\cong ({\mathbb{Z}}_{r_1}\times \cdots \times {\mathbb{Z}}_{r_k})/\ker \Phi ,$$

所以 $G$ 的全部结构信息都装在核

$$K=\ker \Phi =\left\{(a_1,\dots ,a_k):g_1^{a_1}\cdots g_k^{a_k}=e\right\}$$

里。$K$ 的元素称为生成元之间的关系 (relations)；它是自由 Abel 群的子格，称为关系格 (relation lattice)。例如 $(r_1,0,\dots ,0)\in K$ 是一条平凡关系（$g_1^{r_1}=e$），但还可能有混合关系，如 $g_1^2{g}_2^3=e$。

4.3 第三步：用 Abelian HSP 求出关系格

考虑函数

$$f:{\mathbb{Z}}_{r_1}\times \cdots \times {\mathbb{Z}}_{r_k}\to \{\text{标签}\},f(a)=\text{“}\Phi (a)\text{ 的标签”}.$$

它满足 $f(a)=f(b)⟺\Phi (a)=\Phi (b)⟺a-b\in K$（同态性质：$\Phi (a)\Phi (b{)}^{-1}=\Phi (a-b)$）。也就是说 $f$ 恰好隐藏子群 $K$：它在 $K$ 的每个陪集上取常值，在不同陪集上取不同值（后一点用到唯一编码；非唯一编码时需借助 equality oracle 把”标签”换成”等价类”，结论不变）。这正是 Abelian 隐藏子群问题的标准输入。套用该算法（傅里叶采样得到与 $K$ 正交的关系，重复采样后用整数线性代数求交），我们得到 $K$ 的一组生成元，写成关系矩阵 $R$。细节见 Abelian 隐藏子群问题。

4.4 第四步：Smith 标准形读出群结构与群阶

把关系矩阵 $R$（列是 $K$ 的生成元）做 Smith 标准形 (Smith normal form)：存在行列式为 $\pm 1$ 的整数矩阵（幺模矩阵）$U,V$，使

$$URV=\mathrm{diag}(d_1,d_2,\dots ,d_t),d_1\mid d_2\mid \cdots \mid d_t,$$

其中 $d_1\mid d_2$ 表示 $d_1$ 整除 $d_2$。幺模变换对应”换一组生成元”和”换一组关系基底”，不改变商群，因此

$$G\cong {\mathbb{Z}}_{d_1}\times \cdots \times {\mathbb{Z}}_{d_t},|G|=\prod _{j=1}^t{d}_j.$$

这就是有限生成 Abel 群的基本定理在黑盒模型下的有效版本：群阶是 Smith 标准形对角元之积，整个分解被多项式时间地算了出来。

4.5 成员判定与构造性表达

给定新元素 $x$，判定 $x\in G$ 的方法朴素而有效：把 $x$ 加入生成集，对 $\{g_1,\dots ,g_k,x\}$ 重新走一遍上面的流程，得到 $|⟨G,x⟩|$，与原群阶比较：

$$x\in G⟺⟨G,x⟩=G⟺|⟨G,x⟩|=|G|.$$

第一个等价是成员关系的定义；第二个等价是因为 $⟨G,x⟩\supseteq G$ 而有限群的子群与原群等阶当且仅当相等。若比较结果阶不变，则 $x\in G$；若阶严格增大，则 $x\notin G$。

此外，在执行 Smith 标准形时保留变换矩阵 $U,V$（即记录下每步行列操作），就能把”$x$ 对应的关系”反解成原生成元的幂乘积，从而把 yes 情形升级为 constructive membership：不仅知道 $x\in G$，还知道 $x$ 具体等于哪个生成元字。

5. 子群均匀态：正交性与隐藏周期

现在离开 Abelian 世界，建立对任意群都成立的核心工具。本节所有结论都不需要 $G$ 交换，但需要子群的正规性条件。

5.1 陪集态的定义与正交性

对有限群 $G$ 的子群 $H$，定义均匀子群态

$$|H⟩=\frac{1}{\sqrt{|H|}}\sum _{h\in H}|h⟩,$$

以及对任意 $g\in G$ 的陪集态 (coset state)

$$|gH⟩=\frac{1}{\sqrt{|H|}}\sum _{h\in H}|gh⟩.$$

它是对 $|H⟩$ 施加左乘 $g$ 的酉变换（即把乘法 oracle 以 $g$ 为控制输入）得到的，因此只要会制备 $|H⟩$ 并调用 oracle，就会制备 $|gH⟩$。

Lemma 1（陪集态的正交性）。对任意 $g_1,g_2\in G$：

• 若 $g_{1}H=g_{2}H$（同一陪集），则 $|g_{1}H⟩=|g_{2}H⟩$；
• 若 $g_{1}H\ne g_{2}H$（不同陪集），则 $⟨g_{1}H|g_{2}H⟩=0$。

特别地，$|gH⟩$ 只依赖陪集 $gH$ 而不依赖代表元 $g$ 的选取。

证明。第一部分：$g_{1}H=g_{2}H$ 意味着两个求和 ${\sum }_{h\in H}|g_{1}h⟩$ 与 ${\sum }_{h\in H}|g_{2}h⟩$ 跑遍同一个集合，只是加项次序不同，故两态相等。

第二部分：群论的基本事实是两个不同的左陪集作为集合不相交（若 $x\in g_{1}H\cap g_{2}H$，写 $x=g_1{h}_1=g_2{h}_2$，则 $g_{1}H=g_2{h}_2{h}_1^{-1}H=g_{2}H$）。于是 $\{|g_{1}h⟩{\}}_{h\in H}$ 与 $\{|g_{2}h⟩{\}}_{h\in H}$ 是两组互不相同的计算基矢，内积

$$⟨g_{1}H|g_{2}H⟩=\frac{1}{|H|}\sum _{h_1,h_2\in H}⟨g_1{h}_1|g_2{h}_2⟩=\frac{1}{|H|}\sum _{h_1,h_2\in H}0=0,$$

因为每个克罗内克内积 $⟨g_1{h}_1|g_2{h}_2⟩$ 的两个基矢都落在不相交的集合里。Q.E.D.

这个引理是整篇论文的支点：陪集空间 $\{gH\}$ 被等距嵌入到希尔伯特空间中成为一组正交归一态，商结构上的任何算术都自动变成正交态序列上的算术。

5.2 正规性：让”陪集序列的周期”等于”商群元素的阶”

设 $g\in G$，定义

$$r=\min \{a>0:g^a\in H\},$$

即 $g$ 的幂首次落回 $H$ 的指数（这样的 $a$ 总存在，因为 $g$ 的阶有限，而 $g$ 的阶次幂等于 $e\in H$）。由陪集相等的判据 $g^{a}H=g^{b}H⟺g^{a-b}\in H$，序列

$$|H⟩,|gH⟩,|g^{2}H⟩,\dots$$

恰好以 $r$ 为最小周期循环：前 $r$ 项两两正交（Lemma 1），且

$$|g^{a+r}H⟩=|g^{a}H⟩,$$

因为 $g^{a+r}H=g^a(g^{r}H)=g^{a}H$（用到 $g^r\in H\Rightarrow g^{r}H=H$）。

现在引入关键的结构条件

$$H⊴⟨H,g⟩,$$

即 $H$ 在由 $H$ 与 $g$ 共同生成的群中是正规子群。它的作用是双重的：

1. 陪集乘法良定义。正规性 $gH=Hg$ 保证 $g^{a}H\cdot g^{b}H=g^a(H{g}^b)H=g^a(g^{b}H)H=g^{a+b}H,$ 即陪集可以像商群元素一样相乘，$\{g^{a}H{\}}_{a=0}^{r-1}$ 在陪集乘法下封闭，构成一个 $r$ 阶循环群——正是商群 $⟨H,g⟩/H$。于是 $r$ 有一个干净的群论身份：$r$ 是 $gH$ 在商群 $⟨H,g⟩/H$ 中的阶。
2. 计数公式。下面的定理说明此时新群的阶就是旧群阶乘以 $r$。

若 $H$ 不正规，这两点都可能失败：陪集乘法不再良定义，$\{g^{a}H\}$ 的并未必是子群，$r|H|$ 也可以不等于 $|⟨H,g⟩|$（习题 4、5 给出一个 $S_3$ 中的具体反例）。这就是 Watrous 算法要求正规列、而不只是任意子群链的原因。

Theorem 2（逐层计数公式）。若 $H⊴⟨H,g⟩$ 且 $r=\min \{a>0:g^a\in H\}$，则

$$⟨H,g⟩=\underset{a=0}{\overset{r-1}{⨆}}{g}^{a}H\text{（无交并）},|⟨H,g⟩|=r|H|.$$

证明。记 $K_0={\bigcup }_{a=0}^{r-1}{g}^{a}H$。分三步。

第一步，$K_0$ 对乘法封闭。任取 $g^a{h}_1,g^b{h}_2\in K_0$（$0\le a,b\le r-1$）：

$$(g^a{h}_1)(g^b{h}_2)=g^a(h_1{g}^b)h_2=g^a(g^b{h}_1^{\prime })h_2=g^{a+b}{h}_1^{\prime }{h}_2,$$

其中第二个等号用了正规性 $H{g}^b=g^{b}H$，故 $h_1{g}^b=g^b{h}_1^{\prime }$ 对某个 $h_1^{\prime }\in H$ 成立。把 $a+b$ 模 $r$ 约化：写 $a+b=qr+s$（$0\le s\le r-1$），则

$$g^{a+b}=g^s{g}^{qr}=g^s(g^r{)}^q,$$

而 $g^r\in H$ 蕴含 $(g^r{)}^q\in H$，所以 $g^{a+b}{h}_1^{\prime }{h}_2\in g^{s}H\subseteq K_0$。

第二步，$K_0$ 对求逆封闭：$(g^{a}h{)}^{-1}=h^{-1}{g}^{-a}$；由正规性 $h^{-1}{g}^{-a}=g^{-a}{h}^{\prime \prime }$（某个 $h^{\prime \prime }\in H$），再把 $-a$ 模 $r$ 约化并用 $g^r\in H$ 吸收，同第一步得逆元落在 $K_0$ 中。

第三步，比较大小。第一、二步说明 $K_0$ 是含 $H$ 与 $g$ 的子群，故 $⟨H,g⟩\subseteq K_0$；反之每个 $g^{a}H\subseteq ⟨H,g⟩$，故 $K_0\subseteq ⟨H,g⟩$。于是 $K_0=⟨H,g⟩$。不同 $a\in \{0,\dots ,r-1\}$ 给出的陪集两两不同（否则 $g^{a-b}\in H$ 且 $0<|a-b|<r$，与 $r$ 的最小性矛盾），每个陪集恰含 $|H|$ 个元素，无交并计数即得 $|⟨H,g⟩|=r|H|$。Q.E.D.

5.3 周期查找电路：把 $r$ 读出来

假设已经能制备 $|H⟩$（如何实现是下一节的主题，本节把它当作原语）。取整数 $M$（选取标准见第 7 节），制备均匀叠加并受控地做 $a$ 次左乘 $g$：

$$|0⟩|H⟩\stackrel{{\mathrm{QFT}}_M\text{ 于第一寄存器}}{\to }\frac{1}{\sqrt{M}}\sum _{a=0}^{M-1}|a⟩|H⟩\stackrel{\text{受控乘 }{g}^a}{\to }\frac{1}{\sqrt{M}}\sum _{a=0}^{M-1}|a⟩|g^{a}H⟩.$$

其中受控乘 $g^a$ 用 repeated squaring 实现：把 $a$ 的二进制位作为控制位，逐位施加受控的左乘 $g^{2^j}$，共 $O(\log M)$ 次 oracle 调用。

现在测量第二寄存器。由于映射 $a\mapsto g^{a}H$ 以 $r$ 为周期，每个陪集 $g^{a_0}H$（$0\le a_0\le r-1$）的原像集是等差数列 $\{a_0,a_0+r,a_0+2r,\dots \}\cap [0,M-1]$。测得该陪集态后，第一寄存器坍缩为等差数列上的均匀叠加

$$\frac{1}{\sqrt{L}}\sum _{j=0}^{L-1}|a_0+jr⟩,L=\left|\{j:0\le a_0+jr\le M-1\}\right|\approx \frac{M}{r}.$$

对第一寄存器施加 ${\mathrm{QFT}}_M$，记 ${\omega }_M=e^{2\pi i/M}$，输出 $c$ 的振幅为

$$\frac{1}{\sqrt{LM}}\sum _{j=0}^{L-1}{\omega }_M^{c(a_0+jr)}=\frac{{\omega }_M^{c{a}_0}}{\sqrt{LM}}\sum _{j=0}^{L-1}{\omega }_M^{jrc}.$$

这是等比数列求和：$|{\sum }_j{\omega }_M^{jrc}{|}^2$ 在 $cr/M$ 接近整数时取得约 $L^2$ 的相长干涉，否则因相位旋转而相消。于是测量结果 $c$ 以高概率满足

$$\left|\frac{c}{M}-\frac{s}{r}\right|\le \frac{1}{2M}\text{对某个 }s\in \{0,1,\dots ,r-1\}.$$

这正是 Shor 算法中”频率谱集中在 $M/r$ 的整数倍附近”的标准结论：$c/M$ 是 $s/r$ 的逼近。只要 $M$ 取得足够大（使 $1/(2M)\le 1/(2r^2)$，即 $M\ge r^2$），由连分数理论，$s/r$ 是 $c/M$ 的唯一分母不超过 $r$ 的渐近分数，于是对 $c/M$ 做连分数展开即可读出既约分数 $s/r$ 的分母。重复采样若干次，各次分母的最小公倍数以高概率等于 $r$（当 $\gcd (s,r)=1$ 时一次即得；$s$ 均匀随机时该事件概率有正的下界，故 $O(1)$ 次重复足够，必要时用 $O(\log \log r)$ 次把失败率压低）。

5.4 从周期到四个任务

读出 $r$ 之后：

• 群阶：Theorem 2 给出 $|⟨H,g⟩|=r|H|$；
• 成员判定：$r=1⟺g\in H$（$r=1$ 意为 $g^1\in H$；反之 $g\in H$ 时最小正指数当然是 1）；
• 构造性成员：周期查找同时给出关系 $g^r\in H$。若我们对 $H$ 已有 constructive membership 能力（能把 $H$ 中任意元素写成生成元的字），则 $g^r$ 可被表达，递归下去就能把 $⟨H,g⟩$ 中任意元素 $g^{a}h$（$0\le a<r$，$h\in H$）写成原生成元的乘积——表达长度按层数线性增长；
• 正规性与相等测试：判断 $H⊴K$ 归结为对每个生成元 $h$ of $H$、$k$ of $K$ 判定 $k^{-1}hk\in H$，即一串成员判定；判断 $H=K$ 归结为双向的成员判定。所以这四个任务全部归约到”求商阶 $r$“这一个原语上。

6. 为什么可解群正好允许逐层做这件事

6.1 可解群与循环因子塔

有限群 $G$ 称为可解群 (solvable group)，如果存在次正规列

$$\{e\}=G_0◃G_1◃\cdots ◃G_t=G,$$

其中每个因子群 $G_{j+1}/G_j$ 都是 Abel 群。可解群的得名来自 Galois 理论：多项式方程根式可解当且仅当其 Galois 群可解。对我们重要的是它的结构性质：把列进一步细化（在每个 Abel 因子内部再插入子群），可以要求每个因子都是循环群。

与细化的列配套的是 polycyclic 生成序列 $h_1,\dots ,h_t$，满足

$$G_j=⟨h_1,\dots ,h_j⟩,G_{j-1}◃G_j(j=1,\dots ,t).$$

也就是说，塔的第 $j$ 层恰好是”在 $G_{j-1}$ 上添加一个元素 $h_j$“，且 $G_{j-1}$ 在结果中正规——这正是第 5 节原语要求的输入形状！可解性提供的不是一条普通的子群链，而是一串逐个满足正规性条件的”加一元素”步骤。这就是”可解群正好允许逐层做这件事”的准确含义；对非可解群，无法把群分解成这样的循环因子塔，逐层策略在塔的某一层就会断裂（见第 9 节）。

6.2 Watrous 算法的主循环

从 $G_0=\{e\}$（其均匀态 $|e⟩=|0\cdots 0⟩$ 的制备是平凡的）开始，对 $j=1,\dots ,t$ 重复以下四步：

1. 周期查找：用手头的 $|G_{j-1}⟩$ 对 $h_j$ 执行第 5.3 节的 coset period finding，即制备 ${\sum }_a|a⟩|h_j^a{G}_{j-1}⟩$ 并做 QFT；
2. 读出商阶：得到 $h_j{G}_{j-1}$ 在 $G_j/G_{j-1}$ 中的阶 $r_j$；
3. 合成新的均匀态：把 $r_j$ 个正交陪集态均匀叠加，制备 $$|G_j⟩=\frac{1}{\sqrt{r_j}}\sum _{a=0}^{r_j-1}|h_j^a{G}_{j-1}⟩;$$
4. 更新数据：记录 $|G_j|=r_j|G_{j-1}|$ 与关系 $h_j^{r_j}\in G_{j-1}$（配合递归的 constructive membership，维护每个元素到生成元字的翻译）。

循环结束后

$$|G|=\prod _{j=1}^t{r}_j.$$

6.3 真正的难点：相干地擦除指数寄存器

第 3 步写出形式目标

$$\frac{1}{\sqrt{r_j}}\sum _{a=0}^{r_j-1}|h_j^a{G}_{j-1}⟩$$

很容易，真正的技术困难在于：周期查找自然给出的态是**纠缠态**

$$\frac{1}{\sqrt{r_j}}\sum _{a=0}^{r_j-1}|a⟩\otimes |h_j^a{G}_{j-1}⟩,$$

第一寄存器里的指数 $a$ 必须被相干地消除 (coherent erasure)，而不能测量——一旦测量，叠加就坍缩成单个陪集态，前功尽弃。

为什么擦除在原则上是可能的？因为映射 $a\mapsto h_j^a{G}_{j-1}$ 在 $\{0,\dots ,r_j-1\}$ 上是单射（Lemma 1：不同 $a$ 给出不同陪集，从而不同正交态）。换句话说，指数 $a$ 由陪集态唯一决定，映射 $|a⟩|h_j^a{G}_{j-1}⟩\mapsto |0⟩|h_j^a{G}_{j-1}⟩$ 是一个部分等距，可以延拓成酉变换。问题在于如何高效实现这个”从陪集读出指数”的求逆——它本质上是商群 $G_j/G_{j-1}\cong {\mathbb{Z}}_{r_j}$ 上的离散对数。Watrous 的解决方案是：该商群是循环的（可解群细化列的因子），循环群上的离散对数恰好又是 Abelian Fourier 采样能解决的问题；配合**振幅放大**（见Grover 与振幅放大）把每一步制备的失败分支相干地旋转回成功分支，并用标准误差控制（各层近似误差以迹距离相加，逐层预算）保证最终产出的是近似纯的均匀态。结论性的说法是：Abelian Fourier 采样与振幅放大使每一层只需多项式资源；把这些组件逐层串起来，整条塔的总代价仍是多项式。

6.4 层数的上界

每层 $r_j\ge 2$（否则 $h_j\in G_{j-1}$，该层可以从序列中删去），而 $|G|={\prod }_j{r}_j$，所以

$$2^t\le \prod _{j=1}^t{r}_j=|G|⟹t\le {\log }_2|G|\le n.$$

塔至多 ${\log }_2|G|$ 层：多项式层的多项式代价仍是多项式。这个简单的计数论证是把”逐层”翻译成”多项式总时间”的关键一步。

7. 复杂度分析

本节逐项解释”$\mathrm{poly}(n,k,\log |G|)$ 总时间”中每个因子的来源。按约定我们不引用原论文中的具体多项式次数，只说明各因子为何出现、以及参数如何平衡。

7.1 单次周期查找的寄存器精度

第 5.3 节留下了一个参数 $M$（QFT 的模数）。选取标准来自连分数提取的唯一性条件：

$$\left|\frac{c}{M}-\frac{s}{r}\right|<\frac{1}{2r^2}\text{需要}M\ge r^2.$$

推导：两个不同的、分母都不超过 $r$ 的既约分数 $s/r^{\prime }$、$s^{\prime \prime }/r^{\prime \prime }$ 之间的距离

$$\left|\frac{s}{r^{\prime }}-\frac{s^{\prime \prime }}{r^{\prime \prime }}\right|=\frac{|s{r}^{\prime \prime }-s^{\prime \prime }{r}^{\prime }|}{r^{\prime }{r}^{\prime \prime }}\ge \frac{1}{r^{\prime }{r}^{\prime \prime }}\ge \frac{1}{r^2},$$

因为分子是非零整数、至少为 1。所以以 $1/(2r^2)$ 为半径的邻域内至多有一个这样的分数，连分数算法必能唯一锁定 $s/r$。周期查找给出的偏差上界是 $1/(2M)$，故要求 $1/(2M)\le 1/(2r^2)$ 即 $M\ge r^2$。

实现上 $r$ 未知，但 $r\le |G|\le 2^n$，因此统一取

$$M=2^{2n}\ge |G{|}^2\ge r^2$$

即可覆盖所有可能。于是第一寄存器需要 ${\log }_{2}M=2n$ 个量子比特，受控乘 $g^a$ 需要 $O(\log M)=O(n)$ 次 oracle 调用——因子 $n$ 的第一个来源。

7.2 各复杂因子的来源

• $n$（标签长度）：每个群元素寄存器占 $n$ 量子比特；QFT 寄存器 $2n$ 比特（上一条）；每次 oracle 调用作用在 $O(n)$ 比特上，其自身门代价是关于 $n$ 的多项式。
• $k$（生成元个数）：输入需要存储和处理 $k$ 个标签；成员/相等/正规性测试对生成元逐个循环，代价含因子 $k$（或 $k^2$，视任务而定，但总是多项式）。
• $\log |G|$：层数 $t\le {\log }_2|G|$（第 6.4 节）；每层内部 Fourier 采样的重复次数、误差预算的分配也都是 $\log |G|$ 的多项式。由于 $\log |G|\le n$，这些因子都可并入 $n$ 的多项式。
• 振幅放大的平方根开销：第 6.3 节中每步相干制备若单轮成功概率为 $p$，振幅放大把重复次数从 $O(1/p)$ 降到 $O(1/\sqrt{p})$；对本词条的各步，$p$ 是常数级的（不随 $n$ 指数缩小），故只贡献常数倍的层内开销。
• 成功概率的提升：把每个随机子程序重复 $O(\log (1/\delta ))$ 次可把总失败率压到 $\delta$；这只贡献对数因子。

7.3 总计与对比

把各层相加：层数 $t\le {\log }_2|G|$，每层是若干个以 $n$、$k$、$\log |G|$ 为参数的多项式代价原语（周期查找、Fourier 采样、振幅放大、经典线性代数后处理如 Smith 标准形与连分数），故总时间是

$$\mathrm{poly}(n,k,\log |G|),$$

对黑盒模型而言这是相对于输入规模的多项式。对比第 2.1 节：经典随机算法在同一模型下对这些任务存在指数查询下界——量子加速的来源不是某个单独的技巧，而是”均匀叠加 $+$ 傅里叶干涉”把指数大的全局结构（群阶、关系格）压缩进多项式大小的频谱测量里。

8. 完整例子：$S_3$ 的群阶与成员测试

把第 5–6 节的机器在一个能完全手算的群上跑一遍。取对称群

$$S_3=\{e,(12),(13),(23),(123),(132)\},|S_3|=6.$$

$S_3$ 可解：取正规列

$$\{e\}◃A_3◃S_3,A_3=⟨(123)⟩=\{e,(123),(132)\},$$

两个因子 $A_3/\{e\}\cong {\mathbb{Z}}_3$ 与 $S_3/A_3\cong {\mathbb{Z}}_2$ 都是循环群。polycyclic 生成序列取 $h_1=(123)$、$h_2=(12)$。

8.1 第一层：求 $|⟨(123)⟩|$

$G_0=\{e\}$，对 $g=(123)$ 做单元素周期查找。取 $M=6$（这里故意取周期的整数倍，使频谱是精确的；一般情形 $r$ 未知，应按第 7.1 节取 $M\ge r^2$，频谱集中在 $M/r$ 整数倍附近，用连分数提取）。制备

$$\frac{1}{\sqrt{6}}\sum _{a=0}^5|a⟩|g^a⟩.$$

把 $g$ 的幂列出来：$g^0=e$，$g^1=(123)$，$g^2=(132)$，$g^3=e$，$g^4=(123)$，$g^5=(132)$。按第二寄存器的值归并，态可写成

$$\frac{1}{\sqrt{6}}\left[\right(|0⟩+|3⟩)|e⟩+(|1⟩+|4⟩)|(123)⟩+(|2⟩+|5⟩)|(132)⟩].$$

测量第二寄存器，三种结果各以概率 $2/6=1/3$ 出现。设测得 $(132)$，第一寄存器坍缩为

$$\frac{1}{\sqrt{2}}(|2⟩+|5⟩).$$

对它做 ${\mathrm{QFT}}_6$（$\omega =e^{2\pi i/6}$），输出 $c$ 的振幅为

$$\frac{1}{\sqrt{12}}({\omega }^{2c}+{\omega }^{5c})=\frac{{\omega }^{2c}}{\sqrt{12}}(1+{\omega }^{3c}).$$

注意 ${\omega }^3=e^{\pi i}=-1$，故 $1+{\omega }^{3c}=1+(-1{)}^c$：当 $c$ 为奇数时振幅为 $0$（相消干涉），当 $c$ 为偶数时振幅模方为 $4/12=1/3$。于是测量结果等概率地落在

$$c\in \{0,2,4\},\frac{c}{M}\in \left\{0,\frac{1}{3},\frac{2}{3}\right\}.$$

把非零结果约成既约分数：$2/6=1/3$、$4/6=2/3$，分母都是 $3$，故 $r_1=3$。验证：$(123{)}^3=e$，阶确实是 3。于是

$$|A_3|=r_1\cdot |G_0|=3\cdot 1=3,$$

并合成均匀态

$$|A_3⟩=\frac{1}{\sqrt{3}}(|e⟩+|(123)⟩+|(132)⟩).$$

8.2 第二层：加入换位 $(12)$

$G_1=A_3$，$g=(12)$。先看商阶应该是多少：$(12)\notin A_3$（它是奇置换，$A_3$ 全是偶置换），而 $(12{)}^2=e\in A_3$，故

$$r_2=\min \{a>0:(12{)}^a\in A_3\}=2.$$

量子算法通过周期查找发现同一个数。两个陪集是

$$A_3=\{e,(123),(132)\},(12)A_3=\{(12),(12)(123),(12)(132)\}=\{(12),(23),(13)\},$$

二者无交（奇偶性不同），故对应陪集态

$$|A_3⟩=\frac{1}{\sqrt{3}}(|e⟩+|(123)⟩+|(132)⟩),|(12)A_3⟩=\frac{1}{\sqrt{3}}(|12⟩+|(23)⟩+|(13)⟩)$$

正交，与 Lemma 1 一致。制备 $\frac{1}{\sqrt{M}}{\sum }_a|a⟩|(12{)}^a{A}_3⟩$ 后，序列在两项之间以周期 2 振荡，QFT 频谱集中在 $c/M\approx 0$ 与 $c/M\approx 1/2$ 处，连分数读出 $r_2=2$。由 Theorem 2，

$$|S_3|=r_2|A_3|=2\times 3=6.$$

同时合成

$$|S_3⟩=\frac{1}{\sqrt{2}}(|A_3⟩+|(12)A_3⟩)=\frac{1}{\sqrt{6}}\sum _{\sigma \in S_3}|\sigma ⟩,$$

即全体六个群元素的均匀叠加——至此塔的顶层完成。

8.3 成员测试：$(13)$ 与 $(132)$

测试 $(13)\stackrel{?}{\in }{A}_3$：计算 $(13)$ 的幂模 $A_3$。$(13)\notin A_3$（奇置换），$(13{)}^2=e\in A_3$，故周期查找返回 $r=2\ne 1$，结论是非成员；并且新群的阶

$$|⟨A_3,(13)⟩|=r|A_3|=2\times 3=6,$$

即 $(13)$ 与 $A_3$ 一起生成整个 $S_3$。

测试 $(132)\stackrel{?}{\in }{A}_3$：$(132)=(123{)}^2\in A_3$，所以 $r=\min \{a>0:(132{)}^a\in A_3\}=1$，结论是成员，阶不变。进一步做 constructive membership：对 $A_3$ 内部的关系数据反查，可得表达 $(132)=(123{)}^2$，即把该元素写成了生成元 $h_1$ 的字。

这个六阶小例子走完了算法的全部环节：逐层周期查找、阶相乘、正交陪集态合成、成员判定与构造性表达——对大群，每一步的”枚举陪集”都被均匀叠加与 QFT 取代，但逻辑结构一模一样。

9. 矩阵群与算法的边界

9.1 矩阵群：跳出黑盒模型

如果群元素显式给成有限域 ${\mathbb{F}}_q$ 上的矩阵（而不是不透明标签），情况发生变化：算法可以直接检查矩阵条目、计算特征值、做高斯消元。Babai、Beals 与 Seress 的结果表明：经典矩阵群结构算法（Aschbacher 框架下的分解等）与量子子程序结合，可以在更广的参数范围内求群阶并完成 constructive membership。量子子程序处理的是经典方法卡壳的算术核心：

• ${\mathbb{F}}_q$ 乘法群的阶 $q-1$ 的因数分解（Shor）；
• 由特征值落出的离散对数（矩阵的特征值在扩域的乘法群里，阶的计算与离散对数都要对其做算术）；
• 以及相关的整数因子问题。

值得强调的是这里的分工：不是把矩阵条目当作黑盒标签塞进 HSP，而是让经典矩阵群理论负责群结构分解、量子算法只负责其中数论硬度集中的少数子问题。这也提示了一个普遍经验：量子群算法的能力边界高度依赖输入模型，黑盒、置换、矩阵三种模型下已知结论各不相同。

9.2 两条边界

第一，Watrous 的结论针对可解黑盒群。证明的骨架是循环因子塔（第 6 节），而非可解群（例如 $A_5$）不存在这样的塔：非 Abel 单群无法分解成循环因子，逐层均匀态构造在塔的某一层失去正规性前提，第 5 节的整个机制失效。对任意非可解黑盒群，能否同样在 $\mathrm{poly}(\log |G|)$ 总时间内完成所有这些任务，不能由本算法推出——这是一个超出本词条方法的开放方向。

第二，输出的长度。constructive membership 要求把元素写成生成元的字；在某些群中，元素的最短生成元字可能非常长，因此算法必须附带”表达有多项式长度”的承诺，否则打印表达本身就可能超出多项式时间。本词条所有关于 constructive membership 的陈述都在这一承诺下理解。

10. 小结与习题

本词条的要点：

• 黑盒群模型只提供标签与乘法/求逆 oracle，$|G|\le 2^n$；经典算法对群阶、成员判定等任务存在指数查询下界，量子算法给出 $\mathrm{poly}(n,k,\log |G|)$ 的解法。
• Abelian 群由生成元关系格与 Smith 标准形完全分解：$G\cong {\mathbb{Z}}_{d_1}\times \cdots \times {\mathbb{Z}}_{d_t}$，$|G|={\prod }_j{d}_j$；成员判定归结为比较添元前后的群阶。
• 均匀子群态使 $g^{a}H$ 成为周期函数：不同陪集态正交（Lemma 1），周期就是 $gH$ 在商群中的阶 $r$；在正规性条件 $H⊴⟨H,g⟩$ 下有计数公式 $|⟨H,g⟩|=r|H|$（Theorem 2），且 $r=1⟺g\in H$。
• 可解群的循环因子列（polycyclic 生成序列）允许逐层制备均匀态：每层一次 coset period finding，群阶逐层相乘，层数不超过 ${\log }_2|G|$；层内的相干擦除与纯化由 Abelian Fourier 采样和振幅放大完成。
• 成员、相等、正规性和构造表达都可复用阶与关系数据；矩阵群结果是经典结构理论与量子数论子程序的结合；非可解黑盒群与输出长度是方法的两条边界。

习题

1.（正交性）证明：同一左陪集的不同代表元给出同一个陪集态，不同左陪集的均匀态正交。你的证明在哪一步用到了”两个左陪集要么相等要么无交”？ 2.（关系格）在加法群 ${\mathbb{Z}}_{12}$ 中取生成元 $g_1=4$、$g_2=3$。写出关系映射 $\Phi :{\mathbb{Z}}^2\to {\mathbb{Z}}_{12}$，$(a,b)\mapsto 4a+3b\mathrm{mod}12$ 的核 $K$，给出 $K$ 作为 ${\mathbb{Z}}^2$ 子格的一组基；对它做 Smith 标准形，验证得到的分解与 ${\mathbb{Z}}_{12}\cong {\mathbb{Z}}_3\oplus {\mathbb{Z}}_4$（中国剩余定理）一致，并读出 $|{\mathbb{Z}}_{12}|$。 3.（二面体群）设 $D_8$ 为正方形的对称群，$r$ 为旋转 $90^{\circ }$、$s$ 为某条反射。沿塔 $\{e\}<⟨r⟩<D_8$ 逐层计算：写出每层商阶、各层的所有陪集，验证 $|D_8|=8$；并说明 $⟨r⟩◃D_8$ 为什么成立。 4.（正规性的必要性）取 $S_3$ 的子群 $H=⟨(12)⟩=\{e,(12)\}$ 与元素 $g=(13)$。验证 $H$ 在 $⟨H,g⟩$ 中不正规；计算 $r=\min \{a>0:g^a\in H\}$ 与并集 ${\bigcup }_{a=0}^{r-1}{g}^{a}H$，说明该并集不是子群，且 $r|H|\ne |⟨H,g⟩|$。这个例子在第 5.2 节的哪一条断言上敲了警钟？ 5.（计数公式）设 $H⊴⟨H,g⟩$，$r=\min \{a>0:g^a\in H\}$。不使用 Theorem 2 的结论，直接证明：陪集 $H,gH,\dots ,g^{r-1}H$ 两两无交且其并对乘法封闭，从而 $|⟨H,g⟩|=r|H|$。 6.（层数与复杂度）证明 Watrous 塔的层数 $t\le {\log }_2|G|$；并结合第 7 节说明：为什么每层代价的多项式性加上层数的对数上界，蕴含总复杂度是 $\mathrm{poly}(n,k,\log |G|)$ 而不显含 $|G|$。

参考文献

• Zoo 编号 74：Michele Mosca, Quantum Computer Algorithms, 1999。
• Zoo 编号 91：John Watrous, Quantum Algorithms for Solvable Groups.
• Zoo 编号 124：László Babai、Robert Beals 与 Ákos Seress, Polynomial-Time Theory of Matrix Groups, STOC 2009。

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch10-hidden-structures/group-order-membership
• 内容遵循 CC BY-NC-SA 4.0 许可协议