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

黑盒群只给元素标签和乘法 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<D_8\) 计算二面体群 \(D_8\) 的阶。

  4. 解释为什么 \(H\trianglelefteq\langle H,g\rangle\) 使陪集乘法和周期解释良定义。

参考文献