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

上一课 [Pell 方程与主理想问题](./pell-principal-ideal.md) 告诉我们：实二次域的基础单位 $\varepsilon$ 通过一个实数周期 $R=\log\varepsilon$ 隐藏在约化理想的序列里，量子傅里叶采样可以把这个周期找出来。但实二次域只是数域中最简单的一族——它的单位群本质上只有"一个自由度"，周期格是一维的。一般数域的单位群有 $r$ 个独立方向，隐藏的对象从一条周期变成一个 $r$ 维实格。本课的任务就是把一维的周期查找机制推广到高维：先用 Dirichlet 单位定理把单位群嵌入为欧氏空间中的格，再逐步推导量子傅里叶采样为什么看到的是这个格的**对偶格**，最后说明单位群、主理想问题（PIP）与类群计算三者如何层层相依、缺一不可。

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

1. **[单位群与 Dirichlet 单位定理](#unit-group-dirichlet)**——能写出单位群与范数的定义，推导范数判据 $|N_{K/\mathbb Q}(u)|=1$，并由 $r_1,r_2$ 计算单位群的秩 $r=r_1+r_2-1$ 与结构分解。
2. **[主理想问题与理想类群](#pip-class-group)**——能写出 PIP 与类群 $\operatorname{Cl}(K)=I_K/P_K$ 的定义，解释类数 $h_K$ 如何度量唯一分解的失效，并用 $\mathbb Q(\sqrt{-5})$ 的例子说明。
3. **[对数嵌入与单位格](#unit-log-lattice)**——能写出对数嵌入 $L$ 的定义并推导单位对数像的坐标和为零，解释 $\Lambda=L(\mathcal O_K^\times)$ 为何是超平面 $H$ 中的满秩格以及调节子 $R_K$ 的几何含义。
4. **[对偶格的傅里叶直觉](#dual-lattice-fourier)**——能从陪集叠加态出发推导格周期函数的傅里叶谱集中在对偶格 $\Lambda^*$ 上，并解释尺度反转与 $(\Lambda^*)^*=\Lambda$ 为何让"再求一次对偶"合法。
5. **[隐藏格量子算法的线路流程](#hidden-lattice-circuit)**——能解释周期函数 $f(x)$ 的构造及 $f(x+\lambda)=f(x)$ 的成因，并按序写出量子线路四个步骤中每一步得到的态。
6. **[从对偶样本恢复单位群](#recover-unit-lattice)**——能列出恢复 $\Lambda^*$ 的基、取对偶、反解对数嵌入的三步经典后处理，并比较高维相对一维新增的三个困难。
7. **[关系格与 Smith 标准形](#relation-lattice-smith)**——能构造关系格同态 $\Phi$ 并由 $\operatorname{Cl}(K)\cong\mathbb Z^m/\ker\Phi$ 说明类群计算归结为恢复隐藏子格，再用 Smith 标准形算出不变量分解。
8. **[GRH 保留条款与 $S$-单位群](#grh-caveat-s-units)**——能说明 GRH 在类群算法中的确切位置及其与傅里叶采样正确性的区别，并解释 $S$-单位群的关系格如何统一单位群、PIP 与类群。

:::

## 1. 问题的来龙去脉

Shor 算法处理的是有限循环群上的周期：$f(x)=a^x\bmod N$ 的周期是一个整数 $r$，傅里叶峰出现在 $r$ 的整数倍频附近。上一课把周期从整数推广到实数：Pell 方程的调节子 $R$ 是实数轴上的周期，难点在于周期函数只是"近似周期"且多对一。本课再做一次推广，这一次是**维数**的推广：

- 实二次域 $\mathbb Q(\sqrt d)$：单位群秩 $r=1$，隐藏周期是实数轴上的格 $R\mathbb Z$；
- 一般 $d$ 次数域 $K$：单位群秩 $r=r_1+r_2-1$ 可以达到 $d-1$，隐藏周期是 $\mathbb R^r$ 中的满秩格 $\Lambda$。

为什么要在意单位群和类群？从纯数学看，类群的大小（类数）度量了 $\mathcal O_K$ 偏离唯一分解的程度，单位群则刻画了环中"可逆元"的全部结构，二者是代数数论中最基本的不变量；从计算和密码学看，主理想问题（判断一个理想是否由单个元素生成并找出该元素）是若干基于理想格的密码方案背后的核心困难问题之一。因此"量子计算机能多快算出单位群与类群"同时具有数论意义与安全意义。

经典计算数论中，计算单位群与类群的标准方法以 Buchmann 等人的工作为代表，其思路是收集足够多的素理想之间的关系再做线性代数。这类算法关于判别式的比特长度 $\log|\Delta_K|$ 一般是**次指数**的（与整数分解的经典次指数算法同属一个难度量级），并且分析通常依赖广义黎曼猜想等假设。这与 Shor 算法出现前整数分解的处境非常相似：问题本身不难表述，但已知经典算法跑不进多项式时间。

量子侧的进展与文末参考文献一一对应：

- Hallgren（Zoo 编号 50）首先对**固定次数**的数域给出计算单位群与类群的多项式时间量子算法，其框架正是本课要讲的"隐藏格 + 傅里叶采样"；
- Schmidt 与 Vollmer（Zoo 编号 116）沿另一技术路线给出了计算单位群的多项式时间算法；
- Eisenträger、Hallgren、Kitaev 与 Song（Zoo 编号 213）借助连续隐藏子群问题的 Lipschitz 表述与平滑的量子格编码，把单位群算法推进到**任意次数**，复杂度关于次数 $d$ 与 $\log|\Delta_K|$ 均为多项式；
- Biasse 与 Song（Zoo 编号 329）进一步从 $S$-单位群切入，统一解决任意次数数域上的类群计算与主理想问题。

本课的目标不是复述这些论文的全部技术细节，而是把它们共同的核心结构讲清楚：**单位群是一个格，格可以用傅里叶采样恢复，而类群与 PIP 都建立在这个格之上。**

## 2. 三个代数对象

### 2.1 数域与整数环

一个**数域** $K$ 是有理数域 $\mathbb Q$ 的有限次扩张。由本原元定理，总可以写成 $K=\mathbb Q(\theta)$，其中 $\theta$ 是一个次数为 $d$ 的不可约有理系数多项式的根，$d=[K:\mathbb Q]$ 称为 $K$ 的**次数**。例如 $\mathbb Q(\sqrt5)$ 中 $\theta=\sqrt5$ 是 $x^2-5$ 的根，次数为 $2$。

$K$ 中的**代数整数**是满足某个首一整系数多项式的元素，全体代数整数构成一个环，记作 $\mathcal O_K$，称为 $K$ 的**整数环**。它是 $\mathbb Q$ 在 $K$ 中的"整数"概念的推广：$\mathbb Q$ 自己的整数环就是 $\mathbb Z$。需要警惕的是，$\mathcal O_K$ 不一定是 $\mathbb Z[\theta]$。例如 $K=\mathbb Q(\sqrt5)$ 时，$\varphi=(1+\sqrt5)/2$ 满足首一整系数方程 $x^2-x-1=0$（直接代入：$\varphi^2=\varphi+1$），所以 $\varphi$ 是代数整数，事实上

$$
\mathcal O_K=\mathbb Z\!\left[\tfrac{1+\sqrt5}{2}\right]=\{a+b\varphi:a,b\in\mathbb Z\},
$$

它比 $\mathbb Z[\sqrt5]$ 大。作为加法群，$\mathcal O_K$ 总是秩 $d$ 的自由 Abel 群，即存在一组**整基** $\omega_1,\ldots,\omega_d$ 使 $\mathcal O_K=\mathbb Z\omega_1\oplus\cdots\oplus\mathbb Z\omega_d$；整基的 Gram 行列式给出**判别式** $\Delta_K$，它是衡量数域"大小"的基本不变量，后文的复杂度都以 $\log|\Delta_K|$ 为输入参数之一。

(unit-group-dirichlet)=
### 2.2 单位群

**单位群**由 $\mathcal O_K$ 中的可逆元构成：

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

注意"逆元也必须是代数整数"这个条件非同小可。例如 $2\in\mathbb Z$ 在 $\mathbb Q$ 中有逆 $1/2$，但 $1/2$ 不是代数整数（它不满足任何首一整系数方程），所以 $2$ 不是 $\mathbb Z$ 的单位，$\mathbb Z^\times=\{\pm1\}$。

判定单位有一把非常实用的尺子：**范数**。设 $K$ 的全部嵌入（把 $K$ 映入 $\mathbb C$ 的域同态）为 $\sigma_1,\ldots,\sigma_d$，则元素 $\alpha\in K$ 的范数定义为

$$
N_{K/\mathbb Q}(\alpha)=\prod_{i=1}^{d}\sigma_i(\alpha).
$$

范数是可乘的：$N(\alpha\beta)=N(\alpha)N(\beta)$（因为每个 $\sigma_i$ 都是域同态，乘积逐项保持乘法）；并且对 $\alpha\in\mathcal O_K$ 有 $N(\alpha)\in\mathbb Z$。于是：

- 若 $u$ 是单位，存在 $v\in\mathcal O_K$ 使 $uv=1$，则 $N(u)N(v)=N(uv)=N(1)=1$。两个整数乘积为 $1$，只可能 $N(u)=\pm1$；
- 反过来，$|N(u)|=1$ 时 $u$ 必为单位（其共轭元之积给出逆元）。

所以单位恰好是范数为 $\pm1$ 的代数整数：

$$
\mathcal O_K^\times=\{u\in\mathcal O_K:|N_{K/\mathbb Q}(u)|=1\}.
$$

这条判据是第 3 节对数嵌入之所以可行的根本原因。

**Dirichlet 单位定理**完整描述了单位群的结构。设 $K$ 有 $r_1$ 个**实嵌入**（像落在 $\mathbb R$ 内的嵌入）和 $r_2$ 对互相共轭的**复嵌入**（每对 $\{\sigma,\bar\sigma\}$ 算一对），则 $d=r_1+2r_2$——实嵌入贡献 $1$ 个，每对复嵌入贡献 $2$ 个，合计恰为次数。定理断言

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

其中 $\mu(K)$ 是 $K$ 中全体单位根构成的**有限**循环群（扭转部分），$r$ 称为单位群的**秩**。换句话说：每个单位都可以唯一地写成

$$
u=\zeta\,\varepsilon_1^{k_1}\varepsilon_2^{k_2}\cdots\varepsilon_r^{k_r},
\qquad \zeta\in\mu(K),\ k_i\in\mathbb Z,
$$

其中 $\varepsilon_1,\ldots,\varepsilon_r$ 称为一组**基本单位**。"计算单位群"的准确含义就是：输出有限群 $\mu(K)$，以及 $r$ 个基本单位（的某种紧凑表示）。

两个极端情形帮助建立直觉：

- 实二次域 $\mathbb Q(\sqrt d)$（$d>0$ 非平方）：$r_1=2,r_2=0$，秩 $r=1$。单位群 $=\{\pm\varepsilon^k\}$，唯一的基本单位就是 Pell 方程给出的 $\varepsilon$——这正是上一课的一维情形；
- 全虚二次域 $\mathbb Q(\sqrt{-d})$：$r_1=0,r_2=1$，秩 $r=0$。单位群只有单位根，是有限群，没有"格"可言。

秩 $r$ 随次数增长（例如全实域 $r_2=0$ 时 $r=d-1$），这就是"多维周期格"的来源。

### 2.3 主理想问题

$\mathcal O_K$ 的非零理想 $I$ 是一个在加法下封闭、且被 $\mathcal O_K$ 中任意元素乘进去仍封闭的子集。若存在单个元素 $\alpha\in K^\times$ 使

$$
I=(\alpha):=\alpha\,\mathcal O_K,
$$

则称 $I$ 为**主理想**，全体主（分式）理想记作

$$
P_K=\{(\alpha):\alpha\in K^\times\}.
$$

**主理想问题（PIP）**：给定理想 $I$（以一组 $\mathbb Z$-基的形式输入），判断 $I\in P_K$ 是否成立；若成立，输出一个生成元 $\alpha$ 的紧凑表示。

上一课已经见过 PIP 的一个要害：生成元永远不唯一。若 $I=(\alpha)$，则对任意单位 $u$，$(\alpha u)=\alpha u\mathcal O_K=\alpha\mathcal O_K=(\alpha)$——倒数第二步用了 $u\mathcal O_K=\mathcal O_K$（乘以可逆元只是整数环的一个自同构）。所以 PIP 的答案天生带有"单位群"这个歧义；要规范地陈述和求解 PIP，绕不开单位群。

(pip-class-group)=
### 2.4 理想类群

主理想只是理想的一部分。**理想类群**度量"有多少理想本质上不是主理想"：把所有非零分式理想构成的乘法群记作 $I_K$，定义

$$
\operatorname{Cl}(K)=I_K/P_K.
$$

两个理想 $I,J$ 属于同一类，当且仅当存在 $\alpha\in K^\times$ 使 $I=\alpha J$，即"相差一个主理想"的理想被等同起来。代数数论的一个基本定理保证 $\operatorname{Cl}(K)$ 是**有限 Abel 群**，其阶 $h_K=|\operatorname{Cl}(K)|$ 称为**类数**。$h_K=1$ 当且仅当 $\mathcal O_K$ 是主理想整环（从而有唯一分解）；$h_K>1$ 时唯一分解失效，失效的方式被类群的结构精确刻画。

经典例子：$K=\mathbb Q(\sqrt{-5})$。在 $\mathcal O_K=\mathbb Z[\sqrt{-5}]$ 中，

$$
6=2\cdot3=(1+\sqrt{-5})(1-\sqrt{-5})
$$

给出 $6$ 的两种本质上不同的不可约分解，唯一分解失效。理想 $\mathfrak p=(2,\,1+\sqrt{-5})$ 不是主理想（若 $\mathfrak p=(\alpha)$，取范数会要求 $|N(\alpha)|=2$，但 $a^2+5b^2=2$ 无整数解），而 $\mathfrak p^2=(2)$ 是主理想，于是 $[\mathfrak p]$ 在类群中是 $2$ 阶元。事实上 $\operatorname{Cl}(K)\cong\mathbb Z/2\mathbb Z$，类数 $h_K=2$。

类群是一个有限 Abel 群，由有限 Abel 群结构定理，它总可以唯一地分解为循环群的直积。因此"计算类群"的标准输出形式是**不变量分解**

$$
\operatorname{Cl}(K)\cong
\mathbb Z/n_1\mathbb Z\times\cdots\times\mathbb Z/n_s\mathbb Z,
\qquad n_1\mid n_2\mid\cdots\mid n_s,
$$

连同每个循环因子对应的理想代表元。

## 3. 对数嵌入：把乘法群变成加法格

### 3.1 为什么取对数

单位群的运算结构是**乘法**的（$u=\zeta\varepsilon_1^{k_1}\cdots\varepsilon_r^{k_r}$），而量子傅里叶采样擅长寻找的是**加法**群中的周期。从乘法到加法的桥梁是对数：$\log(ab)=\log a+\log b$，指数 $k_i$ 在对数坐标下变成线性坐标。这一节把这个想法严格化。

把 $r_1$ 个实嵌入记作 $\sigma_1,\ldots,\sigma_{r_1}$，从 $r_2$ 对共轭复嵌入中每对取一个代表，记作 $\sigma_{r_1+1},\ldots,\sigma_{r_1+r_2}$（取代表是因为共轭嵌入的绝对值相同，$|\bar\sigma(u)|=|\sigma(u)|$，成对的信息只需保留一份）。定义**对数嵌入** $L:K^\times\to\mathbb R^{r_1+r_2}$：

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

三个设计细节逐一说明：

- **取绝对值**：$\sigma_i(u)$ 可能是负数或复数，而 $\log$ 需要正实数输入；范数公式中出现的本来也是绝对值；
- **取对数**：乘法变加法，$L(uv)=L(u)+L(v)$，即 $L$ 是从乘法群 $K^\times$ 到加法群 $\mathbb R^{r_1+r_2}$ 的同态；
- **复嵌入处系数 $2$**：与共轭对 $\{\sigma,\bar\sigma\}$ 在范数中贡献 $|\sigma(u)|^2$ 相呼应，下面的推导会看到它保证"坐标和"恰好是 $\log|N(u)|$。

### 3.2 坐标和为零：逐步推导

范数可以用嵌入写成

$$
N_{K/\mathbb Q}(u)=\prod_{i=1}^{d}\sigma_i(u)
=\underbrace{\prod_{i=1}^{r_1}\sigma_i(u)}_{\text{实嵌入}}\cdot
\underbrace{\prod_{j=r_1+1}^{r_1+r_2}\sigma_j(u)\,\overline{\sigma_j(u)}}_{\text{每对共轭复嵌入}}.
$$

第一步是把 $d$ 个嵌入按"实 / 共轭复对"分组，实嵌入共 $r_1$ 个，复嵌入共 $2r_2$ 个、配成 $r_2$ 对。第二步对每对复嵌入用 $z\bar z=|z|^2$：

$$
\sigma_j(u)\,\overline{\sigma_j(u)}=|\sigma_j(u)|^2.
$$

于是

$$
|N(u)|=\prod_{i=1}^{r_1}|\sigma_i(u)|\cdot\prod_{j=r_1+1}^{r_1+r_2}|\sigma_j(u)|^2.
$$

两边取对数（$\log$ 把乘积变和、把平方变系数 $2$）：

$$
\log|N(u)|
=\sum_{i=1}^{r_1}\log|\sigma_i(u)|
+\sum_{j=r_1+1}^{r_1+r_2}2\log|\sigma_j(u)|
=\langle L(u),\,(1,1,\ldots,1)\rangle.
$$

右端正是 $L(u)$ 的全部坐标之和。现在代入单位判据：$u$ 是单位当且仅当 $|N(u)|=1$，而 $\log 1=0$，所以

$$
u\in\mathcal O_K^\times\ \Longrightarrow\ \text{$L(u)$ 的坐标和为零},
$$

即所有单位的对数像都落在超平面

$$
H=\{x\in\mathbb R^{r_1+r_2}:\textstyle\sum_i x_i=0\}
$$

中。$H$ 是 $\mathbb R^{r_1+r_2}$ 中法向量为 $(1,\ldots,1)$ 的超平面，维数 $=r_1+r_2-1=r$——恰好等于 Dirichlet 定理预言的单位群秩。这不是巧合，而是同一事实的两面。

(unit-log-lattice)=
### 3.3 格与调节子

Dirichlet 单位定理的证明（此处只陈述其结论的几何内容）告诉我们两件事：

1. **核**：$L$ 在 $\mathcal O_K^\times$ 上的核恰好是单位根群 $\mu(K)$。直觉上，$\log|\sigma_i(\zeta)|=\log 1=0$ 对单位根成立；反过来，若 $L(u)=0$ 则所有共轭的绝对值都是 $1$，代数数论证明这样的代数整数只有有限多个，正是单位根；
2. **像**：$\Lambda:=L(\mathcal O_K^\times)$ 是 $H$ 中的**满秩离散格**，即存在 $\mathbb R$-线性无关的 $r$ 个向量 $\lambda_1,\ldots,\lambda_r\in H$ 使

$$
\Lambda=\mathbb Z\lambda_1\oplus\cdots\oplus\mathbb Z\lambda_r,
$$

并且 $\lambda_i=L(\varepsilon_i)$ 正好对应基本单位。

把两条合起来：对数嵌入把乘法群 $\mathcal O_K^\times\cong\mu(K)\times\mathbb Z^r$ 同构地映为加法格 $\Lambda\cong\mathbb Z^r$（扭转部分被压进核里）。**计算单位群的问题就此完全等价于：恢复 $H$ 中未知实格 $\Lambda$ 的一组 $\mathbb Z$-基**，再从每个基向量反解出对应的基本单位。

格 $\Lambda$ 的**基本平行体**（由一组基张成的平行多面体 $\{\sum_i t_i\lambda_i:0\le t_i<1\}$）在 $H$ 中的体积称为数域 $K$ 的**调节子** $R_K$。基本平行体的体积不依赖于基的选取——两组基之间相差一个行列式为 $\pm1$ 的整数矩阵（$\mathrm{GL}_r(\mathbb Z)$ 变换），而体积在行列式 $\pm1$ 的线性变换下不变——所以 $R_K$ 是数域自身的良定义不变量。它同时度量了"单位群有多稀疏"：基本单位越大，格越稀疏，$R_K$ 越大。实二次域时 $r=1$，"基本平行体"就是区间 $[0,\log\varepsilon)$，其体积（长度）$\log\varepsilon$ 正是上一课的调节子 $R$，两个定义在此衔接。

### 3.4 完整算例：$\mathbb Q(\sqrt5)$

把上面每个抽象概念在 $K=\mathbb Q(\sqrt5)$ 上走一遍。这里 $d=2$，$r_1=2$，$r_2=0$，秩 $r=2+0-1=1$；$\mathcal O_K=\mathbb Z[\varphi]$，$\varphi=(1+\sqrt5)/2$。

两个实嵌入分别是

$$
\sigma_1(a+b\sqrt5)=a+b\sqrt5,\qquad
\sigma_2(a+b\sqrt5)=a-b\sqrt5.
$$

作用在 $\varphi$ 上：

$$
\sigma_1(\varphi)=\frac{1+\sqrt5}{2}=\varphi,\qquad
\sigma_2(\varphi)=\frac{1-\sqrt5}{2}.
$$

第二步验证 $\sigma_2(\varphi)=-1/\varphi$：

$$
\varphi\cdot\frac{1-\sqrt5}{2}=\frac{(1+\sqrt5)(1-\sqrt5)}{4}=\frac{1-5}{4}=-1,
$$

所以 $(1-\sqrt5)/2=-1/\varphi$。由此立得范数

$$
N(\varphi)=\sigma_1(\varphi)\,\sigma_2(\varphi)=-1,
$$

$|N(\varphi)|=1$，故 $\varphi$ 是单位（其逆为 $-\sigma_2(\varphi)=\varphi-1\in\mathcal O_K$，可直接验证 $\varphi(\varphi-1)=\varphi^2-\varphi=1$，用了 $\varphi^2=\varphi+1$）。

对数嵌入：

$$
L(\varphi)=\bigl(\log|\sigma_1(\varphi)|,\ \log|\sigma_2(\varphi)|\bigr)
=\bigl(\log\varphi,\ \log\tfrac1\varphi\bigr)
=(\log\varphi,\ -\log\varphi).
$$

两个坐标之和为零，与 3.2 节的推导一致；$\Lambda=L(\mathcal O_K^\times)$ 是直线 $H=\{(x,-x)\}$ 上以 $(\log\varphi,-\log\varphi)$ 为基向量的一维格，调节子

$$
R_K=\sqrt2\,\log\varphi
$$

（$H$ 中欧氏度规下的基向量长度；文献中常用归一化约定差一个因子，定性结论是 $R_K\propto\log\varphi\approx0.4812$）。单位群为

$$
\mathcal O_K^\times=\{\pm\varphi^k:k\in\mathbb Z\},
$$

扭转部分 $\mu(K)=\{\pm1\}$，基本单位 $\varepsilon_1=\varphi$。这个例子同时说明：上节课"一维周期 $R$"在一般框架中的正确写法，就是一维格被放进二维空间的"和为零"超平面里。

(dual-lattice-fourier)=
## 4. 傅里叶直觉：周期格的谱是对偶格

在进入算法之前，先用一节把核心直觉讲透：**为什么对格周期函数做傅里叶变换，看到的是对偶格？**

回顾一维情形。设 $f:\mathbb R\to\mathcal S$ 满足 $f(x+R)=f(x)$。在量子周期查找中，制备均匀叠加 $\sum_x|x\rangle|f(x)\rangle$ 并测量第二寄存器，第一寄存器坍缩为某个**陪集** $x_0+R\mathbb Z$ 上的均匀叠加：

$$
|\psi\rangle\propto\sum_{k\in\mathbb Z}|x_0+kR\rangle.
$$

对它做傅里叶变换，频率 $y$ 处的振幅正比于

$$
\sum_{k\in\mathbb Z}e^{2\pi i\,y(x_0+kR)}
=e^{2\pi i yx_0}\sum_{k\in\mathbb Z}e^{2\pi i\,k\,yR}.
$$

观察这个和：若 $yR\in\mathbb Z$，每一项 $e^{2\pi i\,k\,yR}=1$，无穷多项同相叠加——**相长干涉**；若 $yR\notin\mathbb Z$，相位 $e^{2\pi i\,yR}\neq1$ 是单位圆上固定的非 $1$ 点，各项绕圆均匀转动、相互抵消——**相消干涉**。所以谱峰出现在 $yR\in\mathbb Z$ 处，即 $y\in\frac1R\mathbb Z$：周期格 $R\mathbb Z$ 的傅里叶谱是**频率格** $\frac1R\mathbb Z$。未知平移 $x_0$ 只贡献整体相位 $e^{2\pi i yx_0}$，对测量概率 $|\text{振幅}|^2$ 毫无影响——这就是为什么"先测量函数值"不会丢失周期信息。

高维推广几乎是逐字平移。设 $f:\mathbb R^r\to\mathcal S$ 以格 $\Lambda$ 为周期：$f(x+\lambda)=f(x)$ 对所有 $\lambda\in\Lambda$ 成立。测量函数值后第一寄存器落在陪集 $x_0+\Lambda$ 的均匀叠加 $\sum_{\lambda\in\Lambda}|x_0+\lambda\rangle$ 上，$r$ 维傅里叶变换在频率 $y\in\mathbb R^r$ 处的振幅正比于

$$
\sum_{\lambda\in\Lambda}e^{2\pi i\langle y,\,x_0+\lambda\rangle}
=e^{2\pi i\langle y,x_0\rangle}\sum_{\lambda\in\Lambda}e^{2\pi i\langle y,\lambda\rangle}.
$$

相长干涉的条件逐分量成立当且仅当每个 $\langle y,\lambda\rangle$ 都是整数——对基向量 $\lambda_1,\ldots,\lambda_r$ 成立即可，因为任意 $\lambda=\sum_i m_i\lambda_i$ 给出 $\langle y,\lambda\rangle=\sum_i m_i\langle y,\lambda_i\rangle\in\mathbb Z$。满足此条件的全部频率构成**对偶格**

$$
\Lambda^*=\{y\in H:\langle y,\lambda\rangle\in\mathbb Z,\ \forall\lambda\in\Lambda\}.
$$

注意对偶格自动落在同一超平面 $H$ 中：若 $y$ 有沿 $(1,\ldots,1)$ 法向的分量，由于 $\Lambda\subset H$，该分量对内积无贡献，可以投影掉。

对偶格还有一个干净的基描述：若 $\Lambda$ 的基为 $\lambda_1,\ldots,\lambda_r$，定义 $\lambda_1^*,\ldots,\lambda_r^*$ 由 $r^2$ 个线性方程 $\langle\lambda_i^*,\lambda_j\rangle=\delta_{ij}$ 确定（这是一个 $r\times r$ 线性方程组，系数矩阵是 Gram 矩阵，格满秩保证可解），则 $\Lambda^*=\bigoplus_i\mathbb Z\lambda_i^*$。由此得到两条定性但关键的事实：

- $\Lambda$ 越**密**（基向量短），$\Lambda^*$ 越**疏**（基向量长）——对偶关系反转了尺度；
- $(\Lambda^*)^*=\Lambda$，取两次对偶回到自身。这就是为什么算法流程末端"再求一次对偶"是合法操作。

一句话总结直觉：**格是空间中的周期，对偶格是频率中的峰位；测不到周期本身，但能测到对偶格的样本，而对偶格与原格互相唯一确定。**

## 5. 量子算法：从隐藏周期到隐藏格

### 5.1 周期函数从哪来

Shor 算法里周期函数 $a^x\bmod N$ 是白给的；这里必须自己构造一个以 $\Lambda$ 为周期、且量子计算机能算的函数。固定次数算法的构造如下：对 $x\in\mathbb R^r$，把 $x$ 解释为一个"缩放指令"，用 $e^x$（逐嵌入取指数）去缩放整数环，得到理想格 $e^x\mathcal O_K$；然后对它做**约化**——格约化在等价类中选出一个规范代表，输出这个约化理想连同它的局部几何信息，记作 $f(x)$。

为什么这个 $f$ 以 $\Lambda$ 为周期？关键观察是：乘上一个单位 $u$ 不改变主理想，$u\mathcal O_K=\mathcal O_K$（这在 2.3 节已经用过）。在对数坐标里，"乘以单位 $u$"恰好是"平移 $L(u)\in\Lambda$"：缩放向量从 $e^x$ 变成 $e^{x+L(u)}=e^x\cdot e^{L(u)}$，而 $e^{L(u)}$ 正是 $u$ 在各嵌入下的绝对值。两个缩放后的格相差一个单位倍数，约化后得到同一个规范代表，于是

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

这就是高维的 infrastructure 思想：约化理想沿着对数坐标排成一张 $r$ 维的周期"地形图"，$\Lambda$ 是这张图的平移对称群。

(hidden-lattice-circuit)=
### 5.2 量子线路的四个步骤

量子计算机是离散设备，先把 $\mathbb R^r$ 截断并离散化：取一个边长为 $D$、网格间距为 $1/N$ 的有限网格 $G\subset\mathbb R^r$。然后：

**第一步，制备网格上的均匀叠加。**

$$
\frac{1}{\sqrt{|G|}}\sum_{x\in G}|x\rangle|0\rangle.
$$

**第二步，可逆计算 $f$。** 利用约化理想的经典可计算性（这一步的代价进入复杂度分析，见第 6 节），把函数值写入第二寄存器：

$$
\frac{1}{\sqrt{|G|}}\sum_{x\in G}|x\rangle|f(x)\rangle.
$$

**第三步，测量第二寄存器。** 设测得某个函数值 $s$。由于 $f$ 以 $\Lambda$ 为周期，所有满足 $f(x)=s$ 的 $x$ 构成（网格与）陪集 $x_0+\Lambda$（的交），第一寄存器坍缩为

$$
|\psi_{x_0}\rangle\propto\sum_{\lambda\in\Lambda:\,x_0+\lambda\in G}|x_0+\lambda\rangle.
$$

$x_0$ 是未知的随机平移，但第 4 节已说明它只影响傅里叶谱的整体相位，不影响测量分布。

**第四步，对第一寄存器做 $r$ 维量子傅里叶变换并测量。** 由第 4 节的推导，输出 $y$ 以高概率落在某个对偶格向量 $\lambda^*\in\Lambda^*$ 附近：

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

每运行一次线路，就得到一个近似对偶格向量的随机样本。

(recover-unit-lattice)=
### 5.3 从对偶样本恢复基本单位

收集到足够多的样本后，全部剩余工作都是经典计算：

1. **恢复 $\Lambda^*$ 的基。** 样本是 $\Lambda^*$ 中向量的带噪版本。先以高精度取整/聚类得到候选的精确对偶向量，再用经典格算法（如 LLL 型规约配合线性代数）从张成集中提取一组 $\mathbb Z$-基 $\lambda_1^*,\ldots,\lambda_r^*$。这里有一个微妙点：$r$ 个线性无关的样本未必生成整个 $\Lambda^*$，它们可能只生成一个有限指数的子格——见练习 6 第 3 题。修补方法是继续采样并用行列式（基本平行体体积）判断是否已经收敛：子格的基本平行体体积是 $\Lambda^*$ 的整数倍，体积降到不再整除变小即停。
2. **取对偶得到 $\Lambda$。** 用 $(\Lambda^*)^*=\Lambda$：写出对偶基满足的线性方程组 $\langle\lambda_i,\lambda_j^*\rangle=\delta_{ij}$ 并求解，即得 $\Lambda$ 的基 $\lambda_1,\ldots,\lambda_r$。
3. **反解对数嵌入。** 每个 $\lambda_i=L(\varepsilon_i)$ 记录了基本单位 $\varepsilon_i$ 在全部嵌入下的绝对值的对数。结合符号/辐角信息（有限多种选择，辅以经典验证）恢复 $\varepsilon_i$ 在某个代数表示下的紧凑描述；用 $\varepsilon_i$ 是否真的在 $\mathcal O_K$ 中且范数为 $\pm1$ 做最终校验。

整个流程与一维周期查找**完全同构**：制备叠加 $\to$ 计算周期函数 $\to$ 测量得到陪集态 $\to$ QFT 得到对偶样本 $\to$ 经典后处理。但维数从 $1$ 涨到 $r$ 后，多了三个一维时没有（或不严重）的困难：

1. **傅里叶峰落在对偶格上，而不是等间隔整数点上。** 一维时峰位是 $\frac1R\mathbb Z$，间距均匀，连分数就能从单个高精度样本挤出 $R$；高维时峰位是斜格子 $\Lambda^*$，没有"连分数"可用，必须用格基规约从多个样本中联合恢复基。
2. **约化理想的表示存在舍入噪声。** $f(x)$ 的输出涉及实数格的约化，只能用有限精度近似；函数在"两个约化代表交界"附近还会跳变。于是 $f$ 只是**近似**周期函数，周期条件在坏点集上失效。正确性证明必须说明坏点占比足够小，压不垮谱峰。
3. **维数增长放大坏边界与采样误差。** 坏点主要来自边界，而高维中"边界面"的相对体积随维数增长；同时每个样本是 $r$ 维向量，恢复基所需的样本数、每一步格规约的代价都随 $r$ 增长。一维论证中随手可压低的误差，在高维必须逐维记账。

### 5.4 从固定次数到任意次数

Hallgren 的早期算法（Zoo 编号 50）先处理**固定次数** $d$ 的数域：此时 $r\le d-1$ 是常数，上面三个困难都可以用"逐维蛮力"的方式控制，复杂度关于 $\log|\Delta_K|$ 是多项式。Schmidt 与 Vollmer（Zoo 编号 116）沿另一路线同样实现了单位群的多项式时间计算。

真正的障碍是让复杂度同时关于 $d$ 也是多项式。Eisenträger、Hallgren、Kitaev 与 Song（Zoo 编号 213）的解决方案包含两个关键思想：

- **连续隐藏子群问题的 Lipschitz 表述**：把"带噪声的周期函数"公理化——要求周期函数在好的输入点上满足 Lipschitz 连续性（函数值的变化被输入距离线性控制），并证明这类连续 HSP 可以被量子傅里叶采样解决。公理化的好处是：数论构造中那些乱七八糟的舍入误差，只要最终归约为"Lipschitz 常数 + 坏点比例"两个参数，就统一由通用定理接管；
- **平滑的量子格编码**：不再把格点硬编码为精确的基矢标签，而是编码为高斯型的平滑叠加，使边界跳变被"抹平"，从根上压低坏点比例。

两者结合，使单位群算法的运行时间关于次数 $d$ 与 $\log|\Delta_K|$ **都**保持多项式——这是"任意次数"算法的标志。

## 6. 复杂度分析

### 6.1 复杂度表达式中每个因子的来源

"多项式时间"是相对四个输入参数而言的：次数 $d$、判别式的比特长度 $\log|\Delta_K|$、理想基的编码长度、以及要求的输出精度。逐项说明各因子从何而来：

- **$d$（维数因子）**：$r\le d-1$ 个量子寄存器、$r$ 维 QFT、每次采样要恢复 $r$ 个基向量、$r\times r$ 的格规约与线性代数——多项式个随 $d$ 多项式增长的步骤，乘积仍是多项式。这正是"任意次数"算法（Zoo 编号 213、329）相对"固定次数"算法（Zoo 编号 50）的改进所在：后者允许代价以 $d$ 的指数形式出现，因为 $d$ 被当作常数；
- **$\log|\Delta_K|$（数域大小因子）**：判别式控制格 $\Lambda$ 的尺度与约化理想表示所需的精度，进而决定网格间距 $1/N$ 与截断长度 $D$ 各需要多少比特。寄存器存的是 $\log$ 尺度下的坐标，比特数关于 $\log|\Delta_K|$ 多项式；
- **精度因子**：傅里叶样本要精确到能把相邻对偶格点区分开，所需精度（从而 QFT 的尺寸、每个寄存器的比特数）关于目标精度的比特数是多项式；
- **采样次数因子**：每个样本以逆多项式概率落在好峰上（第 5.2 节第三步、第四步的成功概率），故需要多项式次重复；恢复 $r$ 个方向又乘上 $O(r)$ 量级的样本数。

一个值得展示的**参数平衡**计算（示意性 toy model，非原论文的精确界）：设网格加密的误差与格点总数之间存在此消彼长。网格间距 $1/N$ 带来的离散化误差量级为 $\varepsilon_{\text{grid}}\sim c_1/N$（$N$ 越大越细，误差越小），而固定线路深度下、窗口截断引入的误差随覆盖范围增长，量级为 $\varepsilon_{\text{win}}\sim c_2 N\delta$（$N$ 越大、在固定边长内点越密，单个格点分到的"演化预算"$\delta$ 摊薄后总误差上升）。总误差

$$
\varepsilon(N)=\frac{c_1}{N}+c_2N\delta.
$$

对 $N$ 求极小：$\varepsilon'(N)=-c_1/N^2+c_2\delta=0$，解出平衡点

$$
N_*=\sqrt{\frac{c_1}{c_2\delta}},
\qquad
\varepsilon(N_*)=2\sqrt{c_1c_2\delta}.
$$

即取 $N$ 使两项误差**同阶**（$c_1/N_*=c_2N_*\delta$），总误差降到两项各自单独优化的最小值的量级。这类"让两项同阶"的平衡在本课涉及的各算法分析中反复出现；真实论文中的参数更多，但平衡的原则完全相同。

### 6.2 输出的紧凑表示

与 Pell 方程一样，基本单位本身可能**指数级大**：$\varepsilon_i$ 的系数可以达到 $e^{R_K}$ 量级，而 $R_K$ 可以大到 $|\Delta_K|$ 的多项式规模——完整写出它的十进制系数需要指数多个比特。因此"多项式时间算法"的输出只能是：

- 基本单位的**紧凑表示**（例如若干小代数数的幂次乘积，或其对数嵌入 $L(\varepsilon_i)$ 的高精度近似）；

若要展开全部系数，任何算法的时间都至少与输出长度成正比，这不是算法的缺陷，而是信息论下界。上一课对调节子 $R$ 与完整 Pell 解的区分，在这里对 $r$ 个基本单位逐字重演。

### 6.3 边界：不能外推的结论

最后避免一个常见误读："能算类群"**不等于**"能解任意格问题"。本课算法利用的是数域特有的三重结构——理想格来自 $\mathcal O_K$ 的乘法、约化映射经典可计算、周期格恰好是单位群的对数像。一般欧氏格上的最短向量问题（SVP）没有因此获得多项式量子算法；基于一般格问题的密码方案也不受本课结果直接威胁。

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

(relation-lattice-smith)=
### 7.1 关系格与类群的循环分解

类群是有限 Abel 群，计算它的标准策略是"生成元 + 关系"。取若干候选理想（通常取范数不超过某个界的小素理想）$\mathfrak p_1,\ldots,\mathfrak p_m$，它们生成了类群（生成性的保证见 7.3 节）。考虑映射

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

$\Phi$ 是群同态（指数的加法对应理想的乘法），并且由于 $\mathfrak p_i$ 生成类群，$\Phi$ 是满射。由同态基本定理，

$$
\operatorname{Cl}(K)\cong\mathbb Z^m/\ker\Phi.
$$

核 $\ker\Phi$ 由全部**关系**组成：$z\in\ker\Phi$ 当且仅当 $\mathfrak p_1^{z_1}\cdots\mathfrak p_m^{z_m}$ 是主理想。它是 $\mathbb Z^m$ 的子格（秩为 $m$），称为**关系格**。求类群的问题于是变成：恢复关系格的一组基，排成 $m\times m$ 整数矩阵 $M$，再做 **Smith 标准形**——用行列初等变换（行列 swap、取负、整系数倍加）把 $M$ 化为对角形 $\operatorname{diag}(d_1,\ldots,d_m)$，$d_1\mid d_2\mid\cdots\mid d_m$，则

$$
\operatorname{Cl}(K)\cong
\mathbb Z/d_1\mathbb Z\times\cdots\times\mathbb Z/d_m\mathbb Z
$$

（跳过 $d_i=1$ 的平凡因子）。量子 Abelian HSP 算法正是为这类"$\mathbb Z^m$ 中隐藏的子格"设计的：把 $\Phi$ 做成周期函数（核是周期格），傅里叶采样恢复 $\ker\Phi$ 的基——结构上与本课第 5 节一模一样，只是环境从实格换成了整数格。

### 7.2 算例：$2\times2$ 关系矩阵的 Smith 标准形

设 $m=2$，关系格的基排成矩阵

$$
M=\begin{pmatrix}2&0\\0&3\end{pmatrix},
$$

即已知关系 $\mathfrak p_1^2\sim1$ 与 $\mathfrak p_2^3\sim1$（$\sim$ 表示在类群中相等）。朴素读法会猜 $\operatorname{Cl}(K)\cong\mathbb Z/2\times\mathbb Z/3$，但 Smith 标准形给出更规范的答案。允许的操作是整系数行列变换，等价于左右乘 $\mathrm{GL}_2(\mathbb Z)$：

第一步，用第二列减第一列（列操作，把第 1 列的 $-1$ 倍加到第 2 列）：

$$
\begin{pmatrix}2&-2\\0&3\end{pmatrix};
$$

第二步，用第一行加第二行（行操作）消出 $\gcd(2,3)=1$：

$$
\begin{pmatrix}2&-2\\0&3\end{pmatrix}
\to
\begin{pmatrix}2&1\\0&3\end{pmatrix}
$$

（第 2 行的 $1$ 倍加到第 1 行：$(-2)+3=1$）。继续用行列操作把 $1$ 换到左上角并清零同行同列：

$$
\begin{pmatrix}2&1\\0&3\end{pmatrix}
\to\begin{pmatrix}1&2\\3&0\end{pmatrix}
\to\begin{pmatrix}1&0\\3&-6\end{pmatrix}
\to\begin{pmatrix}1&0\\0&-6\end{pmatrix}
\to\begin{pmatrix}1&0\\0&6\end{pmatrix},
$$

依次是交换两列、第 1 列的 $-2$ 倍加到第 2 列、第 1 行的 $-3$ 倍加到第 2 行、第 2 列取负。每一步都是 $\mathrm{GL}_2(\mathbb Z)$ 中的操作，商群不变。最终 Smith 标准形为 $\operatorname{diag}(1,6)$，于是

$$
\operatorname{Cl}(K)\cong\mathbb Z/1\mathbb Z\times\mathbb Z/6\mathbb Z
\cong\mathbb Z/6\mathbb Z.
$$

与朴素读法比较：$\mathbb Z/2\times\mathbb Z/3\cong\mathbb Z/6$（中国剩余定理，因 $\gcd(2,3)=1$），结论一致，但 Smith 标准形给出的是**不变量分解**（$1\mid 6$），它不依赖于你最初选了哪组关系基。这也解释了为什么"收集关系 + Smith 标准形"是类群计算的标准收尾。

### 7.3 单位歧义：为什么底层需要单位群与 PIP

上面的框架有一个被轻描淡写的环节：判断 $z$ 是否为关系，需要判定 $\prod_i\mathfrak p_i^{z_i}$ **是否为主理想**——这正是 PIP；而 PIP 的答案（生成元 $\alpha$）只确定到单位倍数（2.3 节）。更实质地，在恢复关系格之后，要规范化每个关系的生成元、并把类群元素表示为具体的理想代表元，都需要知道单位群：两个"看似不同"的生成元 $\alpha,\alpha'$ 可能只差一个单位 $\alpha'=\alpha u$，不算出 $u$ 就无法确认它们代表同一个关系。因此在算法栈中，**单位群与 PIP 是类群计算的底层子程序**，三者层层相依：单位群 $\to$ PIP $\to$ 类群。

(grh-caveat-s-units)=
### 7.4 GRH 出现在哪里（保留条款）

常见复杂度陈述中，**广义黎曼猜想（GRH）** 被用来保证：范数不超过某个（关于 $\log|\Delta_K|$ 多项式的）界的素理想已经生成整个类群。它的角色必须精确界定：

- GRH 是一个**数论假设**，用于限制生成集合 $\{\mathfrak p_1,\ldots,\mathfrak p_m\}$ 的大小 $m$，从而限制关系格计算的输入规模；
- 它**不是**量子傅里叶采样正确性的假设。傅里叶采样恢复关系格这一步是无条件的；有条件的只是"我们选的有限素理想集足够生成类群"这个数论命题；
- 因此正确的表述是"在 GRH 下，类群算法有多项式运行时间上界"，而不是"量子算法的正确性依赖 GRH"。不假设 GRH 时，算法依然输出正确的关系格，只是生成集合的界失去保证。

这条保留条款在引用类群算法复杂度时必须一并引用，不可省略。

### 7.5 Biasse–Song：从 $S$-单位群统一出发

Biasse 与 Song 的任意次数算法（Zoo 编号 329）改变了切入顺序：不再"先单位群、再 PIP、再类群"顺序攻关，而是直接瞄准一个更大的对象——**$S$-单位群**。给定有限素理想集合 $S$，$S$-单位是允许在 $S$ 中的素理想上具有非零赋值的元素：

$$
\mathcal O_{K,S}^\times
=\{\alpha\in K^\times:v_{\mathfrak p}(\alpha)=0,\ \forall\mathfrak p\notin S\},
$$

其中 $v_{\mathfrak p}$ 是 $\mathfrak p$ 进赋值。普通单位群是 $S=\varnothing$ 的特例（所有赋值都为零、且范数条件给出单位）。$S$-单位的关系格同时编码三类信息：

- 全部赋值都为零的部分 $\to$ **普通单位群**；
- 元素与理想之间的赋值对应 $\to$ **理想关系格**（即类群）；
- 单个主理想的赋值向量 $\to$ **PIP 的生成元**。

恢复这一个关系格后，单位群、类群与主理想生成元可以依次读出。这就是"改从 $S$-单位群入手"的含义：一个更高维的隐藏格问题，统一了三个经典问题。

## 8. 输入、输出与复杂度口径

把第 6、7 节的口径集中重申，避免误引：

- **输入**：数域以定义多项式（或 $\mathcal O_K$ 的一组整基）给出，规模为 $d$ 与 $\log|\Delta_K|$；理想以 $\mathbb Z$-基给出，规模为其编码长度；另需指定输出精度。
- **输出**：单位群输出 $\mu(K)$ 与基本单位的**紧凑表示**（或对数嵌入的高精度近似）；类群输出不变量分解 $\mathbb Z/n_1\times\cdots\times\mathbb Z/n_s$ 及代表理想；PIP 输出"是/否"及生成元的紧凑表示。若要求把基本单位展开为完整系数，时间至少与输出长度成正比——这是输出大小的下界，不与多项式时间结论矛盾。
- **复杂度**：任意次数算法（Zoo 编号 213、329）关于 $d$、$\log|\Delta_K|$、编码长度与精度均为多项式；固定次数算法（Zoo 编号 50、116）只保证关于 $\log|\Delta_K|$ 多项式。
- **保留条款**：类群部分的复杂度上界通常以 GRH 为前提（见 7.4 节）；结论不能外推到一般格问题（见 6.3 节）。

## 9. 本课小结

- Dirichlet 单位定理把无限单位群分成有限扭转部分与秩 $r=r_1+r_2-1$ 的自由部分；对数嵌入把自由部分变成 $r$ 维超平面 $H$ 中的满秩格 $\Lambda$，其基本平行体体积是调节子 $R_K$。
- 格周期函数的傅里叶谱是对偶格 $\Lambda^*$；量子线路制备陪集态、多维 QFT 直接采样对偶格向量，经典格规约恢复基，再取一次对偶回到 $\Lambda$，最后反解对数嵌入得到基本单位。
- 从一维到高维新增三个困难：峰位是斜格而非等间隔点、约化理想表示带舍入噪声、维数放大边界误差；固定次数与任意次数算法的分水岭正是后两者能否被关于 $d$ 多项式地控制（Lipschitz 连续 HSP + 平滑格编码）。
- 类群计算 = 恢复关系格 + Smith 标准形；判断关系是否为主理想、规范化生成元时遇到的单位歧义，使单位群与 PIP 成为底层子程序；GRH 只用于保证小素理想生成类群，不是量子傅里叶采样正确性的假设；Biasse–Song 用 $S$-单位群把三者统一为一个隐藏格问题。
- 复杂度以 $d$、$\log|\Delta_K|$、编码长度与精度为参数；输出必须是紧凑表示，否则违反输出长度下界。

## 练习题

**练习 1【单位群与 Dirichlet 单位定理】**（→ [2.2 节](#unit-group-dirichlet)）

1. 基础：分别写出实二次域 $\mathbb Q(\sqrt d)$（$d>0$ 非平方）与全虚二次域 $\mathbb Q(\sqrt{-d})$ 的 $(r_1,r_2)$，由 $r=r_1+r_2-1$ 计算单位群的秩，并指出哪一种的单位群是有限群。
2. 基础：对 $K=\mathbb Q(\sqrt5)$、$\varphi=(1+\sqrt5)/2$：计算 $\sigma_1(\varphi)$、$\sigma_2(\varphi)$ 与 $N(\varphi)$，判定 $\varphi$ 是否为单位，并借助 $\varphi^2=\varphi+1$ 写出它的逆。
3. 进阶：证明范数判据的"反向"：若 $u\in\mathcal O_K$ 满足 $|N_{K/\mathbb Q}(u)|=1$，则 $u$ 是单位——写出逆元的表达式并说明它确实是代数整数。

> 提示（第 3 题）：设 $u$ 的极小多项式为 $p(T)=T^n+c_{n-1}T^{n-1}+\cdots+c_0$，由 $p(u)=0$ 把 $u^{-1}$ 写成 $u$ 的整系数多项式，并注意 $|c_0|=1$。

**练习 2【主理想问题与理想类群】**（→ [2.4 节](#pip-class-group)）

1. 基础：写出 PIP 的任务（输入什么、判断什么、输出什么），并解释为什么对任意单位 $u$ 都有 $(\alpha u)=(\alpha)$，从而 PIP 的答案天生带有单位群歧义。
2. 基础：说明 $h_K=1$ 当且仅当 $\mathcal O_K$ 是主理想整环，并用 $6=2\cdot3=(1+\sqrt{-5})(1-\sqrt{-5})$ 指出 $\mathbb Z[\sqrt{-5}]$ 中唯一分解失效的表现。
3. 进阶：在 $K=\mathbb Q(\sqrt{-5})$ 中，验证理想 $\mathfrak p=(2,1+\sqrt{-5})$ 满足 $\mathfrak p^2=(2)$（计算乘积理想的生成元），并由此说明 $[\mathfrak p]$ 在类群中的阶整除 $2$。

> 提示（第 3 题）：$\mathfrak p^2$ 由两两乘积生成，共三个生成元；用它们的整系数线性组合表出 $2$，而每个生成元都属于 $(2)$ 是显然的。

**练习 3【对数嵌入与单位格】**（→ [3.3 节](#unit-log-lattice)）

1. 基础：写出对数嵌入 $L(u)$ 的定义（注意复嵌入处系数 $2$ 的位置），并验证 $L(uv)=L(u)+L(v)$。
2. 基础：解释为什么基本平行体的体积不依赖基的选取（两组基之间相差什么变换？），并说明实二次域时 $R_K$ 与上一课的调节子 $R=\log\varepsilon$ 如何衔接。
3. 进阶：设 $K$ 为实二次域，直接验证任意单位 $u$ 的对数像 $L(u)$ 的两个坐标之和为零（写出范数分解并逐步取对数），并用 $u=\varphi=(1+\sqrt5)/2$ 与 $u=-\varphi^3$ 各验算一次。

> 提示（第 3 题）：先证 $\sigma_2(\varphi)=-1/\varphi$，于是 $|\sigma_1(\pm\varphi^k)|=\varphi^k$、$|\sigma_2(\pm\varphi^k)|=\varphi^{-k}$。

**练习 4【对偶格的傅里叶直觉】**（→ [第 4 节](#dual-lattice-fourier)）

1. 基础：对一维周期 $R$ 的陪集叠加态 $|\psi\rangle\propto\sum_{k}|x_0+kR\rangle$，写出频率 $y$ 处振幅的分解式，并说明未知平移 $x_0$ 为什么不影响测量概率。
2. 基础：解释为什么对偶格 $\Lambda^*$ 自动落在同一超平面 $H$ 中，以及 $(\Lambda^*)^*=\Lambda$ 为什么使算法末端"再求一次对偶"合法。
3. 进阶：证明峰位条件的加法封闭性：若 $y$ 与每个基向量 $\lambda_i$ 都满足 $\langle y,\lambda_i\rangle\in\mathbb Z$，则对任意 $\lambda\in\Lambda$ 有 $\langle y,\lambda\rangle\in\mathbb Z$，从而这些 $y$ 构成加法群。

> 提示（第 3 题）：把 $\lambda$ 展开成基向量的整系数组合，再按内积的双线性拆开。

**练习 5【隐藏格量子算法的线路流程】**（→ [5.2 节](#hidden-lattice-circuit)）

1. 基础：按顺序列出量子线路的四个步骤，并分别写出第一步、第二步制备的态以及第三步测量后第一寄存器坍缩到的态。
2. 进阶：解释周期函数 $f$（"缩放 + 约化"）为什么满足 $f(x+\lambda)=f(x)$：从"乘单位不改变理想"出发，说明对数坐标中的平移 $L(u)$ 对应理想格的什么操作。
3. 进阶：说明固定次数算法与任意次数算法的分水岭：固定次数时为什么允许关于 $d$ 的指数代价？Eisenträger–Hallgren–Kitaev–Song 用哪两个关键思想把代价降到关于 $d$ 也是多项式？

> 提示（第 2 题）：关键事实是 $u\mathcal O_K=\mathcal O_K$（2.3 节已用过）。

**练习 6【从对偶样本恢复单位群】**（→ [5.3 节](#recover-unit-lattice)）

1. 基础：按顺序列出从对偶样本到基本单位的三步经典后处理，并指出其中哪一步用了 $(\Lambda^*)^*=\Lambda$、哪一步用范数判据做最终校验。
2. 进阶：说明为什么算法输出的是基本单位的紧凑表示而不是完整系数，以及这与"多项式时间"结论为什么不矛盾。
3. 进阶：假设采样得到 $r$ 个线性无关的对偶向量 $y_1,\ldots,y_r\in\Lambda^*$。解释为什么它们未必已经生成整个 $\Lambda^*$（提示：考虑 $\mathbb Z^2$ 中由 $(2,0),(0,2)$ 生成的子格，它与 $\mathbb Z^2$ 的关系是什么？基本平行体体积相差多少倍？），并说明如何用体积判据决定何时停止采样。

**练习 7【关系格与 Smith 标准形】**（→ [7.1 节](#relation-lattice-smith)）

1. 基础：写出关系格同态 $\Phi:\mathbb Z^m\to\operatorname{Cl}(K)$ 的定义与 $\ker\Phi$ 中元素的含义，并说明 $\operatorname{Cl}(K)\cong\mathbb Z^m/\ker\Phi$ 的推导中哪一步用到了"$\mathfrak p_i$ 生成类群"。
2. 基础：解释 Smith 标准形给出的分解为什么是不依赖关系基选取的不变量分解，而朴素读数为什么可能依赖。
3. 进阶：对关系矩阵 $M=\begin{pmatrix}4&0\\0&6\end{pmatrix}$ 计算 Smith 标准形，写出对应的有限 Abel 群的不变量分解；它与 $\mathbb Z/4\mathbb Z\times\mathbb Z/6\mathbb Z$ 是否同构？（提示：先求 $\gcd(4,6)$。）

**练习 8【GRH 保留条款与 $S$-单位群】**（→ [7.4 节](#grh-caveat-s-units)）

1. 基础：写出 $S$-单位群 $\mathcal O_{K,S}^\times$ 的定义，并说明 $S=\varnothing$ 时它与普通单位群的关系。
2. 进阶：说明 GRH 在类群算法中出现的位置，并解释"在 GRH 下运行时间为多项式"与"量子算法正确性依赖 GRH"为什么不是同一句话。
3. 进阶：设 $S$-单位群的关系格已求出。描述如何从中分别读出：普通单位群、某个主理想的生成元、以及类群的一个关系（各用一句话说明取关系格的哪一部分信息）。

## 参考文献

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