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

环是最基本的代数结构之一：它同时带有一个加法 Abel 群和一个（可能不交换的）乘法。密码学、编码理论和计算数论中的许多对象——模整数剩余类环 $\mathbb Z_n$、有限域上的矩阵环、群环——都是有限环。对有限环，我们最关心的问题往往不是"某个元素长什么样"，而是关于**理想 (ideal)** 的计算问题：判断一个元素是否属于给定理想、求两个理想的交、解理想上的线性方程、判断元素是否可逆。理想之于环，正如正规子群之于群、子空间之于向量空间：它是取商、做同态、分解结构的出发点。

表面上看，理想问题似乎无法回避环的**非交换乘法**：理想的定义本身就要求对任意左乘封闭，而左乘结构可以非常复杂。本课要讲的量子算法的切入点恰恰相反：**先完全绕开乘法**。关键观察是，任何理想 $I$ 对加法封闭，因此 $(I,+)$ 是环的加法 Abel 群的子群——而 Abelian 群结构正是 [Abelian 隐藏子群问题](../ch10-hidden-structures/abelian-hidden-subgroup.md)的量子算法最擅长处理的对象。算法的路线是：

1. 把理想作为**加法群**完整恢复出来（求出它的不变因子基）；
2. 再用乘法黑盒算出有限个**结构常数**，把乘法信息"回填"到加法坐标上。

乘法没有被当作一个整体来理解，而是被压缩成一张有限的乘法表。一旦有了这套"基表示"，成员关系、理想的交与商、单位判定、环上线性方程等问题，要么直接化为陪集 HSP，要么化为经典的整数线性代数。

**经典算法能做到什么程度？** 在黑盒模型下，经典算法对环几乎无能为力：Arvind、Das 与 Mukhopadhyay 对黑盒环问题的经典复杂性做了系统研究（见参考文献 Zoo 119），表明诸如"判断黑盒环是否交换""判断元素是否为零因子"等基本问题在经典查询模型下需要指数多次查询，或者必须依赖随机化与额外假设；同一批作者关于多线性恒等式测试的量子查询复杂度研究（Zoo 120）则表明某些环恒等式问题存在量子加速。真正把"理想"作为对象系统地量子化处理的是 Wocjan、Jordan、Ahmadi 与 Brennan 的工作（Zoo 118）：他们证明，在带唯一编码与相干黑盒的模型下，可以在 $\operatorname{poly}(\log|R|)$ 次黑盒操作内得到任意左理想的基表示，并由此解决上面列出的一大串问题。本课就是这篇工作的核心推导。

**关于模型的一句提醒**：本节所有结论都建立在三个前提上——元素有**唯一编码**、加法与乘法都有**相干（可逆）黑盒**、输入附带**短生成集**。这些前提不是总能满足的，第 6 节会解释它们在哪里被用到、失效时会怎样。这也是原文献明确标注的模型依赖条款，阅读复杂度结论时应始终记得它们。

**前置知识**：本课默认读者熟悉有限 Abel 群的基本事实（Lagrange 定理、不变因子分解），以及本站前面章节中的 QFT、相位估计与 Abelian HSP 算法；我们会引用 Abelian HSP 的结论（"对有限 Abel 群上周期/隐藏子群结构的函数，量子算法可用多项式次查询恢复隐藏子群"），但不重新推导它。

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

1. **[环、左理想与生成理想](#ring-left-ideal)**——能写出带幺环与左理想的公理、写出生成理想 $\langle S\rangle=\{\sum_k r_ks_k\}$ 的显式形式，并解释左乘封闭中的 $r$ 为何必须取遍整个环。
2. **[黑盒模型的三前提](#black-box-model)**——能列出唯一编码、相干黑盒与短生成集三项假设，并逐一解释它们分别保证了流水线中的哪一步。
3. **[基表示与结构常数](#basis-representation)**——能写出基表示的三个组成部分、用不变因子分解写出元素坐标，并解释结构常数 $M_{ij}^{k}$ 如何把乘法压缩成坐标上的双线性运算。
4. **[理想封闭性判据](#closure-criterion)**——能证明 $B_k=I\iff rb\in B_k\ (\forall r\in\widetilde R,\,b\in\widetilde B_k)$，并说明该判据如何把对全环的全称检查归约为多项式个生成元对检查。
5. **[陪集态与 Hadamard 测试](#coset-hadamard-test)**——能证明陪集引理（平移后的子群态要么不变要么正交），并用 Hadamard 测试把成员判定化为概率 $1$ 与 $\tfrac12$ 的区分。
6. **[翻倍引理与轮数上界](#doubling-lemma)**——能由 Lagrange 定理推导子群严格扩张至少翻倍 $|B_{k+1}|\ge 2|B_k|$，并计算迭代轮数的对数上界 $\log_2|I|$。
7. **[坐标化的 HSP 构造](#coordinate-hsp)**——能构造群 $G$ 与函数 $f$，推导隐藏子群 $H$ 由 $(n_1(i),\dots,n_\ell(i),-1)$ 生成，从而把"求坐标"归约为 Abelian HSP。
8. **[环上线性方程的求解](#ideal-linear-equation)**——能用结构常数把 $ax=b$ 化为模 $s_k$ 的坐标同余式，并说明松弛变量如何把它变成可经典求解的整数线性方程组。

:::

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

(ring-left-ideal)=
### 1.1 有限环与左理想

先固定记号。**环 (ring)** $R$ 是一个集合，上面有两种运算：加法 $+$ 与乘法 $\cdot$，满足

- $(R,+)$ 是 Abel 群：加法满足结合律、交换律，存在零元素 $0$ 与加法逆元 $-a$；
- 乘法满足结合律，并存在乘法幺元 $1$（我们约定环**带幺**）；
- 乘法对加法满足分配律：$r(a+b) = ra + rb$ 与 $(a+b)r = ar + br$。

注意我们**不要求乘法交换**：矩阵环就是典型的非交换环。本课中 $R$ 始终是**有限**环，记其元素个数为 $|R|$。

**左理想 (left ideal)** $I \subseteq R$ 是一个非空子集，满足两条封闭性：

- 对加法封闭且含逆：$a, b \in I \Rightarrow a - b \in I$（即 $(I,+)$ 是 $(R,+)$ 的子群）；
- 对**任意左乘**封闭：对一切 $r \in R$ 与 $a \in I$，都有 $ra \in I$。

第二条是理想与普通加法子群的本质区别：左乘封闭性里的 $r$ 取自**整个环**，而不只是 $I$ 内部。给定任意子集 $S \subseteq R$，由 $S$ **生成的左理想** $\langle S \rangle$ 定义为包含 $S$ 的所有左理想的交——等价地说，它是包含 $S$、对加法和任意左乘封闭的**最小**集合。它的显式形式是

$$
\langle S \rangle = \left\{\sum_{k=1}^{t} r_k s_k :\ t \ge 0,\ r_k \in R,\ s_k \in S\right\},
$$

即"环元素乘生成元再求和"所能得到的一切。这个显式形式里 $r_k$ 遍历整个环，所以直接按定义计算生成理想需要枚举 $|R|$ 个元素——正是量子算法要绕开的地方。

(black-box-model)=
### 1.2 黑盒模型

设 $R$ 是带幺有限环，不要求交换。算法的输入不是环的乘法表（那将有 $|R|^2$ 个条目，对 $\log|R|$ 而言是指数大的），而是以下三项。

**唯一编码**。每个元素 $a \in R$ 由唯一比特串 $\eta(a) \in \{0,1\}^n$ 编码，$n = O(\log|R|)$。"唯一"有两层含义：不同元素编码不同（单射），且每个合法比特串至多对应一个元素。这样我们才能把环元素直接当作量子寄存器的计算基矢 $|a\rangle := |\eta(a)\rangle$ 使用。

**相干黑盒**。我们只能通过两个可逆黑盒访问环运算：

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

与通常的量子预言机一样，"可逆"意味着它们可以相干地作用在叠加态上：对叠加 $\sum_{a,b}\alpha_{a,b}|a,b,0\rangle$ 施加加法黑盒，得到 $\sum_{a,b}\alpha_{a,b}|a,b,a+b\rangle$。由于环加法群上 $x \mapsto a + x$ 本身是双射，第一个黑盒还可以直接实现**加法平移**$|x\rangle \mapsto |a + x\rangle$——这一步在第 2 节会反复用到。

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

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

其大小都假定为 $O(\log|R|)$。这里 $\widetilde R$ "生成" $R$ 指：每个环元素都能由 $\widetilde R$ 中的元素经有限次加法与乘法得到；$\widetilde I$ 生成左理想 $I = \langle \widetilde I \rangle$ 的含义见 1.1 节。短生成集的存在性是一个实质性假设：对许多自然出现的环（如 $\mathbb Z_n$ 由单个元素 $1$ 生成）它成立且高效可得，但并非对任意黑盒环都免费。

(basis-representation)=
### 1.3 目标：基表示

算法要求的输出"基表示"包含三部分：

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.
   $$

逐个解释这三个部分。

**第 1、2 部分是有限 Abel 群结构定理的实例**。该定理说：任何有限 Abel 群都同构于若干循环群的直积，即存在元素 $h_1,\dots,h_\ell$，其加法阶分别为 $s_1,\dots,s_\ell$，使得群里每个元素 $x$ 都能**唯一**写成

$$
x = \sum_{j=1}^{\ell} n_j h_j,\qquad 0 \le n_j < s_j.
$$

这正是 $(I,+) \cong \mathbb Z_{s_1}\times\cdots\times\mathbb Z_{s_\ell}$ 的展开写法。换句话说，$(n_1,\dots,n_\ell)$ 是元素 $x$ 的**坐标**：理想中每个元素对应一个唯一的坐标向量，坐标分量 $n_j$ 在模 $s_j$ 意义下取值。

**第 3 部分把乘法压缩成一张表**。两个基元素的乘积 $h_i h_j$ 仍是理想中的元素（理想对左乘封闭，而 $h_i \in R$、$h_j \in I$），因此它自己也有坐标展开；$M_{ij}^k$ 就是该展开中 $h_k$ 的系数。这样的常数一共只有 $\ell^3$ 个，而 $\ell \le \log_2|I|$（理想的加法群大小不超过环的大小，且每个生成元至少贡献一个因子 2），所以这张表是"短"的。有了它，任意两个元素 $x = \sum_i x_i h_i$ 与 $y = \sum_j y_j h_j$ 的乘积可由分配律展开为

$$
xy = \sum_{i,j} x_i y_j\, h_i h_j = \sum_k\left(\sum_{i,j} M_{ij}^{k} x_i y_j\right) h_k,
$$

即：**坐标上的乘法 = 结构常数张量 $M$ 给出的双线性运算**。乘法的一切信息都在 $M$ 里。

有了基表示，任意理想元素都可用短坐标向量表示，而不再只是一个毫无结构的黑盒标签。"知道理想的基表示"与"只拿到几个生成元"的差别，类似于"知道线性子空间的一组基"与"只知道子空间非空"的差别：前者让成员判断、求交、解方程都变成机械计算。

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

本节解决第一个子问题：输入只有理想生成集 $\widetilde I$，如何得到加法群 $(I,+)$ 的（普通意义下的）生成集？思路是迭代扩张：维护一个加法子群 $B_k \subseteq I$，不断检查它是否已经"大到对左乘封闭"；若没有，就量子地找到一个漏掉的元素加进来。

(closure-criterion)=
### 2.1 封闭性判据

先令 $\widetilde B_1=\widetilde I$，$B_k=\langle\widetilde B_k\rangle_+$ 为当前生成的加法子群（即 $\widetilde B_k$ 中元素的一切有限和与差）。关键判据是：

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

这个判据把"是否是理想"这个涉及**全体环元素**的全称命题，归约为对**有限个生成元对** $(r,b)$ 的检查——右边只有 $|\widetilde R|\cdot|\widetilde B_k|$ 个条件，而两个生成集的大小都是 $\operatorname{poly}(\log|R|)$。

**证明**。"仅若"方向是直接的：若 $B_k = I$，则由理想的左乘封闭性，$rb \in I = B_k$ 对一切 $r \in R$（当然也包括 $r \in \widetilde R$）与 $b \in \widetilde B_k \subseteq I$ 成立。

"若"方向分两步扩展，每步只用一条环公理。

第一步，从生成元扩展到整个 $B_k$。任取 $x \in B_k$ 与 $r \in \widetilde R$。由 $B_k = \langle \widetilde B_k \rangle_+$ 的定义，$x$ 是 $\widetilde B_k$ 中元素的有限和：$x = \sum_t \pm b_t$，其中 $b_t \in \widetilde B_k$。由**左分配律**，

$$
rx = r\sum_t (\pm b_t) = \sum_t (\pm rb_t).
$$

右端的每一项 $rb_t$ 由假设属于 $B_k$，而 $B_k$ 对加法与取负封闭（它是加法子群），故 $rx \in B_k$。

第二步，从 $\widetilde R$ 扩展到整个 $R$。任取 $r \in R$ 与 $x \in B_k$。由 $\widetilde R$ 的生成性，$r$ 可由 $\widetilde R$ 中元素经加法与乘法得到。我们对"构造 $r$ 所用的运算次数"归纳：若 $r \in \widetilde R$，第一步已给出 $rx \in B_k$；若 $r = r_1 + r_2$，由**右分配律** $rx = r_1 x + r_2 x$，两项由归纳假设属于 $B_k$，其和亦然；若 $r = r_1 r_2$，则 $rx = r_1(r_2 x)$，先由归纳假设 $r_2 x \in B_k$，再对 $r_1$ 用归纳假设得 $r_1(r_2x) \in B_k$。故 $B_k$ 对任意左乘封闭。

合起来，$B_k$ 是包含 $\widetilde I$ 的左理想；但 $I = \langle \widetilde I \rangle$ 是这样的左理想中**最小**的一个，所以 $I \subseteq B_k$；另一方面 $B_k$ 由 $I$ 的元素经加法生成，$I$ 对加法封闭给出 $B_k \subseteq I$。两边夹逼即 $B_k = I$。Q.E.D.

(coset-hadamard-test)=
### 2.2 用量子方法检测 $rb \in B_k$

对每一对 $(r, b)$，如何判断 $rb$ 是否落在当前子群 $B_k$ 里？经典地，这需要枚举 $B_k$ 的元素；量子地，我们用**子群均匀态**。制备

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

即对 $B_k$ 中所有元素的均匀叠加。（如何制备：在第 3 节得到加法结构后这是标准的；在迭代过程中，也可以由生成集通过"随机组合 + 黑盒加法"的相干版本制备，详见 Wocjan 等人的论文。这里我们把它作为可调用的子程序。）

**Lemma 1（陪集的两种命运）**. 记加法平移 $T_{c}|x\rangle=|c+x\rangle$，其中 $c = rb$ 由乘法黑盒算出。则

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

**证明**。先看态变成了什么：$T_c|B_k\rangle = \frac{1}{\sqrt{|B_k|}}\sum_{x\in B_k}|c+x\rangle$，这是对集合 $c + B_k = \{c + x : x \in B_k\}$（即 $B_k$ 的**陪集**）的均匀叠加，即陪集态 $|c + B_k\rangle$。

再看陪集 $c + B_k$ 与 $B_k$ 作为**集合**的关系。若 $c \in B_k$：子群对加法封闭给出 $c + B_k \subseteq B_k$；而映射 $x \mapsto c + x$ 是 $B_k$ 到自身的双射（逆映射是 $y \mapsto y - c$，仍用了子群对取负与加法的封闭性），所以 $c + B_k = B_k$，两个态相等。

若 $c \notin B_k$：我们证明两个陪集**不相交**。反设存在 $x, y \in B_k$ 使 $c + x = y$，则 $c = y - x \in B_k$（子群对减法封闭），矛盾。因此 $c + B_k \cap B_k = \varnothing$，两个均匀叠加没有任何公共基矢，内积

$$
\langle B_k | c + B_k\rangle = \frac{1}{|B_k|}\sum_{x,y \in B_k}\langle x | c + y\rangle = 0,
$$

即两态正交。Q.E.D.

这个引理把代数问题"$c \in B_k$ 吗"翻译成了量子信息问题"两个态是相等还是正交"——这正是 **Hadamard 测试 (Hadamard test)** 的标准场景：用控制位的叠加制备 $\frac{1}{\sqrt2}(|0\rangle|B_k\rangle + |1\rangle T_c|B_k\rangle)$，对控制位再做一次 Hadamard 后测量，测得 $0$ 的概率为

$$
\frac{1}{2}\left(1 + \operatorname{Re}\langle B_k|T_c|B_k\rangle\right)
=
\begin{cases}
1, & c \in B_k,\\[2pt]
\frac12, & c \notin B_k.
\end{cases}
$$

两种情况的概率 $1$ 与 $\frac12$ 相差常数，重复 $O(1)$ 次即可以高概率区分。

(doubling-lemma)=
### 2.3 翻倍引理与轮数上界

若找到不属于 $B_k$ 的 $rb$，将它加入 $\widetilde B_k$，得到新子群 $B_{k+1} = \langle \widetilde B_k \cup \{rb\}\rangle_+$。它能比 $B_k$ 大多少？

**Lemma 2（严格扩张至少翻倍）**. 有限群中，若子群严格扩张，则大小至少增大一倍：

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

**证明**。这是 Lagrange 定理的直接推论。$B_k$ 是 $B_{k+1}$ 的子群，Lagrange 定理给出 $|B_{k+1}| = [B_{k+1} : B_k]\cdot|B_k|$，其中指数 $[B_{k+1}:B_k]$ 是 $B_k$ 在 $B_{k+1}$ 中不同陪集的个数，必为正整数。扩张是严格的（$rb \notin B_k$ 而 $rb \in B_{k+1}$），所以 $B_{k+1} \supsetneq B_k$，陪集至少有 $B_k$ 自身与 $rb + B_k$ 两个，即 $[B_{k+1}:B_k] \ge 2$。代入即得。Q.E.D.

因此迭代次数有干净的上界：从 $|B_1| \ge 1$ 出发，每轮至少翻倍，而任何时刻 $B_k \subseteq I$ 给出 $|B_k| \le |I|$，故最多 $\log_2|I|$ 轮就会停止；每轮只枚举多项式多的生成元对（$|\widetilde R| \cdot |\widetilde B_k| = \operatorname{poly}(\log|R|)$ 个），每对做 $O(1)$ 次 Hadamard 测试。整个第 2 节的总开销是 $\operatorname{poly}(\log|R|)$ 次黑盒调用。

值得停下来看一眼这个论证的结构：**"翻倍"贡献了 $\log$，"短生成集"贡献了每轮的多项式**——两处都依赖模型的前提，缺一不可。

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

第 2 节结束时，我们手里是 $(I,+)$ 的一个普通加法生成集——元素之间可能有冗余（比如 $\{4, 8\}$ 也生成 $\{0,4,8\}$，但 $8 = 4+4$ 是冗余的）。本节做两件事：先把生成集精炼成不变因子基 $h_j$ 与阶 $s_j$；再解决"给定黑盒标签 $i\in I$，求其坐标 $(n_1(i),\dots,n_\ell(i))$"的问题。坐标化是整个方案的枢纽：结构常数 $M_{ij}^k$ 不过是 $h_i h_j$ 的坐标，而第 4 节的所有应用都以坐标为语言。

### 3.1 从生成集到不变因子基

有限 Abel 群分解问题——给定一个有限 Abel 群的生成集（以及可相干计算的群运算），求其不变因子分解——是 Abelian HSP 量子算法的标准应用之一：对群的"关系格"（即满足 $\sum_j n_j g_j = 0$ 的指数向量 $(n_j)$ 构成的格）做傅里叶采样，用多项式次查询恢复一组基，再由经典后处理（整数矩阵的 Smith 标准形）整理出 $h_j$ 与 $s_j$。本站 Abelian HSP 教程中已给出一般框架，这里直接引用结论：**分解 $(I,+)$ 需要 $\operatorname{poly}(\log|I|)$ 次加法黑盒调用**。

(coordinate-hsp)=
### 3.2 坐标化：把"求坐标"写成一个 HSP

现在设已有不变因子基 $h_1,\dots,h_\ell$ 与阶 $s_1,\dots,s_\ell$，并给定元素 $i \in I$（一个黑盒标签）。由基表示的唯一性，存在唯一的坐标 $(n_1(i),\dots,n_\ell(i))$，$0 \le n_j(i) < s_j$，使

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

如何把这个隐藏在内的坐标向量挖出来？考虑群

$$
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),
$$

即：用坐标 $(n_1,\dots,n_\ell,m)$ 算出对应的环元素，再输出它的黑盒标签。$f$ 是可相干计算的：$\sum_j n_j h_j + mi$ 只需 $O(\ell)$ 次黑盒加法（甚至可用重复加倍加速），$\eta$ 就是编码本身。

**这个函数为什么隐藏一个子群？** 回忆 HSP 的框架：函数 $f$ 隐藏子群 $H \le G$，当且仅当 $f$ 在每个 $H$-陪集上取常值、在不同陪集上取不同值。由于编码 $\eta$ 是**唯一**的（模型前提在这里用上），$f$ 的值完全相同当且仅当环元素相同，即

$$
f(n_1,\dots,n_\ell,m) = f(n_1',\dots,n_\ell',m')
\;\Longleftrightarrow\;
\sum_j (n_j - n_j') h_j + (m - m') i = 0.
$$

所以 $f$ 的"层次集"结构由核

$$
H = \left\{(a_1,\dots,a_\ell,c) \in G :\ \sum_j a_j h_j + c\, i = 0\right\}
$$

决定：$f$ 在每个 $H$-陪集上取常值，且由编码唯一性，不同陪集对应不同标签。因此 $f$ 隐藏子群 $H$。

**隐藏子群长什么样？** 把 $i = \sum_j n_j(i) h_j$ 代入 $H$ 的定义式：

$$
\sum_j a_j h_j + c\sum_j n_j(i) h_j = \sum_j \bigl(a_j + c\, n_j(i)\bigr) h_j = 0.
$$

由不变因子基的线性无关性（坐标唯一），这个等式成立当且仅当每个分量分别为零：

$$
a_j \equiv -c\, n_j(i) \pmod{s_j},\qquad j = 1,\dots,\ell.
$$

也就是说，$H$ 恰好由向量

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

生成：任取 $c$，令 $a_j = -c\,n_j(i)$ 即得 $H$ 中元素；反之 $H$ 中任意元素都由此而来。$H$ 是 $G$ 中由这个单一生成元张成的循环子群。注意生成元的最后一个分量是 $-1$，而前 $\ell$ 个分量正是我们想要的坐标——**坐标向量把自己编码进了隐藏子群的生成元里**。

Abelian HSP 恢复该生成元，也就恢复 $i$ 的坐标。具体地说，对 $f$ 做傅里叶采样，每次测量得到一个与 $H$ 正交的特征标（即满足 $\sum_j a_j \chi_j - c\,\chi_{m} \equiv 0$ 的对偶向量），采样 $O(\ell)$ 次后以高概率张成 $H$ 的零化子，解这个模线性方程组即得生成元 $(n_1(i),\dots,n_\ell(i),-1)$。寄存器长度为 $\log|G| = O(\log|I|)$，QFT 与采样的总开销为 $\operatorname{poly}(\log|I|)$。

### 3.3 回填乘法：结构常数

最后一步把乘法翻译到坐标上。对所有 $\ell^2$ 对基元素 $(h_i, h_j)$：

1. 调用乘法黑盒计算 $h_i h_j$（理想对左乘封闭保证 $h_i h_j \in I$）；
2. 对结果元素跑 3.2 节的坐标化 HSP，读出它的坐标 $(M_{ij}^{1},\dots,M_{ij}^{\ell})$。

这就得到整个张量 $M_{ij}^{k}$。由于 $\ell = O(\log|I|)$，需要坐标化的元素只有 $O(\log^2|I|)$ 个，每个花费 $\operatorname{poly}(\log|I|)$，总开销仍是 $\operatorname{poly}(\log|R|)$。至此基表示的三部分全部到手。

回顾一下这一节的手法：**我们没有发明任何新算法，而是把"求坐标"精心包装成一个具体的隐藏子群函数**。包装的关键设计是往群里多加一个分量 $\mathbb Z_s$ 并配上系数 $m$——正是这个 $m$ 让 $i$ 本身参与函数值，从而把 $i$ 的坐标"逼"进了隐藏子群的生成元。这是把代数问题归约为 HSP 的典型技巧。

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

有了基表示，一大批理想问题迎刃而解。本节逐个过一遍，重点说明每个归约为什么正确。

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

给定 $a \in R$，判断 $a \in I$ 是否成立。制备陪集态

$$
|a+I\rangle = \frac{1}{\sqrt{|I|}}\sum_{x\in I}|a+x\rangle
$$

（由第 3 节的不变因子基，对坐标均匀采样再经黑盒加法即可制备）。由 Lemma 1，$|a+I\rangle$ 与 $|I\rangle$ 相同当且仅当 $a\in I$，否则两态正交——成员判定就是一次 Hadamard 测试。也可以完全走经典路线：对 $a$ 做坐标化（3.2 节的 HSP 对任意 $a \in R$ 都适用，只是隐藏子群的定义换成相对于 $I$ 的），$a \in I$ 当且仅当它的坐标全落在 $I$ 的坐标范围内。

理想相等 $I \stackrel{?}{=} J$ 有两个判法：其一，制备两者的均匀态 $|I\rangle$、$|J\rangle$，估计 overlap $|\langle I|J\rangle|^2$——若 $I = J$ 则重叠为 $1$，否则（一者是另一者的真子群，或互不包含）重叠至多为 $\frac12$，因为 $|I \cap J| \le \frac12 \max(|I|,|J|)$（还是 Lagrange 定理：真子群指数至少为 2）；其二，直接比较两个不变因子基——对 $J$ 的每个基元素 $h_j^J$ 判定它是否属于 $I$，反之亦然，$2\ell$ 次成员判定即可。

### 4.2 理想的交与商

**交** $I \cap J$ 也能写成一个 HSP。定义映射：对 $x\in I$，输出量子态

$$
|x+J\rangle.
$$

（精确地说，在第一个寄存器上制备 $|I\rangle$ 中元素，第二个寄存器上制备对应的陪集态。）同一陪集对应相同状态，不同陪集正交——这正是 Lemma 1 的结论。换句话说，$x \mapsto |x + J\rangle$ 作为 $I$ 的加法群上的函数，在 $x, x' \in I$ 上取相同值当且仅当 $x + J = x' + J$，即 $x - x' \in J$，即 $x - x' \in I \cap J$（注意 $x - x' \in I$ 自动成立）。所以该映射隐藏加法子群 $I\cap J$；Abelian HSP 直接给出交的生成元。交作为加法群是隐藏的——这是"陪集态编码商结构"的又一例：$I/(I\cap J)$ 的每个元素对应一个正交态。

**商理想（理想的冒号）**

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

可用多个陪集寄存器隐藏：对 $J$ 的每个生成元 $g_t$，条件化地制备 $|x g_t + I\rangle$。这些态同时与 $|I\rangle^{\otimes}$ 相同，当且仅当每个 $xg_t \in I$；而 $J$ 由 $\{g_t\}$ 生成，分配律把"$xg_t \in I$ 对所有生成元成立"扩展为"$xJ \subseteq I$"（与 2.1 节判据的扩展论证完全平行）。因此这个多寄存器函数隐藏子群 $(I:J)$，HSP 再次给出答案。

### 4.3 单位与逆元

元素 $r$ 为单位（存在 $r^{-1}$ 使 $r r^{-1} = r^{-1} r = 1$）当且仅当它生成的左理想 $Rr$ 等于 $R$。为什么？若 $r$ 是单位，则任意 $s \in R$ 可写成 $s = (sr^{-1})r \in Rr$，故 $Rr = R$；反之若 $Rr = R$，则 $1 \in Rr$，即存在 $s$ 使 $sr = 1$——在**有限**环中，左逆自动是双边逆（左乘 $s$ 的映射是有限集上的单射从而是双射），故 $r$ 是单位。

于是单位判定流程是：先分别求 $Rr$ 与 $R$ 的基表示（$Rr$ 由单个生成元 $r$ 生成，$R$ 由 $\widetilde R$ 生成，都走第 2、3 节的流程）并比较（4.1 节的方法）；若相等，$r$ 是单位。进一步求逆元：在有限环中乘法幂序列 $r, r^2, r^3, \dots$ 最终循环，$r$ 作为乘法可逆元的阶 $c$ 可以用量子阶查找（与 Shor 算法中的阶查找相同）求得，于是

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

因为 $r^{c-1}\cdot r = r^c = 1$。阶查找的寄存器长度为 $O(\log|R|)$，乘法黑盒提供了所需的受控幂运算。

(ideal-linear-equation)=
### 4.4 环上线性方程

最后看一个综合性例子：给定 $a, b \in I$，解方程 $ax = b$，其中 $x \in I$。把三个元素都在基表示下展开（$a, b$ 的坐标由 3.2 节的坐标化得到）：

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

代入方程并用分配律与结构常数展开左边：

$$
ax = \left(\sum_i a_i h_i\right)\left(\sum_j x_j h_j\right)
= \sum_{i,j} a_i x_j\, h_i h_j
= \sum_{i,j,k} a_i x_j M_{ij}^{k} h_k
= \sum_k \left(\sum_{i,j} M_{ij}^{k} a_i x_j\right) h_k.
$$

第二个等号用分配律把双重求和提出，第三个等号代入 $h_i h_j = \sum_k M_{ij}^k h_k$。由不变因子基的坐标唯一性，$ax = b$ 当且仅当两边每个坐标分量相等（注意 $x_j$ 是模 $s_j$ 的未知数，分量比较在模 $s_k$ 意义下进行）：

$$
\sum_{i,j} M_{ij}^{k} a_i\, x_j\equiv b_k\pmod{s_k},\qquad k = 1,\dots,\ell.
$$

把 $A_{kj} := \sum_i M_{ij}^{k} a_i$（已知常数，因为 $M$ 与 $a$ 的坐标都已知）合并，这就是

$$
\sum_j A_{kj}x_j\equiv b_k\pmod{s_k}.
$$

加入松弛变量（把模 $s_k$ 的同余写成等式 $\sum_j A_{kj} x_j + s_k y_k = b_k$）后，这是经典整数线性丢番图方程组，可用 Hermite/Smith 标准形在多项式时间求解——方程个数与未知数个数都是 $O(\log|I|)$，系数位长也是多项式的，故整个后处理在 $\operatorname{poly}(\log|R|)$ 经典时间内完成。这个例子最能体现整套方案的哲学：**量子部分负责从黑盒标签提取结构（基、阶、坐标、乘法张量），后处理则是经典线性代数**。

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

用一个可手算的小例子把全流程过一遍。取交换环 $R=\mathbb Z_{12}$（整数模 12 的剩余类环，$|R| = 12$），理想由单个元素生成：

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

验证它确是理想：它对加法封闭（$4+4=8$，$4+8=12\equiv 0$，$8+8=16\equiv 4$）；对任意左乘封闭，因为任意 $r \cdot 4 = 4r$ 是 4 的倍数，而 4 的倍数模 12 只有 $0, 4, 8$。

**第一步：扩张加法生成元（第 2 节）**。取 $\widetilde R = \{1\}$（1 生成整个环）与 $\widetilde B_1 = \widetilde I = \{4\}$。此时 $B_1 = \langle 4\rangle_+ = \{0,4,8\}$。检查判据：$r b = 1\cdot 4 = 4 \in B_1$，封闭性成立，故 $B_1 = I$，一轮即终止。注意这个例子里 $B_1$ 一步就达到 $I$：因为 $|I| = 3$ 是素数，$(I,+)$ 没有非平凡子群，任何非零生成元都直接生成整个理想；翻倍引理 $|B_{k+1}| \ge 2|B_k|$ 给出的只是下界，实际扩张可以更快（例如从平凡子群 $\{0\}$ 加入一个非零元素，大小直接从 1 跳到 3）。

**第二步：不变因子基（第 3 节）**。作为加法群，$I$ 由 $h=4$ 生成且阶为 3（$4+4+4 = 12 \equiv 0$，而 $4, 8 \ne 0$），所以

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

不变因子基为 $h_1 = 4$，$s_1 = 3$。理想中每个元素的坐标：$0 = (0)$，$4 = (1)$，$8 = (2)$。

**坐标化演示**。以 $i = 8$ 为例走一遍 3.2 节的构造。$i$ 的加法阶为 $s = 3$，故

$$
G = \mathbb Z_3 \times \mathbb Z_3,\qquad
f(n_1, m) = \eta(4n_1 + 8m \bmod 12).
$$

把 $f$ 的取值表列出来（$4n_1 + 8m \bmod 12$）：

- $m = 0$：$n_1 = 0,1,2$ 给出 $0, 4, 8$；
- $m = 1$：$n_1 = 0,1,2$ 给出 $8, 0, 4$；
- $m = 2$：$n_1 = 0,1,2$ 给出 $4, 8, 0$。

可以看到 $f$ 只取三个值 $0, 4, 8$，每个值恰好被三个输入取到。先按 3.2 节的公式写出隐藏子群：$i = 8$ 的坐标是 $n_1(i) = 2$，故 $H$ 由 $(n_1(i), -1) = (2, -1) \equiv (2, 2) \pmod 3$ 生成，即

$$
H = \{(0,0),\ (2,2),\ (4,4)\equiv(1,1)\}.
$$

逐项验证 $f$ 在 $H$ 的每个陪集上取常值。陪集 $(0,0) + H$ 的三个输入给出的函数值分别是 $f(0,0) = 0$、$f(2,2) = 4\cdot 2 + 8\cdot 2 = 24 \equiv 0$、$f(1,1) = 4 + 8 = 12 \equiv 0$——全为 $0$，吻合；陪集 $(1,0) + H = \{(1,0), (0,2), (2,1)\}$ 给出 $f(1,0) = 4$、$f(0,2) = 16 \equiv 4$、$f(2,1) = 16 \equiv 4$——全为 $4$，同样吻合。而且 $f = 0$ 的输入集合恰好就是 $H$ 本身，不同陪集对应不同标签，隐藏子群的定义逐条满足。HSP 恢复生成元 $(2, -1)$，第一个分量 $2$ 正是 $i = 8$ 的坐标（$8 = 2\cdot 4$）。

**第三步：结构常数**。只有一个基元素，故只需求 $h^2$ 的坐标：

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

故唯一结构常数是 $M_{11}^{1}=1\pmod3$。乘法表的全部信息就是"坐标相乘后在模 3 下不变"：$(n_1) \cdot (n_2) = (n_1 n_2 \bmod 3)$。

**应用演示（第 4 节）**。成员关系：陪集 $2+I=\{2,6,10\}$ 与 $I$ 不相交，立即证明 $2\notin I$；而 $8+I=\{8,0,4\}=I$，证明 $8\in I$。线性方程：解 $4x = 8$。坐标化给出 $a = 1$，$b = 2$，同余式为 $M_{11}^1 a\, x_1 \equiv b \pmod 3$，即 $x_1 \equiv 2 \pmod 3$，对应 $x = 2\cdot 4 = 8$。验证：$4\cdot 8 = 32 \equiv 8 \pmod{12}$，正确。

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

### 6.1 复杂度逐项清点

把全流程的开销按来源拆开，确认每一项都是 $\operatorname{poly}(\log|R|)$：

- **第 2 节扩张**：轮数至多 $\log_2|I| \le \log_2|R|$（翻倍引理）；每轮检查 $|\widetilde R|\cdot|\widetilde B_k|$ 对，两个因子都是 $O(\log|R|)$（短生成集假设；$|\widetilde B_k|$ 每轮至多增加 1，故也不超过 $O(\log|R|)$）；每对 $O(1)$ 次 Hadamard 测试，每次测试 $O(1)$ 次黑盒调用。合计 $\operatorname{poly}(\log|R|)$。
- **第 3 节分解与坐标化**：Abelian HSP 的寄存器长度为 $\log|G| = O(\log|I|)$，傅里叶采样次数与 QFT 门数都是该长度的多项式；对每个待坐标化的元素调用一次。结构常数需要坐标化 $\ell^2 = O(\log^2|I|)$ 个乘积。合计 $\operatorname{poly}(\log|R|)$。
- **第 4 节应用**：成员判定、交、商都是常数次 HSP 或 Hadamard 测试；单位判定多一次阶查找；线性方程的后处理是 $O(\log|I|)$ 阶整数矩阵的 Hermite/Smith 标准形，经典多项式时间。

轮数、生成元数和 Abelian HSP 寄存器长度都关于 $\log|R|$ 为多项式，前提是唯一编码、相干加乘黑盒和短生成集可用。**这三个前提各自在哪里被用到，值得对照检查**：唯一编码保证了"标签相同 $\Leftrightarrow$ 元素相同"，这是 3.2 节隐藏子群良定义的前提；相干黑盒保证了子群态、陪集态与平移算子可以制备与施加；短生成集保证了第 2 节每轮的枚举量与 HSP 函数的可构造性。

若元素编码不唯一，两个不同标签可能代表同一元素，后果是连锁的：陪集态 $|a + I\rangle$ 与 $|I\rangle$ 即使作为集合相同，其叠加也可能因标签不同而不再相等（正交性论证失效）；隐藏子群函数 $f$ 会在理应相同的元素上输出不同标签（隐藏子群结构被破坏）。整条流水线随之崩溃——这不是技术上的困难，而是模型假设的本质之处。类似地，若只有经典（非相干）黑盒，子群态无法制备；若没有短生成集，连要检查的封闭性条件的个数都无法控制。

### 6.2 不能推出的结论

同样重要的是说清楚这套算法**不**做什么。

这些算法不自动解决环同构、环自同构或任意无限环问题，也不等于把非交换乘法群当作 Abelian 群。环同构判定需要比较两个环的全部结构，而本课的基表示是针对"给定环内部的理想"的；无限环则连"有限 Abel 群分解"这一出发点都不存在。尤其要避免一个误读：算法**从未**假设乘法可交换或乘法群是 Abel 的——非交换性完全被吸收进结构常数 $M_{ij}^k$ 中（$M_{ij}^k$ 与 $M_{ji}^k$ 可以不同）。量子优势来自每个理想天然具有 Abelian **加法**结构，以及乘法可通过有限结构常数回填。

另外，与第 4.3 节单位判定相关的阶查找继承了 Shor 类算法的一切标准注意事项；而 4.2 节商理想等构造中"用多个陪集寄存器隐藏"的开销随 $J$ 的生成元个数线性增长，在短生成集假设下仍是多项式的。

## 7. 小结

本课的要点可以压缩为四条：

- 先检测当前加法子群是否对环生成元左乘封闭（2.1 节判据把对全环的全称条件归约为对生成元对的有限检查）。
- 每次加入新元素至少使子群大小翻倍（Lagrange 定理），因此迭代次数为对数级。
- Abelian HSP 给出不变因子基、元素坐标和乘法张量——坐标化通过往群上附加一个 $\mathbb Z_s$ 分量实现，坐标藏身于隐藏循环子群的生成元中。
- 大量理想问题随后化为陪集 HSP（成员、相等、交、商）或经典丢番图方程（线性方程）；量子负责提取结构，经典负责线性代数。

## 练习题

**练习 1【环、左理想与生成理想】**（→ [1.1 节](#ring-left-ideal)）

1. 写出带幺环的三组公理与左理想的两条封闭性，并用一句话说明左理想与普通加法子群的本质区别。
2. 在 $\mathbb Z_{12}$ 中计算由 $S=\{8\}$ 生成的左理想 $\langle S\rangle$ 的全部元素，验证它与 $\langle\{4\}\rangle$ 相等，并说明它为何对任意左乘封闭。
3. 证明生成理想的显式形式 $\langle S\rangle=\{\sum_{k=1}^{t}r_ks_k\}$ 确是包含 $S$ 的最小左理想。

> 提示：先验证该集合包含 $S$ 且对减法、任意左乘封闭；再证任何包含 $S$ 的左理想都对上述有限和封闭。

**练习 2【黑盒模型的三前提】**（→ [1.2 节](#black-box-model)）

1. 列出黑盒模型的三项前提，并各用一句话说明：若去掉它，正文流水线中的哪一步会率先失效。
2. （模型依赖）假设编码不唯一：元素 $a$ 可能有两个标签 $\eta_1(a) \ne \eta_2(a)$。具体说明 3.2 节的函数 $f$ 为什么不再隐藏任何子群（构造一个反例：同一 $H$-陪集上的两个输入使 $f$ 取不同值）。

> 提示：让同一陪集上的两个输入算出同一个环元素，但输出它的两种不同标签即可。

**练习 3【基表示与结构常数】**（→ [1.3 节](#basis-representation)）

1. 写出基表示的三个组成部分，并说明结构常数为何只有 $\ell^3$ 个、且 $\ell \le \log_2|I|$。
2. 设 $x=\sum_i x_ih_i$、$y=\sum_j y_jh_j$，用分配律推导坐标乘法公式 $xy=\sum_k\bigl(\sum_{i,j}M_{ij}^{k}x_iy_j\bigr)h_k$。
3. （不变因子计算）在 $\mathbb Z_{18}$ 中求理想 $(6)$ 的不变因子表示（基元素、阶、结构常数），并列出它的所有加法陪集。

> 提示：$(6)=\{0,6,12\}$，且 $h^2=36\equiv 0\pmod{18}$；陪集个数为 $|R|/|I|=6$。

**练习 4【理想封闭性判据】**（→ [2.1 节](#closure-criterion)）

1. 陈述封闭性判据 $B_k=I\iff rb\in B_k\ (\forall r\in\widetilde R,\ b\in\widetilde B_k)$，并指出右边共需检查多少对生成元、为什么这只是 $\operatorname{poly}(\log|R|)$ 量级。
2. （封闭性扩展）证明 $rb\in B$ 对生成元 $r\in\widetilde R,\ b\in\widetilde B$ 成立时，$B$ 对任意环元素左乘封闭。要求：只用两条分配律与生成性，写清归纳的载体是什么。

> 提示：对"构造 $r$ 所用的运算次数"归纳，和与积两种情形分别用一条分配律。

**练习 5【陪集态与 Hadamard 测试】**（→ [2.2 节](#coset-hadamard-test)）

1. 写出子群均匀态 $|B_k\rangle$ 的定义，并分别计算 $c\in B_k$ 与 $c\notin B_k$ 时 $\langle B_k|T_c|B_k\rangle$ 的值。
2. 写出 Hadamard 测试中测得 $0$ 的概率公式，代入上题结果说明两种情形的概率分别为 $1$ 与 $\tfrac12$，并解释为何重复 $O(1)$ 次即可高概率区分。
3. （陪集引理）证明 $a+I$ 与 $I$ 要么相同要么不相交，并进一步证明：$I$ 的所有不同加法陪集构成 $R$ 的一个划分，每个陪集大小都等于 $|I|$。

> 提示：若 $c+x=y$ 则 $c=y-x\in I$；平移 $x\mapsto a+x$ 是保持基矢个数不变的双射。

**练习 6【翻倍引理与轮数上界】**（→ [2.3 节](#doubling-lemma)）

1. 由 Lagrange 定理证明：有限群中子群的严格扩张至少翻倍，即 $|B_{k+1}|\ge 2|B_k|$。
2. 把轮数上界 $\log_2|I|$、每轮检查的生成元对数与每对的 $O(1)$ 次 Hadamard 测试相乘，推导第 2 节总开销为 $\operatorname{poly}(\log|R|)$，并指出推导中用到了哪两条模型前提。

> 提示：每轮对数 $|\widetilde R|\cdot|\widetilde B_k|$ 是 $O(\log|R|)$ 依赖短生成集；概率 $1$ 与 $\tfrac12$ 的常数间隙依赖相干黑盒能制备陪集态。

**练习 7【坐标化的 HSP 构造】**（→ [3.2 节](#coordinate-hsp)）

1. 写出坐标化所用的群 $G=\mathbb Z_{s_1}\times\cdots\times\mathbb Z_{s_\ell}\times\mathbb Z_s$ 与函数 $f$ 的定义，并说明 $f$ 为何只需 $O(\ell)$ 次黑盒加法即可相干计算。
2. 推导隐藏子群 $H=\{(a_1,\dots,a_\ell,c):\ \sum_j a_jh_j+ci=0\}$ 恰由 $(n_1(i),\dots,n_\ell(i),-1)$ 生成，并指出坐标唯一性在哪一步用到。
3. （坐标化构造）在 $\mathbb Z_{12}$ 的理想 $(4)$ 中，对元素 $i = 4$ 写出 3.2 节的群 $G$、函数 $f$ 与隐藏子群 $H$ 的生成元，并验证 $f$ 在 $H$ 的每个陪集上取常值。

> 提示：$i=4$ 的坐标是 $1$，故 $H$ 由 $(1,-1)$ 生成；仿照正文 $i=8$ 的取值表逐一核对。

**练习 8【环上线性方程的求解】**（→ [4.4 节](#ideal-linear-equation)）

1. 把 $ax=b$ 的两边按不变因子基展开，推导坐标同余式 $\sum_j A_{kj}x_j\equiv b_k\pmod{s_k}$（其中 $A_{kj}=\sum_i M_{ij}^{k}a_i$），并说明加入松弛变量后为何得到可经典求解的整数线性方程组。
2. （线性方程）用结构常数写出 $\mathbb Z_{12}$ 的理想 $(4)$ 内方程 $4x=8$ 的坐标同余式并求解；再讨论：方程 $4x = 4$ 在 $I$ 内有几个解？这与坐标同余式的解的个数如何对应？

> 提示：同余式是模 $s_1=3$ 的一元方程，$I$ 中每个元素恰对应一个坐标，故两边解数相同。

## 参考文献

- 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.