数域的单位群与类群：隐藏格上的量子算法

Pell 方程只有一个实周期；一般数域则出现多维周期格。本课先用 Dirichlet 单位定理把单位群变成欧氏空间中的格，再推导量子傅里叶采样如何恢复其对偶格，最后说明单位群、主理想问题与类群计算为何层层相依。

1. 三个代数对象

设 \(K=\mathbb Q(\theta)\) 是 \(d\) 次数域，\(\mathcal O_K\) 是其整数环。

单位群由可逆代数整数构成：

\[ \mathcal O_K^\times=\{u\in\mathcal O_K:\exists v\in\mathcal O_K,uv=1\}. \]

若 \(K\) 有 \(r_1\) 个实嵌入和 \(r_2\) 对共轭复嵌入，则 \(d=r_1+2r_2\)。Dirichlet 单位定理给出

\[ \mathcal O_K^\times\cong\mu(K)\times\mathbb Z^r, \qquad r=r_1+r_2-1, \]

其中 \(\mu(K)\) 是有限的单位根群。计算单位群，就是找出扭转部分和 \(r\) 个基本单位。

主理想问题判断给定理想 \(I\) 是否属于

\[ P_K=\{(\alpha):\alpha\in K^\times\}, \]

并在答案为是时恢复生成元。理想类群则是

\[ \operatorname{Cl}(K)=I_K/P_K, \]

它把相差一个主理想的分式理想视为同一类，是有限 Abel 群。目标通常是输出不变量分解

\[ \operatorname{Cl}(K)\cong \mathbb Z/n_1\mathbb Z\times\cdots\times\mathbb Z/n_s\mathbb Z. \]

2. 对数嵌入把单位变成格

记实嵌入为 \(\sigma_1,\ldots,\sigma_{r_1}\)，从每对复嵌入中取一个代表。定义

\[ L(u)=\bigl(\log|\sigma_1(u)|,\ldots, \log|\sigma_{r_1}(u)|, 2\log|\sigma_{r_1+1}(u)|,\ldots\bigr). \]

代数范数满足 \(|N_{K/\mathbb Q}(u)|=1\)，故坐标和为零。所有 \(L(u)\) 落在 \(r\) 维超平面

\[ H=\{x:\textstyle\sum_i x_i=0\} \]

中，并形成满秩格 \(\Lambda=L(\mathcal O_K^\times)\)。格的基本平行体体积是调节子 \(R_K\)。因此单位群计算可重述为：恢复未知实格 \(\Lambda\) 的一组基。

例：\(K=\mathbb Q(\sqrt5)\) 的整数环是 \(\mathbb Z[(1+\sqrt5)/2]\)。令 \(\varphi=(1+\sqrt5)/2\)，则

\[ \mathcal O_K^\times=\{\pm\varphi^k:k\in\mathbb Z\}. \]

两个实嵌入把 \(\varphi\) 送到 \(\varphi\) 与 \(-1/\varphi\)，所以

\[ L(\varphi)=(\log\varphi,-\log\varphi). \]

这正是上一课一维周期在二维和为零超平面中的写法。

3. 从隐藏周期到隐藏格

固定次数算法构造可计算函数 \(f:\mathbb R^r\to\mathcal S\)，其输出是与缩放格 \(e^x\mathcal O_K\) 关联的约化理想及局部几何信息，并满足近似周期关系

\[ f(x+\lambda)=f(x),\qquad \lambda\in\Lambda. \]

在细网格上量子并行计算 \(f\)，测量函数值后得到位于某个陪格附近的叠加态。多维 QFT 把空间周期转成频率样本

\[ y\approx\lambda^*,\qquad \lambda^*\in\Lambda^* =\{y:\langle y,\lambda\rangle\in\mathbb Z, \ \forall\lambda\in\Lambda\}. \]

收集足够多的近似对偶向量，用经典格规约求 \(\Lambda^*\) 的基，再求对偶便得到 \(\Lambda\)。最后把每个格基向量反解成基本单位。这个过程和一维周期查找完全同构，但多了三个困难：

  1. 傅里叶峰是对偶格而非等间隔整数；

  2. 约化理想的表示存在舍入噪声；

  3. 维数增长会放大坏边界与采样误差。

Hallgren 的早期算法因此先处理固定次数数域。Eisenträger、Hallgren、Kitaev 与 Song 后来使用满足 Lipschitz 条件的连续 HSP 表述以及平滑的量子格编码，使单位群算法关于 \(d\) 与 \(\log|\Delta_K|\) 都保持多项式复杂度。

4. 为什么类群计算依赖单位群

给定若干候选理想 \(\mathfrak p_1,\ldots,\mathfrak p_m\)，考虑映射

\[ \Phi:\mathbb Z^m\to\operatorname{Cl}(K), \qquad z\mapsto [\mathfrak p_1^{z_1}\cdots\mathfrak p_m^{z_m}]. \]

其核是所有乘积成为主理想的关系格。量子 Abelian HSP 可以寻找这些关系；对关系矩阵做 Smith 标准形，就得到类群的循环分解。不过，判断一个关系是否为主理想并规范化生成元时会遇到单位歧义，因此单位群与 PIP 是底层子程序。

在常见复杂度陈述中，广义黎曼猜想用于保证范数不太大的素理想已生成整个类群。它不是量子傅里叶变换本身的假设，而是选择有限生成集合时的数论假设，二者不可混淆。

Biasse--Song 的任意次数算法改从 \(S\)-单位群入手。给定有限素理想集合 \(S\)，允许元素只在 \(S\) 上具有非零赋值；\(S\)-单位关系同时编码普通单位、理想关系和 PIP。恢复这个关系格后，可以依次导出单位群、类群与主理想生成元。

5. 输入、输出与复杂度口径

“多项式时间”以次数 \(d\)、判别式的比特长度 \(\log|\Delta_K|\)、基的编码长度和要求精度为参数。基本单位本身可能极大，所以算法输出紧凑表示或对数嵌入；若要求展开全部系数，时间至少与输出长度成正比。

还应避免把“能算类群”误写成“能解任意格问题”。这里利用的是数域理想格、乘法结构和可计算约化映射。一般欧氏格上的最短向量问题没有因此获得多项式量子算法。

6. 小结与习题

  • Dirichlet 单位定理把无限单位群分成有限扭转部分与秩 \(r\) 的自由部分。

  • 对数嵌入把基本单位变为格基；量子 QFT 直接采样对偶格。

  • 单位群支撑 PIP，二者又支撑类群的关系格计算。

  • 固定次数与任意次数算法的分水岭是高维舍入噪声和可计算编码。

  1. 对实二次域证明 \(L(u)\) 的两个坐标之和为零。

  2. 若采到 \(r\) 个线性无关的对偶向量，解释为什么它们未必已经生成整个 \(\Lambda^*\)。

  3. 写出 \(2\times2\) 整数关系矩阵的 Smith 标准形与对应有限 Abel 群。

  4. 说明 GRH 在类群算法中出现的位置，并解释它为何不等同于“量子算法正确性依赖 GRH”。

参考文献