Pell 方程与主理想问题

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

预备知识：量子傅里叶变换、相位估计和 Shor 因数分解。我们不会再推导 QFT 本身，但会反复用到 Shor 算法的整体框架：“制备叠加—可逆计算函数值—测量—QFT—经典后处理恢复周期”。本词条的核心是看清：当周期变成实数、函数变成多对一且带跳变时，这个框架的哪几步会出问题，以及如何补救。

1. Pell 方程：问题从哪里来

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

$$x^2-d{y}^2=1,x,y\in \mathbb{Z}.$$

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

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

• 代数原因：$x^2-d{y}^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) 存在多项式时间的量子算法；而已知的经典算法一般都是次指数的。因此它是”量子计算在整数分解之外真正扩大优势版图”的标志性问题之一，也是通往类群计算、进而通往更多数论问题的入口（见单位群与类群）。

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

2.1 范数与共轭

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

$$\bar{\alpha }=x-y\sqrt{d},N(\alpha )=\alpha \bar{\alpha }=x^2-d{y}^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)

$$\epsilon =x_1+y_1\sqrt{d}>1.$$

注意 $\epsilon$ 的共轭满足

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

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

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

$$x_k+y_k\sqrt{d}={\epsilon }^k.$$

证明。分两步。

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

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

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

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

$$1\le \beta <\epsilon .$$

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

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

2.3 小例子：$d=2$

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

• $y=1$：$x^2=1+2\cdot 1=3$，不是平方数；
• $y=2$：$x^2=1+2\cdot 4=9$，$x=3$。

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

$$\epsilon =3+2\sqrt{2}\approx 5.82842712,{\epsilon }^{-1}=\bar{\epsilon }=3-2\sqrt{2}\approx \mathrm{0.17157288.}$$

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

$$R=\log (3+2\sqrt{2})\approx \mathrm{1.76275.}$$

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

$${\epsilon }^2=(3+2\sqrt{2}{)}^2=9+12\sqrt{2}+8=17+12\sqrt{2},$$

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

$${\epsilon }^3=\epsilon \cdot {\epsilon }^2=(3+2\sqrt{2})(17+12\sqrt{2})=51+36\sqrt{2}+34\sqrt{2}+48=99+70\sqrt{2},$$

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

3. 为什么输出必须重新定义：调节子

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

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

$$n=\lceil {\log }_{2}d\rceil .$$

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

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

$$R=\log \epsilon ,$$

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

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

4. 经典算法能走多远

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

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

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

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

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

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

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

直觉是这样的。把 $\mathbb{Q}(\sqrt{d})$ 中所有主理想 $(\alpha )$ 想成平面上的点。乘上基础单位不改变理想：$(\alpha \epsilon )=(\alpha )$（理想只关心生成元相差一个可逆元）。在对数坐标里，“乘 $\epsilon$“就是”平移 $R=\log \epsilon$“。于是所有主理想在一条长度为 $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\equiv 2,3(\mathrm{mod}4)$ 就是 $\mathbb{Z}[\sqrt{d}]$；$d\equiv 1(\mathrm{mod}4)$ 时还包含 $\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$ 的紧凑描述。

6.2 单位与”乘 $\epsilon$ 不改变理想”

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

$$(\alpha {\epsilon }^k)=(\alpha ).$$

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

对数坐标把乘法变加法：

$$\log |\alpha {\epsilon }^k|=\log |\alpha |+kR.$$

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

6.3 约化理想与 infrastructure

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

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

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

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

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

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

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⟩$）：

$$\frac{1}{\sqrt{q}}\sum _{j=0}^{q-1}|j⟩|0⟩.$$

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

$$|j⟩|0⟩⟼|j⟩|\tilde{f}(j/N)⟩,$$

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

整个状态是

$$\frac{1}{\sqrt{q}}\sum _{j=0}^{q-1}|j⟩|\tilde{f}(j/N)⟩.$$

7.3 测量得到”梳子”

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

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

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

7.4 QFT 与谱峰

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

$$|\psi ⟩=\frac{1}{\sqrt{M}}\sum _{m=0}^{M-1}|j_0+mT⟩,T=NR,M\approx \frac{q}{T},$$

则 QFT 后 $|k⟩$ 的振幅为

$$\frac{1}{\sqrt{qM}}\sum _{m=0}^{M-1}{e}^{2\pi ik(j_0+mT)/q}=\frac{e^{2\pi ik{j}_0/q}}{\sqrt{qM}}\sum _{m=0}^{M-1}{\left(e^{2\pi ikT/q}\right)}^m.$$

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

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

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

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

每个样本给出

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

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

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

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

$$T=NR\approx 16\times 1.76275=\mathrm{28.204.}$$

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

$$k\approx 9,18,27,36,\dots$$

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

$$\frac{2\pi kT}{q}=\frac{2\pi \times 9\times 28.204}{256}\approx 2\pi \times 0.9916,$$

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

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

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

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

8. 正确性的三个误差源

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

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

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

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

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

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

9. 从周期到主理想生成元

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

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

即 $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 |(\mathrm{mod}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⟩$ 处的振幅多出一个因子

$$e^{2\pi ik\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 步的"$\mathrm{mod}R$"：单位 ${\epsilon }^k$ 会把生成元改为 $\alpha {\epsilon }^k$，在对数轴上平移 $kR$。所以算法只能把 $\log |\alpha |$ 确定到模 $R$——这不是算法缺陷，而是主理想生成元本来就不唯一（第 6.2 节）。模 $R$ 的任一代表都同样合法。

10. 复杂度、优势与边界

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

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

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

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

11. 小结与习题

• Pell 方程的解是二次域的单位；由 Lemma 1，所有正解是基础单位的幂，问题归结为求 $\epsilon$。
• 基础解可能占指数多比特，自然的压缩量是调节子 $R=\log \epsilon$；多项式时间算法以 $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$）。
• 量子时间为 $\mathrm{poly}(\log d)$；已知经典算法次指数；因数分解可约化到 Pell 型问题但反向约化未知，二者不能称等价。

习题

1. 验证 $(3+2\sqrt{2}{)}^2=17+12\sqrt{2}$，并检查两组系数都满足 Pell 方程；再用范数乘性（不展开乘法）解释为什么 ${\epsilon }^k$ 自动是解。
2. 仿照第 2.3 节，对 $d=3$ 找出最小正解（逐个试 $y=1,2,\dots$），写出基础单位 $\epsilon$、共轭 ${\epsilon }^{-1}$ 与调节子 $R$ 的近似值，并用 ${\epsilon }^2$ 验证 Lemma 1。
3. 假设理想生成元从 $\alpha$ 改为 $\alpha {\epsilon }^k$，证明对数位移只改变 $kR$，即 $\log |\alpha {\epsilon }^k|=\log |\alpha |+kR$；由此说明 PIP 算法第 3 步为什么只求出 $\log |\alpha |\mathrm{mod}R$ 也足够。
4. 若 QFT 样本满足 $|k/q-\ell /(NR)|\le 1/(2q)$，说明为什么一个样本通常不足以同时确定未知的 $\ell$ 与 $R$（提示：把等式看成关于两个未知量 $\ell ,R$ 的一条约束）；进一步说明为什么两个独立样本通常也不够、需要连分数与格规约做联合处理。
5. 解释”多项式时间求紧凑表示”与”多项式时间打印完整整数”为什么不矛盾：用第 3 节的输出长度论证，说明后者存在指数级的输出下界，而前者绕开它的原因是什么。
6. 第 7.4 节中，设梳子的齿数为 $M\approx q/T$。用等比数列求和公式证明：在谱峰 $kT/q=\ell$ 处，$|k⟩$ 的概率约为 $1/T$；并解释这意味着测量结果近似均匀分布在 $T$ 个谱峰上，因此每个非零 $\ell$ 都有机会被采到（这是后处理能工作的前提）。

参考文献

• Quantum Algorithm Zoo 编号 49：Sean Hallgren, Polynomial-Time Quantum Algorithms for Pell’s Equation and the Principal Ideal Problem.
• Quantum Algorithm Zoo 编号 131：Arthur Schmidt, Quantum Algorithms for many-to-one Functions to Solve the Regulator and the Principal Ideal Problem.
• 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.

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch09-algebra-number-theory/pell-principal-ideal
• 内容遵循 CC BY-NC-SA 4.0 许可协议