有限黑盒环与理想

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

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

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

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

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

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

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

1. 黑盒模型与输出格式

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$ 生成的左理想 $⟨S⟩$ 定义为包含 $S$ 的所有左理想的交——等价地说，它是包含 $S$、对加法和任意左乘封闭的最小集合。它的显式形式是

$$⟨S⟩=\left\{\sum _{k=1}^t{r}_k{s}_k:t\ge 0,r_k\in R,s_k\in S\right\},$$

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

1.2 黑盒模型

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

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

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

$$|a,b,0⟩\mapsto |a,b,a+b⟩,|a,b,0⟩\mapsto |a,b,ab⟩.$$

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

短生成集。输入还包括环生成集 $\tilde{R}$ 和左理想生成集

$$\tilde{I}=\{i_1,\dots ,i_m\},$$

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

1.3 目标：基表示

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

1. 加法群的不变因子生成元 $h_1,\dots ,h_{\ell }$；
2. 各生成元的加法阶 $s_1,\dots ,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,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. 从理想生成元扩张出加法生成元

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

2.1 封闭性判据

先令 ${\tilde{B}}_1=\tilde{I}$，$B_k=⟨{\tilde{B}}_k{⟩}_{+}$ 为当前生成的加法子群（即 ${\tilde{B}}_k$ 中元素的一切有限和与差）。关键判据是：

$$B_k=I⟺rb\in B_k\forall r\in \tilde{R},b\in {\tilde{B}}_k.$$

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

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

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

第一步，从生成元扩展到整个 $B_k$。任取 $x\in B_k$ 与 $r\in \tilde{R}$。由 $B_k=⟨{\tilde{B}}_k{⟩}_{+}$ 的定义，$x$ 是 ${\tilde{B}}_k$ 中元素的有限和：$x={\sum }_t\pm b_t$，其中 $b_t\in {\tilde{B}}_k$。由左分配律，

$$rx=r\sum _t(\pm b_t)=\sum _t(\pm r{b}_t).$$

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

第二步，从 $\tilde{R}$ 扩展到整个 $R$。任取 $r\in R$ 与 $x\in B_k$。由 $\tilde{R}$ 的生成性，$r$ 可由 $\tilde{R}$ 中元素经加法与乘法得到。我们对”构造 $r$ 所用的运算次数”归纳：若 $r\in \tilde{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_{2}x)\in B_k$。故 $B_k$ 对任意左乘封闭。

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

2.2 用量子方法检测 $rb\in B_k$

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

$$|B_k⟩=\frac{1}{\sqrt{|B_k|}}\sum _{x\in B_k}|x⟩,$$

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

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

$$T_c|B_k⟩=\{\begin{array}{ll}|B_k⟩,& c\in B_k,\\ |c+B_k⟩\perp |B_k⟩,& c\notin B_k.\end{array}$$

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

再看陪集 $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$，两个均匀叠加没有任何公共基矢，内积

$$⟨B_k|c+B_k⟩=\frac{1}{|B_k|}\sum _{x,y\in B_k}⟨x|c+y⟩=0,$$

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

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

$$\frac{1}{2}\left(1+\mathrm{Re}⟨B_k|T_c|B_k⟩\right)=\{\begin{array}{ll}1,& c\in B_k,\\ \frac{1}{2},& c\notin B_k.\end{array}$$

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

2.3 翻倍引理与轮数上界

若找到不属于 $B_k$ 的 $rb$，将它加入 ${\tilde{B}}_k$，得到新子群 $B_{k+1}=⟨{\tilde{B}}_k\cup \{rb\}{⟩}_{+}$。它能比 $B_k$ 大多少？

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

$$|B_{k+1}|\ge 2|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}⊋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|$ 轮就会停止；每轮只枚举多项式多的生成元对（$|\tilde{R}|\cdot |{\tilde{B}}_k|=\mathrm{poly}(\log |R|)$ 个），每对做 $O(1)$ 次 Hadamard 测试。整个第 2 节的总开销是 $\mathrm{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,+)$ 需要 $\mathrm{poly}(\log |I|)$ 次加法黑盒调用。

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,\dots ,n_{\ell },m)=\eta \left(\sum _j{n}_j{h}_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^{\prime },\dots ,n_{\ell }^{\prime },m^{\prime })⟺\sum _j(n_j-n_j^{\prime })h_j+(m-m^{\prime })i=0.$$

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

$$H=\left\{(a_1,\dots ,a_{\ell },c)\in G:\sum _j{a}_j{h}_j+ci=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(a_j+c{n}_j(i))h_j=0.$$

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

$$a_j\equiv -c{n}_j(i)(\mathrm{mod}{s}_j),j=1,\dots ,\ell .$$

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

$$(n_1(i),\dots ,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 与采样的总开销为 $\mathrm{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|)$ 个，每个花费 $\mathrm{poly}(\log |I|)$，总开销仍是 $\mathrm{poly}(\log |R|)$。至此基表示的三部分全部到手。

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

4. 基表示支持哪些算法

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

4.1 成员关系与理想相等

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

$$|a+I⟩=\frac{1}{\sqrt{|I|}}\sum _{x\in I}|a+x⟩$$

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

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

4.2 理想的交与商

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

$$|x+J⟩.$$

（精确地说，在第一个寄存器上制备 $|I⟩$ 中元素，第二个寄存器上制备对应的陪集态。）同一陪集对应相同状态，不同陪集正交——这正是 Lemma 1 的结论。换句话说，$x\mapsto |x+J⟩$ 作为 $I$ 的加法群上的函数，在 $x,x^{\prime }\in I$ 上取相同值当且仅当 $x+J=x^{\prime }+J$，即 $x-x^{\prime }\in J$，即 $x-x^{\prime }\in I\cap J$（注意 $x-x^{\prime }\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⟩$。这些态同时与 $|I{⟩}^{\otimes }$ 相同，当且仅当每个 $x{g}_t\in I$；而 $J$ 由 $\{g_t\}$ 生成，分配律把”$x{g}_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=(s{r}^{-1})r\in Rr$，故 $Rr=R$；反之若 $Rr=R$，则 $1\in Rr$，即存在 $s$ 使 $sr=1$——在有限环中，左逆自动是双边逆（左乘 $s$ 的映射是有限集上的单射从而是双射），故 $r$ 是单位。

于是单位判定流程是：先分别求 $Rr$ 与 $R$ 的基表示（$Rr$ 由单个生成元 $r$ 生成，$R$ 由 $\tilde{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|)$，乘法黑盒提供了所需的受控幂运算。

4.4 环上线性方程

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

$$a=\sum _i{a}_i{h}_i,b=\sum _i{b}_i{h}_i,x=\sum _j{x}_j{h}_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(\mathrm{mod}{s}_k),k=1,\dots ,\ell .$$

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

$$\sum _j{A}_{kj}{x}_j\equiv b_k(\mathrm{mod}{s}_k).$$

加入松弛变量（把模 $s_k$ 的同余写成等式 ${\sum }_j{A}_{kj}{x}_j+s_k{y}_k=b_k$）后，这是经典整数线性丢番图方程组，可用 Hermite/Smith 标准形在多项式时间求解——方程个数与未知数个数都是 $O(\log |I|)$，系数位长也是多项式的，故整个后处理在 $\mathrm{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 节）。取 $\tilde{R}=\{1\}$（1 生成整个环）与 ${\tilde{B}}_1=\tilde{I}=\{4\}$。此时 $B_1=⟨4{⟩}_{+}=\{0,4,8\}$。检查判据：$rb=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,f(n_1,m)=\eta (4n_1+8m\mathrm{mod}12).$$

把 $f$ 的取值表列出来（$4n_1+8m\mathrm{mod}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)(\mathrm{mod}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\equiv 4=h(\mathrm{mod}12),$$

故唯一结构常数是 $M_{11}^1=1(\mathrm{mod}3)$。乘法表的全部信息就是”坐标相乘后在模 3 下不变”：$(n_1)\cdot (n_2)=(n_1{n}_2\mathrm{mod}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(\mathrm{mod}3)$，即 $x_1\equiv 2(\mathrm{mod}3)$，对应 $x=2\cdot 4=8$。验证：$4\cdot 8=32\equiv 8(\mathrm{mod}12)$，正确。

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

6.1 复杂度逐项清点

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

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

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

若元素编码不唯一，两个不同标签可能代表同一元素，后果是连锁的：陪集态 $|a+I⟩$ 与 $|I⟩$ 即使作为集合相同，其叠加也可能因标签不同而不再相等（正交性论证失效）；隐藏子群函数 $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. （封闭性扩展）证明 $rb\in B$ 对生成元 $r\in \tilde{R},b\in \tilde{B}$ 成立时，$B$ 对任意环元素左乘封闭。要求：只用两条分配律与生成性，写清归纳的载体是什么。
2. （不变因子计算）在 ${\mathbb{Z}}_{18}$ 中求理想 $(6)$ 的不变因子表示（基元素、阶、结构常数），并列出它的所有加法陪集。
3. （陪集引理）证明 $a+I$ 与 $I$ 要么相同要么不相交，并进一步证明：$I$ 的所有不同加法陪集构成 $R$ 的一个划分，每个陪集大小都等于 $|I|$。
4. （坐标化构造）在 ${\mathbb{Z}}_{12}$ 的理想 $(4)$ 中，对元素 $i=4$ 写出 3.2 节的群 $G$、函数 $f$ 与隐藏子群 $H$ 的生成元，并验证 $f$ 在 $H$ 的每个陪集上取常值。
5. （线性方程）用结构常数写出 ${\mathbb{Z}}_{12}$ 的理想 $(4)$ 内方程 $4x=8$ 的坐标同余式并求解；再讨论：方程 $4x=4$ 在 $I$ 内有几个解？这与坐标同余式的解的个数如何对应？
6. （模型依赖）假设编码不唯一：元素 $a$ 可能有两个标签 ${\eta }_1(a)\ne {\eta }_2(a)$。具体说明 3.2 节的函数 $f$ 为什么不再隐藏任何子群（构造一个反例：同一 $H$-陪集上的两个输入使 $f$ 取不同值）。

参考文献

• Zoo 编号 118：Pawel Wocjan、Stephen Jordan、Hamed Ahmadi 与 Joseph Brennan, Efficient Quantum Processing of Ideals in Finite Rings（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.

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch09-algebra-number-theory/finite-rings-ideals
• 内容遵循 CC BY-NC-SA 4.0 许可协议