Gauss 和估计

Gauss 和是数论中最经典的指数和之一：它把有限域的加法结构（通过一个加法特征）与乘法结构（通过一个乘法特征）压缩成单个复数。这个复数的模长是已知的 $\sqrt{q}$，但它的相位凝聚了全部非平凡信息——Gauss 本人为了确定二次 Gauss 和的符号就花费了数年时间。

经典算法要估计这个相位，目前已知的办法本质上都要逐项处理 $q-1$ 个求和项。van Dam 与 Seroussi 提出的量子算法走了另一条路：把乘法特征制备成一个量子态，用加法量子傅里叶变换作用上去，Gauss 和会自动以本征相位的形式出现，然后交给相位估计读出。本词条完整推导这条”特征态 $\to$ 傅里叶变换 $\to$ 逆元置换 $\to$ 可测相位”的链条，并说清楚复杂度中每个因子的来源。

学习本词条需要量子傅里叶变换、相位估计的基础，以及Shor 因数分解中”叠加求指数、再用傅里叶变换提取周期”的经验——本词条的离散对数子程序与之一脉相承。

1. 问题从何而来

1.1 指数和与相位问题

在数论中，我们经常遇到形如”对有限域中所有元素，把某个乘性函数与某个振荡因子相乘后求和”的表达式，统称指数和 (exponential sums)。它们出现在素数分布、方程解数计数、编码论权分布等问题中。Gauss 和是其中结构最干净的一种：

$$G(\chi ,\psi )=\sum _{x\in {\mathbb{F}}_q^{\times }}\chi (x)\psi (x),$$

其中 ${\mathbb{F}}_q$ 是 $q$ 元有限域，$\chi$ 是乘法特征（乘性），$\psi$ 是加法特征（振荡因子）。每一项 $\chi (x)\psi (x)$ 都是模长为 $1$ 的复数，一共 $q-1$ 项。如果各项相位随机无关，由”随机行走”直觉，总和的模长应当在 $\sqrt{q}$ 量级；而数论的严格结果（下文将完整证明）是：当两个特征都非平凡时，模长恰好是 $\sqrt{q}$。

于是 $G(\chi ,\psi )$ 这个复数被分解为”已知的模长”乘”未知的相位”：

$$G(\chi ,\psi )=\sqrt{q}{e}^{i\gamma }.$$

估计问题就是：给定 $\chi$ 与 $\psi$ 的描述，把 $\gamma$ 估计到加性误差 $ϵ$ 以内。这个问题的经典难度不在”模长”而在”相位”：相位由 $q-1$ 个单位复数之间极其精细的相消干涉决定，任何一项算错都会污染结果。

1.2 历史与动机

Gauss 和在 Gauss 研究分圆问题与二次互反律时就已经出现；二次情形（$\chi$ 取 Legendre 符号、$q$ 为奇素数）的相位符号问题曾困扰 Gauss 多年，其闭式解是数论的标志性结果之一。但对一般的 $\chi$ 与 $q$，并不存在可用的统一闭式，“给定特征、算出相位”在经典计算中只能硬算。

van Dam 与 Seroussi（Zoo 编号 90）给出了估计 Gauss 和的高效量子算法，并给出一个方向的复杂性证据：离散对数问题可以约化到 Gauss 和估计。Geraci 与 Lidar（Zoo 编号 47）则把这类结果与统计物理中的 Potts 模型配分函数联系起来。这些联系的边界条件我们在第 10 节详细讨论。

1.3 经典算法能做到什么程度

朴素的经典算法就是按定义求和：枚举 $q-1$ 个非零元素，对每个元素算一次 $\chi (x)$ 与 $\psi (x)$（各自需要 $\mathrm{poly}(\log q)$ 次域运算），累加后取辐角。总成本是

$$O\left(q\cdot \mathrm{poly}(\log q)\right),$$

即关于输入规模 $\log q$ 是指数的。更精细的经典方法（利用特征的代数结构分段求和）目前已知最好也只是把常数和低阶因子压低，没有一个能在 $\mathrm{poly}(\log q,1/ϵ)$ 时间内输出相位的一般方法。量子算法的目标正是把对 $q$ 的依赖从 $O(q)$ 压到 $\mathrm{poly}(\log q)$，代价是答案只能以概率方式读出、且精度 $ϵ$ 要付出 $1/ϵ$ 的代价——这两个保留条件贯穿全课。

2. 有限域与两类特征

本节把后文需要的有限域工具备齐：域迹、加法特征、乘法特征，以及两组正交关系。所有结论都给出证明，因为第 6 节的关键恒等式就是它们的直接推论。

2.1 有限域与域迹

设 $p$ 为素数，$q=p^m$，记 $q$ 元有限域为 ${\mathbb{F}}_q$。它包含素域 ${\mathbb{F}}_p\cong \mathbb{Z}/p\mathbb{Z}$，并且是 ${\mathbb{F}}_p$ 上的 $m$ 维线性空间。非零元素全体在乘法下构成循环群

$${\mathbb{F}}_q^{\times }=\{1,g,g^2,\dots ,g^{q-2}\},g^{q-1}=1,$$

其中 $g$ 是任意取定的生成元（本原元）。

域迹 (field trace) 定义为

$$\mathrm{Tr}(x)=x+x^p+x^{p^2}+\cdots +x^{p^{m-1}}.$$

它有三条我们需要的性质：

• 取值在 ${\mathbb{F}}_p$ 中。由费马小定理的域版本，$t\in {\mathbb{F}}_q$ 属于 ${\mathbb{F}}_p$ 当且仅当 $t^p=t$。而

$$\mathrm{Tr}(x{)}^p=x^p+x^{p^2}+\cdots +x^{p^{m-1}}+x^{p^m}=x^p+x^{p^2}+\cdots +x^{p^{m-1}}+x=\mathrm{Tr}(x),$$

其中用了特征 $p$ 域中的恒等式 $(a+b{)}^p=a^p+b^p$（二项式系数 $\left(\genfrac{}{}{0ex}{}{p}{k}\right)$ 在 $1\le k\le p-1$ 时都被 $p$ 整除）以及 $x^{p^m}=x^q=x$。

• ${\mathbb{F}}_p$-线性：$\mathrm{Tr}(x+y)=\mathrm{Tr}(x)+\mathrm{Tr}(y)$（同样由 $(a+b{)}^{p^k}=a^{p^k}+b^{p^k}$），且对 $c\in {\mathbb{F}}_p$ 有 $\mathrm{Tr}(cx)=c\mathrm{Tr}(x)$（因为 $c^{p^k}=c$）。

• 非零（从而满射）：$\mathrm{Tr}$ 是一个次数 $p^{m-1}$ 的多项式，在 ${\mathbb{F}}_q$ 中至多有 $p^{m-1}<q$ 个根，故不可能恒为零；作为 ${\mathbb{F}}_p$-线性映射，它的像是 ${\mathbb{F}}_p$ 的非零子空间，只能是整个 ${\mathbb{F}}_p$。由维数公式，核的大小是 $p^{m-1}$。

2.2 加法特征

加法特征 (additive character) 是群同态 $\psi :({\mathbb{F}}_q,+)\to {\mathbb{C}}^{\times }$，即满足 $\psi (x+y)=\psi (x)\psi (y)$ 的模长为 $1$ 的复值函数。固定 $a\in {\mathbb{F}}_q$，定义

$${\psi }_a(x)=\exp \left(\frac{2\pi i}{p}\mathrm{Tr}(ax)\right).$$

这个定义是合法的：$\mathrm{Tr}(ax)\in {\mathbb{F}}_p\cong \mathbb{Z}/p\mathbb{Z}$，所以 $\frac{1}{p}\mathrm{Tr}(ax)$ 只相差整数倍，$e^{2\pi i\cdot (\cdot )}$ 不受影响。同态性质由迹的线性立即得到：

$${\psi }_a(x+y)=e^{\frac{2\pi i}{p}\mathrm{Tr}(ax+ay)}=e^{\frac{2\pi i}{p}\mathrm{Tr}(ax)}\cdot e^{\frac{2\pi i}{p}\mathrm{Tr}(ay)}={\psi }_a(x){\psi }_a(y).$$

$a=0$ 给出平凡特征 ${\psi }_0\equiv 1$；可以证明 $\{{\psi }_a:a\in {\mathbb{F}}_q\}$ 穷尽了全部加法特征，但本词条只需要这一族。关键的解析工具是下面的正交关系。

Lemma 1（加法正交关系）. 对 $a\ne 0$，

$$\sum _{x\in {\mathbb{F}}_q}{\psi }_a(x)=0.$$

证明。映射 $x\mapsto \mathrm{Tr}(ax)$ 是 ${\mathbb{F}}_q\to {\mathbb{F}}_p$ 的 ${\mathbb{F}}_p$-线性映射。$a\ne 0$ 时它不是零映射（取 $x$ 使 $\mathrm{Tr}(x)\ne 0$，再乘上适当的域元素即可），故满射，其核的维数是 $m-1$、大小是 $p^{m-1}$。满射线性映射的每个原像集都与核等势，所以当 $x$ 遍历 ${\mathbb{F}}_q$ 时，$\mathrm{Tr}(ax)$ 取 ${\mathbb{F}}_p$ 中每个值恰好 $p^{m-1}$ 次。于是

$$\sum _{x\in {\mathbb{F}}_q}{\psi }_a(x)=p^{m-1}\sum _{k=0}^{p-1}{e}^{2\pi ik/p}=p^{m-1}\cdot \frac{e^{2\pi i}-1}{e^{2\pi i/p}-1}=0,$$

其中第二个等号是等比级数求和（全体 $p$ 次单位根之和为零）。Q.E.D.

2.3 乘法特征

乘法特征 (multiplicative character) 是群同态 $\chi :{\mathbb{F}}_q^{\times }\to {\mathbb{C}}^{\times }$。由于 ${\mathbb{F}}_q^{\times }$ 是 $q-1$ 阶循环群，取定生成元 $g$ 后，每个乘法特征由一个整数 $s$（模 $q-1$）唯一决定：

$${\chi }_s(g^j)=\exp \left(\frac{2\pi isj}{q-1}\right),j=0,1,\dots ,q-2.$$

$s\equiv 0(\mathrm{mod}q-1)$ 给出平凡特征 ${\chi }_0\equiv 1$。乘性 $\chi (xy)=\chi (x)\chi (y)$ 由指数相加直接得到；特别地 $\chi (y^{-1})=\chi (y{)}^{-1}=\overline{\chi (y)}$（模长为 $1$ 的复数取逆等于取共轭）。

Lemma 2（乘法正交关系）. 若 $s\not\equiv 0(\mathrm{mod}q-1)$，则

$$\sum _{x\in {\mathbb{F}}_q^{\times }}{\chi }_s(x)=0.$$

证明。把 $x=g^j$ 代入，化为等比级数：

$$\sum _{j=0}^{q-2}{e}^{2\pi isj/(q-1)}=\frac{e^{2\pi is}-1}{e^{2\pi is/(q-1)}-1}.$$

分子 $e^{2\pi is}-1=0$（$s$ 是整数）；分母 $e^{2\pi is/(q-1)}-1\ne 0$，因为 $s/(q-1)$ 不是整数。分式值为 $0$。Q.E.D.

3. Gauss 和：定义、模长与经典瓶颈

3.1 定义

固定一个乘法特征 $\chi$ 与一个加法特征 $\psi$（都允许带参数），Gauss 和 (Gauss sum) 是

$$G(\chi ,\psi )=\sum _{x\in {\mathbb{F}}_q^{\times }}\chi (x)\psi (x).$$

先排除两个退化情形，它们在算法中需要单独分类处理（见第 9 节）：

• 若 $\chi$ 平凡而 $\psi ={\psi }_a$ 非平凡，则 $G={\sum }_{x\ne 0}{\psi }_a(x)={\sum }_{x\in {\mathbb{F}}_q}{\psi }_a(x)-{\psi }_a(0)=0-1=-1$（用 Lemma 1）；
• 若 $\chi$ 非平凡而 $\psi$ 平凡，则 $G={\sum }_{x\ne 0}\chi (x)=0$（用 Lemma 2）。

两个都非平凡时，模长是普适的 $\sqrt{q}$：

Theorem 3. 设 $\chi$ 与 $\psi$ 都非平凡，则

$$|G(\chi ,\psi )|=\sqrt{q}.$$

证明。计算模方，把求和写成双重求和（$x,y$ 都遍历 ${\mathbb{F}}_q^{\times }$）：

$$|G(\chi ,\psi ){|}^2=G\cdot \overline{G}=\sum _{x\ne 0}\sum _{y\ne 0}\chi (x)\overline{\chi (y)}\psi (x)\overline{\psi (y)}.$$

逐步化简。第一步，用特征的同态性质合并：$\chi (x)\overline{\chi (y)}=\chi (x)\chi (y{)}^{-1}=\chi (x{y}^{-1})$；而 $\psi (x)\overline{\psi (y)}=\psi (x)\psi (-y)=\psi (x-y)$（加法特征满足 $\overline{\psi (y)}=\psi (y{)}^{-1}=\psi (-y)$）。于是

$$|G{|}^2=\sum _{x\ne 0}\sum _{y\ne 0}\chi (x{y}^{-1})\psi (x-y).$$

第二步，换元 $x=ty$。对每个固定的 $y\ne 0$，当 $x$ 遍历 ${\mathbb{F}}_q^{\times }$ 时 $t=x{y}^{-1}$ 也遍历 ${\mathbb{F}}_q^{\times }$（乘 $y^{-1}$ 是双射），故可改写成对 $(t,y)$ 求和：

$$|G{|}^2=\sum _{t\ne 0}\chi (t)\sum _{y\ne 0}\psi \left(y(t-1)\right).$$

注意现在内层求和只通过 $t-1$ 依赖 $t$，可以按 $t=1$ 与 $t\ne 1$ 分类。

第三步，算内层和。当 $t=1$ 时 $\psi (0)=1$，内层和为 ${\sum }_{y\ne 0}1=q-1$。当 $t\ne 1$ 时 $a:=t-1\ne 0$，由 Lemma 1 有 ${\sum }_{y\in {\mathbb{F}}_q}\psi (ay)=0$，减去 $y=0$ 那一项（值为 $1$）得

$$\sum _{y\ne 0}\psi \left(y(t-1)\right)=-1.$$

第四步，代回并对 $t$ 求和：

$$|G{|}^2=\chi (1)(q-1)+\sum _{\begin{array}{c}t\ne 0\\ t\ne 1\end{array}}\chi (t)\cdot (-1)=(q-1)-\sum _{\begin{array}{c}t\ne 0\\ t\ne 1\end{array}}\chi (t).$$

由 Lemma 2，${\sum }_{t\ne 0}\chi (t)=0$，所以 ${\sum }_{t\ne 0,t\ne 1}\chi (t)=-\chi (1)=-1$。代回得

$$|G{|}^2=(q-1)-(-1)=q.$$

Q.E.D.

3.2 问题归结为相位

Theorem 3 说明：对非平凡特征，$G(\chi ,\psi )$ 落在一个已知半径 $\sqrt{q}$ 的圆周上，全部未知信息是归一化相位

$$e^{i\gamma }=\frac{G(\chi ,\psi )}{\sqrt{q}}.$$

这正是量子计算擅长处理的对象：本征相位。第 4–7 节的目标就是构造一个酉算子 $U$，使 $e^{i\gamma }$ 成为它的本征值，且对应的本征态可以高效制备。

经典算法的瓶颈也在这里看得更清楚：要拿到 $\gamma$，就得确定 $q-1$ 个单位复数相消之后剩下的合成方向。任何不实际枚举求和项的方法，都必须利用 $\chi ,\psi$ 之间更深层的代数巧合；对一般的输入，目前没有这样的多项式时间经典方法。

4. 量子算法总览：一句话与三个部件

整个算法可以用一句话说完：制备乘法特征态 $|\chi ⟩$，用加法傅里叶变换 $F_{\psi }$ 把它变成自己的”逆特征态”并附带相位 $G/\sqrt{q}$，再用逆元置换 $J$ 把态送回原处，使相位成为本征相位，最后做相位估计。

三个部件各自的角色：

• 特征态制备（第 5 节）：把经典的函数 $\chi$ 编码成量子叠加 $|\chi ⟩\propto {\sum }_x\chi (x)|x⟩$。这是”乘性数据进量子态”的一步，需要一个 Shor 型离散对数子程序。
• 加法 QFT $F_{\psi }$（第 6 节）：由加法特征定义的傅里叶变换。它作用在 $|\chi ⟩$ 上时，Gauss 和作为整体因子出现——这是全课的核心恒等式。
• 逆元置换 $J$ 与相位估计（第 7、8 节）：$F_{\psi }$ 把 $|\chi ⟩$ 映到 $|{\chi }^{-1}⟩$ 而不是自身，补上 $J$ 后才得到本征方程，相位估计才有用武之地。

直觉上，这套构造与 Shor 算法同构：Shor 用叠加制备周期函数、用 QFT 把周期变成频域峰值；这里用叠加制备特征函数、用”对偶”的傅里叶变换把乘性振荡与加性振荡的关联（即 Gauss 和）变成相位。

5. 特征态的制备

定义归一化的特征态 (character state)

$$|\chi ⟩=\frac{1}{\sqrt{q-1}}\sum _{x\in {\mathbb{F}}_q^{\times }}\chi (x)|x⟩.$$

因为 $|\chi (x)|=1$ 且共 $q-1$ 项，该态已归一。我们按 $|\chi ⟩=|{\chi }_s⟩$ 的参数 $s$ 给出制备流程，分四步：

第一步：指数寄存器的均匀叠加。 制备

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

$q-1$ 一般不是 $2$ 的幂，标准的做法是：在 $\lceil {\log }_2(q-1)\rceil$ 个量子比特上制备均匀叠加，用一次可逆比较标记 $j\ge q-1$ 的分量并测量该标志；单次成功概率 $\ge \frac{1}{2}$，期望 $O(1)$ 次重复即得（也可以用振幅放大做成精确制备）。成本 $\mathrm{poly}(\log q)$。

第二步：可逆计算 $x=g^j$。 调用模 $q$（即 ${\mathbb{F}}_q$ 中）的平方–乘指数电路：

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

有限域乘法与指数运算用可逆电路实现，成本关于 $\log q$ 是多项式。

第三步：按 $j$ 加相位。 对第一个寄存器施以相位 $e^{2\pi isj/(q-1)}$（受控相位门的组合，角度精度取 $O(\log q)$ 比特即可），得到

$$\frac{1}{\sqrt{q-1}}\sum _{j=0}^{q-2}{e}^{2\pi isj/(q-1)}|j⟩|g^j⟩.$$

第四步：清除 $j$。 现在两个寄存器纠缠在一起。由于 $x=g^j$ 与 $j$ 一一对应，$j$ 就是 $x$ 的离散对数；调用 Shor 型离散对数量子子程序（结构上与Shor 算法中求阶子程序相同，作用在 $q-1$ 阶循环群上），从第二个寄存器可逆地反算出 $j$ 并把第一个寄存器清回 $|0⟩$：

$$\frac{1}{\sqrt{q-1}}\sum _{j=0}^{q-2}{e}^{2\pi isj/(q-1)}|g^j⟩=\frac{1}{\sqrt{q-1}}\sum _{x\in {\mathbb{F}}_q^{\times }}{\chi }_s(x)|x⟩=|{\chi }_s⟩,$$

其中等号只是换元 $x=g^j$ 并代入 ${\chi }_s$ 的定义式。

整条链路的门复杂度是 $\mathrm{poly}(\log q)$（其中离散对数子程序贡献了主要部分；角度与域运算的有限精度引入的误差多项式地被 $\log q$ 与精度参数控制，此处按惯例忽略精度多项式因子）。记住这个成本量级，第 8 节做总账时会用到。

6. 关键恒等式：加法傅里叶变换作用在特征态上

6.1 加法量子傅里叶变换

由加法特征 $\psi$ 定义的加法量子傅里叶变换是

$$F_{\psi }|x⟩=\frac{1}{\sqrt{q}}\sum _{y\in {\mathbb{F}}_q}\psi (xy)|y⟩,x\in {\mathbb{F}}_q.$$

它是酉的：两个不同列的内积为

$$\frac{1}{q}\sum _y\psi (x_{1}y)\overline{\psi (x_{2}y)}=\frac{1}{q}\sum _y\psi \left((x_1-x_2)y\right)={\delta }_{x_1,x_2},$$

最后一步正是 Lemma 1（$x_1\ne x_2$ 时和为零；$x_1=x_2$ 时每项为 $1$，归一化因子 $\frac{1}{q}$ 给出 $1$）。实现上，取 ${\mathbb{F}}_q$ 在 ${\mathbb{F}}_p$ 上的适当基后，迹型 $(x,y)\mapsto \mathrm{Tr}(xy)$ 成为逐坐标的 pairing，$F_{\psi }$ 分解为 $m$ 个 $p$ 维 QFT 的张量积（至多相差一组基变换），因此电路规模为 $m\cdot \mathrm{poly}(\log p)=\mathrm{poly}(\log q)$。

6.2 核心计算

现在把 $F_{\psi }$ 作用到 $|\chi ⟩$ 上。我们对每个输出基矢 $|y⟩$ 单独算振幅，分 $y\ne 0$ 与 $y=0$ 两种情形。

情形一：$y\ne 0$。 由定义展开（两个归一化因子 $\frac{1}{\sqrt{q}}$ 与 $\frac{1}{\sqrt{q-1}}$ 合并）：

$$⟨y|F_{\psi }|\chi ⟩=\frac{1}{\sqrt{q(q-1)}}\sum _{x\ne 0}\chi (x)\psi (xy).$$

做换元 $z=xy$。因为 $y\ne 0$，乘 $y$ 是 ${\mathbb{F}}_q^{\times }$ 上的双射，所以 $x$ 遍历 ${\mathbb{F}}_q^{\times }$ 时 $z$ 也恰好遍历 ${\mathbb{F}}_q^{\times }$；反解 $x=z{y}^{-1}$，利用 $\chi$ 的乘性：

$$\chi (x)=\chi (z{y}^{-1})=\chi (z)\chi (y^{-1})=\chi (z)\chi (y{)}^{-1}.$$

因子 $\chi (y{)}^{-1}$ 不含求和变量 $z$，可以提出求和号：

$$\sum _{x\ne 0}\chi (x)\psi (xy)=\chi (y{)}^{-1}\sum _{z\ne 0}\chi (z)\psi (z)=\chi (y{)}^{-1}G(\chi ,\psi ),$$

其中最后一步认出括号里正是 Gauss 和的定义式。于是

$$⟨y|F_{\psi }|\chi ⟩=\frac{G(\chi ,\psi )}{\sqrt{q(q-1)}}\chi (y{)}^{-1},y\ne 0.$$

情形二：$y=0$。 此时 $\psi (x\cdot 0)=\psi (0)=1$，振幅退化为乘法特征的总和：

$$⟨0|F_{\psi }|\chi ⟩=\frac{1}{\sqrt{q(q-1)}}\sum _{x\ne 0}\chi (x)=0,$$

由 Lemma 2（$\chi$ 非平凡）。非零特征态经 $F_{\psi }$ 后没有 $|0⟩$ 分量。

把两种情形合并，输出态只在 $y\ne 0$ 的基矢上有振幅：

$$F_{\psi }|\chi ⟩=\frac{G(\chi ,\psi )}{\sqrt{q(q-1)}}\sum _{y\ne 0}\chi (y{)}^{-1}|y⟩=\frac{G(\chi ,\psi )}{\sqrt{q}}\cdot \frac{1}{\sqrt{q-1}}\sum _{y\ne 0}{\chi }^{-1}(y)|y⟩,$$

即

$$F_{\psi }|\chi ⟩=\frac{G(\chi ,\psi )}{\sqrt{q}}|{\chi }^{-1}⟩,$$

其中 ${\chi }^{-1}$ 表示逐点取逆的特征（${\chi }^{-1}(y):=\chi (y{)}^{-1}$），它同样是一个乘法特征（把参数 $s$ 换成 $-s$），故 $|{\chi }^{-1}⟩$ 是归一化的。

这就是算法的关键恒等式。 值得停下来体会两点：

• Gauss 和不再是需要逐项相加的 $q-1$ 个数，而是作为一个整体因子从求和中”掉出来”——这正是量子并行性的体现：换元 $z=xy$ 在叠加态的所有分量上同时发生。
• 输出与输入的模长必须一致（$F_{\psi }$ 酉）：$|G(\chi ,\psi )|/\sqrt{q}$ 必须等于 $1$。这与 Theorem 3 完全自洽——量子构造”要求”$|G|=\sqrt{q}$，数论定理保证这一点。

7. 逆元置换与本征化

上式的输出是 $|{\chi }^{-1}⟩$ 而不是 $|\chi ⟩$，相位 $G/\sqrt{q}$ 还只是一个”全局相位”，测量不到。要把它变成可测的本征相位，需要把输出态映回输入态。

定义计算基上的可逆置换

$$J|x⟩=|x^{-1}⟩(x\ne 0),J|0⟩=|0⟩,$$

即 ${\mathbb{F}}_q$ 中的取逆映射。它在经典上是双射，做成可逆电路只需扩展欧几里得算法级别的域运算，成本 $\mathrm{poly}(\log q)$；$|0⟩$ 单独指定像以保证整个算子是置换（从而是酉的）。

Lemma 4. $J|{\chi }^{-1}⟩=|\chi ⟩$。

证明。逐分量代入并换元 $w=x^{-1}$（取逆是 ${\mathbb{F}}_q^{\times }$ 上的双射）：

$$J|{\chi }^{-1}⟩=\frac{1}{\sqrt{q-1}}\sum _{x\ne 0}\chi (x{)}^{-1}|x^{-1}⟩=\frac{1}{\sqrt{q-1}}\sum _{w\ne 0}\chi (w^{-1}{)}^{-1}|w⟩=\frac{1}{\sqrt{q-1}}\sum _{w\ne 0}\chi (w)|w⟩=|\chi ⟩,$$

其中第二个等号用了 $\chi (w^{-1})=\chi (w{)}^{-1}$，故 $\chi (w^{-1}{)}^{-1}=\chi (w)$。Q.E.D.

令 $U=J{F}_{\psi }$（两个酉算子的复合，仍酉）。把第 6 节的恒等式与 Lemma 4 串起来：

$$U|\chi ⟩=J\left(\frac{G(\chi ,\psi )}{\sqrt{q}}|{\chi }^{-1}⟩\right)=e^{i\gamma }|\chi ⟩,e^{i\gamma }=\frac{G(\chi ,\psi )}{\sqrt{q}}.$$

$|\chi ⟩$ 是 $U$ 的本征态，本征值恰好是归一化 Gauss 和。 由于 $U$ 酉，其本征值模长必为 $1$——这再次与 $|G|=\sqrt{q}$ 自洽。

顺便回答一个自然疑问（也是习题）：为什么不能直接测量 $F_{\psi }|\chi ⟩$ 的计算基分布？因为 $|y⟩$ 分量的概率是 $|\frac{G}{\sqrt{q(q-1)}}\chi (y{)}^{-1}{|}^2=\frac{1}{q-1}$，与 $\gamma$ 无关——相位信息在干涉中，而不在概率分布里。本征相位必须通过相位估计这类干涉测量才能读出。

8. 相位估计与复杂度分析

现在直接对酉算子 $U$ 和本征态 $|\chi ⟩$ 做相位估计：制备 $|\chi ⟩$ 作为目标寄存器，$t$ 个辅助比特上加载受控的 $U^{2^k}$（$k=0,\dots ,t-1$），逆 QFT 后读出 $\gamma /(2\pi )$ 的 $t$ 比特近似。

逐项算总账：

• 相位估计的调用次数：要把 $\gamma$ 估到加性误差 $ϵ$ 且成功概率为常数，需要 $t=O(\log \frac{1}{ϵ})$ 个辅助比特，受控 $U$ 的总调用次数为 ${\sum }_{k=0}^{t-1}{2}^k=2^t-1=O(\frac{1}{ϵ})$。因子 $\frac{1}{ϵ}$ 完全来自相位估计的采样复杂度，与 $\log q$ 无关。
• 单次受控 $U$ 的成本：$U=J{F}_{\psi }$ 中，$F_{\psi }$ 的电路规模是 $\mathrm{poly}(\log q)$，$J$ 是 $\mathrm{poly}(\log q)$，受控化只增加常数倍开销；幂次 $U^{2^k}$ 通过重复受控 $U$ 实现，不引入关于 $q$ 的新缩放。
• 本征态制备：$|\chi ⟩$ 制备一次（相位估计开始前），成本 $\mathrm{poly}(\log q)$，含离散对数子程序。

合起来，总门数为

$$O\left(\frac{1}{ϵ}\cdot \mathrm{poly}(\log q)\right).$$

一个必须强调的保留条款：这个表达式中，对 $q$ 是多项式对数，但对精度 $ϵ$ 是 $1/ϵ$ 的多项式（线性）。也就是说，“高效”指的是关于输入规模 $\log q$ 高效；若要指数级高的精度（$ϵ=2^{-\Omega (n)}$），成本仍是指数的。不能把上面的复杂度误写成”对精度也只有对数代价”。此外，第 5 节中域运算与角度近似带来的系统误差也要计入总误差预算：把目标精度 $ϵ$ 拆成相位估计误差与算术近似误差两份（各 $ϵ/2$），算术精度取 $O(\log \frac{1}{ϵ})$ 比特即可，这只在 $\mathrm{poly}$ 因子内部增加对数项。

与第 1.3 节经典成本 $O(q\cdot \mathrm{poly}(\log q))$ 对比：量子算法把对 $q$ 的依赖从线性压到多项式对数，这是指数级的分离；作为交换，输出是概率性的、且精度受 $1/ϵ$ 限制。

9. 手算例子：${\mathbb{F}}_5$ 的二次 Gauss 和

用一个可以完全手算的小例子，把上面每一步走一遍。取 $q=5$（素数域，$m=1$，迹就是恒等），加法特征

$$\psi (x)=e^{2\pi ix/5},$$

乘法特征取 Legendre 特征（二次特征）：$\chi (x)=1$ 当 $x$ 是模 $5$ 的二次剩余，$\chi (x)=-1$ 否则。先确定它的取值：模 $5$ 的平方为

$$1^2=1,2^2=4,3^2=9\equiv 4,4^2=16\equiv 1(\mathrm{mod}5),$$

所以二次剩余是 $\{1,4\}$，非剩余是 $\{2,3\}$：

$$\chi (1)=1,\chi (2)=-1,\chi (3)=-1,\chi (4)=1.$$

9.1 按定义逐项求和

$$G=\sum _{x=1}^4\chi (x)\psi (x)=\psi (1)-\psi (2)-\psi (3)+\psi (4).$$

利用单位根的对称性把共轭项配对。由于 $\psi (5-x)=\overline{\psi (x)}$（因为 $e^{2\pi i(5-x)/5}=e^{-2\pi ix/5}$），有

$$\psi (1)+\psi (4)=2\mathrm{Re}\psi (1)=2\cos \frac{2\pi }{5},\psi (2)+\psi (3)=2\cos \frac{4\pi }{5}.$$

于是

$$G=2\cos \frac{2\pi }{5}-2\cos \frac{4\pi }{5}.$$

9.2 算出余弦的精确值

记 $c=\cos \frac{2\pi }{5}$，并设 $\theta =\frac{2\pi }{5}$。由 $5\theta =2\pi$ 得 $3\theta =2\pi -2\theta$，两边取余弦（$\cos (2\pi -x)=\cos x$）：

$$\cos 3\theta =\cos 2\theta .$$

分别用三倍角与倍角公式 $\cos 3\theta =4c^3-3c$、$\cos 2\theta =2c^2-1$，得方程

$$4c^3-3c=2c^2-1⟺4c^3-2c^2-3c+1=0.$$

$c=1$（对应 $\theta =0$）是这个方程的一个根，因式分解：

$$4c^3-2c^2-3c+1=(c-1)(4c^2+2c-1).$$

（展开验证：$(c-1)(4c^2+2c-1)=4c^3+2c^2-c-4c^2-2c+1=4c^3-2c^2-3c+1$。）由于 $c=\cos 72^{\circ }\ne 1$，$c$ 满足

$$4c^2+2c-1=0⟹c=\frac{-2\pm \sqrt{4+16}}{8}=\frac{-1\pm \sqrt{5}}{4}.$$

$\cos 72^{\circ }>0$，取正根：

$$\cos \frac{2\pi }{5}=\frac{\sqrt{5}-1}{4}.$$

再由倍角公式与 $4c^2=1-2c$：

$$\cos \frac{4\pi }{5}=2c^2-1=\frac{1-2c}{2}-1=-\frac{1+2c}{2}=-\frac{1+\frac{\sqrt{5}-1}{2}}{2}=-\frac{\sqrt{5}+1}{4}.$$

9.3 代回并与定理对照

$$G=2\cdot \frac{\sqrt{5}-1}{4}-2\cdot \left(-\frac{\sqrt{5}+1}{4}\right)=\frac{\sqrt{5}-1}{2}+\frac{\sqrt{5}+1}{2}=\sqrt{5}.$$

结果：$G=\sqrt{5}$ 是正实数，故

$$e^{i\gamma }=\frac{G}{\sqrt{5}}=1,\gamma =0.$$

逐项检查自洽性：Theorem 3 预言 $|G|=\sqrt{5}$，手算给出 $G=\sqrt{5}$，模长吻合；第 6 节的恒等式则预言 $F_{\psi }|\chi ⟩=1\cdot |{\chi }^{-1}⟩$，而二次特征满足 $\chi ={\chi }^{-1}$（取值 $\pm 1$），所以本例中 $F_{\psi }$ 本身就已经以 $|\chi ⟩$ 为本征态、本征值 $1$。

对照情形：若素数 $p\equiv 3(\mathrm{mod}4)$，同样约定下二次 Gauss 和为 $G=i\sqrt{p}$，归一化相位变为 $i$（$\gamma =\pi /2$）。这是 Gauss 当年确定的著名符号规律的两半：$p\equiv 1(\mathrm{mod}4)$ 时相位为 $1$，$p\equiv 3(\mathrm{mod}4)$ 时相位为 $i$。量子算法不需要先知道这个数论闭式——它通过本征相位直接估计答案；闭式在这里只是供我们验证算法输出正确性的基准。

10. 速度提升来自哪里、边界与推广

10.1 加速的来源

把两条路线并排看：

• 直接经典求和要遍历 $q-1$ 个域元素，逐点计算 $\chi (x)\psi (x)$ 并累加，成本关于 $\log q$ 是指数的；
• 量子电路只操作 $O(\log q)$ 个量子比特：叠加态的 $q-1$ 个分量同时参与换元与求和，Gauss 和以整体相位形式出现，读取交给相位估计。

需要如实标注的证据等级：van Dam 与 Seroussi 给出的从离散对数到 Gauss 和估计的约化，说明如果 Gauss 和估计有多项式时间经典算法，则离散对数也有——这为”经典上不易多项式求解”提供了有力证据，但这不是无条件的经典下界。本词条所有复杂度对比都必须保留”相对于当前已知经典算法”和精度模型（成功概率常数、加性误差 $ϵ$）这两个限定语。

10.2 平凡特征与退化情形

第 3.1 节已算出：$\chi$ 平凡、$\psi$ 非平凡时 $G=-1$；$\chi$ 非平凡、$\psi$ 平凡时 $G=0$。两者的模长都不是 $\sqrt{q}$，第 6–7 节的本征化推导也不再原样成立（例如 $\chi$ 平凡时 $F_{\psi }|{\chi }_0⟩$ 的 $|0⟩$ 分量不再为零）。因此算法输入必须先分类：确认两个特征都非平凡，或者对退化情形直接用闭式。

10.3 有限环推广

把有限域换成有限环（例如 $\mathbb{Z}/N\mathbb{Z}$）时，求和域要限制到单位群（可逆元全体），因为零因子的存在会改变 Gauss 和的模长与结构；实现上需要分别构造环的加法 QFT 与单位群的特征态。有限环可以分解为局部环的直积（对中国剩余定理成立的环尤为如此），Gauss 和随之分解，因此该推广的结构比有限域情形更依赖输入环的具体分解，不能一概而论地套用本词条定理。

10.4 与编码论、统计物理的联系

Gauss 和估计是很多代数指数和的”原子操作”：它连接到编码论中循环码的权枚举式 (weight enumerators)、统计物理中 Potts 模型的配分函数以及图论的 Tutte 多项式（Zoo 编号 47 的方向）。但这里的边界必须划清：量子加速只覆盖具有特定循环码或代数结构的特殊实例，不能由这些结果推出”任意图上的配分函数都能被量子计算机高效精确计算”——一般性的 Tutte 多项式精确求值已知是 p-难的，本词条的结论与之并无矛盾。

11. 小结与习题

本词条的核心链条：

• 加法特征定义 QFT（$F_{\psi }$），乘法特征定义输入态（$|\chi ⟩$）；
• $F_{\psi }$ 把 $|\chi ⟩$ 送到 $|{\chi }^{-1}⟩$，Gauss 和以整体因子 $G/\sqrt{q}$ 出现（第 6 节恒等式）；
• 逆元置换 $J$ 把输出态送回输入态，于是 $U=J{F}_{\psi }$ 以 $|\chi ⟩$ 为本征态、$e^{i\gamma }$ 为本征值，相位估计可以读出 $G/\sqrt{q}$；
• 总成本必须同时写明对 $\log q$ 的多项式依赖与对精度 $1/ϵ$ 的线性依赖，并保留”相对于已知经典算法”的限定。

习题

1.（推导）补全第 6.2 节换元 $z=xy$ 的全部细节：说明为什么 $x$ 遍历 ${\mathbb{F}}_q^{\times }$ 时 $z$ 也恰好遍历 ${\mathbb{F}}_q^{\times }$，并逐步验证系数中出现的是 $\chi (y{)}^{-1}$ 而不是 $\chi (y)$。 2.（正交关系）证明非平凡乘法特征满足 ${\sum }_{x\ne 0}\chi (x)=0$（Lemma 2），并指出证明中”非平凡”用在哪一步；进而计算 $\chi$ 平凡、$\psi$ 非平凡时的 Gauss 和，验证第 3.1 节给出的 $G=-1$。 3.（手算）对 ${\mathbb{F}}_3$ 计算二次 Gauss 和（取 $\psi (x)=e^{2\pi ix/3}$），验证结果为 $i\sqrt{3}$，即归一化相位为 $i$；对照第 9 节 $p=5$ 的情形，说明 $p\mathrm{mod}4$ 如何影响相位。 4.（概念）说明为什么只测量 $F_{\psi }|\chi ⟩$ 的计算基分布看不到 $\gamma$，而受控相位估计可以。提示：分别写出计算基测量概率与 $U$ 的本征方程。 5.（自洽性）第 6 节末尾指出，$F_{\psi }$ 的酉性”要求”$|G(\chi ,\psi )|=\sqrt{q}$。把这句话写成一个严格的论证：假设第 6.2 节恒等式成立，由 $\Vert F_{\psi }|\chi ⟩\Vert =1$ 推出 $|G|=\sqrt{q}$，并说明这与 Theorem 3 的证明互为印证而非循环论证。 6.（综合）对二次特征（${\chi }^2={\chi }_0$、$\chi$ 非平凡），证明 $|\chi ⟩$ 本身就是 $F_{\psi }$ 的本征态，并说明此时第 7 节的逆元置换 $J$ 可以省略；这与第 9 节 ${\mathbb{F}}_5$ 例子的哪一步对应？

参考文献

• Zoo 编号 90：Wim van Dam 与 Gadiel Seroussi, Efficient Quantum Algorithms for Estimating Gauss Sums.
• Zoo 编号 47：Joseph Geraci 与 Daniel A. Lidar, On the Exact Evaluation of Certain Instances of the Potts Partition Function by Quantum Computers.

---

参考资料

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