# Gauss 和估计：加法傅里叶变换与乘法特征的相位干涉

Gauss 和把有限域的加法结构与乘法结构压缩成一个复数。经典算法很难高精度恢复它的相位，而量子计算能把这个相位变成某个量子态的本征相位，再调用相位估计。本课完整推导这一“特征态 $\rightarrow$ 傅里叶变换 $\rightarrow$ 可测相位”的链条。

## 1. 有限域上的两类特征

设 $q=p^m$，有限域为 $\mathbb F_q$。域迹

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

把 $\mathbb F_q$ 映到 $\mathbb F_p$。选定 $a\ne0$ 后，加法特征可写为

$$
\psi_a(x)=
\exp\!\left(\frac{2\pi i}{p}\operatorname{Tr}(ax)\right),
$$

并满足 $\psi_a(x+y)=\psi_a(x)\psi_a(y)$。

非零元素形成循环群 $\mathbb F_q^\times$。若 $g$ 是生成元，乘法特征由某个整数 $s$ 指定：

$$
\chi_s(g^j)=\exp\!\left(\frac{2\pi i sj}{q-1}\right).
$$

它满足 $\chi_s(xy)=\chi_s(x)\chi_s(y)$。对应的 Gauss 和是

$$
G(\chi,\psi)=
\sum_{x\in\mathbb F_q^\times}\chi(x)\psi(x).
$$

当 $\chi$ 与 $\psi$ 都非平凡时，正交关系给出

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

因此未知信息只剩归一化相位 $G/\sqrt q=e^{i\gamma}$。

## 2. 把乘法特征制成量子态

定义归一化特征态

$$
|\chi\rangle=
\frac1{\sqrt{q-1}}
\sum_{x\ne0}\chi(x)|x\rangle.
$$

从指数寄存器的均匀叠加出发，可逆计算 $g^j$，并按 $sj/(q-1)$ 加相位。为了只留下 $|x\rangle$ 而清除 $j$，需要可逆离散对数或等价的 Shor 型子程序。这里的域运算、指数运算和离散对数都只使用 $\operatorname{poly}(\log q)$ 个基本门（忽略精度多项式）。

加法量子傅里叶变换定义为

$$
F_\psi|x\rangle=
\frac1{\sqrt q}\sum_{y\in\mathbb F_q}\psi(xy)|y\rangle.
$$

把它作用到 $|\chi\rangle$。对 $y\ne0$，输出振幅为

$$
\begin{aligned}
\langle y|F_\psi|\chi\rangle
&=\frac1{\sqrt{q(q-1)}}
\sum_{x\ne0}\chi(x)\psi(xy)\\
&=\frac{G(\chi,\psi)}{\sqrt{q(q-1)}}\chi(y)^{-1},
\end{aligned}
$$

其中第二步令 $z=xy$。$y=0$ 的振幅因非平凡特征求和为零。于是

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

这就是算法的关键恒等式：Gauss 和不再是需要逐项相加的 $q-1$ 个数，而是一个整体相位。

## 3. 相位如何被读出

定义可逆置换 $J|x\rangle=|x^{-1}\rangle$（并单独处理 $|0\rangle$）。变量替换表明

$$
J|\chi^{-1}\rangle=|\chi\rangle.
$$

所以酉算子 $U=JF_\psi$ 满足

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

现在直接对 $U$ 和本征态 $|\chi\rangle$ 做[相位估计](../ch03-algo-basics/phase-estimation.md)，即可得到 $\gamma$。若要求相位加性误差 $\epsilon$，标准相位估计需要 $O(1/\epsilon)$ 次受控 $U$ 调用；每次调用的有限域运算成本关于 $\log q$ 为多项式。不能把这句话误写成“对精度也只有对数复杂度”。

平凡特征、加法特征参数为零以及有限环中存在零因子的情况会改变 Gauss 和的模，需先分类处理。有限环推广把求和域限制到单位群，并分别实现环的加法 QFT 与单位群特征；其结构比有限域情形更依赖输入环的分解。

## 4. 手算 $\mathbb F_5$ 的二次特征

取 Legendre 特征

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

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

$$
G=\psi(1)-\psi(2)-\psi(3)+\psi(4).
$$

把共轭项配对：

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

所以 $e^{i\gamma}=1$。若素数 $p\equiv3\pmod4$，相应二次 Gauss 和的相位会变为 $i$（在上述特征约定下）。量子算法不需要先知道这个数论闭式；它通过本征相位直接估计答案。

## 5. 速度提升究竟来自哪里

直接经典求和要遍历 $q-1$ 个域元素，而量子电路操作 $O(\log q)$ 个量子比特上的叠加。van Dam 与 Seroussi 还给出了从离散对数到 Gauss 和估计的约化，为“经典上不易多项式求解”提供证据。但这不是无条件经典下界；复杂度陈述必须保留“相对于当前已知经典算法”和精度模型。

Gauss 和也连接到编码论的权枚举式、Potts 模型配分函数和 Tutte 多项式。量子加速只覆盖具有特定循环码或代数结构的实例，不能由此推出任意图上的配分函数都能高效精确计算。

## 6. 小结与习题

- 加法特征定义 QFT，乘法特征定义输入态。
- $F_\psi$ 把 $|\chi\rangle$ 送到 $|\chi^{-1}\rangle$，Gauss 和成为全局相位。
- 逆元置换把输出态送回输入态，于是相位估计可以读出 $G/\sqrt q$。
- 总成本必须同时写明 $\log q$ 与精度 $1/\epsilon$ 的依赖。

1. 补全变量替换 $z=xy$ 的推导，并证明系数中出现 $\chi(y)^{-1}$。
2. 证明非平凡乘法特征满足 $\sum_{x\ne0}\chi(x)=0$。
3. 对 $\mathbb F_3$ 计算二次 Gauss 和，并验证归一化相位为 $i$。
4. 说明为什么只测量 $F_\psi|\chi\rangle$ 的计算基分布看不到 $\gamma$，而受控相位估计可以。

## 参考文献

- Zoo 编号 90：Wim van Dam 与 Gadiel Seroussi, [Efficient Quantum Algorithms for Estimating Gauss Sums](https://arxiv.org/abs/quant-ph/0207131).
- Zoo 编号 47：Joseph Geraci 与 Daniel A. Lidar, [On the Exact Evaluation of Certain Instances of the Potts Partition Function by Quantum Computers](https://arxiv.org/abs/quant-ph/0703023).