有限域曲线的 Zeta 函数

本词条的主题是有限域上代数曲线的 zeta function。先澄清一个几乎必然的误会：这里的 zeta function 不是 Riemann zeta 函数 $\zeta (s)={\sum }_{n\ge 1}{n}^{-s}$，而是记录一条代数曲线在所有有限扩域上点数的一个生成函数。它为什么会出现在量子算法教程里？原因在于下面这个对比：

• 经典一侧：逐个数出曲线在 ${\mathbb{F}}_{q^n}$ 上的点数，朴素做法是枚举所有可能的坐标对并代入曲线方程检验，代价随 $q^n$ 指数增长。对椭圆曲线（genus $1$），Schoof 等人的 $\ell$-进方法给出了关于 $\log q$ 多项式的算法；对一般 genus，也有若干 $p$-进方法，但其复杂度对域特征、genus 的依赖各不相同。
• 量子一侧：Kedlaya（Zoo 编号 64）观察到，点数的全部信息被压缩在一个 $2g$ 次多项式（Weil 多项式）里，而这个多项式的”指纹”恰好是曲线 Jacobian 群在若干扩域上的群阶——而求 Abel 群的阶，正是 Shor 型黑盒群算法（）的拿手好戏。整条流水线关于 genus $g$ 与 $\log q$ 都是多项式的。

这个问题的意义不止于”又一个大数难算问题被量子拿下”。有限域曲线的点数直接等于椭圆曲线密码中群的阶（选曲线、验参数都要数点），也决定代数几何码的参数；而 zeta function 的有理性、函数方程与”曲线的 Riemann 假设”正是 20 世纪代数几何的核心成就（Weil 猜想的曲线情形由 Weil 本人证明，一般情形的有理性由 Dwork 证明，Riemann 假设部分由 Deligne 证明）。Kedlaya 的量子算法展示了一条颇具代数数论风味的路线：不逐个数点，而是把数点问题翻译成 Abel 群阶问题，量子求解后再经典地把答案拼回去。文末 van Dam 的工作（Zoo 编号 87）则从另一角度研究用量子过程获取 zeta zeros 的谱信息，两者不能混为一谈（见第 6 节）。

预备知识。本词条默认读者熟悉前面的词条：量子态与测量（）、相位估计与 Shor 型阶求算法（）、有限域的基本概念。涉及的代数几何对象（曲线、divisor、Jacobian、Riemann–Roch 定理）我们会在用到的层面给出定义与直觉，引用其标准结论但不重新证明。

路线图。第 1 节定义局部 zeta function 并用 Weil 猜想推出点数公式；第 2 节证明 Jacobian 扩域群阶就是 Weil 多项式与 $T^n-1$ 的 resultant；第 3 节把 Jacobian 包装成 Abel 黑盒群并给出量子求阶；第 4 节讲如何从有限个”指纹”经典重建 Weil 多项式；第 5 节是两个可以完整手算的例子；第 6 节讨论复杂度、与经典算法的比较以及结论的边界。

1. 定义与有理性

1.1 曲线与点数

固定一个有限域 ${\mathbb{F}}_q$（$q$ 是素数幂），记 ${\mathbb{F}}_{q^n}$ 为它的 $n$ 次扩域。设 $C$ 是定义在 ${\mathbb{F}}_q$ 上的一条光滑、射影、几何连通曲线。三个修饰词各自的直觉是：

• 射影 (projective)：曲线包含”无穷远点”，就像把仿射平面直线 ${\mathbb{A}}^1$ 补全成射影直线 ${\mathbb{P}}^1$；这保证点数是干净的有限数，也使下面的理论形式整齐；
• 光滑 (smooth)：曲线没有尖点、自交等奇点，每一点都有良好定义的切线；
• 几何连通 (geometrically connected)：在代数闭包上看仍是一整块，不会分裂成几条互不相干的曲线。

对每条这样的曲线有一个数值不变量——亏格 (genus) $g$，可直观理解为”洞的数量”：射影直线 $g=0$，椭圆曲线 $g=1$，一般的光滑平面 $d$ 次曲线 $g=\frac{(d-1)(d-2)}{2}$。

我们关心的基本量是曲线在各扩域上的有理点数

$$N_n=|C({\mathbb{F}}_{q^n})|,$$

即坐标取自 ${\mathbb{F}}_{q^n}$、满足曲线方程的（射影）点的个数。因为 ${\mathbb{F}}_{q^n}$ 只有 $q^n$ 个元素，逐一枚举坐标对总能算出 $N_n$，但代价是 $q^{O(n)}$ 量级的——这正是要被避免的”逐个数点”。

1.2 局部 zeta function 的定义

把无穷序列 $\{N_n{\}}_{n\ge 1}$ 打包成一个形式幂级数：

$$Z_C(T)=\exp \left(\sum _{n=1}^{\infty }{N}_n\frac{T^n}{n}.\right)$$

为什么取这种”指数套对数”的形状，而不是普通的生成函数 $\sum N_n{T}^n$？深层原因是点数本身具有Euler 乘积结构：每个 ${\mathbb{F}}_{q^n}$-点都由某个”闭点”（Frobenius 轨道）生成，把指数展开后会得到

$$Z_C(T)=\prod _{P\text{闭点}}\frac{1}{1-T^{\mathrm{deg}P}},$$

即 $Z_C$ 是所有闭点贡献的乘积——这与 Riemann zeta 写成素数乘积 ${\prod }_p(1-p^{-s}{)}^{-1}$ 完全平行，“zeta”之名由此而来。$\exp (\sum N_n{T}^n/n)$ 正是让这个乘积结构成立的正确打包方式；本词条不需要 Euler 乘积的推导，把它当作动机即可。

1.3 Weil 猜想（曲线情形）

下面的定理是本词条的基石（曲线情形由 Weil 证明）：

定理 1（Weil 猜想，曲线情形）。设 $C$ 如上，genus 为 $g$。则：

1. 有理性：$Z_C(T)$ 是有理函数，且精确形式为

$$Z_C(T)=\frac{P_C(T)}{(1-T)(1-qT)};$$

2. 分子次数与整性：$P_C(T)$ 是整系数多项式，次数恰为 $2g$，常数项为 $1$；
3. Riemann 假设：把 $P_C$ 在 $\mathbb{C}$ 上分解为

$$P_C(T)=\prod _{j=1}^{2g}(1-{\alpha }_{j}T),$$

则所有根（在任意复嵌入下）满足 $|{\alpha }_j|=\sqrt{q}$； 4. 函数方程：根集在 $\alpha \mapsto q/\alpha$ 下封闭，等价地 ${\prod }_{j=1}^{2g}{\alpha }_j=q^g$，即 $P_C$ 的 $T^{2g}$ 项系数固定为 $q^g$。

多项式 $P_C$ 称为曲线 $C$ 的 Weil 多项式；诸 ${\alpha }_j$ 称为它的 Weil 根（它们正是 Frobenius 在 $\ell$-进上同调上的本征值，本词条只需要把它们当作满足定理 1 的 $2g$ 个复数）。

这个定理直接改变了问题的性质。原本”计算 zeta function”意味着确定无穷序列 $\{N_n\}$；定理 1 说明全部信息都装在 $P_C$ 的 $2g$ 个整系数里。输出规模因此是有限的：由第 3 条，$P_C(T)={\sum }_k{a}_k{T}^k$ 的系数是 ${\alpha }_j$ 的初等对称函数，满足 Weil 界

$$|a_k|\le \left(\genfrac{}{}{0ex}{}{2g}{k}\right)q^{k/2},$$

故每个系数只需 $O(g\log q)$ 量级的比特来表示——输出只需 $O(g\log q)$ 量级系数位（对每个系数而言），而不是一个无限点数序列。一个良定义的”计算 zeta function”算法，其目标就是精确输出 $P_C$ 的全部系数。

1.4 从有理性推出点数公式

定理 1 的有理性与定义式放在一起，立刻给出 $N_n$ 的封闭表达式。推导的核心工具是形式对数展开

$$\log (1-x)=-\sum _{n=1}^{\infty }\frac{x^n}{n}(\text{形式幂级数恒等式}).$$

对定义式取对数：

$$\log Z_C(T)=\sum _{n=1}^{\infty }{N}_n\frac{T^n}{n}.$$

另一方面，对有理性表达式取对数（对数和差变乘积商的对数）：

$$\log Z_C(T)=\sum _{j=1}^{2g}\log (1-{\alpha }_{j}T)-\log (1-T)-\log (1-qT).$$

把上面三条 $\log (1-x)$ 分别展开，合并 $T^n$ 的系数：

$$\log Z_C(T)=\sum _{n=1}^{\infty }\left(-\sum _{j=1}^{2g}{\alpha }_j^n+1+q^n\right)\frac{T^n}{n}.$$

两个展开式逐项相等（形式幂级数系数唯一），于是由对数导数比较得到：

$$\boxed{N_n=q^n+1-\sum _{j=1}^{2g}{\alpha }_j^n}$$

这个公式值得逐端详读：

• $q^n+1$ 是射影直线 ${\mathbb{P}}^1$ 的点数（见第 5 节的例子），可看作”背景项”；
• $-{\sum }_j{\alpha }_j^n$ 是曲线相对背景的修正项。由 $|{\alpha }_j|=\sqrt{q}$，修正项的绝对值至多是 $2g{q}^{n/2}$——这正是 Hasse–Weil 界

$$|N_n-(q^n+1)|\le 2g{q}^{n/2}.$$

换句话说，一条曲线的点数永远不会偏离”射影直线的点数”超过 $2g\sqrt{q^n}$。修正项编码了曲线全部有趣的算术信息，而它又由 $2g$ 个 Weil 根的幂和完全决定。已知 $P_C$ 就能算出一切 $N_n$；反过来，Kedlaya 算法的任务就是在不逐个数任何 $N_n$ 的前提下求出 $P_C$。

2. Jacobian 群阶编码同一根

2.1 Jacobian：曲线自带的 Abel 群

每条（光滑射影几何连通）曲线 $C$ 都伴随一个 $g$ 维 Abel 簇——它的 Jacobian $J_C$。对不熟悉的读者，可以暂时只接受以下三条事实，它们足以支撑全课：

• $J_C$ 的 ${\mathbb{F}}_{q^n}$-有理点 $J_C({\mathbb{F}}_{q^n})$ 构成一个有限 Abel 群；
• 群元素可以具体地实现为曲线上的 degree-zero divisor class（下一节详述），因此是可以用有限域元素编码、可以实际做群运算的对象；
• 定义 $Z_C$ 时出现的 Weil 根 ${\alpha }_1,\dots ,{\alpha }_{2g}$，同时是 Frobenius 自同态作用在 $J_C$ 上的本征值——曲线与它的 Jacobian 共享同一组 ${\alpha }_j$。

椭圆曲线是最好的直觉来源：$g=1$ 时 $J_C$ 就是 $C$ 自己（椭圆曲线上的点本身在弦切法下成群），Weil 根就是 Frobenius 的两个本征值。高 genus 时 $J_C$ 不再是曲线本身，但”Frobenius 本征值同为 ${\alpha }_j$“这一条完全保留。

2.2 群阶公式

${\mathbb{F}}_{q^n}$-有理点恰好是 Frobenius 第 $n$ 次幂的不动点。用代数几何中”不动点数 = $\det (1-\text{Frobenius})$“的标准结论（对 Jacobian 的 Tate 模计数），Frobenius 本征值同为 ${\alpha }_j$，于是其阶满足

$$\boxed{|J_C({\mathbb{F}}_{q^n})|=\prod _{j=1}^{2g}(1-{\alpha }_j^n)}$$

先检验两个特例，建立手感。取 $n=1$：

$$|J_C({\mathbb{F}}_q)|=\prod _{j=1}^{2g}(1-{\alpha }_j)=P_C(1),$$

即基域上的群阶就是 Weil 多项式在 $T=1$ 处的取值。取 $g=1$（椭圆曲线），$P_E(T)=1-aT+q{T}^2$，则

$$|E({\mathbb{F}}_q)|=P_E(1)=1-a+q=q+1-a,$$

这正是椭圆曲线教科书里的标准公式（第 5 节会展开）。

再估计群阶的比特长度，第 3 节的复杂度分析要用。由 $|{\alpha }_j|=\sqrt{q}$ 与三角不等式，每个因子满足

$$q^{n/2}-1\le |1-{\alpha }_j^n|\le q^{n/2}+1,$$

全部 $2g$ 个因子相乘得

$$(q^{n/2}-1{)}^{2g}\le |J_C({\mathbb{F}}_{q^n})|\le (q^{n/2}+1{)}^{2g}.$$

取对数：$\log |J_C({\mathbb{F}}_{q^n})|=\Theta (gn\log q)$。也就是说，这个群阶是一个大约 $gn\log q$ 比特的整数——对 Shor 型算法而言是多项式规模的输入。

2.3 与 resultant 的精确关系

群阶公式还有另一种代数包装，它把”群阶”和”未知多项式 $P_C$“直接焊在一起。回忆两个多项式的 resultant：设 $f$ 的根为 ${\rho }_1,\dots ,{\rho }_m$、首项系数为 $a_f$，则（一种标准约定下）

$$\mathrm{Res}(f,g)=a_f^{\mathrm{deg}g}\prod _{i=1}^{m}g({\rho }_i).$$

resultant 是两个多项式的系数的整系数多项式，且为 $0$ 当且仅当两多项式有公共根；它可以在不知根的情况下由系数高效算出。

另一方面，若把 reciprocal polynomial 约定处理好（$P_C$ 的根是 $1/{\alpha }_j$，且由定理 1 第 4 条其首项系数为 ${\prod }_j{\alpha }_j=q^g$），对 $f=P_C$、$g(T)=T^n-1$ 套用定义：

$$\mathrm{Res}(P_C,T^n-1)=(q^g{)}^n\prod _{j=1}^{2g}((\frac{1}{{\alpha }_j}{)}^n-1).$$

把每个因子改写：

$$(\frac{1}{{\alpha }_j}{)}^n-1=\frac{1-{\alpha }_j^n}{{\alpha }_j^n},$$

全部乘起来时，分母是 ${\prod }_j{\alpha }_j^n=({\prod }_j{\alpha }_j{)}^n=(q^g{)}^n$（再用一次定理 1 第 4 条），恰好与前面的因子 $(q^g{)}^n$ 抵消：

$$\mathrm{Res}(P_C,T^n-1)=(q^g{)}^n\cdot \frac{{\prod }_{j=1}^{2g}(1-{\alpha }_j^n)}{(q^g{)}^n}=\prod _{j=1}^{2g}(1-{\alpha }_j^n)=|J_C({\mathbb{F}}_{q^n})|.$$

若采用 resultant 的其它符号/幂次约定，上式至多乘上一个可知的符号或 $q$ 的幂因子，不影响下文任何推理。定义

$$R_n=\mathrm{Res}(P_C(T),T^n-1),$$

序列 $\{R_n\}$ 称为 cyclic resultants。我们把上面的恒等式重述成一句话：

$$\text{求出群阶 }|J_C({\mathbb{F}}_{q^n})|⟺\text{求出未知 }{P}_C\text{ 的第 }n\text{ 个 cyclic resultant }{R}_n.$$

注意 $R_n$ 是根 ${\alpha }_j$ 的非线性函数（$2g$ 个因子的乘积），而不是幂和 ${\sum }_j{\alpha }_j^n$ 那样的线性组合。因此每个群阶都是未知 Weil 多项式的一枚非线性指纹：它混入了所有根的信息，不能直接解出单个 ${\alpha }_j$，但多枚指纹合起来可以钉死整个多项式——这正是第 4 节的重建问题。量子算法的分工至此完全清楚：求若干 Jacobian 群阶，就等于获得未知 Weil polynomial 的若干非线性指纹。

3. 如何把 Jacobian 做成黑盒群

Shor 型 Abel 群算法（的阶求与离散对数是它的特例）并不直接吃”几何对象”，它吃的是一个黑盒群：群元素有唯一的比特串编码，群运算与取逆有量子线路实现，并且能生成一组覆盖整个群的元素。本节把 $J_C({\mathbb{F}}_{q^n})$ 逐项装进这个框架。

3.1 元素：divisor class 的规范表示

Divisor 是曲线上点的形式和 $D={\sum }_P{m}_{P}P$（系数 $m_P\in \mathbb{Z}$，只有有限项非零），其次数为 $\mathrm{deg}D={\sum }_P{m}_P$。两个 degree-zero divisor 若相差一个有理函数的零点减极点（称线性等价），则视为同一个群元素；等价类称为 degree-zero divisor class，它们在”形式和相加”下构成群——这正是 $J_C$ 的点的具体化身。直观地说：Jacobian 的元素是”曲线上加减抵消后的点丛”，而 $g$ 控制着每个类需要多少个点来表示。

直接操作等价类不行：同一个类有无穷多个代表元，黑盒群要求每个群元素有唯一的编码，否则连”两个元素是否相等”都无法判定。算法的解决办法是选择可计算规范表示（canonical representation）：每个类里挑出一个唯一确定的代表元。对超椭圆曲线，这就是经典的 Mumford 表示（一对次数受控的多项式）；对一般曲线，可以用 reduced divisor：Riemann–Roch 定理保证每个 degree-zero 类都存在约化代表，且在 genus 固定/输入给定时可以取到唯一规范的版本。无论哪种，每个群元素最终都是 ${\mathbb{F}}_{q^n}$ 上 $O(g)$ 个域元素的比特串。

3.2 群运算：加完再约化

群运算分两步（这正是”后通过 Riemann–Roch/约化回到规范形式”的含义）：

$$[D_1]+[D_2]=[D_1+D_2],-[D]=[-D]$$

先在代表元层面做形式和（取负），得到的类再约化回规范代表元。第一步是平凡的多项式拼接；第二步——divisor reduction——是计算的核心，经典算法（超椭圆情形即 Cantor 算法）在指定曲线模型和固定/输入 genus 条件下用 $\mathrm{poly}(g)$ 次域运算完成。

复杂度逐项盘点：${\mathbb{F}}_{q^n}$ 上的域算术（加、乘、求逆、多项式因式分解）代价为 $\mathrm{poly}(n\log q)$ 比特操作；每次群运算是 $\mathrm{poly}(g)$ 次域运算；全部用量子可逆电路实现只引入常数开销。因此对扩域 ${\mathbb{F}}_{q^n}$，域算术、因式分解与 divisor reduction 在指定曲线模型和固定/输入 genus 条件下为 $\mathrm{poly}(g,n,\log q)$——黑盒群的”单次查询”是多项式代价的。

3.3 量子求阶：分解整个群

Abelian 黑盒群 order algorithm 的标准流程（工具的 Abel 群版本）是：

1. 取群中若干元素 $g_1,\dots ,g_t$；
2. 用量子傅里叶变换/相位估计求各元素的阶及元素间关系，把关系整理成整数格；
3. 对关系格做 Smith 标准形分解，读出群的不变量：

$$J_C({\mathbb{F}}_{q^n})\cong {\mathbb{Z}}_{d_1}\times \cdots \times {\mathbb{Z}}_{d_s},$$

于是

$$R_n=|J_C({\mathbb{F}}_{q^n})|=\prod _{i=1}^s{d}_i.$$

这一步的量子代价关于 $\log |J_C({\mathbb{F}}_{q^n})|=\Theta (gn\log q)$ 为多项式——这正是 Shor 算法相对经典群阶算法的加速点，全部”量子性”都集中在这一格。

但整个流程有一个容易忽略的前提：第 1 步取的元素必须能（高概率）生成整个群。如果随机取来的 $g_i$ 都落在某个真子群里，分解出的就是子群而非 $J_C$ 本身，得到的”群阶”会系统性地偏小。这里不能拍脑袋假设”随便在曲线上选几个点就生成 Jacobian”——Kedlaya 构造的是可证明近均匀的随机 divisor classes：利用约化表示的参数空间做随机取样，并证明其分布与均匀分布的统计距离足够小，从而收集足够元素后高概率生成整个 $J_C({\mathbb{F}}_{q^n})$。这个”可证明”是本算法模型正确性的关键一环，而不是工程细节。

4. 从 cyclic resultants 重建 $P_C$

现在假设量子部分已经交出了 $R_1,R_2,\dots ,R_m$（$m$ 待定）。剩下的是一个纯经典问题：

已知未知根 ${\alpha }_1,\dots ,{\alpha }_{2g}$ 的若干 cyclic resultants $R_n={\prod }_j(1-{\alpha }_j^n)$，恢复初等对称函数，从而恢复 $P_C(T)={\prod }_j(1-{\alpha }_{j}T)$。

4.1 为什么不是直接的反演

$R_n$ 是根的对称函数，但是高度非线性的：展开后是诸 ${\alpha }_j$ 幂的交错乘积和，而不是幂和 $p_n={\sum }_j{\alpha }_j^n$。如果手里是幂和，Newton 恒等式会立刻给出初等对称函数；cyclic resultant 没有这样的直接反演公式。更糟的是，对一般多项式，确实存在不同的根集合产生部分相同 resultants 的现象——有限个 $R_n$ 原则上不足以唯一确定一个任意的 $2g$ 次多项式。

4.2 Weil 多项式的额外约束

出路在于 $P_C$ 不是任意多项式，而是 Weil 多项式，额外满足：

• 整系数与固定的首项系数 $q^g$（原文表述为”固定常数项 $q^g$“，指在 reciprocal/首一化约定下：由定理 1 第 4 条，$P_C$ 的 $T^{2g}$ 项系数为 ${\prod }_j{\alpha }_j=q^g$，等价地其倒互反多项式的常数项为 $q^g$）；
• reciprocal functional equation：根在 $\alpha \mapsto q/\alpha$ 下成对出现，系数因而回文对称（$a_{2g-k}=q^{g-k}{a}_k$），未知系数实际只有约 $g$ 个；
• 所有根绝对值 $\sqrt{q}$（定理 1 第 3 条）；
• 系数有 Weil bounds：$|a_k|\le \left(\genfrac{}{}{0ex}{}{2g}{k}\right)q^{k/2}$（第 1 节）。

每一条都在大幅削减候选。整性 + Weil 界把每个系数限制在一个有限的整数集合里；函数方程把独立未知量减半；根的模长条件是一个强的 Archimedes 约束，与 $R_n$ 的大小信息互相印证。合在一起，这些约束把候选压到有限且可有效区分的集合。

4.3 重建流程

具体重建分三步：

1. 取足够多的指纹：取关于 $g$ 多项式多个 $n$（即 $m=\mathrm{poly}(g)$），对每个 $n$ 用量子算法求 $R_n$。注意 $R_n$ 本身可达 $q^{ng}$ 量级，但它是被精确输出的整数，不是近似值；
2. 逐层恢复对称函数：用整数因子/对数界和 Fried cyclic-resultant reconstruction 的有效版本（effective version，即把存在性结论做成带显式界、可实际执行的算法），从 $\{R_n\}$ 逐步恢复 elementary symmetric polynomials $e_1,\dots ,e_{2g}$，从而得到 $P_C(T)$ 的全部系数。直觉是：$R_n$ 对不同的 $n$ 以不同的非线性方式混合诸根，足够多的混合方程加上 4.2 的离散约束，解集合就坍缩到唯一（或一个可有效枚举的小集合）；
3. 经典验证：把候选 $P_C$ 对所有已求出的 $R_n$ 逐一验证 $\mathrm{Res}(P_C,T^n-1)=R_n$。resultant 可以只从系数多项式时间算出，因此验证是廉价且严格的——即使第 2 步输出的是一个小候选集，也能确定性地筛出正确答案。

这一步没有任何量子成分，但它是整条流水线里最”代数数论”的部分；值得强调的是，它之所以可行，恰恰是因为目标是精确恢复一个整系数多项式，而不是数值逼近某些根。

5. 例子：射影直线与椭圆曲线

5.1 射影直线：$g=0$ 的完整手算

$C={\mathbb{P}}^1$ 的 genus 为 0。它的 ${\mathbb{F}}_{q^n}$-点由 $q^n$ 个仿射点加一个无穷远点组成，故

$$N_n=q^n+1.$$

把这个代入 zeta 定义，可以从头算出整个 $Z_C$，并与定理 1 对照。先用对数展开（第 1 节用过的恒等式，用两次）：

$$\sum _{n=1}^{\infty }{N}_n\frac{T^n}{n}=\sum _{n=1}^{\infty }\frac{(qT{)}^n}{n}+\sum _{n=1}^{\infty }\frac{T^n}{n}=-\log (1-qT)-\log (1-T).$$

两边取 $\exp$（$\exp$ 与 $\log$ 互为逆，$\exp (a+b)=e^a{e}^b$）：

$$Z_C(T)=\exp (-\log (1-qT))\cdot \exp (-\log (1-T))=\frac{1}{(1-T)(1-qT)}.$$

与定理 1 的有理性形式对比：分子 $P_C(T)=1$，次数 $0=2g$，与 $g=0$ 一致；没有 Weil 根，Hasse–Weil 界的修正项恒为 $0$，$N_n=q^n+1$ 精确成立——一切都自洽。Jacobian 是平凡的（$g=0$ 时 $J_C$ 是一个点），群阶公式给出空乘积 $|J_C({\mathbb{F}}_{q^n})|=1$，也与 $R_n=\mathrm{Res}(1,T^n-1)=1$ 吻合。

5.2 椭圆曲线：一般公式

椭圆曲线 $E$ 的 genus 为 1，Weil 多项式是二次的：

$$P_E(T)=1-aT+q{T}^2,$$

其中整数 $a$ 称为 Frobenius 迹。由第 2 节，基域点数为

$$|E({\mathbb{F}}_q)|=P_E(1)=q+1-a,$$

而定理 1 第 3 条给出 Hasse 界

$$|a|=|{\alpha }_1+{\alpha }_2|\le |{\alpha }_1|+|{\alpha }_2|=2\sqrt{q}.$$

把 $P_E$ 分解为 $(1-\alpha T)(1-\bar{\alpha }T)$，比较系数得 $\alpha +\bar{\alpha }=a$、$\alpha \bar{\alpha }=q$。扩域点数由第 1 节的公式给出：记幂和 $s_n={\alpha }^n+{\bar{\alpha }}^n$，则

$$|E({\mathbb{F}}_{q^n})|=q^n+1-s_n.$$

幂和满足线性递推（因为 $\alpha ,\bar{\alpha }$ 都是 $x^2-ax+q=0$ 的根，两边乘 $x^{n-2}$ 后相加）：$s_0=2$，$s_1=a$，

$$s_n=a{s}_{n-1}-q{s}_{n-2}(n\ge 2).$$

所以只要知道 $a$，所有扩域点数都由递推唯一确定。而求 $E({\mathbb{F}}_q)$ 的群阶就得到 $a$（单个扩域已足以确定二次 Weil polynomial）；高 genus 时单个 $R_1$ 不足以钉死 $2g$ 个根，需要更多 cyclic resultants。

5.3 一个可以完整手算的数值例子

取 $q=5$ 上的椭圆曲线

$$E:y^2=x^3+1.$$

第一步：逐个数 $E({\mathbb{F}}_5)$ 的点。 ${\mathbb{F}}_5$ 中的平方只有 $0,1,4$。对每个 $x$ 计算 $x^3+1\mathrm{mod}5$ 并数平方根：

$x$	$x^3+1\mathrm{mod}5$	是否为平方	$y$ 的个数
0	1	是	2（$y=1,4$）
1	2	否	0
2	4	是	2（$y=2,3$）
3	3	否	0
4	0	是	1（$y=0$）

加上唯一一个无穷远点，共 $|E({\mathbb{F}}_5)|=2+0+2+0+1+1=6$。

第二步：读出 Weil 多项式。 由 $|E({\mathbb{F}}_q)|=q+1-a$：

$$a=q+1-|E({\mathbb{F}}_q)|=5+1-6=0,$$

Hasse 界检验：$|a|=0\le 2\sqrt{5}\approx 4.47$，通过。于是

$$P_E(T)=1+5T^2.$$

由 $\alpha +\bar{\alpha }=0$、$\alpha \bar{\alpha }=5$ 解出 $\alpha =\pm i\sqrt{5}$；模长检验 $|\alpha |=\sqrt{5}$，与定理 1 第 3 条一致。

第三步：预测并验证扩域点数。 用递推：$s_0=2$，$s_1=a=0$，

$$s_2=a{s}_1-q{s}_0=0-5\cdot 2=-10,$$

故

$$|E({\mathbb{F}}_{25})|=25+1-s_2=36.$$

第四步：对照 resultant 语言。 本曲线的 cyclic resultants 为

$$R_1=|E({\mathbb{F}}_5)|=(1-i\sqrt{5})(1+i\sqrt{5})=1+5=6=P_E(1),R_2=|E({\mathbb{F}}_{25})|=(1-{\alpha }^2)(1-{\bar{\alpha }}^2)=(1+5{)}^2=36,$$

两个群阶都来自同一个二次多项式 $1+5T^2$。如果假装 $P_E$ 未知：由 $R_1=P_E(1)=6$、$q=5$ 与 Hasse 界 $|a|\le 4$，方程 $6=6-a$ 直接钉死 $a=0$——这就是”单个 resultant 确定 genus 1 的 Weil 多项式”在最小规模上的样子。genus $\ge 2$ 时 $R_1$ 只留下一个方程而未知数有 $g$ 个（利用函数方程回文对称后），这才需要第 4 节的多指纹重建。

6. 速度提升与限制

量子复杂度的来源逐项拆解。 整条流水线对每个被选中的 $n$（共 $\mathrm{poly}(g)$ 个）执行：

• 域算术：$\mathrm{poly}(n\log q)$（${\mathbb{F}}_{q^n}$ 元素是 $n\log q$ 比特的对象）；
• 单次群运算（含约化）：$\mathrm{poly}(g)$ 次域运算；
• Abel 群分解：$\mathrm{poly}(\log |J_C({\mathbb{F}}_{q^n})|)=\mathrm{poly}(gn\log q)$ 量子门（第 3.3 节）；
• 经典重建与验证：$\mathrm{poly}(g,\log q)$（第 4 节）。

把所有因子乘起来、再对 $n$ 的多项式上界求和，总量子复杂度关于 $g,\log q$ 为多项式——注意这个结论依赖两端的”多项式性”同时成立：一端是高效曲线/Jacobian 算术与可证明近均匀的随机元素构造（保证单次黑盒查询便宜且生成元可靠），另一端是 Weil 多项式的输出规模本身只有 $O(g)$ 个系数、每系数 $O(g\log q)$ 比特（保证”求出整个 zeta”是个有限任务）。

与经典算法的比较需要谨慎陈述。 已知经典通用算法在某些参数（特别是域特征、genus）有不同表现：例如椭圆曲线（$g=1$）早有关于 $\log q$ 多项式的经典 $\ell$-进算法，固定小特征下也有高效的 $p$-进方法；因此”量子超多项式加速”不应笼统断言，而应按论文所比较的联合参数族陈述——即 $g$ 与 $\log q$（及特征）同时变化的特定序列上，已知最佳经典算法的复杂度增长超过多项式，而本算法保持多项式。这一限定是原论文结论的一部分，引用时不应省略。

结论的边界。 还有两点不能越界：

• 算法输出完整的 zeta rational function（即精确的整系数 Weil 多项式 $P_C$），而不是零点的浮点近似。得到 $P_C$ 之后当然可以在经典机器上数值求根到任意精度，但那是后处理，不是算法的一部分；
• van Dam 的相关工作（Zoo 编号 87）研究的是用量子过程（谱估计类思路）获取 zeta zeros/谱信息，问题设定与本词条不同。尤其重要的是：本词条一切结果都关于有限域曲线的 zeta function——Weil 根模长 $\sqrt{q}$、有理性、函数方程是这个世界的定理；不能把有限域曲线结果外推到计算 Riemann zeta 非平凡零点。两者的相似是类比层面的（Euler 乘积、“Riemann 假设”的措辞），不是算法层面的。

7. 小结与习题

• 曲线 zeta function 由 $2g$ 次 Weil polynomial $P_C$ 完全决定：有理性把无穷点数序列压缩成有限个整系数，Weil 界保证每个系数只需 $O(g\log q)$ 量级比特；
• 点数公式 $N_n=q^n+1-{\sum }_j{\alpha }_j^n$ 把”数点”翻译成”Weil 根的幂和”，Hasse–Weil 界是它的直接推论；
• Jacobian 扩域群阶是 Weil 根的 cyclic resultant：$|J_C({\mathbb{F}}_{q^n})|={\prod }_j(1-{\alpha }_j^n)=\mathrm{Res}(P_C,T^n-1)$，群阶即指纹；
• 把 Jacobian 包装成 Abel 黑盒群（规范 divisor 表示 + Riemann–Roch 约化 + 可证明近均匀的随机元素），量子 Abel 群分解高效求这些群阶，经典重建恢复多项式；
• 整性、functional equation 和 Weil bounds 是从有限指纹唯一恢复的关键——没有这些离散约束，cyclic resultants 不能唯一确定一般多项式；
• 复杂度关于 $g,\log q$ 多项式的结论依赖曲线算术、随机元素构造与重建算法的多项式性同时成立；“超多项式加速”须按联合参数族陈述，且结果不可外推到 Riemann zeta。

习题

1. 从 $P_C(T)={\prod }_{j=1}^{2g}(1-{\alpha }_{j}T)$ 的根表达与 $Z_C$ 的定义出发，补全第 1.4 节推导 $N_n=q^n+1-{\sum }_j{\alpha }_j^n$ 的全部中间步骤，并进一步推出 Hasse–Weil 界 $|N_n-(q^n+1)|\le 2g{q}^{n/2}$。
2. 对椭圆曲线 $P(T)=1-aT+q{T}^2$，用递推 $s_n=a{s}_{n-1}-q{s}_{n-2}$ 写出 $|E({\mathbb{F}}_{q^2})|$ 与 $|E({\mathbb{F}}_{q^3})|$ 的显式公式（答案只含 $a$ 与 $q$）。
3. 在 5.3 节的例子（$E:y^2=x^3+1$，$q=5$）中，改用 resultant 定义直接计算 $\mathrm{Res}(1+5T^2,T-1)$ 与 $\mathrm{Res}(1+5T^2,T^2-1)$，验证它们分别等于 $R_1=6$ 与 $R_2=36$。
4. 解释为何 Jacobian 元素必须有唯一/可比较的规范编码：如果同一个 divisor class 允许两个不同的比特串代表，Abel 黑盒群算法的哪一步会出错？（提示：回想相位估计要求”群的正则表示”是良好定义的。）
5. 用第 2.2 节的群阶估计证明 $\log |J_C({\mathbb{F}}_{q^n})|=\Theta (gn\log q)$，并据此说明：为什么求单个 $R_n$ 的量子代价关于 $g,n,\log q$ 是多项式的？如果改为要求 $n$ 大到 $q^{ng}$ 超过输入规模，会在哪一步破坏多项式性？
6. 区分局部 zeta function 与 Riemann zeta：各在什么域/环上定义、各自的”Euler 乘积”遍历什么对象、各自的”Riemann 假设”分别断言什么？为什么说 Kedlaya 算法与 Riemann zeta 非平凡零点的计算没有关系？

参考文献

• Zoo 编号 64：Kiran Kedlaya, Quantum Computation of Zeta Functions of Curves.
• Zoo 编号 87：Wim van Dam, Quantum Computing and Zeros of Zeta Functions.

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch13-topology-statistical-physics/zeta-functions
• 内容遵循 CC BY-NC-SA 4.0 许可协议