# 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.
$$

## 2. 为什么理想会形成一把“周期尺”

考虑实二次域 $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$ 在边界处不连续，并且一段小区间可能映到同一个理想；算法的核心难点正是证明这些缺陷不会抹掉傅里叶谱峰。

## 3. 连续周期查找的量子步骤

量子计算机仍是离散设备，因此先选择网格精度 $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$。

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

1. 网格化使 $j/N$ 代替连续变量；
2. 约化理想函数在边界跳变；
3. 有限窗口截断了无限周期列。

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

## 4. 从周期恢复主理想生成元

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

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

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

1. 先用周期采样求 $R$；
2. 对两条 infrastructure 序列做带偏移的傅里叶采样；
3. 由样本解出 $\log|\alpha|\pmod R$；
4. 经典验证候选生成元是否确实生成 $I$。

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

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

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

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

## 6. 小结与习题

- 基础解的自然压缩量是 $R=\log\varepsilon$。
- 约化理想把 $R$ 编码为实数周期；量子 QFT 采样其对偶频率。
- 多对一、近似和边界跳变必须进入正确性证明。
- PIP 是同一周期结构上的隐藏平移问题，生成元只确定到单位倍数。

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

## 参考文献

- 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).