# 黑盒群的阶与成员关系：沿可解群正规列做量子周期查找

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

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

:::{admonition} 本课知识点
:class: tip

1. **[黑盒群模型与四个计算任务](#black-box-group-model)**——能写出乘法与求逆两类 oracle 在计算基矢上的作用，列出群阶、成员判定、构造性成员与子群比较四个任务，并解释唯一/非唯一编码的差别与 $|G|\le 2^n$ 这条基准不等式。
2. **[经典查询下界与算法史](#classical-query-lower-bound)**——能解释经典算法求群阶为何需要 $\Omega(|G|)$ 次查询，并比较 Mosca、Watrous、Babai–Beals–Seress 三项结果各自的输入模型与适用范围。
3. **[Abelian 群的关系格与 Smith 标准形](#abelian-relation-lattice)**——能构造 Abelian 黑盒群的关系映射 $\Phi$ 并证明它是同态，说明如何用 Abelian HSP 求出关系格、用 Smith 标准形读出群分解与群阶，并把成员判定化为添元前后比阶。
4. **[均匀子群态与陪集态的正交性](#uniform-subgroup-state)**——能解释"商群里的阶 $=$ 态序列的周期"这条核心翻译，写出 $|H\rangle$ 与 $|gH\rangle$ 的定义，并证明 $|H\rangle$ 对 $H$ 内右乘不变、不同陪集态正交（Lemma 1）。
5. **[正规性与逐层计数公式](#normality-counting-formula)**——能证明正规性 $H\trianglelefteq\langle H,g\rangle$ 下陪集乘法良定义且 $|\langle H,g\rangle|=r|H|$（Theorem 2），并用 $S_3$ 中的反例说明该条件不可去掉。
6. **[陪集周期查找与任务归约](#coset-period-finding)**——能写出陪集周期查找电路并推导 QFT 频谱集中于 $M/r$ 整数倍附近，说明连分数提取 $r$ 的精度条件 $M\ge r^2$、成员判据 $r=1\iff g\in H$ 与其余任务到求 $r$ 的归约。
7. **[可解群的循环因子塔与 Watrous 主循环](#solvable-tower-watrous)**——能写出 polycyclic 生成序列与主循环四步，解释相干擦除为何不能换成测量及其实现思路，并证明层数上界 $t\le\log_2|G|$ 从而总复杂度为 $\operatorname{poly}(n,k,\log|G|)$。
8. **[S₃ 手算实例与算法边界](#s3-example-boundary)**——能沿塔 $\{e\}\triangleleft A_3\triangleleft S_3$ 手算每层商阶、频谱与成员测试并验证 $|S_3|=6$，并说明可解性假设与输出长度承诺两条边界及矩阵群路线的分工。

:::

(black-box-group-model)=
## 1. 黑盒群模型与四个任务

### 1.1 输入模型

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

$$
|G|\le 2^n,
\qquad\text{即}\qquad
\log_2|G|\le n.
$$

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

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

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

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

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

1. **群阶 (order)**：计算 $|\langle g_1,\ldots,g_k\rangle|$；
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 表（乘法表）当作输入——如果允许读乘法表，求群阶就是平凡的，整个问题也就失去了意义。

(classical-query-lower-bound)=
## 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 群推进到**可解群**：对可解黑盒群，群阶、成员判定、构造性成员、子群相等与正规性测试都有 $\operatorname{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\rangle|g^a\rangle$ 制备出来，对第一个寄存器做 QFT，干涉相消后只有满足"$cr$ 接近 $M$ 的整数倍"的频率 $c$ 存活，于是 $r$ 被读了出来。整个技巧成立的前提是：**序列 $|g^a\rangle$ 只依赖 $a\bmod r$**，且不同剩余类给出**正交**的态——这样第二个寄存器才能把第一个寄存器"筛"成等差数列。

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

$$
H,\ gH,\ g^2H,\ \ldots
$$

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

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

$$
|H\rangle=\frac1{\sqrt{|H|}}\sum_{h\in H}|h\rangle.
$$

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

$$
|Hh'\rangle=\frac1{\sqrt{|H|}}\sum_{h\in H}|hh'\rangle=|H\rangle.
$$

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

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

(abelian-relation-lattice)=
## 4. 热身：Abelian 群由关系格完全决定

先看 Abelian 情形。它是 [Abelian 隐藏子群问题](abelian-hidden-subgroup.md) 的直接应用，也为后面一般情形提供了"关系数据"的样板。

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

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

$$
\frac1{\sqrt M}\sum_{a=0}^{M-1}|a\rangle|g_i^a\rangle,
$$

对第一寄存器做 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,
\qquad
(a_1,\ldots,a_k)\mapsto g_1^{a_1}\cdots g_k^{a_k}.
$$

由于 $g_1,\ldots,g_k$ 生成 $G$，$\Phi$ 是满射：每个群元素至少有一个指数向量作为原像。当 $G$ 是 **Abelian** 群时，$\Phi$ 还是群同态——直接验证：对 $a=(a_1,\ldots,a_k)$、$b=(b_1,\ldots,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
\big(\mathbb Z_{r_1}\times\cdots\times\mathbb Z_{r_k}\big)\big/\ker\Phi,
$$

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

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

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

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

考虑函数

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

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

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

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

$$
URV=
\operatorname{diag}(d_1,d_2,\ldots,d_t),
\qquad
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},
\qquad
|G|=\prod_{j=1}^{t}d_j.
$$

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

### 4.5 成员判定与构造性表达

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

$$
x\in G
\iff
\langle G,x\rangle=G
\iff
|\langle G,x\rangle|=|G|.
$$

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

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

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

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

(uniform-subgroup-state)=
### 5.1 陪集态的定义与正交性

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

$$
|H\rangle=\frac1{\sqrt{|H|}}\sum_{h\in H}|h\rangle,
$$

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

$$
|gH\rangle=\frac1{\sqrt{|H|}}\sum_{h\in H}|gh\rangle.
$$

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

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

- 若 $g_1H=g_2H$（同一陪集），则 $|g_1H\rangle=|g_2H\rangle$；
- 若 $g_1H\ne g_2H$（不同陪集），则 $\langle g_1H|g_2H\rangle=0$。

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

**证明**。第一部分：$g_1H=g_2H$ 意味着两个求和 $\sum_{h\in H}|g_1h\rangle$ 与 $\sum_{h\in H}|g_2h\rangle$ 跑遍同一个集合，只是加项次序不同，故两态相等。

第二部分：群论的基本事实是两个不同的左陪集作为集合**不相交**（若 $x\in g_1H\cap g_2H$，写 $x=g_1h_1=g_2h_2$，则 $g_1H=g_2h_2h_1^{-1}H=g_2H$）。于是 $\{|g_1h\rangle\}_{h\in H}$ 与 $\{|g_2h\rangle\}_{h\in H}$ 是两组互不相同的计算基矢，内积

$$
\langle g_1H|g_2H\rangle
=\frac1{|H|}\sum_{h_1,h_2\in H}\langle g_1h_1|g_2h_2\rangle
=\frac1{|H|}\sum_{h_1,h_2\in H}0=0,
$$

因为每个克罗内克内积 $\langle g_1h_1|g_2h_2\rangle$ 的两个基矢都落在不相交的集合里。Q.E.D.

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

(normality-counting-formula)=
### 5.2 正规性：让"陪集序列的周期"等于"商群元素的阶"

设 $g\in G$，定义

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

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

$$
|H\rangle,\ |gH\rangle,\ |g^2H\rangle,\ \ldots
$$

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

$$
|g^{a+r}H\rangle=|g^aH\rangle,
$$

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

现在引入关键的结构条件

$$
H\trianglelefteq\langle H,g\rangle,
$$

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

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

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

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

$$
\langle H,g\rangle=\bigsqcup_{a=0}^{r-1}g^aH
\quad\text{（无交并）},
\qquad
|\langle H,g\rangle|=r\,|H|.
$$

**证明**。记 $K_0=\bigcup_{a=0}^{r-1}g^aH$。分三步。

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

$$
(g^ah_1)(g^bh_2)=g^a(h_1g^b)h_2=g^a(g^bh_1')h_2=g^{a+b}h_1'h_2,
$$

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

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

而 $g^r\in H$ 蕴含 $(g^r)^q\in H$，所以 $g^{a+b}h_1'h_2\in g^sH\subseteq K_0$。

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

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

(coset-period-finding)=
### 5.3 周期查找电路：把 $r$ 读出来

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

$$
|0\rangle|H\rangle
\xrightarrow{\ \mathrm{QFT}_M\text{ 于第一寄存器}\ }
\frac1{\sqrt M}\sum_{a=0}^{M-1}|a\rangle|H\rangle
\xrightarrow{\ \text{受控乘 }g^a\ }
\frac1{\sqrt M}\sum_{a=0}^{M-1}|a\rangle|g^aH\rangle.
$$

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

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

$$
\frac1{\sqrt L}\sum_{j=0}^{L-1}|a_0+jr\rangle,
\qquad
L=\left|\{j:\ 0\le a_0+jr\le M-1\}\right|\approx\frac Mr.
$$

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

$$
\frac1{\sqrt{LM}}\sum_{j=0}^{L-1}\omega_M^{c(a_0+jr)}
=
\frac{\omega_M^{ca_0}}{\sqrt{LM}}\sum_{j=0}^{L-1}\omega_M^{jrc}.
$$

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

$$
\left|\frac cM-\frac sr\right|\le\frac1{2M}
\quad\text{对某个 }s\in\{0,1,\ldots,r-1\}.
$$

这正是 Shor 算法中"频率谱集中在 $M/r$ 的整数倍附近"的标准结论：$c/M$ 是 $s/r$ 的逼近。只要 $M$ 取得足够大（使 $1/(2M)\le1/(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 给出 $|\langle H,g\rangle|=r|H|$；
- **成员判定**：$r=1\iff g\in H$（$r=1$ 意为 $g^1\in H$；反之 $g\in H$ 时最小正指数当然是 1）；
- **构造性成员**：周期查找同时给出关系 $g^r\in H$。若我们对 $H$ 已有 constructive membership 能力（能把 $H$ 中任意元素写成生成元的字），则 $g^r$ 可被表达，递归下去就能把 $\langle H,g\rangle$ 中任意元素 $g^ah$（$0\le a<r$，$h\in H$）写成原生成元的乘积——表达长度按层数线性增长；
- **正规性与相等测试**：判断 $H\trianglelefteq K$ 归结为对每个生成元 $h$ of $H$、$k$ of $K$ 判定 $k^{-1}hk\in H$，即一串成员判定；判断 $H=K$ 归结为双向的成员判定。所以这四个任务全部归约到"求商阶 $r$"这一个原语上。

(solvable-tower-watrous)=
## 6. 为什么可解群正好允许逐层做这件事

### 6.1 可解群与循环因子塔

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

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

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

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

$$
G_j=\langle h_1,\ldots,h_j\rangle,
\qquad
G_{j-1}\triangleleft G_j
\qquad(j=1,\ldots,t).
$$

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

### 6.2 Watrous 算法的主循环

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

1. **周期查找**：用手头的 $|G_{j-1}\rangle$ 对 $h_j$ 执行第 5.3 节的 coset period finding，即制备 $\sum_a|a\rangle|h_j^aG_{j-1}\rangle$ 并做 QFT；
2. **读出商阶**：得到 $h_jG_{j-1}$ 在 $G_j/G_{j-1}$ 中的阶 $r_j$；
3. **合成新的均匀态**：把 $r_j$ 个正交陪集态均匀叠加，制备
   $$
   |G_j\rangle=\frac1{\sqrt{r_j}}\sum_{a=0}^{r_j-1}|h_j^aG_{j-1}\rangle;
   $$
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 步写出形式目标

$$
\frac1{\sqrt{r_j}}\sum_{a=0}^{r_j-1}|h_j^aG_{j-1}\rangle
$$

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

$$
\frac1{\sqrt{r_j}}\sum_{a=0}^{r_j-1}|a\rangle\otimes|h_j^aG_{j-1}\rangle,
$$

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

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

### 6.4 层数的上界

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

$$
2^t\le\prod_{j=1}^{t}r_j=|G|
\qquad\Longrightarrow\qquad
t\le\log_2|G|\le n.
$$

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

## 7. 复杂度分析

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

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

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

$$
\left|\frac cM-\frac sr\right|<\frac1{2r^2}
\quad\text{需要}\quad
M\ge r^2.
$$

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

$$
\left|\frac{s}{r'}-\frac{s''}{r''}\right|
=\frac{|sr''-s''r'|}{r'r''}
\ge\frac1{r'r''}\ge\frac1{r^2},
$$

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

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

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

即可覆盖所有可能。于是第一寄存器需要 $\log_2M=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 标准形与连分数），故总时间是

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

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

(s3-example-boundary)=
## 8. 完整例子：$S_3$ 的群阶与成员测试

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

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

$S_3$ 可解：取正规列

$$
\{e\}\triangleleft A_3\triangleleft S_3,
\qquad
A_3=\langle(123)\rangle=\{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 第一层：求 $|\langle(123)\rangle|$

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

$$
\frac1{\sqrt6}\sum_{a=0}^{5}|a\rangle\,|g^a\rangle.
$$

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

$$
\frac1{\sqrt6}\Big[
\big(|0\rangle+|3\rangle\big)|e\rangle
+\big(|1\rangle+|4\rangle\big)|(123)\rangle
+\big(|2\rangle+|5\rangle\big)|(132)\rangle
\Big].
$$

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

$$
\frac1{\sqrt2}\big(|2\rangle+|5\rangle\big).
$$

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

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

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

$$
c\in\{0,\,2,\,4\},
\qquad
\frac cM\in\left\{0,\ \frac13,\ \frac23\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\cdot1=3,
$$

并合成均匀态

$$
|A_3\rangle=\frac1{\sqrt3}\Big(|e\rangle+|(123)\rangle+|(132)\rangle\Big).
$$

### 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)\},
\qquad
(12)A_3=\{(12),(12)(123),(12)(132)\}=\{(12),(23),(13)\},
$$

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

$$
|A_3\rangle=\tfrac1{\sqrt3}\big(|e\rangle+|(123)\rangle+|(132)\rangle\big),
\qquad
|(12)A_3\rangle=\tfrac1{\sqrt3}\big(|12\rangle+|(23)\rangle+|(13)\rangle\big)
$$

正交，与 Lemma 1 一致。制备 $\frac1{\sqrt M}\sum_a|a\rangle|(12)^aA_3\rangle$ 后，序列在两项之间以周期 2 振荡，QFT 频谱集中在 $c/M\approx0$ 与 $c/M\approx1/2$ 处，连分数读出 $r_2=2$。由 Theorem 2，

$$
|S_3|=r_2\,|A_3|=2\times3=6.
$$

同时合成

$$
|S_3\rangle=\frac1{\sqrt2}\Big(|A_3\rangle+|(12)A_3\rangle\Big)
=\frac1{\sqrt6}\sum_{\sigma\in S_3}|\sigma\rangle,
$$

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

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

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

$$
|\langle A_3,(13)\rangle|=r|A_3|=2\times3=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 节的整个机制失效。对任意非可解黑盒群，能否同样在 $\operatorname{poly}(\log|G|)$ 总时间内完成所有这些任务，**不能由本算法推出**——这是一个超出本文方法的开放方向。

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

## 10. 小结

本篇的要点：

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

## 练习题

**练习 1【黑盒群模型与四个计算任务】**（→ [第 1 节](#black-box-group-model)）

1. 基础：写出黑盒群模型中乘法与求逆两个 oracle 在计算基矢上的作用，并解释为什么"把运算乘到目标寄存器上"保证这两个映射都是置换、从而是可以在叠加态上相干执行的酉操作。
2. 进阶：说明复杂度为什么以 $n$、$k$、$\log|G|$ 为参数而不把规模 $|G|^2$ 的 Cayley 表当作输入，并比较唯一编码与非唯一编码两种情形下模型分别需要（额外）提供哪些 oracle。

> 提示：想想若允许读完整乘法表，求群阶会退化成什么难度。

**练习 2【经典查询下界与算法史】**（→ [第 2 节](#classical-query-lower-bound)）

1. 基础：描述"从单位元出发不断用生成元右乘、记录新标签"的朴素枚举策略，说明其查询次数为何是 $\Omega(|G|)$、而 $|G|$ 可以达到 $2^n$，因此这是输入规模的指数。
2. 进阶：用"每次查询只得到一个新标签、信息以加法速度积累，而 $k$ 个生成元生成的群以乘法速度膨胀"解释经典下界的直觉，并把 Mosca（1999）、Watrous（2000）、Babai–Beals–Seress（2009）分别归入"黑盒 Abelian 群、黑盒可解群、显式矩阵群"三条路线。

> 提示：先比较三项工作各自的输入模型。

**练习 3【Abelian 群的关系格与 Smith 标准形】**（→ [第 4 节](#abelian-relation-lattice)）

1. 基础：写出关系映射 $\Phi:\mathbb Z_{r_1}\times\cdots\times\mathbb Z_{r_k}\to G$ 的定义，验证 $G$ 为 Abelian 群时 $\Phi(a+b)=\Phi(a)\Phi(b)$，并指出证明中哪一步用到了元素两两交换。
2. 进阶：在加法群 $\mathbb Z_{12}$ 中取生成元 $g_1=4$、$g_2=3$。写出关系映射 $\Phi:\mathbb Z^2\to\mathbb Z_{12}$，$(a,b)\mapsto 4a+3b\bmod 12$ 的核 $K$，给出 $K$ 作为 $\mathbb Z^2$ 子格的一组基；对它做 Smith 标准形，验证得到的分解与 $\mathbb Z_{12}\cong\mathbb Z_3\oplus\mathbb Z_4$（中国剩余定理）一致，并读出 $|\mathbb Z_{12}|$。

> 提示：把 $4a+3b\equiv0\pmod{12}$ 分别模 3、模 4，解出对 $a$、$b$ 的整除条件。

**练习 4【均匀子群态与陪集态的正交性】**（→ [5.1 节](#uniform-subgroup-state)）

1. 基础：写出均匀子群态 $|H\rangle$ 与陪集态 $|gH\rangle$ 的定义，并证明对任意 $h'\in H$ 有 $|Hh'\rangle=|H\rangle$，说明这为什么意味着该态"看不见" $H$ 的内部结构。
2. 进阶：证明：同一左陪集的不同代表元给出同一个陪集态，不同左陪集的均匀态正交。你的证明在哪一步用到了"两个左陪集要么相等要么无交"？

> 提示：若 $x\in g_1H\cap g_2H$，写 $x=g_1h_1=g_2h_2$，考察 $g_2^{-1}g_1$。

**练习 5【正规性与逐层计数公式】**（→ [5.2 节](#normality-counting-formula)）

1. 基础：设 $r=\min\{a>0:\ g^a\in H\}$。利用判据 $g^aH=g^bH\iff g^{a-b}\in H$ 证明陪集序列 $H,gH,g^2H,\ldots$ 恰以 $r$ 为最小周期。
2. 进阶：取 $S_3$ 的子群 $H=\langle(12)\rangle=\{e,(12)\}$ 与元素 $g=(13)$。验证 $H$ 在 $\langle H,g\rangle$ 中**不**正规；计算 $r=\min\{a>0:g^a\in H\}$ 与并集 $\bigcup_{a=0}^{r-1}g^aH$，说明该并集不是子群，且 $r|H|\ne|\langle H,g\rangle|$。这个例子在第 5.2 节的哪一条断言上敲了警钟？
3. 进阶：设 $H\trianglelefteq\langle H,g\rangle$，$r=\min\{a>0:g^a\in H\}$。不使用 Theorem 2 的结论，直接证明：陪集 $H,gH,\ldots,g^{r-1}H$ 两两无交且其并对乘法封闭，从而 $|\langle H,g\rangle|=r|H|$。

> 提示：算出 $(13)H$ 与 $\langle(12),(13)\rangle$ 各自的阶，并检查 $(13)(12)(13)$ 是否落在 $H$ 内。

**练习 6【陪集周期查找与任务归约】**（→ [5.3 节](#coset-period-finding)）

1. 基础：在周期查找电路中测得第二寄存器为某个陪集 $g^{a_0}H$ 后，写出第一寄存器坍缩成的态，并解释其支撑集为什么是等差数列 $\{a_0,a_0+r,a_0+2r,\ldots\}\cap[0,M-1]$。
2. 基础：证明成员判据 $r=1\iff g\in H$，并说明群阶、正规性与相等测试如何各自归约到"求商阶 $r$"这一个原语。
3. 进阶：对坍缩后的第一寄存器做 $\mathrm{QFT}_M$，推导输出 $c$ 的振幅为 $\frac{\omega_M^{ca_0}}{\sqrt{LM}}\sum_{j=0}^{L-1}\omega_M^{jrc}$，说明概率在 $cr/M$ 接近整数时约为 $L/M$、否则近似相消，并解释 $M\ge r^2$ 时连分数为何能唯一锁定 $s/r$。

> 提示：等比数列 $\sum_j\omega_M^{jrc}$ 的模方由公比的辐角 $2\pi rc/M$ 决定。

**练习 7【可解群的循环因子塔与 Watrous 主循环】**（→ [第 6 节](#solvable-tower-watrous)）

1. 基础：写出可解群的定义与 polycyclic 生成序列满足的两条性质 $G_j=\langle h_1,\ldots,h_j\rangle$ 与 $G_{j-1}\triangleleft G_j$，并解释为什么"每层恰好在上一层上加一个元素且保持正规"正是第 5 节原语所要求的输入形状。
2. 进阶：解释第 6.3 节为什么必须相干地擦除指数寄存器而不能测量：一旦测量会发生什么？映射 $a\mapsto h_j^aG_{j-1}$ 的哪个性质保证"擦除"可以延拓成酉变换？
3. 进阶：证明 Watrous 塔的层数 $t\le\log_2|G|$；并结合第 7 节说明：为什么每层代价的多项式性加上层数的对数上界，蕴含总复杂度是 $\operatorname{poly}(n,k,\log|G|)$ 而不显含 $|G|$。

> 提示：回忆 Lemma 1——不同指数给出两两正交的陪集态。

**练习 8【S₃ 手算实例与算法边界】**（→ [第 8 节](#s3-example-boundary)）

1. 基础：在 8.1 节的设置（$g=(123)$、$M=6$）中，设第二寄存器测得 $(123)$ 而非 $(132)$：写出第一寄存器坍缩后的态，对其做 $\mathrm{QFT}_6$ 计算频谱，并解释为什么换一个测量结果不会改变读出的周期 $r_1=3$。
2. 进阶：设 $D_8$ 为正方形的对称群，$r$ 为旋转 $90^\circ$、$s$ 为某条反射。沿塔 $\{e\}<\langle r\rangle<D_8$ 逐层计算：写出每层商阶、各层的所有陪集，验证 $|D_8|=8$；并说明 $\langle r\rangle\triangleleft D_8$ 为什么成立。
3. 进阶：解释为什么对非可解群（如 $A_5$）不存在循环因子塔、Watrous 的逐层机制会在哪一步失效；并说明 constructive membership 的结论为什么要附带"表达有多项式长度"的承诺。

> 提示：$A_5$ 是单群——没有非平凡正规子群可以充当塔顶之下的那一层。

## 参考文献

- Zoo 编号 74：Michele Mosca, [Quantum Computer Algorithms](https://www.iqc.ca/~mmosca/web/papers/moscathesis.pdf), 1999。
- Zoo 编号 91：John Watrous, [Quantum Algorithms for Solvable Groups](https://arxiv.org/abs/quant-ph/0011023).
- Zoo 编号 124：László Babai、Robert Beals 与 Ákos Seress, *Polynomial-Time Theory of Matrix Groups*, STOC 2009。