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

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”。

## 参考文献

- Zoo 编号 50：Sean Hallgren, [Fast Quantum Algorithms for Computing the Unit Group and Class Group of a Number Field](https://www.cse.psu.edu/~sjh26/unitgroup.pdf).
- Zoo 编号 116：Arthur Schmidt 与 Ulrich Vollmer, *Polynomial Time Quantum Algorithm for the Computation of the Unit Group of a Number Field*, STOC 2005.
- Zoo 编号 213：Kirsten Eisenträger、Sean Hallgren、Alexei Kitaev 与 Fang Song, [A Quantum Algorithm for Computing the Unit Group of an Arbitrary Degree Number Field](https://bpb-us-e1.wpmucdn.com/sites.psu.edu/dist/a/166357/files/2023/06/unitgroup.pdf).
- Zoo 编号 329：Jean-François Biasse 与 Fang Song, [Efficient Quantum Algorithms for Computing Class Groups and Solving the Principal Ideal Problem in Arbitrary Degree Number Fields](https://fangsong.info/files/pubs/BS_SODA16.pdf).