# 黑盒群的阶与成员关系：沿可解群正规列做量子周期查找 黑盒群只给元素标签和乘法 oracle，连“这个群有多少元素”都可能在经典多项式查询内不可知。量子算法的关键原语是均匀子群态：一旦能制备 $|H\rangle$，元素 $g$ 在商结构中的阶就成为 coset state 序列的周期。Watrous 用这一思路沿可解群的循环因子逐层扩张，得到群阶、成员、子群相等与正规性测试的多项式量子算法。 ## 1. 输入模型与四个相关任务 有限黑盒群 $G$ 的元素由 $n$ 比特标签编码，并提供可逆 oracle $$ |x,y\rangle\mapsto|x,xy\rangle, \qquad |x,y\rangle\mapsto|x,x^{-1}y\rangle. $$ 输入生成元 $g_1,\ldots,g_k$。常见任务包括： 1. 计算 $|\langle g_1,\ldots,g_k\rangle|$； 2. 判断给定 $x$ 是否属于该子群； 3. 在 yes 情形给出 $x$ 的生成元乘积表达（constructive membership）； 4. 比较两个生成子群是否相等或判断一个子群是否正规。 唯一编码时标签可直接比较；非唯一编码还需 identity/equality oracle。复杂度以 $n$、$k$ 和 $\log|G|$ 为参数，不把指数大的 Cayley 表当作输入。 ## 2. Abelian 群：关系格决定群结构 先求每个生成元的阶 $r_i$，并定义满射 $$ \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$ Abelian 时 $\Phi$ 是群同态，其核 $K$ 是所有生成元关系。函数“输出 $\Phi(a)$ 的标签”隐藏 $K$；Abelian HSP 求得关系格后，对关系矩阵做 Smith 标准形，得到 $$ G\cong\mathbb Z_{d_1}\times\cdots\times\mathbb Z_{d_t}, \qquad |G|=\prod_jd_j. $$ 给定 $x$，把它加入生成集并比较新旧群阶：若阶不变则 $x\in G$。保留 Smith 变换矩阵还能把 $x$ 写成原生成元的幂乘积。 ## 3. 子群均匀态把商阶变成周期 对一般群，若已能制备 $$ |H\rangle= \frac1{\sqrt{|H|}} \sum_{h\in H}|h\rangle, $$ 并且 $H\trianglelefteq\langle H,g\rangle$，则状态 $$ |g^aH\rangle =\frac1{\sqrt{|H|}} \sum_{h\in H}|g^ah\rangle $$ 只依赖陪集 $g^aH$。令 $$ r=\min\{a>0:g^a\in H\}. $$ 不同陪集态彼此正交，且 $$ |g^{a+r}H\rangle=|g^aH\rangle. $$ 因此映射 $$ |a\rangle|H\rangle \mapsto|a\rangle|g^aH\rangle $$ 隐藏整数周期 $r$。用 Shor 式 QFT 求得 $r$，便有 $$ |\langle H,g\rangle|=r|H|. $$ $r=1$ 恰好表示 $g\in H$。同时，周期查找得到的关系 $g^r\in H$ 可与前层的 constructive membership 表达组合，递归给出新群中元素的生成元分解。 ## 4. 为什么“可解群”正好允许逐层做这件事 有限可解群存在次正规列 $$ \{e\}=G_0\triangleleft G_1\triangleleft\cdots \triangleleft G_t=G, $$ 其中各因子 $G_{j+1}/G_j$ Abelian；进一步细化可令因子循环。选择 polycyclic generating sequence $h_1,\ldots,h_t$，使 $$ G_j=\langle h_1,\ldots,h_j\rangle, \qquad G_{j-1}\triangleleft G_j. $$ 从 $G_0$ 开始，Watrous 算法重复： 1. 用现有 $|G_{j-1}\rangle$ 对 $h_j$ 做 coset period finding； 2. 得到商中阶 $r_j$； 3. 由 $r_j$ 个正交陪集的均匀叠加合成 $|G_j\rangle$； 4. 更新群阶 $|G_j|=r_j|G_{j-1}|$ 和关系数据。 难点不是写出形式和 $$ \frac1{\sqrt{r_j}} \sum_{a=0}^{r_j-1}|h_j^aG_{j-1}\rangle, $$ 而是相干消除指数寄存器、控制近似误差并保持纯均匀态。Abelian Fourier 采样和振幅放大使每层只需多项式资源。 ## 5. 例子：$S_3$ 的群阶 $S_3$ 可解，取正规列 $$ \{e\}\triangleleft A_3\triangleleft S_3. $$ $A_3=\langle(123)\rangle$，第一层商阶为 3。再加入换位 $(12)$；其陪集平方回到 $A_3$，所以第二层商阶为 2。算法相乘得到 $$ |S_3|=3\times2=6. $$ 成员测试也随之清楚：$(13)\notin A_3$，加入后阶从 3 增到 6；$(132)\in A_3$，加入后阶不变。 ## 6. 矩阵群与边界 若群元素显式给成有限域上的矩阵，经典矩阵群结构算法结合量子因数分解和离散对数，可在更广的参数范围求阶和 constructive membership。这里的量子子程序主要处理域乘法群阶、特征值相关离散对数和整数因子，而不是简单把矩阵条目放入 HSP。 Watrous 结论针对可解黑盒群。对任意非可解黑盒群，能否同样在 $\operatorname{poly}(\log|G|)$ 总时间内完成所有这些任务不能由本算法推出。另一个边界是输出：constructive membership 表达必须有多项式长度承诺，否则打印本身可能昂贵。 ## 7. 小结与习题 - Abelian 群由生成元关系格和 Smith 标准形完全分解。 - 均匀子群态使 $g^aH$ 成为周期函数，周期就是 $gH$ 在商中的阶。 - 可解群的循环因子列允许逐层制备均匀态并相乘得到群阶。 - 成员、相等、正规性和构造表达都可复用阶与关系数据。 1. 证明不同左陪集的均匀态正交。 2. 对 $\mathbb Z_{12}=\langle4,3\rangle$ 写出关系映射 $\Phi$ 的核。 3. 沿 $\{e\}<\langle r\rangle