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

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

1. 问题与输出为何必须重新定义¶

给定正的非平方整数 \(d\)，Pell 方程是

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

若 \((x_1,y_1)\) 是最小正解，令

\[ \varepsilon=x_1+y_1\sqrt d>1. \]

共轭数 \(x_1-y_1\sqrt d=\varepsilon^{-1}\)，所以所有正解满足

\[ x_k+y_k\sqrt d=\varepsilon^k. \]

输入长度是 \(n=\lceil\log_2 d\rceil\)，但 \(x_1,y_1\) 可能需要指数多个比特。任何声称在 \(\operatorname{poly}(n)\) 时间内直接打印完整 \((x_1,y_1)\) 的算法都违反输出长度下界。正确的计算目标是调节子

\[ R=\log\varepsilon, \]

或基础解的紧凑乘积表示。给出足够精度的 \(R\) 就能唯一确定基础单位，并可按需要逐步恢复它。

例：\(d=2\) 时最小解为 \((3,2)\)，

\[ \varepsilon=3+2\sqrt2,\qquad R=\log(3+2\sqrt2)\approx1.76275. \]

考虑实二次域 \(K=\mathbb Q(\sqrt d)\) 及其整数环 \(\mathcal O_K\)。非零分式理想 \(I\) 是 \(K\) 中在加法和 \(\mathcal O_K\) 乘法下封闭的格。若存在 \(\alpha\in K^\times\) 使

\[ I=(\alpha)=\alpha\mathcal O_K, \]

则 \(I\) 是主理想。

二次域中的约化理想可以按“距离”排列成一个环状的 infrastructure。沿实数轴移动距离 \(t\)，约化过程给出一个规范理想 \(f(t)\)。乘上基础单位不改变主理想：

\[ (\alpha\varepsilon)=(\alpha). \]

在对数坐标中这恰好意味着

\[ f(t+R)=f(t). \]

于是 \(R\) 是隐藏在约化理想序列中的实数周期。与 Shor 的 \(a^j\bmod N\) 不同，\(f\) 在边界处不连续，并且一段小区间可能映到同一个理想；算法的核心难点正是证明这些缺陷不会抹掉傅里叶谱峰。

量子计算机仍是离散设备，因此先选择网格精度 \(N\) 和长度 \(q\)，在寄存器中制备

\[ \frac1{\sqrt q}\sum_{j=0}^{q-1}|j\rangle|0\rangle, \]

再可逆计算约化理想及其局部距离标签：

\[ |j\rangle|0\rangle\longmapsto |j\rangle|\widetilde f(j/N)\rangle. \]

测量第二寄存器后，第一寄存器集中在若干近似等间隔的位置；间距约为 \(NR\)。对第一寄存器做 \(q\) 点 QFT，振幅在满足

\[ \frac{k}{q}\approx\frac{\ell}{NR},\qquad \ell\in\mathbb Z \]

的位置相长干涉。重复采样得到若干近似的对偶周期，再用连分数与格规约恢复 \(R\)。

这里不能只引用“周期查找”四个字。正确性需要同时控制三种误差：

Hallgren 的分析表明，可以用输入长度的多项式位精度把坏网格点比例压低，并让谱峰保留逆多项式概率。因此重复多项式次即可得到足够样本；寄存器保存的是 \(R\) 的比特而不是大小为 \(e^R\) 的整数，空间仍为多项式。

主理想问题（PIP）的输入是理想 \(I\)，任务是判断是否存在 \(\alpha\) 使 \(I=(\alpha)\)，并在存在时给出 \(\alpha\) 的紧凑描述。若 \(I=(\alpha)\)，那么 \(I\) 的约化序列与 \(\mathcal O_K\) 的序列相差一个对数位移：

\[ f_I(t)=f_{\mathcal O_K}(t+\log|\alpha|). \]

因此 PIP 变成同一周期 \(R\) 下的隐藏平移问题：

若不存在一致位移，理想不是主理想。单位 \(\varepsilon^k\) 会把生成元改为 \(\alpha\varepsilon^k\)，所以“模 \(R\)”的歧义不是算法错误，而是主理想生成元本来就不唯一。

量子运行时间关于 \(\log d\) 和要求的精度位数是多项式；已知经典算法对调节子与 PIP 一般为次指数而非多项式。因数分解可约化到 Pell 型问题，但反方向没有已知约化，所以不能简单称二者等价。

还要区分三个结论：Pell 调节子与实二次域 PIP 不需要直接输出指数长整数；用它们进一步生成类群时，某些“小素理想生成类群”的步骤通常要假设广义黎曼猜想；推广到任意次数数域还需要更高维的单位格技术，见下一课。

验证 \((3+2\sqrt2)^2=17+12\sqrt2\)，并检查两组系数都满足 Pell 方程。
假设理想生成元从 \(\alpha\) 改为 \(\alpha\varepsilon^k\)，证明对数位移只改变 \(kR\)。
若 QFT 样本满足 \(|k/q-\ell/(NR)|\le 1/(2q)\)，说明为什么一个样本通常不足以同时确定未知的 \(\ell\) 与 \(R\)。
解释“多项式时间求紧凑表示”与“多项式时间打印完整整数”为什么不矛盾。