# Pell 方程与主理想问题：从实数周期到量子傅里叶采样

Pell 方程看起来只含平方与整数，却揭示了 Shor 周期查找之后一个更深的主题：周期不一定是整数，也不一定能由一个严格的一一函数隐藏。本课从二次域的"基础单位"出发，推导 Hallgren 如何在实数轴上寻找周期，并说明同一机制为什么能解决主理想问题。

阅读本课前，我们假设你已经掌握[量子傅里叶变换](../ch03-algo-basics/quantum-fourier-transform.md)、[相位估计](../ch03-algo-basics/phase-estimation.md)和 [Shor 因数分解](../ch04-classic-algorithms/shors-algorithm-tutorial.md)。我们不会再推导 QFT 本身，但会反复用到 Shor 算法的整体框架："制备叠加—可逆计算函数值—测量—QFT—经典后处理恢复周期"。本课的核心是看清：当周期变成实数、函数变成多对一且带跳变时，这个框架的哪几步会出问题，以及如何补救。

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

1. **[Pell 方程与基础单位](#pell-fundamental-unit)**——能写出 Pell 方程并说明它的解就是二次域中范数为 $1$ 的单位，进而证明所有正解恰为基础单位 $\varepsilon$ 的幂并完成 $d=2$ 的演算。
2. **[调节子与输出长度](#regulator-output-length)**——能论证直接输出最小解 $(x_1,y_1)$ 受指数级输出长度下界的限制，并解释为什么 $R=\log\varepsilon$ 的高精度值是多项式长度的无损压缩。
3. **[经典算法的边界](#classical-barriers)**——能比较连分数法与次指数算法的耗时来源，并说明因数分解到 Pell 型问题的约化方向及反向约化未知意味着什么。
4. **[主理想与生成元的非唯一性](#principal-ideal-generators)**——能写出分式理想与主理想的定义，证明 $(\alpha)=(\beta)$ 当且仅当 $\beta=\alpha\varepsilon^k$，并解释生成元在对数轴上构成间隔为 $R$ 的等差点列。
5. **[约化理想与实数周期函数](#infrastructure-periodic-function)**——能说明约化理想与 infrastructure 如何把 $R$ 编码为可计算的周期函数 $f$，验证 $f(t+R)=f(t)$，并指出多对一与边界跳变两处缺陷。
6. **[量子实数周期查找](#quantum-period-finding)**——能按网格化、制备叠加、测量、QFT 四步写出各阶段寄存器状态，推导谱峰条件 $k/q\approx\ell/(NR)$，并复算 $d=2$ 的玩具数值示例。
7. **[正确性的三个误差源](#error-sources)**——能列出网格化、函数缺陷、窗口截断三个误差源，并说明为什么三者可控时谱峰保留逆多项式概率、重复多项式次采样即可恢复 $R$。
8. **[隐藏平移求解主理想问题](#hidden-shift-pip)**——能推导谱峰相位因子 $e^{2\pi i\ell\log|\alpha|/R}$ 的来源，并解释为什么生成元只能恢复到模 $R$、而这源于问题本身的非唯一性。

:::

(pell-fundamental-unit)=
## 1. Pell 方程：问题从哪里来

设 $d$ 是一个正的、非完全平方的整数（例如 $d=2,3,5,6,7,8,\dots$；$d=4$ 被排除，因为那时方程退化）。**Pell 方程**是

$$
x^2-dy^2=1,\qquad x,y\in\mathbb Z.
$$

这是一个丢番图方程：我们只在整数里找解。它有两个平凡解 $(x,y)=(\pm1,0)$，除此以外的解称为非平凡解。Lagrange 证明了一个经典事实：只要 $d$ 是非平方正整数，非平凡解一定存在。所以问题从来不是"有没有解"，而是"最小的那个解有多大、能不能算出来"。

这个方程为什么重要？至少有三层原因。

- **代数原因**：$x^2-dy^2$ 恰好是数 $x+y\sqrt d$ 在二次域 $\mathbb Q(\sqrt d)$ 中的范数。Pell 方程的解就是这个域里范数为 $1$ 的代数整数——即所谓**单位 (unit)**。求 Pell 方程的解，等价于求二次域的单位群，这是代数数论最基本的计算任务之一。
- **算法原因**：最小解可以大到难以置信。著名的例子是 $d=61$（这是 Fermat 在 1657 年向同行提出的挑战）：最小正解是

$$
(x_1,y_1)=(1766319049,\;226153980),
$$

而 $d=62$ 的最小解只有 $(63,8)$。$d$ 只增加 $1$，答案的位数却相差近十位数。这种"输入稍微变一点、输出大小就剧烈跳动"的现象预示着：问题的难度不在 $d$ 的数值，而在某个隐藏的、起伏剧烈的数论对象上。
- **复杂性原因**：Hallgren 证明了 Pell 方程（的适当版本）与**主理想问题 (principal ideal problem, PIP)** 存在多项式时间的量子算法；而已知的经典算法一般都是次指数的。因此它是"量子计算在整数分解之外真正扩大优势版图"的标志性问题之一，也是通往类群计算、进而通往更多数论问题的入口（见[单位群与类群](unit-class-groups.md)）。

## 2. 基础单位与解的全部结构

### 2.1 范数与共轭

把方程因式分解到 $\mathbb Q(\sqrt d)$ 中看。对 $\alpha=x+y\sqrt d$（$x,y\in\mathbb Z$），定义它的**共轭**与**范数**为

$$
\bar\alpha=x-y\sqrt d,\qquad N(\alpha)=\alpha\bar\alpha=x^2-dy^2.
$$

范数的关键性质是**乘性**：对任意 $\alpha,\beta\in\mathbb Q(\sqrt d)$，

$$
N(\alpha\beta)=N(\alpha)N(\beta).
$$

验证只需一行：记 $\beta=u+v\sqrt d$，则

$$
N(\alpha\beta)=(\alpha\beta)(\overline{\alpha\beta})=(\alpha\bar\alpha)(\beta\bar\beta)=N(\alpha)N(\beta),
$$

其中用到 $\overline{\alpha\beta}=\bar\alpha\bar\beta$（共轭是域自同构：它保持加减乘，把 $\sqrt d$ 送到 $-\sqrt d$）。

Pell 方程的解恰好是 $N(\alpha)=1$ 的元素。乘性立刻解释了两件事：

- 若 $\alpha$ 是解，则 $N(\alpha^2)=N(\alpha)^2=1$，所以 $\alpha$ 的任意幂仍是解——解在乘法下封闭；
- 若 $N(\alpha)=1$，则 $\alpha^{-1}=\bar\alpha$ 也是解——解在取逆下封闭。

于是 Pell 方程的解集构成一个乘法群，它就是 $\mathbb Q(\sqrt d)$ 中代数整数环的**单位群**。这就是为什么解 Pell 方程等于计算二次域的单位群。

### 2.2 最小解生成一切

在所有满足 $x+y\sqrt d>1$ 的解中，取使 $x+y\sqrt d$ 最小的那个（由 Lagrange 的存在性定理，这样的最小者存在）。记它的系数为 $(x_1,y_1)$，并定义**基础单位 (fundamental unit)**

$$
\varepsilon=x_1+y_1\sqrt d>1.
$$

注意 $\varepsilon$ 的共轭满足

$$
\bar\varepsilon=x_1-y_1\sqrt d=\frac{N(\varepsilon)}{\varepsilon}=\frac1\varepsilon=\varepsilon^{-1},
$$

第一步用定义，第二步用 $N(\varepsilon)=1$（因为 $(x_1,y_1)$ 是 Pell 方程的解），第三步就是 $1/\varepsilon$ 的记号。这个恒等式后面会反复用到：乘 $\varepsilon^{-1}$ 就是乘 $\bar\varepsilon$，而后者的系数仍是整数。

**Lemma 1**. Pell 方程的所有满足 $x+y\sqrt d>0$ 的解恰好是 $\{\varepsilon^k:k\in\mathbb Z\}$。也就是说，若把解从小到大排成 $(x_k,y_k)$，则

$$
x_k+y_k\sqrt d=\varepsilon^k.
$$

**证明**。分两步。

第一步，每个 $\varepsilon^k$ 都是解：由范数乘性，$N(\varepsilon^k)=N(\varepsilon)^k=1$，且 $\varepsilon^k>0$。

第二步，没有别的解。设 $\alpha=x+y\sqrt d>1$ 是任一解（$0<\alpha<1$ 的情形用 $\alpha^{-1}$ 代替即可）。由于 $\varepsilon>1$，数列 $\varepsilon^k$ 严格递增且趋于无穷，故存在唯一的整数 $k\ge0$ 使

$$
\varepsilon^k\le\alpha<\varepsilon^{k+1}.
$$

令 $\beta=\alpha\varepsilon^{-k}=\alpha\bar\varepsilon^{\,k}$。因为 $\bar\varepsilon$ 的系数是整数，$\beta$ 形如 $u+v\sqrt d$，$u,v\in\mathbb Z$；又由乘性 $N(\beta)=N(\alpha)N(\varepsilon)^{-k}=1$，所以 $\beta$ 也对应 Pell 方程的解。而上面的不等式两边同乘 $\varepsilon^{-k}>0$ 给出

$$
1\le\beta<\varepsilon.
$$

若 $\beta>1$，则 $(u,v)$ 是比 $(x_1,y_1)$ 更小的正解，与 $\varepsilon$ 的最小性矛盾。因此 $\beta=1$，即 $\alpha=\varepsilon^k$。Q.E.D.

这个引理把"无穷多个解"压缩成一个对象 $\varepsilon$：**求 Pell 方程的全部解 = 求基础单位**。一切计算目标都应围绕 $\varepsilon$ 展开。

### 2.3 小例子：$d=2$

把上面的结构完整算一遍。先试小的 $y$：

- $y=1$：$x^2=1+2\cdot1=3$，不是平方数；
- $y=2$：$x^2=1+2\cdot4=9$，$x=3$。

所以最小正解是 $(x_1,y_1)=(3,2)$，基础单位与共轭为

$$
\varepsilon=3+2\sqrt2\approx5.82842712,\qquad \varepsilon^{-1}=\bar\varepsilon=3-2\sqrt2\approx0.17157288.
$$

两者的乘积是 $(3+2\sqrt2)(3-2\sqrt2)=9-8=1$，确实是范数 $1$。调节子（下面正式定义）为

$$
R=\log(3+2\sqrt2)\approx1.76275.
$$

按 Lemma 1，下一个解应当是 $\varepsilon^2$：

$$
\varepsilon^2=(3+2\sqrt2)^2=9+12\sqrt2+8=17+12\sqrt2,
$$

检验：$17^2-2\cdot12^2=289-288=1$。再来一个：

$$
\varepsilon^3=\varepsilon\cdot\varepsilon^2=(3+2\sqrt2)(17+12\sqrt2)=51+36\sqrt2+34\sqrt2+48=99+70\sqrt2,
$$

检验：$99^2-2\cdot70^2=9801-9800=1$。三个解 $(3,2),(17,12),(99,70)$ 确实排成 $\varepsilon$ 的幂，系数增长约 $\varepsilon\approx5.83$ 倍——这就是"幂次增长"的直观含义。

(regulator-output-length)=
## 3. 为什么输出必须重新定义：调节子

现在进行复杂性分析的第一步：明确输入和输出的长度。

输入是 $d$，它的比特长度是

$$
n=\lceil\log_2 d\rceil.
$$

输出如果是 $(x_1,y_1)$ 本身，那么麻烦来了：$x_1,y_1$ 可能需要**指数多个比特**才能写下。原因可以从 Lemma 1 看出：$\varepsilon=x_1+y_1\sqrt d$ 完全可能大到 $d$ 的指数量级（$d=61$ 的例子已经给出预告：$d$ 只有 $6$ 个比特，$x_1$ 却有 $10$ 位十进制数，而且这个比值随 $d$ 增大没有多项式上界）。一旦 $x_1\sim e^{c\cdot\operatorname{poly}(n)}$，仅仅"把答案打印出来"就需要指数时间。

这是一个**输出长度下界**：任何声称在 $\operatorname{poly}(n)$ 时间内直接打印完整 $(x_1,y_1)$ 的算法都违反它，无论量子还是经典。所以，要谈论多项式时间算法，必须先修改计算目标。正确的目标是**调节子 (regulator)**

$$
R=\log\varepsilon,
$$

或基础解的紧凑乘积表示（例如把 $\varepsilon$ 表示成若干短元素的幂积）。$R$ 是一个普通的正实数，它的前 $n$ 位有效数字只需 $O(n)$ 个比特——输出长度回到了多项式。

为什么给出足够精度的 $R$ 就"等于"解决了问题？因为 $\varepsilon=e^R$，给定 $R$ 的足够多位小数后，可以按需要逐步恢复 $x_1,y_1$ 的任意前缀：$\varepsilon$ 是代数整数，$x_1=(\varepsilon+\varepsilon^{-1})/2$，用高精度实数运算即可逐位提取。换句话说，$R$ 是基础单位的**多项式长度无损压缩**：信息没有丢，只是换了一种表示。本课中"求解 Pell 方程"一律指"计算 $R$ 到多项式位精度"。

(classical-barriers)=
## 4. 经典算法能走多远

在引入量子算法之前，先搞清楚经典计算的边界，这样才知道量子加速到底加速了什么。

- **连分数法**：经典理论给出 $\sqrt d$ 的连分数展开是周期的，而 Pell 方程的最小解可以从一个周期内的渐近分数读出。这个方法优雅且对小 $d$ 极快，但它的运行时间正比于连分数周期的长度——而周期长度与 $\log\varepsilon=R$ 同阶增长，最坏情况关于 $n$ 是指数的。$d=61$ 的巨大解正对应很长的周期。
- **次指数算法**：借助数域筛与类群计算的技术，已知的经典算法对调节子与主理想问题一般为**次指数**而非多项式（典型形式是关于 $\log d$ 的 $L$ 记号，即 $\exp\big((\log d)^c(\log\log d)^{1-c}\big)$ 型的时间，$0<c<1$）。这与整数分解的经典处境非常相似。
- **与因数分解的关系**：因数分解可以**约化到** Pell 型问题（给定合数 $N$，某些与 $N$ 相关的 Pell 方程的解泄露 $N$ 的因子），但反方向没有已知约化——没人知道如何用分解整数预言机高效求解 Pell 方程。所以不能简单称二者"等价"；Pell/PIP 很可能是比因数分解更难的问题。

## 5. 直觉：理想为什么会形成一把"周期尺"

量子算法需要的不是一个数论对象，而是一个**可计算的周期函数**。本节先给直觉，下一节再给形式化定义。

回顾 Shor 算法：周期 $r$ 藏在函数 $j\mapsto a^j\bmod N$ 里，定义域是整数，函数严格周期（$a^{j+r}\equiv a^j$）且在周期内一一对应。QFT 之所以干净利落地给出谱峰，靠的正是这两条性质。

Pell 方程的 $R$ 也想藏进一个函数里，但有两个本质困难：

1. $R$ 是**实数**，不是整数。定义域必须也换成实数轴，或者换成实数轴的网格；
2. 没有自然的"指数函数"把 $t$ 映到有限集合。能用的只有二次域的**理想**。

直觉是这样的。把 $\mathbb Q(\sqrt d)$ 中所有主理想 $(\alpha)$ 想成平面上的点。乘上基础单位不改变理想：$(\alpha\varepsilon)=(\alpha)$（理想只关心生成元相差一个可逆元）。在对数坐标里，"乘 $\varepsilon$"就是"平移 $R=\log\varepsilon$"。于是所有主理想在一条长度为 $R$ 的"圆环"上重复出现——$R$ 成了这条圆环的周长。量子算法要做的，就是沿着这条圆环均匀采样，再用傅里叶变换读出周长。

把"圆环上的点"做成可在多项式时间内计算的对象，靠的是**约化理想 (reduced ideal)**：每个理想都有一个规范的约化代表，约化理想只有有限多个，并且它们可以按"距离"排成一个环状结构，称为 **infrastructure**（基础设施）。沿实数轴移动距离 $t$、随时约化，就得到规范理想 $f(t)$——这就是我们的周期函数。

这个函数有两处"缺陷"，正是本课的技术核心：

- 它是**多对一**的：$t$ 的一小段区间可能映到同一个约化理想（约化有"粘性"）；
- 它在某些点**跳变**：$t$ 跨过约化边界时 $f(t)$ 不连续。

Shor 的谱峰证明建立在"周期内一一对应"上，这里两条性质都失效，所以必须重做傅里叶分析——但正如后文将看到的，缺陷可以被压成低比例事件，谱峰依然存活。

## 6. 二次域与理想：把直觉变成函数

### 6.1 二次域、整数环与理想

**实二次域**是

$$
K=\mathbb Q(\sqrt d)=\{a+b\sqrt d:a,b\in\mathbb Q\},
$$

它对加减乘除封闭（除法用分母有理化）。$K$ 中的**代数整数环**记作 $\mathcal O_K$：粗略地说，它是 $K$ 中满足整系数首一多项式的元素构成的环（对 $d\equiv2,3\pmod4$ 就是 $\mathbb Z[\sqrt d]$；$d\equiv1\pmod4$ 时还包含 $\frac{1+\sqrt d}{2}$ 这样的元素）。细节不影响本课，只需记住 $\mathcal O_K$ 是 $\mathbb Z$ 在 $K$ 中的类比。

**分式理想 (fractional ideal)** $I\subset K$ 是一个非零子集，满足：对加法封闭；对 $\mathcal O_K$ 中元素的乘法封闭（$r\in\mathcal O_K,\ x\in I\Rightarrow rx\in I$）；并且存在非零的 $m\in\mathcal O_K$ 使 $mI\subseteq\mathcal O_K$（"分母有界"）。几何上，$I$ 是 $K\cong\mathbb Q^2$ 中的一个**格 (lattice)**：存在 $\omega_1,\omega_2\in I$ 使 $I=\mathbb Z\omega_1+\mathbb Z\omega_2$。这个格结构正是理想可以被多项式比特描述、并在经典多项式时间内运算（相加、相乘、比较）的原因。

若存在 $\alpha\in K^\times$ 使

$$
I=(\alpha)=\alpha\mathcal O_K=\{\alpha r:r\in\mathcal O_K\},
$$

则称 $I$ 为**主理想 (principal ideal)**。**主理想问题 (PIP)**：给定理想 $I$（以格基形式给出），判断它是否为主理想；若是，求生成元 $\alpha$ 的紧凑描述。

(principal-ideal-generators)=
### 6.2 单位与"乘 $\varepsilon$ 不改变理想"

PIP 与 Pell 方程的桥梁是下面这个简单事实。设 $I=(\alpha)$，$k\in\mathbb Z$，则

$$
(\alpha\varepsilon^k)=(\alpha).
$$

**验证**：$\varepsilon^k\in\mathcal O_K$ 给出 $\alpha\varepsilon^k\mathcal O_K\subseteq\alpha\mathcal O_K$；反之 $\varepsilon^{-k}\in\mathcal O_K$（因为 $\varepsilon^{-1}=\bar\varepsilon$ 系数为整数）给出 $\alpha\mathcal O_K=\alpha\varepsilon^k\cdot\varepsilon^{-k}\mathcal O_K\subseteq\alpha\varepsilon^k\mathcal O_K$。两方向包含即相等。换句话说，**生成元只确定到单位倍数**：$(\alpha)=(\beta)$ 当且仅当 $\beta=\alpha\varepsilon^k$ 对某个 $k\in\mathbb Z$ 成立（反方向用 $\beta\alpha^{-1}$ 是范数 $\pm1$ 的代数整数、即单位，而二次域的单位群就是 $\{\pm\varepsilon^k\}$——这正是 Lemma 1 的代数表述）。

对数坐标把乘法变加法：

$$
\log|\alpha\varepsilon^k|=\log|\alpha|+kR.
$$

所以"所有生成同一个主理想的生成元"在对数轴上恰好是一个间隔为 $R$ 的等差点列。$R$ 就是这个点列的周期。

(infrastructure-periodic-function)=
### 6.3 约化理想与 infrastructure

把上面的点列变成可计算函数还需要一步：规范化。二次域理论（与二元二次型的约化理论等价）给出：

- 每个理想有唯一的**约化**代表，约化理想只有有限多个（准确数目与 $\sqrt d$ 同阶量级，但每个都可用多项式比特表示）；
- 从一个约化理想出发，可以做"向前一步"的局部操作（约化步），把整个理想类排成一个环；环上每个位置附带一个连续的**距离 (distance)** 标签，相邻位置的距离差可以多项式时间计算；
- 从距离 $t$ 处的理想走到距离 $t+\delta$ 处的理想，是多项式时间的经典操作。

综合起来，我们得到一个函数：对实数 $t$，$f(t)$ 是"从 $\mathcal O_K$ 出发、沿 infrastructure 走到距离 $t$ 再约化"所得的规范理想（连同局部距离标签，使函数在点附近可区分——这是对付多对一性的技巧之一）。由于乘 $\varepsilon$ 不改变主理想，沿环走一圈恰好回到原地，而对数坐标中一圈的长度是 $R$，因此

$$
f(t+R)=f(t)\qquad\text{对所有 }t\in\mathbb R.
$$

**$R$ 是隐藏在约化理想序列中的实数周期。** 这就是量子算法要挖的矿。

与 Shor 的 $a^j\bmod N$ 不同，$f$ 在约化边界处不连续，并且一段小区间可能映到同一个理想（多对一）。算法的核心难点正是证明这些缺陷不会抹掉傅里叶谱峰。

(quantum-period-finding)=
## 7. 量子算法：实数周期查找

### 7.1 网格化

量子计算机仍是离散设备，不能直接处理连续变量 $t$。选择两个参数：

- **网格精度** $N$：把 $t$ 离散为 $t=j/N$，$j\in\mathbb Z$；
- **窗口长度** $q$：只取 $j=0,1,\dots,q-1$（$q$ 取 $2$ 的幂以便用标准 QFT）。

于是"周期"在对网格而言表现为：$j$ 与 $j+NR$ 给出同一个理想。注意 $NR$ 一般不是整数，这本身就是误差来源之一（见第 8 节）。

### 7.2 状态制备与函数求值

第一步，在第一寄存器制备均匀叠加（$q$ 点 Hadamard 或直接用 QFT 作用于 $|0\rangle$）：

$$
\frac1{\sqrt q}\sum_{j=0}^{q-1}|j\rangle|0\rangle.
$$

第二步，可逆计算约化理想及其局部距离标签。上节说过，从 $\mathcal O_K$ 走距离 $t=j/N$ 再约化是多项式时间经典操作，因此可以做成可逆电路：

$$
|j\rangle|0\rangle\longmapsto|j\rangle\big|\widetilde f(j/N)\big\rangle,
$$

其中 $\widetilde f$ 表示理想加上距离标签的完整编码（带波浪线提醒我们：它是 $f$ 的"增强版"，标签使相邻点更可能被区分开）。

整个状态是

$$
\frac1{\sqrt q}\sum_{j=0}^{q-1}|j\rangle\big|\widetilde f(j/N)\big\rangle.
$$

### 7.3 测量得到"梳子"

测量第二寄存器，得到某个约化理想 $I_0$。第一寄存器坍缩到所有满足 $\widetilde f(j/N)=I_0$ 的 $j$ 的叠加。由周期性，这些 $j$ 近似构成等差数列

$$
j\approx j_0+m\cdot NR,\qquad m=0,1,2,\dots,
$$

即第一寄存器集中在若干**近似等间隔**的位置，间距约为 $NR$。"近似"二字包含两层：$NR$ 不是整数，所以实际间距在 $\lfloor NR\rfloor$ 与 $\lceil NR\rceil$ 间抖动；多对一性可能让相邻的坏点混入。先忽略这些缺陷，看理想情形。

### 7.4 QFT 与谱峰

对第一寄存器做 $q$ 点 QFT。若测量后的状态是理想的梳子

$$
|\psi\rangle=\frac1{\sqrt M}\sum_{m=0}^{M-1}|j_0+mT\rangle,\qquad T=NR,\ M\approx\frac qT,
$$

则 QFT 后 $|k\rangle$ 的振幅为

$$
\frac1{\sqrt{qM}}\sum_{m=0}^{M-1}e^{2\pi i k(j_0+mT)/q}
=\frac{e^{2\pi i k j_0/q}}{\sqrt{qM}}\sum_{m=0}^{M-1}\left(e^{2\pi i kT/q}\right)^m.
$$

这是一个等比数列求和（与 Shor 算法中的分析完全同型）。当 $kT/q$ 接近整数 $\ell$ 时，公比 $e^{2\pi i kT/q}\approx1$，各项同相相加，振幅大小约 $\sqrt{M/q}$，概率约 $M/q\approx1/T$——**相长干涉**；当 $kT/q$ 离整数较远时，各项相位均匀绕单位圆，求和相消。因此谱峰出现在满足

$$
\frac{k}{q}\approx\frac{\ell}{T}=\frac{\ell}{NR},\qquad \ell\in\mathbb Z
$$

的 $k$ 处。测量 QFT 后的寄存器，就以可观的概率得到这样一个 $k$。

### 7.5 经典后处理：从对偶样本恢复 $R$

每个样本给出

$$
\frac{k}{q}\approx\frac{\ell}{NR},
$$

其中 $k,q,N$ 已知，$\ell$ 是未知整数，$R$ 是目标。单个样本含两个未知量，无法直接解出 $R$（这正是练习 6 第 3 题的内容）。标准做法与 Shor 算法后处理同精神：重复采样得到若干近似的对偶周期，用**连分数**把每个 $k/q$ 展开、寻找与小整数 $\ell$ 相容的候选 $NR$，再用**格规约**把多个含噪样本联合起来，求出一致的高精度 $R$。只要样本数与精度都取输入长度的多项式，恢复 $R$ 的成功概率就是高概率。

### 7.6 玩具数值示例：把谱峰算一遍

用 $d=2$ 的真实调节子 $R\approx1.76275$ 演算整个过程。取网格精度 $N=16$、窗口 $q=256$，则梳齿间距

$$
T=NR\approx16\times1.76275=28.204.
$$

测量第二寄存器后，第一寄存器近似是间距 $28$ 左右的梳齿叠加，齿数约 $M\approx q/T\approx9$。对第一寄存器做 $q$ 点 QFT，谱峰应出现在 $k\approx q\ell/T\approx9.077\,\ell$ 处，即

$$
k\approx9,\;18,\;27,\;36,\dots
$$

检验相长干涉：在 $k=9$ 处，等比求和的公比相位为

$$
\frac{2\pi kT}{q}=\frac{2\pi\times9\times28.204}{256}\approx2\pi\times0.9916,
$$

离整数 $1$ 只差约 $0.05$ 弧度/步，$9$ 项几乎同相相加；而在邻近的 $k=10$ 处，相位是 $2\pi\times1.1017$，每步偏 $0.64$ 弧度，$9$ 项累计展开约 $5$ 弧度、绕单位圆将近一圈，求和明显相消。谱峰确实立在 $k=9$ 附近。

经典后处理：测得 $k=9$ 后，由峰条件 $k/q\approx\ell/(NR)$ 解出

$$
R\approx\frac{\ell q}{kN}.
$$

$\ell$ 未知，但从小整数试起：$\ell=1$ 给出 $\widehat R=256/(9\times16)=1.7778$，与真值 $1.76275$ 的相对误差约 $0.85\%$。误差来自 $k$ 只能取整数（峰宽约为一个格子），把 $q,N$ 加大即可按比例压低。关键是再取第二个样本：若测得 $k=18$，它对应 $\ell=2$，给出 $\widehat R=2\times256/(18\times16)=1.7778$；测得 $k=27$（$\ell=3$）给出 $3\times256/(27\times16)=1.7778$。**不同 $\ell$ 的样本给出一致的 $R$ 估计**——这种一致性正是区分真峰与噪声、并确定 $\ell$ 的依据，也是第 7.5 节连分数与格规约所做的事的雏形。

(error-sources)=
## 8. 正确性的三个误差源

第 7.4 节的分析是在理想梳子上做的。真实状态偏离理想梳子有三条路，任何一条失控都会毁掉谱峰：

1. **网格化误差**：连续变量 $t$ 被 $j/N$ 代替，周期 $NR$ 不是整数，梳齿位置在小数级别抖动；
2. **函数缺陷**：约化理想函数在边界跳变，且多对一——测量后第一寄存器混入了不属于梳子的"坏点"；
3. **窗口截断**：真正的周期列无穷长，而 $q$ 有限，截断在谱上引入泄漏（sidelobe）。

Hallgren 的分析（以及 Schmidt 针对多对一情形的改进）表明，可以按下述思路同时控制三者：把网格精度 $N$ 与窗口 $q$ 取为输入长度的多项式比特规模，使

- 误差源 1 造成的相位偏差远小于一个 QFT 谱峰的宽度（直觉：抖动幅度 $\ll1$，而 $q$ 足够大时，峰宽对应的相位容差足以吸收它）；
- 误差源 2 中的坏网格点比例被压低到逆多项式以下，从而让理想梳齿仍然携带总振幅的常数份额；
- 误差源 3 的泄漏只影响远离主峰的频率。

综合结果是：**谱峰保留逆多项式概率**。一旦单次采样成功概率是 $1/\operatorname{poly}(n)$，重复多项式次即可得到足够多样本（期望重复次数就是该概率的倒数）。同时注意，整个过程中寄存器保存的是 $R$ 的比特（多项式长），而不是大小为 $e^R$ 的整数——空间复杂度因此也是多项式的。这与第 3 节"调节子是正确的输出格式"前后呼应：算法从来不需要、也从来不会把基础单位本身展开。

定性地总结正确性论证的形状：把真实状态写成"理想梳子 + 小误差"的分解，分别用 $N,q$ 的多项式规模压住三项误差，再用有限几何级数估计谱峰处的相长干涉。所有"显然可以忽略"的地方，正是证明的技术含量所在。

(hidden-shift-pip)=
## 9. 从周期到主理想生成元

有了周期 $R$，PIP 变成同一结构上的**隐藏平移 (hidden shift)** 问题。回忆第 6.2 节：若 $I=(\alpha)$，则 $I$ 的约化序列与 $\mathcal O_K$ 的序列是同一个环，只是起点不同。精确地说，

$$
f_I(t)=f_{\mathcal O_K}\big(t+\log|\alpha|\big),
$$

即 $I$ 的 infrastructure 函数是 $\mathcal O_K$ 的函数平移了 $\log|\alpha|$。道理直接：把 $\mathcal O_K$ 的环上每个理想乘上 $\alpha$，就得到 $I$ 的环；乘法在对数坐标里是平移 $\log|\alpha|$。求生成元 $\alpha$ 因此等价于求这个平移量。

算法分四步：

1. **求周期**：用第 7 节的周期采样求 $R$（对 $\mathcal O_K$ 做一次即可）；
2. **带偏移的傅里叶采样**：对两条 infrastructure 序列分别制备第 7.3 节的梳子态并做 QFT——等价地，在一个寄存器中叠加两个函数 $f_{\mathcal O_K}$ 与 $f_I$，测量后得到同时依赖于周期 $R$ 与平移 $\log|\alpha|$ 的对偶样本（隐藏平移问题的标准采样方式，与第 7.4 节同型，只是梳子的相位里多出一个与平移成正比的项，见下面的推导）；
3. **解出位移**：由样本解出 $\log|\alpha|\pmod R$；
4. **经典验证**：由 $\log|\alpha|$ 的近似值构造候选生成元（用高精度实数与格运算），多项式时间验证它生成的理想是否确实等于 $I$；同时，若第 2、3 步找不到任何一致的位移，就判定 $I$ 不是主理想。

第 2 步中相位如何携带位移，可以直接算出来。$f_I$ 的梳子与 $f_{\mathcal O_K}$ 的梳子形状相同，只是所有梳齿位置平移了 $\delta=\log|\alpha|$：若 $\mathcal O_K$ 的梳子在 $j_0+mT$ 处，$I$ 的梳子就在 $j_0+\delta+mT$ 处（这里 $\delta$ 以网格为单位）。重复第 7.4 节的等比求和，$I$ 侧在 $|k\rangle$ 处的振幅多出一个因子

$$
e^{2\pi i k\delta/q}.
$$

在谱峰 $k/q\approx\ell/(NR)$ 处代入 $k\approx q\ell/(NR)$，这个相位变成

$$
e^{2\pi i\ell\delta/(NR)}=e^{2\pi i\ell\log|\alpha|/R}.
$$

于是同一个 $\ell$ 下，两侧样本的相位差正比于 $\log|\alpha|/R$：频率标签 $\ell$ 已知（由峰位置读出），相位差可测，二者相乘即得 $\log|\alpha|$——但只能确定到模 $R$，因为相位本身是以 $2\pi$ 为周期的，$\log|\alpha|$ 增加 $R$ 时 $\ell\log|\alpha|/R$ 增加整数 $\ell$，相位不变。

关于第 3 步的"$\bmod\ R$"：单位 $\varepsilon^k$ 会把生成元改为 $\alpha\varepsilon^k$，在对数轴上平移 $kR$。所以算法只能把 $\log|\alpha|$ 确定到模 $R$——这不是算法缺陷，而是主理想生成元本来就不唯一（第 6.2 节）。模 $R$ 的任一代表都同样合法。

## 10. 复杂度、优势与边界

把全文的资源消耗逐项清点：

- **量子部分**：每次采样用 $O(\log q)=O(\operatorname{poly}(n))$ 个量子比特；电路是"制备均匀叠加 + 一次理想计算 + 一次 $q$ 点 QFT"，门数关于 $\log q$ 与理想计算的经典复杂度是多项式。理想计算是经典多项式时间操作，所以整个电路深度是 $\operatorname{poly}(n)$。
- **采样次数**：第 8 节给出单次成功概率为逆多项式，故重复多项式次；后处理（连分数 + 格规约）是多项式时间。
- **总计**：量子运行时间关于 $\log d$（即输入长度 $n$）和要求的精度位数是**多项式**。
- **经典对比**：已知经典算法对调节子与 PIP 一般为次指数而非多项式（第 4 节）。因此这是一个超多项式（推测为指数级）的量子加速，且问题本身不属于因数分解的已知约化范围之内。

最后必须区分三个结论，它们经常被混为一谈：

1. **输出格式**：Pell 调节子与实二次域 PIP 的多项式时间算法，建立在"不直接输出指数长整数、只输出 $R$ 或紧凑表示"之上（第 3 节）。这不是偷懒，而是输出长度下界所迫。
2. **假设条件**：本节以上所有内容是无条件的。但若要用这些工具进一步计算**类群**，某些"小素理想生成类群"的步骤通常要假设**广义黎曼猜想 (GRH)**——那是一个独立的、启发式/模型依赖的保留条款，与本课算法的正确性无关，但引用后续结果时不能省略。
3. **推广范围**：任意次数的数域中，单位不再是单个 $\varepsilon$ 而是高维单位格，infrastructure 也要推广；Biasse 与 Song 给出了任意次数数域上类群与 PIP 的高效量子算法，需要更高维的单位格技术，见[下一课](unit-class-groups.md)。

## 11. 本课小结

- Pell 方程的解是二次域的单位；由 Lemma 1，所有正解是基础单位的幂，问题归结为求 $\varepsilon$。
- 基础解可能占指数多比特，自然的压缩量是**调节子** $R=\log\varepsilon$；多项式时间算法以 $R$ 为输出。
- 主理想的生成元只确定到单位倍数；在对数坐标中它们构成间隔 $R$ 的等差点列。
- 约化理想的 infrastructure 把 $R$ 编码为实数周期 $f(t+R)=f(t)$；量子算法在网格上采样、用 QFT 读出对偶频率 $k/q\approx\ell/(NR)$，再用连分数与格规约恢复 $R$。
- 正确性证明必须同时控制网格化、边界跳变/多对一、窗口截断三种误差；分析结论是谱峰保留逆多项式概率，重复多项式次即可。
- PIP 是同一周期结构上的隐藏平移问题：$f_I(t)=f_{\mathcal O_K}(t+\log|\alpha|)$，求出位移即求出生成元（模 $R$）。
- 量子时间为 $\operatorname{poly}(\log d)$；已知经典算法次指数；因数分解可约化到 Pell 型问题但反向约化未知，二者不能称等价。

## 练习题

**练习 1【Pell 方程与基础单位】**（→ [第 1 节](#pell-fundamental-unit)）

1. 基础：写出 $d=7$ 时的 Pell 方程与它的两个平凡解；再把 $d$ 换成完全平方数 $d=4$，用因式分解 $x^2-4y^2=(x-2y)(x+2y)$ 说明方程为什么只剩平凡解。
2. 基础：验证 $(3+2\sqrt2)^2=17+12\sqrt2$，并检查两组系数都满足 Pell 方程；再用范数乘性（不展开乘法）解释为什么 $\varepsilon^k$ 自动是解。
3. 进阶：仿照第 2.3 节，对 $d=3$ 找出最小正解（逐个试 $y=1,2,\dots$），写出基础单位 $\varepsilon$、共轭 $\varepsilon^{-1}$ 与调节子 $R$ 的近似值，并用 $\varepsilon^2$ 验证 Lemma 1。

> 提示（第 3 题）：从 $y=1$ 试起；$\varepsilon^2$ 的系数可用 $(a+b\sqrt3)^2=a^2+3b^2+2ab\sqrt3$ 直接展开。

**练习 2【调节子与输出长度】**（→ [第 3 节](#regulator-output-length)）

1. 基础：对 $d=2$，由 $\varepsilon=3+2\sqrt2$ 计算调节子 $R$（保留三位小数），并用 $x_1=(\varepsilon+\varepsilon^{-1})/2$ 恢复 $x_1$。
2. 进阶：解释"多项式时间求紧凑表示"与"多项式时间打印完整整数"为什么不矛盾：用第 3 节的输出长度论证，说明后者存在指数级的输出下界，而前者绕开它的原因是什么。

**练习 3【经典算法的边界】**（→ [第 4 节](#classical-barriers)）

1. 基础：列出经典求解 Pell 方程的两类主要方法，并各用一句话说明它们为什么达不到多项式时间。
2. 进阶：说明"因数分解可以约化到 Pell 型问题"与"Pell/PIP 不比因数分解难"为什么不是一回事：解释约化方向的确切含义，以及反向约化未知时能得出什么结论、不能得出什么结论。

> 提示：$A$ 约化到 $B$ 只说明"若有解 $B$ 的预言机就能解 $A$"，它不保证反方向。

**练习 4【主理想与生成元的非唯一性】**（→ [6.2 节](#principal-ideal-generators)）

1. 基础：写出分式理想与主理想的定义，并从格结构出发说明为什么理想可以用多项式个比特描述。
2. 进阶：假设理想生成元从 $\alpha$ 改为 $\alpha\varepsilon^k$，证明对数位移只改变 $kR$，即 $\log|\alpha\varepsilon^k|=\log|\alpha|+kR$；由此说明 PIP 算法第 3 步为什么只求出 $\log|\alpha|\bmod R$ 也足够。

> 提示：$\varepsilon^{-1}=\bar\varepsilon$ 的系数仍是整数，故 $(\alpha\varepsilon^k)=(\alpha)$；生成元本来只确定到单位倍数。

**练习 5【约化理想与实数周期函数】**（→ [6.3 节](#infrastructure-periodic-function)）

1. 基础：复述约化理想的三条关键性质（唯一的约化代表、只有有限多个、沿环移动的距离运算多项式时间可算），并写出周期关系 $f(t+R)=f(t)$。
2. 进阶：与 Shor 算法的 $a^j\bmod N$ 对比，解释 $f$ 的多对一性与边界跳变为什么会使"周期内一一对应"式的谱峰论证失效，以及正文的补救思路是什么。

> 提示：回顾第 5 节末尾指出的两处"缺陷"，再对照第 8 节误差源 2 的处理。

**练习 6【量子实数周期查找】**（→ [第 7 节](#quantum-period-finding)）

1. 基础：按顺序写出第 7.1–7.4 节的四个步骤，并写出测量第二寄存器后第一寄存器的"梳子"结构与谱峰条件 $k/q\approx\ell/(NR)$。
2. 进阶：第 7.4 节中，设梳子的齿数为 $M\approx q/T$。用等比数列求和公式证明：在谱峰 $kT/q=\ell$ 处，$|k\rangle$ 的概率约为 $1/T$；并解释这意味着测量结果近似均匀分布在 $T$ 个谱峰上，因此每个非零 $\ell$ 都有机会被采到（这是后处理能工作的前提）。
3. 进阶：若 QFT 样本满足 $|k/q-\ell/(NR)|\le1/(2q)$，说明为什么一个样本通常不足以同时确定未知的 $\ell$ 与 $R$；进一步说明为什么两个独立样本通常也不够、需要连分数与格规约做联合处理。

> 提示（第 3 题）：把 $k/q\approx\ell/(NR)$ 看成关于两个未知量 $\ell,R$ 的一条约束。

**练习 7【正确性的三个误差源】**（→ [第 8 节](#error-sources)）

1. 基础：列出真实状态偏离理想梳子的三个误差源，并各用一句话说明其成因。
2. 进阶：解释"谱峰保留逆多项式概率"为什么足以保证整体多项式时间：从单次成功概率 $1/\operatorname{poly}(n)$ 出发估计期望重复次数，并说明寄存器为何从不需要存储大小为 $e^R$ 的整数。

> 提示：期望重复次数是成功概率的倒数；算法自始至终只保存 $R$ 的比特。

**练习 8【隐藏平移求解主理想问题】**（→ [第 9 节](#hidden-shift-pip)）

1. 基础：写出关系式 $f_I(t)=f_{\mathcal O_K}(t+\log|\alpha|)$，并解释求生成元为什么等价于求这个平移量。
2. 进阶：推导 $I$ 侧梳子在谱峰 $k/q\approx\ell/(NR)$ 处多出的相位因子 $e^{2\pi i\ell\log|\alpha|/R}$，并解释为什么由它只能把 $\log|\alpha|$ 确定到模 $R$、而这并非算法缺陷。

> 提示：把第 7.4 节等比求和中的梳齿位置整体平移 $\delta=N\log|\alpha|$（网格单位）；相位以 $2\pi$ 为周期。

## 参考文献

- Quantum Algorithm Zoo 编号 49：Sean Hallgren, [Polynomial-Time Quantum Algorithms for Pell's Equation and the Principal Ideal Problem](https://www.cse.psu.edu/~sjh26/pell.pdf).
- Quantum Algorithm Zoo 编号 131：Arthur Schmidt, [Quantum Algorithms for many-to-one Functions to Solve the Regulator and the Principal Ideal Problem](https://arxiv.org/abs/0912.4807).
- Quantum Algorithm 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).