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

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

本课知识点

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

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，绕不开单位群。

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 定理预言的单位群秩。这不是巧合，而是同一事实的两面。

3.3 格与调节子¶

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

核：$L$ 在 $\mathcal O_K^\times$ 上的核恰好是单位根群 $\mu(K)$。直觉上，$\log|\sigma_i(\zeta)|=\log 1=0$ 对单位根成立；反过来，若 $L(u)=0$ 则所有共轭的绝对值都是 $1$，代数数论证明这样的代数整数只有有限多个，正是单位根；
像：$\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$"在一般框架中的正确写法，就是一维格被放进二维空间的"和为零"超平面里。

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$ 是这张图的平移对称群。

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\}. \]

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

5.3 从对偶样本恢复基本单位¶

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

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

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

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

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$，关系格的基排成矩阵

\[\begin{split} M=\begin{pmatrix}2&0\\0&3\end{pmatrix}, \end{split}\]

即已知关系 $\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{split} \begin{pmatrix}2&-2\\0&3\end{pmatrix}; \end{split}\]

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

\[\begin{split} \begin{pmatrix}2&-2\\0&3\end{pmatrix} \to \begin{pmatrix}2&1\\0&3\end{pmatrix} \end{split}\]

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

\[\begin{split} \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}, \end{split}\]

依次是交换两列、第 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$ 类群。

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 节）

基础：分别写出实二次域 $\mathbb Q(\sqrt d)$（$d>0$ 非平方）与全虚二次域 $\mathbb Q(\sqrt{-d})$ 的 $(r_1,r_2)$，由 $r=r_1+r_2-1$ 计算单位群的秩，并指出哪一种的单位群是有限群。
基础：对 $K=\mathbb Q(\sqrt5)$、$\varphi=(1+\sqrt5)/2$：计算 $\sigma_1(\varphi)$、$\sigma_2(\varphi)$ 与 $N(\varphi)$，判定 $\varphi$ 是否为单位，并借助 $\varphi^2=\varphi+1$ 写出它的逆。
进阶：证明范数判据的"反向"：若 $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 的任务（输入什么、判断什么、输出什么），并解释为什么对任意单位 $u$ 都有 $(\alpha u)=(\alpha)$，从而 PIP 的答案天生带有单位群歧义。
基础：说明 $h_K=1$ 当且仅当 $\mathcal O_K$ 是主理想整环，并用 $6=2\cdot3=(1+\sqrt{-5})(1-\sqrt{-5})$ 指出 $\mathbb Z[\sqrt{-5}]$ 中唯一分解失效的表现。
进阶：在 $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 节）

基础：写出对数嵌入 $L(u)$ 的定义（注意复嵌入处系数 $2$ 的位置），并验证 $L(uv)=L(u)+L(v)$。
基础：解释为什么基本平行体的体积不依赖基的选取（两组基之间相差什么变换？），并说明实二次域时 $R_K$ 与上一课的调节子 $R=\log\varepsilon$ 如何衔接。
进阶：设 $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 节）

基础：对一维周期 $R$ 的陪集叠加态 $|\psi\rangle\propto\sum_{k}|x_0+kR\rangle$，写出频率 $y$ 处振幅的分解式，并说明未知平移 $x_0$ 为什么不影响测量概率。
基础：解释为什么对偶格 $\Lambda^*$ 自动落在同一超平面 $H$ 中，以及 $(\Lambda^*)^*=\Lambda$ 为什么使算法末端"再求一次对偶"合法。
进阶：证明峰位条件的加法封闭性：若 $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 节）

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

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

练习 6【从对偶样本恢复单位群】（→ 5.3 节）

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

练习 7【关系格与 Smith 标准形】（→ 7.1 节）

基础：写出关系格同态 $\Phi:\mathbb Z^m\to\operatorname{Cl}(K)$ 的定义与 $\ker\Phi$ 中元素的含义，并说明 $\operatorname{Cl}(K)\cong\mathbb Z^m/\ker\Phi$ 的推导中哪一步用到了"$\mathfrak p_i$ 生成类群"。
基础：解释 Smith 标准形给出的分解为什么是不依赖关系基选取的不变量分解，而朴素读数为什么可能依赖。
进阶：对关系矩阵 $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 节）

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

参考文献¶

Zoo 编号 50：Sean Hallgren, Fast Quantum Algorithms for Computing the Unit Group and Class Group of a Number Field.
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.
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.