# 有限黑盒环与理想：用 Abelian HSP 恢复加法基

环同时具有加法 Abel 群和可能非交换的乘法。表面上，理想问题似乎需要直接理解非交换乘法；量子算法的切入点却是先把理想作为**加法群**完整恢复，再把乘法转成有限个结构常数。本课推导如何在 $\operatorname{poly}(\log|R|)$ 次黑盒操作内得到理想的基表示，并由此解决成员关系、交、商、单位与线性方程等问题。

## 1. 黑盒模型与输出格式

设 $R$ 是带幺有限环，不要求交换。每个元素由唯一比特串 $\eta(a)$ 编码，只能通过可逆黑盒访问

$$
|a,b,0\rangle\mapsto|a,b,a+b\rangle,
\qquad
|a,b,0\rangle\mapsto|a,b,ab\rangle.
$$

输入还包括环生成集 $\widetilde R$ 和左理想生成集

$$
\widetilde I=\{i_1,\ldots,i_m\},
$$

其大小都假定为 $O(\log|R|)$。左理想 $I$ 是包含 $\widetilde I$、对加法和任意左乘 $rI$ 封闭的最小集合。

目标“基表示”包含三部分：

1. 加法群的不变因子生成元 $h_1,\ldots,h_\ell$；
2. 各生成元的加法阶 $s_1,\ldots,s_\ell$，使
   $$
   (I,+)\cong\mathbb Z_{s_1}\times\cdots\times\mathbb Z_{s_\ell};
   $$
3. 乘法结构常数
   $$
   h_i h_j=\sum_k M_{ij}^{k}h_k.
   $$

有了它，任意理想元素都可用短坐标向量表示，而不再只是一个毫无结构的黑盒标签。

## 2. 从理想生成元扩张出加法生成元

先令 $\widetilde B_1=\widetilde I$，$B_k=\langle\widetilde B_k\rangle_+$ 为当前生成的加法子群。关键判据是：

$$
B_k=I
\quad\Longleftrightarrow\quad
rb\in B_k
\quad\forall r\in\widetilde R,\ b\in\widetilde B_k.
$$

“若”方向的理由是：生成集上的左乘封闭经分配律扩展到整个 $B_k$，再由 $\widetilde R$ 的加法与乘法生成性扩展到任意 $r\in R$。所以 $B_k$ 已是包含 $\widetilde I$ 的左理想，只能等于最小的 $I$。

怎样量子判断 $rb\in B_k$？制备均匀子群态

$$
|B_k\rangle=
\frac1{\sqrt{|B_k|}}
\sum_{x\in B_k}|x\rangle.
$$

加法平移 $T_{rb}|x\rangle=|rb+x\rangle$ 满足

$$
T_{rb}|B_k\rangle=
\begin{cases}
|B_k\rangle,&rb\in B_k,\\
|rb+B_k\rangle\perp|B_k\rangle,&rb\notin B_k.
\end{cases}
$$

Hadamard 测试即可区分两种情况。若找到不属于 $B_k$ 的 $rb$，将它加入 $\widetilde B_k$。严格扩张的有限群至少增大一倍：

$$
|B_{k+1}|\ge2|B_k|.
$$

因此最多 $\log_2|I|$ 轮就会停止；每轮只枚举多项式多的生成元对。

## 3. Abelian HSP 如何给出不变因子坐标

得到普通加法生成集后，使用有限 Abel 群分解算法把它转换成不变因子基 $h_j$ 和阶 $s_j$。还需解决“给定黑盒标签 $i\in I$，求其坐标”的问题。考虑群

$$
G=\mathbb Z_{s_1}\times\cdots\times
\mathbb Z_{s_\ell}\times\mathbb Z_s,
$$

其中 $s$ 是 $i$ 的加法阶，并定义

$$
f(n_1,\ldots,n_\ell,m)
=\eta\!\left(\sum_j n_jh_j+mi\right).
$$

若

$$
i=\sum_j n_j(i)h_j,
$$

则 $f$ 隐藏由

$$
(n_1(i),\ldots,n_\ell(i),-1)
$$

生成的循环子群。Abelian HSP 恢复该生成元，也就恢复 $i$ 的坐标。对所有 $h_ih_j$ 调用乘法黑盒并做同样分解，即得到整个张量 $M_{ij}^{k}$。

## 4. 基表示支持哪些算法

### 成员关系与理想相等

给定 $a$，制备陪集态 $|a+I\rangle$。它与 $|I\rangle$ 相同当且仅当 $a\in I$，否则两态正交。理想相等也可通过各自均匀态的 overlap 或比较不变因子基来判断。

### 理想的交与商

对 $x\in I$ 输出量子态 $|x+J\rangle$。同一陪集对应相同状态，不同陪集正交，所以该映射隐藏加法子群 $I\cap J$；Abelian HSP 直接给出交的生成元。类似地，

$$
(I:J)=\{x\in R:xJ\subseteq I\}
$$

可用多个陪集寄存器隐藏。

### 单位与逆元

元素 $r$ 为单位当且仅当它生成的左理想 $Rr$ 等于 $R$。先分别求二者基表示并比较；若相等，再用量子阶查找求乘法阶 $c$，于是

$$
r^{-1}=r^{c-1}.
$$

### 环上线性方程

写

$$
a=\sum_i a_ih_i,quad
b=\sum_i b_ih_i,quad
x=\sum_j x_jh_j.
$$

由乘法张量把 $ax=b$ 化成

$$
\sum_j A_{ij}x_j\equiv b_i\pmod{s_i}.
$$

加入松弛变量后，这是经典整数线性丢番图方程组，可用 Hermite/Smith 标准形在多项式时间求解。量子部分负责从黑盒标签提取结构，后处理则是经典线性代数。

## 5. 例子：$\mathbb Z_{12}$ 中的理想 $(4)$

在交换环 $R=\mathbb Z_{12}$ 中，

$$
I=(4)=\{0,4,8\}.
$$

作为加法群，它由 $h=4$ 生成且阶为 3，所以

$$
(I,+)\cong\mathbb Z_3.
$$

乘法满足

$$
h^2=16\equiv4=h\pmod{12},
$$

故唯一结构常数是 $M_{11}^{1}=1\pmod3$。陪集 $2+I=\{2,6,10\}$ 与 $I$ 不同，立即证明 $2\notin I$；而 $8+I=I$，证明 $8\in I$。

## 6. 复杂度与不能推出的结论

轮数、生成元数和 Abelian HSP 寄存器长度都关于 $\log|R|$ 为多项式，前提是唯一编码、相干加乘黑盒和短生成集可用。若元素编码不唯一，两个不同标签可能代表同一元素，陪集正交性和隐藏子群函数都会失效。

这些算法不自动解决环同构、环自同构或任意无限环问题，也不等于把非交换乘法群当作 Abelian 群。量子优势来自每个理想天然具有 Abelian **加法**结构，以及乘法可通过有限结构常数回填。

## 7. 小结与习题

- 先检测当前加法子群是否对环生成元左乘封闭。
- 每次加入新元素至少使子群大小翻倍，因此迭代次数为对数级。
- Abelian HSP 给出不变因子基、元素坐标和乘法张量。
- 大量理想问题随后化为陪集 HSP 或经典丢番图方程。

1. 证明 $rb\in B$ 对生成元 $r,b$ 成立时，$B$ 对任意环元素左乘封闭。
2. 在 $\mathbb Z_{18}$ 中求理想 $(6)$ 的不变因子表示。
3. 证明 $a+I$ 与 $I$ 要么相同要么不相交。
4. 用结构常数写出 $\mathbb Z_{12}$ 的理想 $(4)$ 内方程 $4x=8$ 的坐标同余式。

## 参考文献

- Zoo 编号 118：Pawel Wocjan、Stephen Jordan、Hamed Ahmadi 与 Joseph Brennan, [Efficient Quantum Processing of Ideals in Finite Rings](https://arxiv.org/abs/0908.0022)（2023 修订版）。
- Zoo 编号 119：V. Arvind、Bireswar Das 与 Partha Mukhopadhyay, *The Complexity of Black-Box Ring Problems*, COCOON 2006.
- Zoo 编号 120：V. Arvind 与 Partha Mukhopadhyay, *Quantum Query Complexity of Multilinear Identity Testing*, STACS 2009.