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

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

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

本课知识点

  1. Pell 方程与基础单位——能写出 Pell 方程并说明它的解就是二次域中范数为 \(1\) 的单位，进而证明所有正解恰为基础单位 \(\varepsilon\) 的幂并完成 \(d=2\) 的演算。

  2. 调节子与输出长度——能论证直接输出最小解 \((x_1,y_1)\) 受指数级输出长度下界的限制，并解释为什么 \(R=\log\varepsilon\) 的高精度值是多项式长度的无损压缩。

  3. 经典算法的边界——能比较连分数法与次指数算法的耗时来源，并说明因数分解到 Pell 型问题的约化方向及反向约化未知意味着什么。

  4. 主理想与生成元的非唯一性——能写出分式理想与主理想的定义，证明 \((\alpha)=(\beta)\) 当且仅当 \(\beta=\alpha\varepsilon^k\)，并解释生成元在对数轴上构成间隔为 \(R\) 的等差点列。

  5. 约化理想与实数周期函数——能说明约化理想与 infrastructure 如何把 \(R\) 编码为可计算的周期函数 \(f\)，验证 \(f(t+R)=f(t)\)，并指出多对一与边界跳变两处缺陷。

  6. 量子实数周期查找——能按网格化、制备叠加、测量、QFT 四步写出各阶段寄存器状态，推导谱峰条件 \(k/q\approx\ell/(NR)\)，并复算 \(d=2\) 的玩具数值示例。

  7. 正确性的三个误差源——能列出网格化、函数缺陷、窗口截断三个误差源，并说明为什么三者可控时谱峰保留逆多项式概率、重复多项式次采样即可恢复 \(R\)。

  8. 隐藏平移求解主理想问题——能推导谱峰相位因子 \(e^{2\pi i\ell\log|\alpha|/R}\) 的来源，并解释为什么生成元只能恢复到模 \(R\)、而这源于问题本身的非唯一性。

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

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\) 倍——这就是"幂次增长"的直观含义。

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\) 到多项式位精度"。

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\) 的紧凑描述。

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\) 就是这个点列的周期。

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\) 在约化边界处不连续，并且一段小区间可能映到同一个理想（多对一）。算法的核心难点正是证明这些缺陷不会抹掉傅里叶谱峰。

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 节连分数与格规约所做的事的雏形。

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\) 的多项式规模压住三项误差，再用有限几何级数估计谱峰处的相长干涉。所有"显然可以忽略"的地方，正是证明的技术含量所在。

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 的高效量子算法，需要更高维的单位格技术，见下一课。

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

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

  1. 基础：对 \(d=2\)，由 \(\varepsilon=3+2\sqrt2\) 计算调节子 \(R\)（保留三位小数），并用 \(x_1=(\varepsilon+\varepsilon^{-1})/2\) 恢复 \(x_1\)。

  2. 进阶：解释"多项式时间求紧凑表示"与"多项式时间打印完整整数"为什么不矛盾：用第 3 节的输出长度论证，说明后者存在指数级的输出下界，而前者绕开它的原因是什么。

练习 3【经典算法的边界】（→ 第 4 节）

  1. 基础：列出经典求解 Pell 方程的两类主要方法，并各用一句话说明它们为什么达不到多项式时间。

  2. 进阶：说明"因数分解可以约化到 Pell 型问题"与"Pell/PIP 不比因数分解难"为什么不是一回事：解释约化方向的确切含义，以及反向约化未知时能得出什么结论、不能得出什么结论。

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

练习 4【主理想与生成元的非唯一性】（→ 6.2 节）

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

  1. 基础：复述约化理想的三条关键性质（唯一的约化代表、只有有限多个、沿环移动的距离运算多项式时间可算），并写出周期关系 \(f(t+R)=f(t)\)。

  2. 进阶：与 Shor 算法的 \(a^j\bmod N\) 对比，解释 \(f\) 的多对一性与边界跳变为什么会使"周期内一一对应"式的谱峰论证失效，以及正文的补救思路是什么。

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

练习 6【量子实数周期查找】（→ 第 7 节）

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

  1. 基础：列出真实状态偏离理想梳子的三个误差源，并各用一句话说明其成因。

  2. 进阶：解释"谱峰保留逆多项式概率"为什么足以保证整体多项式时间：从单次成功概率 \(1/\operatorname{poly}(n)\) 出发估计期望重复次数，并说明寄存器为何从不需要存储大小为 \(e^R\) 的整数。

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

练习 8【隐藏平移求解主理想问题】（→ 第 9 节）

  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\) 为周期。

参考文献