群同构测试

两个群可以使用完全不同的元素标签、不同的生成元、不同的乘法表写法，却具有完全相同的乘法结构——就像同一篇文章的两种不同语言的译本。群同构问题（group isomorphism problem）要求判断两个给定的群之间是否存在同构，即双射 $\phi :G\to H$ 满足

$$\phi (xy)=\phi (x)\phi (y)(\forall x,y\in G).$$

这个问题是著名的图同构问题的”近亲”，其精确复杂度至今悬而未决：对一般黑盒群，既无已知的多对数时间经典算法，也尚无统一的多对数时间量子算法。但是，一旦对群的结构加以限制，局面就完全不同。本词条讲清两个正结果的来龙去脉：

1. Abel 群（Cheung–Mosca，Zoo 127）：有限 Abel 群可以由不变因子序列完全分类，而分解可以归结为 Abel 隐藏子群问题，因此量子算法在 $\mathrm{poly}(\log |G|)$ 时间内不仅能判定同构，还能把同构映射显式构造出来；
2. Abel 正规子群被循环群扩张的一类非交换群（Le Gall，Zoo 128）：同构测试被进一步化为”作用矩阵的幂后共轭”问题，再化为可由 Abel HSP 求解的多重集合离散对数。

阅读本词条需要 Abel 隐藏子群问题（见Abel 隐藏子群问题）和 Shor 阶查找（见 Shor 算法）作为前提；本词条不再重新推导它们，只引用结论。

1. 问题从哪里来：标签与结构

1.1 同构是”换一套标签”

先建立一个具体直觉。考虑两个群：一个是模 $4$ 加法群

$${\mathbb{Z}}_4=\{0,1,2,3\},x\ast y=(x+y)\mathrm{mod}4,$$

另一个是复数乘法群 $\{1,i,-1,-i\}$。它们的元素名字、运算符号完全不同，但映射

$$\phi :{\mathbb{Z}}_4\to \{1,i,-1,-i\},\phi (a)=i^a$$

满足 $\phi (a\ast b)=i^{a+b\mathrm{mod}4}=i^a{i}^b=\phi (a)\phi (b)$（这里用了 $i^4=1$，所以指数可以模 $4$ 计算）。因此两个群同构：群的本质是乘法表的结构，而不是元素的名字。

同构测试的困难恰恰在于：算法拿到的只有”名字”（标签），而需要回答”结构”问题。两个群可能标签体系毫无相似之处，结构却相同；也可能许多容易计算的统计量全部吻合，结构却不同。

1.2 为什么群阶远远不够

同构必保持一切”结构不变量”：群阶、每个元素的阶、中心、交换性等等。反过来，比较不变量是否足够？不够——这些不变量通常不完备。例如

$${\mathbb{Z}}_6\text{与}{S}_3$$

都有 $6$ 个元素，但一个是 Abel 群、一个不是（$S_3$ 中两个对换不交换），因此不同构。这个例子里”交换性”一个不变量就足够区分；但加上更多统计量之后，仍然存在所有常见不变量都吻合却不同构的群对。结论：算法必须产生规范结构（canonical form），或者直接构造出同构映射，而不是只比较若干容易计算的统计量。这是全文的指导思想。

1.3 黑盒群模型与经典瓶颈

本词条采用黑盒群（black-box group）模型，这是讨论群算法查询复杂度的标准设定：

• 群 $G$ 的每个元素被编码为一个唯一的长度 $n=O(\log |G|)$ 的比特串（unique encoding：一个元素只有一个合法标签）；
• 算法只能通过群运算预言机做乘法、求逆、判断相等；
• 输入还包括一小组生成元 $g_1,\dots ,g_k$。

注意输入长度只有 $O(\log |G|)$：几个生成元加上预言机接口。因此，任何需要枚举全部 $|G|$ 个元素的算法，对输入长度而言都是指数时间的。经典算法面对的正是这个瓶颈：如果群以完整乘法表给出（输入长度约 $|G{|}^2\log |G|$），经典算法可以穷举生成元的像，在约 $|G{|}^{\log |G|+O(1)}$ 时间内判定同构；对图同构，已有拟多项式时间的经典算法。但在黑盒模型下输入只有 $O(\log |G|)$ 长，这些”指数级枚举”办法全部失效，经典算法对一般黑盒群是指数时间的。量子算法的机会在于：Shor 式的周期/隐藏子群机制恰好能在 $\mathrm{poly}(\log |G|)$ 时间内提取群的”关系结构”，这正是同构测试所需要的信息。

1.4 历史脉络

• Zoo 127（Cheung–Mosca, 2001）：给出分解有限 Abel 黑盒群的量子算法——求出一组生成元及完整关系，把 Abel 群写成循环群直积。Abel 群同构测试是它的直接推论。
• Zoo 128（Le Gall, 2010）：把同构测试推进到一类非交换群——含 Abel 正规子群 $A$、且商群为与 $|A|$ 互素的循环群的群（“Abel-by-cyclic”）。算法把问题化为有限域上矩阵的”幂后共轭”与多重集合离散对数，仍由 Abel HSP 求解。
• Zoo 202（Zatloukal, 2013）：研究更一般的群扩张等价测试，用 Abel HSP 加速作用相容性与上同调类的检查。

需要在一开始就强调：这些结果都没有解决一般群同构问题，也没有直接解决图同构问题。它们依赖明确的结构承诺（Abel、Abel-by-cyclic、互素阶、唯一编码），本词条第 7 节会回到这个边界。

2. 工具箱回顾

本词条反复使用四件工具，这里只陈述结论并注明出处，不重新推导。

阶查找（order finding）。给定黑盒群中元素 $g$，求最小正整数 $r$ 使 $g^r=e$。量子算法（Shor 阶查找，即相位估计作用于模乘酉算子的群论版本）在 $\mathrm{poly}(\log |G|)$ 时间完成。

Abel 隐藏子群问题（Abelian HSP）。设 $D$ 为已知结构的有限 Abel 群，函数 $f:D\to S$ 满足：存在子群 $K\le D$，使得 $f$ 在 $K$ 的每个陪集上取常值、在不同陪集上取不同值。这样的 $f$ 称为隐藏（hide）子群 $K$。量子算法（Simon/Shor 框架对一般 Abel 群的推广）用 $\mathrm{poly}(\log |D|)$ 次查询求出 $K$ 的一组生成元。详见Abel 隐藏子群问题。

构造性成员测试（constructive membership）。给定生成元 $g_1,\dots ,g_k$ 和元素 $h\in G$（$G$ Abel），求指数向量 $a$ 使 $h={\prod }_i{g}_i^{a_i}$。做法是对函数 $(a,t)\mapsto \Phi (a)\cdot h^{-t}$（其中 $\Phi$ 见下节）做 Abel HSP：隐藏子群由关系与 $h$ 的表示共同生成，求出后即读出 $a$。复杂度同为 $\mathrm{poly}(\log |G|)$。

Smith 标准形（Smith normal form）。对任意整数矩阵 $R$，存在行列式为 $\pm 1$ 的整数方阵（幺模矩阵）$U,V$，使

$$URV=\mathrm{diag}(d_1,d_2,\dots ,d_t,0,\dots ,0),d_1\mid d_2\mid \cdots \mid d_t,d_i\ge 1.$$

对角元 $d_i$（不变因子）由 $R$ 唯一确定；$U,V$ 与对角化过程可以在多项式时间内算出（经典算法，只需要整数行列运算）。

3. Abel 群：关系子群与 Smith 标准形

本节把 Cheung–Mosca 分解完整走一遍。核心思想一句话：Abel 群与”循环群直积”之间的差别，全部藏在生成元满足的关系里；而关系构成一个格子（${\mathbb{Z}}^k$ 的子群），量子算法擅长的正是找格子。

3.1 从生成元到关系子群

设 Abel 黑盒群 $G$ 的生成元为 $g_1,\dots ,g_k$。第一步，用量子阶查找求出每个生成元的阶

$$r_i=|g_i|,i=1,\dots ,k,$$

即最小正整数使 $g_i^{r_i}=e$。第二步，定义”自由”直积群到 $G$ 的映射

$$\Phi :D={\mathbb{Z}}_{r_1}\times \cdots \times {\mathbb{Z}}_{r_k}⟶G,a=(a_1,\dots ,a_k)\mapsto \prod _{i=1}^k{g}_i^{a_i}.$$

先验证 $\Phi$ 是群同态。这一步必须用到 $G$ 是 Abel 群：

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

其中第三个等号把 $g_i^{b_i}$ 逐个移到对应位置，只有两两可交换时才合法。由于 $g_1,\dots ,g_k$ 生成 $G$，每个群元素都能写成 ${\prod }_i{g}_i^{a_i}$，即 $\Phi$ 是满射。

定义关系子群

$$K=\ker \Phi =\{a\in D:g_1^{a_1}\cdots g_k^{a_k}=e\}.$$

$K$ 正是”生成元之间全部乘法关系”的集合：每个 $a\in K$ 是一条关系 $g_1^{a_1}\cdots g_k^{a_k}=e$。例如若 $g_1{g}_2=g_2{g}_1$ 之外的唯一关系是 $g_1^2=g_2^3$，那么 $(2,-3)\in K$。

3.2 用 Abel HSP 求关系子群

把 $\Phi$ 看成函数 $f:D\to G$（输出用元素的标签表示）。它满足 Abel HSP 的全部条件：

• $f$ 在 $K$ 的每个陪集上取常值：若 $b=a+k$、$k\in K$，则

$$f(b)=\Phi (a+k)=\Phi (a)\Phi (k)=\Phi (a)\cdot e=f(a),$$

用了同态性质与 $k\in \ker \Phi$；

• $f$ 在不同陪集上取不同值：若 $f(a)=f(b)$，则 $\Phi (a-b)=\Phi (a)\Phi (b{)}^{-1}=e$，即 $a-b\in K$，二者属于同一陪集。

（这正是群同态基本定理证明里”纤维即陪集”的那一步。）因此运行 Abel HSP 算法，用 $\mathrm{poly}(\log |D|)$ 次查询得到 $K$ 的一组生成元 $k^{(1)},\dots ,k^{(s)}\in D$——每个生成元是一个 $k$ 维整数向量（分量按模 $r_i$ 理解）。

再由群同态基本定理（第一同构定理）：满同态 $\Phi :D\to G$ 诱导同构

$$G\cong D/K.$$

到此，$G$ 的结构完全被”数据化”：$D$ 是已知的循环直积，$K$ 是已知生成元的子群。

3.3 Smith 标准形：从关系到不变因子

$D/K$ 仍不是一个”规范”的答案——同一个群可以由不同的 $D,K$ 给出。规范化的工具是 Smith 标准形。

把 $K$ 的生成元写成行向量，添上各分量的模 $r_i$ 关系，排成一个整数矩阵 $R$（关系矩阵，relation matrix）：每一行是 ${\mathbb{Z}}^k$ 中一个把生成元组合映到 $e$ 的关系。于是

$$G\cong {\mathbb{Z}}^k/⟨R\text{ 的行}⟩.$$

对这个商群做 Smith 标准形的代数含义是：

• 行变换（左乘幺模阵 $U$）= 更换关系集合的基，不改变它们生成的子群；
• 列变换（右乘幺模阵 $V$）= 更换 ${\mathbb{Z}}^k$ 的基，也就是把 $g_1,\dots ,g_k$ 换成一组新生成元 $h_j={\prod }_i{g}_i^{V_{ij}}$（整数可逆组合仍生成同一个群）。

由于行列变换不改变商群的同构型，Smith 标准形给出

$$G\cong {\mathbb{Z}}_{d_1}\times \cdots \times {\mathbb{Z}}_{d_t},d_1\mid d_2\mid \cdots \mid d_t,$$

其中删去了 $d_i=1$ 的平凡因子。不变因子序列 $(d_1,\dots ,d_t)$ 由 $G$ 唯一确定（Smith 标准形的唯一性），因此：

判定准则：两个有限 Abel 群同构，当且仅当它们的不变因子序列 $(d_1,\dots ,d_t)$ 完全相同。

这就是第 1.2 节所说的”规范结构”：同构测试被归结为计算并比较一个整数序列。而且 Smith 变换的矩阵 $V$ 记录了新基与旧生成元之间的坐标，所以算法不只是回答 yes/no——把两边的规范基对齐，就能构造出显式同构映射（constructive membership 负责把任意元素换算到规范基坐标）。

3.4 小例子：手算一次 Smith 标准形

设 Abel 群 $G$ 由 $g_1,g_2$ 生成，阶查找给出 $r_1=r_2=6$，即 $D={\mathbb{Z}}_6\times {\mathbb{Z}}_6$。运行 Abel HSP 后，设返回的关系子群 $K$ 由

$$k^{(1)}=(2,2),k^{(2)}=(0,3)$$

生成（即关系 $g_1^2{g}_2^2=e$ 与 $g_2^3=e$）。关系矩阵为

$$R=\left(\begin{array}{cc}2& 2\\ 0& 3\end{array}\right).$$

下面只做整数幺模行列运算，把 $R$ 对角化。每一步都标注依据：

第一步，第 2 列减去第 1 列（列变换，合法）：

$$\left(\begin{array}{cc}2& 0\\ 0& 3\end{array}\right).$$

第二步，把第 2 列加到第 1 列，再把第 1 行从第 2 行中减去，目的是用 $\gcd (2,3)=1$ 造出角上的 $1$：

$$\left(\begin{array}{cc}2& 0\\ 0& 3\end{array}\right)\stackrel{C_1\leftarrow C_1+C_2}{\to }\left(\begin{array}{cc}2& 0\\ 3& 3\end{array}\right)\stackrel{R_2\leftarrow R_2-R_1}{\to }\left(\begin{array}{cc}2& 0\\ 1& 3\end{array}\right).$$

第三步，交换两行把 $1$ 换到左上角，再消去同行的 $3$ 与同列的 $2$：

$$\left(\begin{array}{cc}2& 0\\ 1& 3\end{array}\right)\stackrel{R_1\leftrightarrow R_2}{\to }\left(\begin{array}{cc}1& 3\\ 2& 0\end{array}\right)\stackrel{C_2\leftarrow C_2-3C_1}{\to }\left(\begin{array}{cc}1& 0\\ 2& -6\end{array}\right)\stackrel{R_2\leftarrow R_2-2R_1}{\to }\left(\begin{array}{cc}1& 0\\ 0& -6\end{array}\right).$$

最后把第二行乘以 $-1$（幺模），得到 Smith 标准形

$$\mathrm{diag}(1,6).$$

验证：对角元整除关系 $1\mid 6$ 成立；行列式绝对值 $=6=|K|$ 在变换下不变（幺模变换行列式为 $\pm 1$）。因此

$$G\cong {\mathbb{Z}}_1\times {\mathbb{Z}}_6={\mathbb{Z}}_6.$$

虽然 $G$ 由两个 $6$ 阶元素生成、表面上”像” ${\mathbb{Z}}_6\times {\mathbb{Z}}_6$，关系 $g_1^2{g}_2^2=e$、$g_2^3=e$ 实际上把它”压缩”成了一个 $6$ 阶循环群。不变因子序列 $(6)$ 就是这个群在同构意义下的”指纹”。

3.5 复杂度逐项分析

整条流水线关于输入长度 $\log |G|$ 是多项式的，逐项看每个因子：

1. 阶查找：对 $k$ 个生成元各做一次 Shor 阶查找。生成元个数 $k\le {\log }_2|G|$（每个生成元至少使群阶翻倍，严格说是群有一个长度 $\le {\log }_2|G|$ 的生成元链），单次代价 $\mathrm{poly}(\log |G|)$，合计 $\mathrm{poly}(\log |G|)$。
2. Abel HSP：作用在 $D={\prod }_i{\mathbb{Z}}_{r_i}$ 上，$\log |D|={\sum }_i\log r_i=O(k\log |G|)$，故查询与后处理都是 $\mathrm{poly}(\log |G|)$。
3. Smith 标准形：经典多项式时间算法，矩阵规模 $O(k)$、表值 $O(\log |G|)$ 比特，代价 $\mathrm{poly}(k,\log |G|)$。
4. 构造性成员测试（组装同构时用到）：每次 $\mathrm{poly}(\log |G|)$。

每一项都是 $\mathrm{poly}(\log |G|)$，复合仍是 $\mathrm{poly}(\log |G|)$。这就是”Abel 群同构测试有多对数时间量子算法”的完整含义——注意它不是单一的量子加速点，而是阶查找与 HSP 两个量子子程序嵌在多项式时间的经典框架里。

4. 循环扩张类 $\mathcal{S}$

Abel 群的情形解决后，自然的下一步是”离 Abel 群最近”的非交换群。Le Gall（Zoo 128）考虑满足

$$G=⟨A,y⟩$$

的一类群，其中

$$A⊴G,A\text{Abelian},|y|=m,\gcd (|A|,m)=1.$$

也就是说：$G$ 由一个 Abel 正规子群 $A$ 和一个循环补 $⟨y⟩\cong {\mathbb{Z}}_m$ 生成，并且两部分阶互素。这类群称为 Abel-by-cyclic 群。

4.1 直觉：非交换性只有一个来源

先看这个结构”长什么样”。由于 $A⊴G$ 且 $G/A=⟨yA⟩\cong {\mathbb{Z}}_m$，每个元素都能唯一写成

$$g=a{y}^j,a\in A,j\in {\mathbb{Z}}_m.$$

两个元素相乘时，麻烦出在把 $y^j$“穿过”$b$：

$$(a{y}^i)(b{y}^j)=a{y}^{i}b{y}^{-i}{y}^{i+j}=a{\alpha }^i(b)y^{i+j},$$

其中

$$\alpha (a)=ya{y}^{-1}$$

是 $y$ 对 $A$ 的共轭作用。因为 $A$ 正规，$ya{y}^{-1}\in A$，所以 $\alpha$ 是 $A$ 的一个自同构；因为 $|y|=m$，${\alpha }^m(a)=y^{m}a{y}^{-m}=a$，即 ${\alpha }^m=\mathrm{id}$。

这个乘法公式说明：$G$ 的全部非交换性都来自 $\alpha$。若 $\alpha =\mathrm{id}$，则 $G=A\times {\mathbb{Z}}_m$ 是 Abel 群；$\alpha$ 越”不平凡”，群越非交换。结构上这是一个半直积

$$G\cong A{⋊}_{\alpha }{\mathbb{Z}}_m.$$

这里需要交代 $\gcd (|A|,m)=1$ 这个条件的作用：群论中的 Schur–Zassenhaus 定理保证，当正规子群与商群的阶互素时，扩张一定分裂——$G$ 一定是半直积（而不是更一般的、由 $2$-cocycle 扭结的扩张，后者见第 7 节），并且补群存在且在共轭意义下唯一。本词条不证明这个定理，但要记住结论：互素阶保证了”$A$ 加循环补”这个描述是完备且良定义的，这是整个算法能成立的前提之一。

4.2 作用矩阵：把 $\alpha$ 变成线性代数

要让算法处理 $\alpha$，需要把它写成矩阵。分三步：

第一步，用第 3 节的方法把 $A$ 分解为不变因子直积，并按素数归并为 Sylow 分量：

$$A=A_{p_1}\times A_{p_2}\times \cdots ,A_p={\mathbb{Z}}_{p^{e_1}}\times \cdots \times {\mathbb{Z}}_{p^{e_s}}.$$

第二步，注意 Abel 群的每个 Sylow $p$-子群是唯一的（所有 $p$ 幂阶元素的集合），因此被任何自同构保持。所以 $\alpha$ 分解为各 Sylow 分量上的自同构 ${\alpha }_p$，不存在分量之间的交叉项。

第三步，在每个 Sylow 分量上取定 Abel 基后，${\alpha }_p$ 就是一个可逆的整数线性变换；在分量的底（即 $p$-挠部分）上，它表示为有限域 ${\mathbb{F}}_p$ 上的可逆矩阵 $M$。于是

群结构由三类数据完全控制：

1. Abel 群 $A$ 的不变因子（第 3 节已解决）；
2. 循环补群的阶 $m$；
3. 作用自同构 $\alpha$ 在合适基下的矩阵（的共轭类）。

第 3 点是新东西，也是同构测试的难点所在：基可以任意换，$M$ 本身不是不变量，$M$ 的共轭类（相似类）才是。

4.3 标准分解：消除表达的任意性

还有一个更隐蔽的任意性：同一个群 $G$ 可能有多种 $(A,y)$ 表达。例如 $G=A⋊{\mathbb{Z}}_m$ 中把 $y$ 换成 $y^k$（$\gcd (k,m)=1$）仍是合法补群生成元；$A$ 也可能有多个”最大的”候选。如果两个待测群各自给出不同的表达，直接比较矩阵毫无意义。

Le Gall 的解决办法是定义标准分解（standard decomposition）：在所有合法分解中取循环阶最小（因而最规范）的那个，把它作为群的规范描述。计算标准分解只需要：

• 量子阶查找（测候选 $y$ 的阶）；
• Abel 群分解（第 3 节，刻画候选 $A$）；
• 构造性成员测试（检验元素属于哪个子群、换算坐标）。

每件工具都是 $\mathrm{poly}(\log |G|)$，候选的数量也有多项式界，所以这一步整体关于 $\log |G|$ 为多项式。此后，同构测试只需在两边标准分解之间进行。

5. 同构判据：幂后共轭

5.1 设定与目标

设两个待测群已经算出匹配的标准分解

$$G=A{⋊}_{\alpha }⟨y⟩,H=B{⋊}_{\beta }⟨z⟩,$$

并且前置检查已通过：$A\cong B$（用第 3 节的 Abel 判定准则）、$|y|=|z|=m$。记 $\alpha ,\beta$ 在各自 Abel 基下的作用矩阵为 $M_{\alpha },M_{\beta }$（在各有限域分量上分别讨论）。本节推导：

同构判据：$G\cong H$ 当且仅当存在 $k\in {\mathbb{Z}}_m^{\ast }$ 与基变换 $P$，使

$P{M}_{\alpha }{P}^{-1}=M_{\beta }^k.$

即：一个矩阵与另一个矩阵的第 $k$ 次幂相似——“幂后共轭”。

5.2 同构在补群上能做什么

设 $\phi :G\to H$ 是同构。先看 $\phi (y)$。把 $\phi$ 复合上商映射 $H\to H/B\cong {\mathbb{Z}}_m$，得到满同态 $G\to {\mathbb{Z}}_m$，其核包含 $A$；标准分解的匹配性保证它诱导的正是商群之间的同构 $G/A\to H/B$。而 ${\mathbb{Z}}_m$ 的自同构恰为乘以单位 $k\in {\mathbb{Z}}_m^{\ast }$（生成元必须映到生成元，阶为 $m$ 的元素恰为 $z^k$、$\gcd (k,m)=1$）。因此

$$\phi (y)=b{z}^k,b\in B,k\in {\mathbb{Z}}_m^{\ast }.$$

同时，标准分解的规范性保证 $\phi$ 把 $A$ 映到 $B$；在两边 Abel 基下，这个 Abel 群同构就是一个可逆的基变换矩阵 $P$：

$$\phi (a)⟷P\mathbf{a},$$

其中 $\mathbf{a}$ 是 $a$ 的坐标列向量。

5.3 逐步推导幂后共轭方程

同构必须保持共轭作用，即对一切 $a\in A$：

$$\phi \left(ya{y}^{-1}\right)=\phi (y)\phi (a)\phi (y{)}^{-1}.$$

左边：由 $\alpha$ 的定义，$ya{y}^{-1}=\alpha (a)$，所以左边 $=\phi (\alpha (a))$，坐标为

$$P{M}_{\alpha }\mathbf{a}.$$

右边：代入 $\phi (y)=b{z}^k$：

$$(b{z}^k)\phi (a)(b{z}^k{)}^{-1}=b{z}^k\phi (a)z^{-k}{b}^{-1}.$$

关键一步：$\phi (a)\in B$ 且 $B$ 是 Abel 群，所以 $b$ 与 $z^k\phi (a)z^{-k}\in B$ 可交换，$b\cdots b^{-1}$ 消去：

$$b{z}^k\phi (a)z^{-k}{b}^{-1}=z^k\phi (a)z^{-k}={\beta }^k(\phi (a)),$$

最后一步用了 $\beta$ 的定义迭代 $k$ 次（${\beta }^k(c)=z^{k}c{z}^{-k}$）。右边坐标为

$$M_{\beta }^{k}P\mathbf{a}.$$

左右相等且对一切 $\mathbf{a}$ 成立，因此

$$P{M}_{\alpha }\mathbf{a}=M_{\beta }^{k}P\mathbf{a}⟹P{M}_{\alpha }{P}^{-1}=M_{\beta }^k.$$

这就是判据的必要性。充分性也成立：给定满足方程的 $k,P$，定义 $\phi (a{y}^j)=\left(P\text{ 对应的元素}\right)z^{kj}$，直接验证它保持第 4.1 节的乘法公式，从而是同构。推导中两处不可省略的依据再强调一次：$B$ 可交换（消去 $b$）和 $k$ 必须是单位（商群同构）。

5.4 从矩阵相似到多重集合离散对数

剩下的问题是纯线性代数：给定 $M_{\alpha },M_{\beta }$，是否存在 $k\in {\mathbb{Z}}_m^{\ast }$ 使 $M_{\alpha }\sim M_{\beta }^k$（相似）？

矩阵相似当且仅当有理标准形（rational canonical form）相同，等价地不变因子/初等因子组相同。若逐个枚举 $k\in {\mathbb{Z}}_m^{\ast }$ 再比较有理标准形，$k$ 有 $\phi (m)$ 种取法，而 $m$ 可以到 $|G|$ 量级——这是指数搜索，必须避免。

换个角度看相似条件。把特征多项式在扩域中完全分解，设 $M_{\alpha }$ 的特征值多重集合为

$$X=\{x_1,\dots ,x_v\},M_{\beta }\text{的特征值多重集合为}Y=\{y_1,\dots ,y_v\}.$$

相似矩阵有相同的特征值多重集合；而 $M_{\beta }^k$ 的特征值恰为 $\{y_1^k,\dots ,y_v^k\}$（特征值随矩阵幂次取幂，这是 Jordan 块或直接对角化的直接推论）。于是必要条件——并且在配合有理标准形逐块核对后也是充分条件——是：

多重集合离散对数（set discrete logarithm）：给定有限域（扩域）中的两个多重集合 $X,Y$，寻找 $k$ 使

$\{y_1^k,\dots ,y_v^k\}=X(\text{作为多重集合相等}).$

5.5 为什么朴素做法失败，Le Gall 如何解决

朴素思路是”逐个猜配对”：猜 $x_1=y_{\pi (1)}^k$，解普通离散对数得 $k$，再验证其余元素。它有两个指数障碍：

1. 配对组合爆炸：$v$ 个元素的配对有 $v!$ 种，逐一枚举是指数的。
2. 模阶歧义：由单个方程 $x_i=y_{\pi (i)}^k$ 解出的 $k$ 只确定到模 $\mathrm{ord}(y_{\pi (i)})$；不同配对给出不同模数的剩余类，中国剩余定理不一定能把它们拼成一个公共的 $k$（各 $\mathrm{ord}(y_j)$ 未必互素，同余式组可能不相容，需要回溯）。

Le Gall 的观察是：这两个障碍本质上是”带有多重配对约束的周期查找”，而 Abel HSP 恰好擅长同时处理耦合的周期约束。他把整个 set discrete logarithm 编码为若干个 Abel HSP 实例：隐藏子群的结构同时记录”哪个 $x$ 对应哪个 $y$ 的幂”与”$k$ 在各模数下的剩余”，一次 HSP 求出隐藏子群即同时消除配对歧义与模阶歧义，而不必枚举。每个 HSP 实例的规模是 $\mathrm{poly}(v,\log |\mathbb{F}|)$，实例个数也是多项式，因此总的求解时间为

$$\mathrm{poly}(v,\log |\mathbb{F}|),$$

其中 $v$ 是矩阵维数（$v\le {\log }_2|A|$，因为每个不变因子分量至少贡献一个因子 $2$），$\log |\mathbb{F}|$ 是扩域的表值长度（扩域次数不超过矩阵维数，故也是 $\mathrm{poly}(\log |G|)$)。逐项看：因子 $v$ 来自矩阵维数与多重集合大小；因子 $\log |\mathbb{F}|$ 来自域中元素的比特长度与域运算代价；HSP 框架本身贡献关于这两个量的多项式开销。

最后，若找到合法的 $k$，回溯整条推导链：离散对数给出 $k$，矩阵共轭给出 $P$，$P$ 与 Abel 基变换（第 3 节的 Smith 坐标）合成 $A\to B$ 的显式映射，再配上 $y\mapsto z^k$（适当补上 $B$ 中的校正项），即组装出显式群同构。判定与构造是同一个算法的两个输出。

6. 小例子：平凡作用与反演作用

取 $A={\mathbb{Z}}_3$、$m=2$，把第 4–5 节的全部机制在最小尺度上演算一遍。

6.1 平凡作用给出 ${\mathbb{Z}}_6$

若 $y$ 对 $A$ 的作用平凡，即 $\alpha (a)=a$，作用矩阵是 $1\times 1$ 矩阵 $[1]$。此时乘法公式退化为

$$(a,y^i)(b,y^j)=(a+b,y^{i+j}),$$

即直积 ${\mathbb{Z}}_3\times {\mathbb{Z}}_2$。由中国剩余定理（$\gcd (2,3)=1$），

$$A⋊{\mathbb{Z}}_2\cong {\mathbb{Z}}_3\times {\mathbb{Z}}_2\cong {\mathbb{Z}}_6.$$

6.2 反演作用给出 $S_3$

若作用为反演

$$\alpha (a)=-a(\mathrm{mod}3),$$

作用矩阵是 $[-1]=[2]$（${\mathbb{F}}_3$ 中 $-1\equiv 2$）。注意 $[2{]}^2=[4]=[1]$，确有 ${\alpha }^2=\mathrm{id}$，与 $m=2$ 自洽。此时

$${\mathbb{Z}}_3{⋊}_{-1}{\mathbb{Z}}_2\cong S_3:$$

把 $A={\mathbb{Z}}_3$ 的生成元对应到 $3$-循环 $(123)$，把 $y$ 对应到对换 $(12)$，则对换共轭 $3$-循环确实把它取逆：$(12)(123)(12)=(132)=(123{)}^{-1}$，这正是 $\alpha (a)=-a$。两个生成元满足 $S_3$ 的定义关系，故同构。

6.3 用判据验证二者不同构

两群的 $A$（不变因子都是 $(3)$）与 $m=2$ 完全相同，唯一差别在 $1\times 1$ 作用矩阵 $[1]$ 与 $[2]$。套用幂后共轭判据：

• 可取的幂次：$k\in {\mathbb{Z}}_2^{\ast }=\{1\}$，只有 $k=1$；
• $1\times 1$ 可逆矩阵的共轭：$P[p]P^{-1}=[p]$，因为 ${\mathbb{F}}_3^{\ast }$ 可交换，一维情形共轭不改变任何东西；
• 因此判据要求 $[1]=[2{]}^1=[2]$，在 ${\mathbb{F}}_3$ 中不成立。

故两群不同构。这与直接观察一致：${\mathbb{Z}}_6$ 可交换而 $S_3$ 不可交换。注意判据里”$k$ 只允许取单位”这一点在本例中是决定性的——如果允许 $k=0$，$[2{]}^0=[1]$ 会错误地判为同构，但 $z^0=e$ 根本不生成商群，对应的”映射”不是双射。

这个例子还说明判据中 ${\mathbb{Z}}_m^{\ast }$ 的”幂次自由度”何时真正起作用：$m=2$ 时 ${\mathbb{Z}}_2^{\ast }$ 只有一个元素，幂自由度消失；$m\ge 3$ 时才会出现”矩阵不共轭但幂后共轭”的非平凡同构（见习题 3）。

7. 群扩张等价与一般边界

7.1 比 Abel-by-cyclic 更一般的扩张

一般群扩张写作短正合列

$$1\to A\to G\to Q\to 1,$$

含义是 $A⊴G$ 且 $G/A\cong Q$，但 $Q$ 不一定能嵌入 $G$ 作为子群（扩张不一定分裂）。此时结构由两部分数据决定：

1. 作用：$Q$ 对 $A$ 的共轭作用（在 $A$ Abel 时，这使 $A$ 成为 $Q$-模）；
2. $2$-cocycle：取截面 $s:Q\to G$（每个陪集选一个代表），乘法亏量

$$s(q)s(q^{\prime })=f(q,q^{\prime })s(q{q}^{\prime })$$

定义函数 $f:Q\times Q\to A$。群乘法结合律迫使 $f$ 满足 cocycle 方程（对 $A$ Abel、作用记为 $q\cdot a$ 的加法记号）：

$$q\cdot f(q^{\prime },q^{\prime \prime })+f(q,q^{\prime }{q}^{\prime \prime })=f(q,q^{\prime })+f(q{q}^{\prime },q^{\prime \prime }),$$

即**$2$-cocycle 条件**——它正是”结合律在代表元层面的表达”。

截面本身有任意性：把 $s(q)$ 换成 $c(q)s(q)$（$c:Q\to A$ 任意），$f$ 会加上一个由 $c$ 决定的coboundary。因此扩张的等价类不是由单个 cocycle、而是由它的上同调类（$H^2(Q,A)$ 中的元素）决定。于是扩张等价测试 = “作用是否相容 + 两个 cocycle 是否属于同一上同调类”，两者都是线性代数/同调性质的约束。Zatloukal（Zoo 202）对若干参数族用 Abel HSP 加速这些线性与同调约束的求解。

7.2 边界：这些结果没有解决什么

必须如实说明适用范围，三类保留条款：

• 不等于一般群同构已解决：Le Gall 算法依赖 Abel-by-cyclic 结构承诺（存在 Abel 正规子群与互素阶循环补）。对没有这种结构的群（例如幂零类更高的群、单群的直积等），标准分解与幂后共轭判据都可能失效或不再完备。
• 不等于图同构已解决：图同构可自然地化为置换群相关的问题，但置换群一般不是 Abel-by-cyclic 群，本词条算法不直接适用。
• 依赖模型承诺：互素阶 $\gcd (|A|,m)=1$ 保证了 Schur–Zassenhaus 分裂与补群的共轭唯一性；unique encoding（每个元素唯一标签）保证了 HSP 中”函数在不同陪集取不同值”的良定义性。超出这些承诺时，standard decomposition 和幂后共轭判据都可能失效。

8. 小结与习题

本词条的链条可以概括为四句话：

• Abel 群同构由关系子群的 Smith 标准形完全决定：生成元的阶给出自由直积 $D$，Abel HSP 求出关系子群 $K$，Smith 标准形给出唯一不变因子序列，比较序列即判定同构，而且构造性；
• Abel-by-cyclic 群还需额外记录循环补群对正规 Abel 子群的共轭作用；互素阶条件（Schur–Zassenhaus）保证半直积描述完备，标准分解消除表达任意性；
• 两个作用给出同构，当且仅当适当幂次（$k\in {\mathbb{Z}}_m^{\ast }$）之后两个作用矩阵在基变换下共轭：$P{M}_{\alpha }{P}^{-1}=M_{\beta }^k$；推导的关键两步是商群同构迫使 $k$ 为单位、$B$ 可交换使补群校正项 $b$ 消去；
• 幂后共轭经特征多项式化为多重集合离散对数；Le Gall 将其分解为若干 Abel HSP，同时消除配对组合与模阶歧义，在 $\mathrm{poly}(v,\log |\mathbb{F}|)$ 时间求 $k$。

习题

1. 求 ${\mathbb{Z}}_4\times {\mathbb{Z}}_6$ 的不变因子分解。（提示：先按素数拆成初等因子 ${\mathbb{Z}}_4\times {\mathbb{Z}}_2\times {\mathbb{Z}}_3$，再用中国剩余定理按”每个素数取一列”的方式重新组装成整除链。）
2. 证明在 $A{⋊}_{\alpha }⟨y⟩$ 中若把补群生成元 $y$ 换成 $y^k$ 且 $\gcd (k,m)=1$，则新生成元对应的作用矩阵变为 $M_{\alpha }^k$。（提示：直接计算 $y^{k}a{y}^{-k}$，并说明 $\gcd$ 条件用在哪里。）
3. 在 ${\mathbb{Z}}_5⋊{\mathbb{Z}}_4$ 中比较两个作用 $\alpha :a\mapsto 2a$ 与 $\beta :a\mapsto 3a$：它们给出的两个群是否同构？（提示：${\mathbb{Z}}_4^{\ast }=\{1,3\}$，检查是否存在 $k\in {\mathbb{Z}}_4^{\ast }$ 使 $[3]=[2{]}^k$ 在 ${\mathbb{F}}_5$ 中成立；并说明为什么 $k$ 不能取 $2$。）
4. 在 ${\mathbb{F}}_7$ 中求所有 $k$ 使多重集合 $\{2^k,3^k\}=\{4,5\}$，并指出单个方程 $2^k=4$ 的解为什么不足以确定答案（模阶歧义的具体体现）。
5. 解释群同构、群扩张等价和图同构三者为何不能互换结论：每个问题的输入承诺分别是什么，本词条算法依赖其中哪些？
6. 第 5.2 节断言 ${\mathbb{Z}}_m$ 的自同构恰为”乘以 $k\in {\mathbb{Z}}_m^{\ast }$“。证明它，并举例说明 $k$ 非单位时映射 $z\mapsto z^k$ 为何不是同构。

参考文献

• Zoo 编号 127：Kevin Cheung 与 Michele Mosca, Decomposing Finite Abelian Groups.
• Zoo 编号 128：François Le Gall, An Efficient Quantum Algorithm for Some Instances of the Group Isomorphism Problem.
• Zoo 编号 202：Kevin Zatloukal, Classical and Quantum Algorithms for Testing Equivalence of Group Extensions.

---

参考资料

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