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

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

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

学习本课需要[量子傅里叶变换](../ch03-algo-basics/quantum-fourier-transform.md)、[相位估计](../ch03-algo-basics/phase-estimation.md)的基础，以及[Shor 因数分解](../ch04-classic-algorithms/shors-algorithm-tutorial.md)中"叠加求指数、再用傅里叶变换提取周期"的经验——本课的离散对数子程序与之一脉相承。

:::{admonition} 本课知识点
:class: tip

1. **[Gauss 和与相位估计问题](#gauss-sum-problem)**——能写出 Gauss 和 $G(\chi,\psi)$ 的定义，解释"模长已知为 $\sqrt q$、相位 $\gamma$ 未知"的分解，并比较经典 $O(q\cdot\operatorname{poly}(\log q))$ 与量子 $\operatorname{poly}(\log q,1/\epsilon)$ 两类成本。
2. **[两类特征与正交关系](#characters-orthogonality)**——能由域迹定义加法特征 $\psi_a$、用生成元参数化乘法特征 $\chi_s$，并证明非平凡特征的加法与乘法两条正交关系。
3. **[Gauss 和的模长定理](#gauss-sum-modulus)**——能用模方展开、换元 $x=ty$ 与两条正交关系推导 $|G(\chi,\psi)|=\sqrt q$，并计算平凡特征组合下的退化值 $-1$ 与 $0$。
4. **[特征态的制备](#character-state-preparation)**——能按"均匀叠加—可逆指数—相位写入—离散对数清除"四步构造特征态 $|\chi\rangle$，并说明每步成本为 $\operatorname{poly}(\log q)$。
5. **[加法 QFT 与关键恒等式](#fourier-key-identity)**——能验证 $F_\psi$ 的酉性，逐振幅推导 $F_\psi|\chi\rangle=\frac{G(\chi,\psi)}{\sqrt q}\,|\chi^{-1}\rangle$，并解释 $|0\rangle$ 分量为零的原因。
6. **[逆元置换与本征化](#eigenization-inverse-permutation)**——能证明 $J|\chi^{-1}\rangle=|\chi\rangle$，把 $U=JF_\psi$ 的本征值与归一化 Gauss 和对应起来，并解释直接测量计算基为何读不到相位。
7. **[相位估计与复杂度分析](#phase-estimation-complexity)**——能核算读出 $\gamma$ 的总成本 $O\big(\frac{1}{\epsilon}\cdot\operatorname{poly}(\log q)\big)$，区分对 $\log q$ 与对精度 $\epsilon$ 的依赖，并说出结论的适用边界。
8. **[手算二次 Gauss 和](#quadratic-gauss-sum-example)**——能对 $\mathbb F_5$ 与 $\mathbb F_3$ 手算二次 Gauss 和，得到 $\gamma=0$ 与 $\gamma=\pi/2$，并归纳相位随 $p\bmod 4$ 的符号规律。

:::

## 1. 问题从何而来

(gauss-sum-problem)=
### 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$ 估计到加性误差 $\epsilon$ 以内。这个问题的经典难度不在"模长"而在"相位"：相位由 $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)$（各自需要 $\operatorname{poly}(\log q)$ 次域运算），累加后取辐角。总成本是

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

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

(characters-orthogonality)=
## 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}\},\qquad g^{q-1}=1,
$$

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

**域迹 (field trace)** 定义为

$$
\operatorname{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$。而

$$
\operatorname{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=\operatorname{Tr}(x),
$$

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

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

- **非零（从而满射）**：$\operatorname{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}\operatorname{Tr}(ax)\right).
$$

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

$$
\psi_a(x+y)=e^{\frac{2\pi i}{p}\operatorname{Tr}(ax+ay)}=e^{\frac{2\pi i}{p}\operatorname{Tr}(ax)}\cdot e^{\frac{2\pi i}{p}\operatorname{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\operatorname{Tr}(ax)$ 是 $\mathbb F_q\to\mathbb F_p$ 的 $\mathbb F_p$-线性映射。$a\ne0$ 时它不是零映射（取 $x$ 使 $\operatorname{Tr}(x)\ne0$，再乘上适当的域元素即可），故满射，其核的维数是 $m-1$、大小是 $p^{m-1}$。满射线性映射的每个原像集都与核等势，所以当 $x$ 遍历 $\mathbb F_q$ 时，$\operatorname{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 i k/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 i\,sj}{q-1}\right),\qquad j=0,1,\dots,q-2.
$$

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

**Lemma 2（乘法正交关系）**. 若 $s\not\equiv0\pmod{q-1}$，则

$$
\sum_{x\in\mathbb F_q^\times}\chi_s(x)=0.
$$

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

$$
\sum_{j=0}^{q-2}e^{2\pi i sj/(q-1)}=\frac{e^{2\pi i s}-1}{e^{2\pi i s/(q-1)}-1}.
$$

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

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

(gauss-sum-modulus)=
### 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\ne0}\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\ne0}\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\ne0}\sum_{y\ne0}\chi(x)\overline{\chi(y)}\,\psi(x)\overline{\psi(y)}.
$$

逐步化简。第一步，用特征的同态性质合并：$\chi(x)\overline{\chi(y)}=\chi(x)\chi(y)^{-1}=\chi(xy^{-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\ne0}\sum_{y\ne0}\chi(xy^{-1})\,\psi(x-y).
$$

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

$$
|G|^2=\sum_{t\ne0}\chi(t)\sum_{y\ne0}\psi\!\left(y(t-1)\right).
$$

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

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

$$
\sum_{y\ne0}\psi\!\left(y(t-1)\right)=-1.
$$

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

$$
|G|^2=\chi(1)(q-1)+\sum_{\substack{t\ne0\\t\ne1}}\chi(t)\cdot(-1)=(q-1)-\sum_{\substack{t\ne0\\t\ne1}}\chi(t).
$$

由 Lemma 2，$\sum_{t\ne0}\chi(t)=0$，所以 $\sum_{t\ne0,t\ne1}\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\rangle$，用加法傅里叶变换 $F_\psi$ 把它变成自己的"逆特征态"并附带相位 $G/\sqrt q$，再用逆元置换 $J$ 把态送回原处，使相位成为本征相位，最后做相位估计。**

三个部件各自的角色：

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

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

(character-state-preparation)=
## 5. 特征态的制备

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

$$
|\chi\rangle=\frac{1}{\sqrt{q-1}}\sum_{x\in\mathbb F_q^\times}\chi(x)\,|x\rangle.
$$

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

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

$$
\frac{1}{\sqrt{q-1}}\sum_{j=0}^{q-2}|j\rangle.
$$

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

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

$$
\frac{1}{\sqrt{q-1}}\sum_{j=0}^{q-2}|j\rangle\,|g^j\rangle.
$$

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

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

$$
\frac{1}{\sqrt{q-1}}\sum_{j=0}^{q-2}e^{2\pi i sj/(q-1)}\,|j\rangle\,|g^j\rangle.
$$

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

$$
\frac{1}{\sqrt{q-1}}\sum_{j=0}^{q-2}e^{2\pi i sj/(q-1)}\,|g^j\rangle
=\frac{1}{\sqrt{q-1}}\sum_{x\in\mathbb F_q^\times}\chi_s(x)\,|x\rangle=|\chi_s\rangle,
$$

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

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

(fourier-key-identity)=
## 6. 关键恒等式：加法傅里叶变换作用在特征态上

### 6.1 加法量子傅里叶变换

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

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

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

$$
\frac1q\sum_{y}\psi(x_1y)\overline{\psi(x_2y)}=\frac1q\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$，归一化因子 $\frac1q$ 给出 $1$）。实现上，取 $\mathbb F_q$ 在 $\mathbb F_p$ 上的适当基后，迹型 $(x,y)\mapsto\operatorname{Tr}(xy)$ 成为逐坐标的 pairing，$F_\psi$ 分解为 $m$ 个 $p$ 维 QFT 的张量积（至多相差一组基变换），因此电路规模为 $m\cdot\operatorname{poly}(\log p)=\operatorname{poly}(\log q)$。

### 6.2 核心计算

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

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

$$
\langle y|F_\psi|\chi\rangle=\frac{1}{\sqrt{q(q-1)}}\sum_{x\ne0}\chi(x)\,\psi(xy).
$$

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

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

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

$$
\sum_{x\ne0}\chi(x)\psi(xy)=\chi(y)^{-1}\sum_{z\ne0}\chi(z)\psi(z)=\chi(y)^{-1}\,G(\chi,\psi),
$$

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

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

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

$$
\langle 0|F_\psi|\chi\rangle=\frac{1}{\sqrt{q(q-1)}}\sum_{x\ne0}\chi(x)=0,
$$

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

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

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

即

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

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

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

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

(eigenization-inverse-permutation)=
## 7. 逆元置换与本征化

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

定义计算基上的可逆置换

$$
J|x\rangle=|x^{-1}\rangle\quad(x\ne0),\qquad J|0\rangle=|0\rangle,
$$

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

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

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

$$
J|\chi^{-1}\rangle=\frac{1}{\sqrt{q-1}}\sum_{x\ne0}\chi(x)^{-1}\,|x^{-1}\rangle
=\frac{1}{\sqrt{q-1}}\sum_{w\ne0}\chi(w^{-1})^{-1}\,|w\rangle
=\frac{1}{\sqrt{q-1}}\sum_{w\ne0}\chi(w)\,|w\rangle=|\chi\rangle,
$$

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

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

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

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

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

(phase-estimation-complexity)=
## 8. 相位估计与复杂度分析

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

逐项算总账：

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

合起来，总门数为

$$
O\!\left(\frac{1}{\epsilon}\cdot\operatorname{poly}(\log q)\right).
$$

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

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

(quadratic-gauss-sum-example)=
## 9. 手算例子：$\mathbb F_5$ 的二次 Gauss 和

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

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

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

$$
1^2=1,\quad 2^2=4,\quad 3^2=9\equiv4,\quad 4^2=16\equiv1\pmod 5,
$$

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

$$
\chi(1)=1,\quad\chi(2)=-1,\quad\chi(3)=-1,\quad\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 i x/5}$），有

$$
\psi(1)+\psi(4)=2\operatorname{Re}\psi(1)=2\cos\frac{2\pi}{5},\qquad
\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.
$$

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

$$
4c^3-3c=2c^2-1\quad\Longleftrightarrow\quad 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=\cos72^\circ\ne1$，$c$ 满足

$$
4c^2+2c-1=0\quad\Longrightarrow\quad c=\frac{-2\pm\sqrt{4+16}}{8}=\frac{-1\pm\sqrt5}{4}.
$$

$\cos72^\circ>0$，取正根：

$$
\cos\frac{2\pi}{5}=\frac{\sqrt5-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{\sqrt5-1}{2}}{2}=-\frac{\sqrt5+1}{4}.
$$

### 9.3 代回并与定理对照

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

结果：$G=\sqrt5$ 是正实数，故

$$
e^{i\gamma}=\frac{G}{\sqrt5}=1,\qquad\gamma=0.
$$

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

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

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

### 10.1 加速的来源

把两条路线并排看：

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

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

### 10.2 平凡特征与退化情形

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

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

## 练习题

**练习 1【Gauss 和与相位估计问题】**（→ [1.1 节](#gauss-sum-problem)）

1. 写出 Gauss 和 $G(\chi,\psi)$ 的定义，指出求和范围、项数，并说明为什么每一项 $\chi(x)\psi(x)$ 都是模长 $1$ 的复数。
2. 解释"各项相位随机无关时模长约为 $\sqrt q$"的随机行走直觉与"模长恰好等于 $\sqrt q$"的严格结论之间的差别，并说明为什么估计问题的难点在相位而不在模长。

> 提示：相位由 $q-1$ 个单位复数之间精细的相消干涉决定，任何一项算错都会污染结果。

**练习 2【两类特征与正交关系】**（→ [第 2 节](#characters-orthogonality)）

1. 对 $q=5$、$a=1$：写出加法特征 $\psi_1(x)=e^{2\pi ix/5}$ 在 $x=0,1,2,3,4$ 处的取值，并验证 $\sum_{x\in\mathbb F_5}\psi_1(x)=0$。
2. 证明非平凡乘法特征满足 $\sum_{x\ne0}\chi(x)=0$（Lemma 2），并指出证明中"非平凡"用在哪一步。

> 提示：把 $x$ 写成 $g^j$ 化为等比级数，"非平凡"保证公比 $e^{2\pi is/(q-1)}\ne1$。

**练习 3【Gauss 和的模长定理】**（→ [3.1 节](#gauss-sum-modulus)）

1. 计算两种退化情形的 Gauss 和：$\chi$ 平凡、$\psi$ 非平凡时 $G=-1$；$\chi$ 非平凡、$\psi$ 平凡时 $G=0$（验证第 3.1 节给出的值）。
2. 补全 Theorem 3 证明的最后一步：由 $|G|^2=(q-1)-\sum_{t\ne0,t\ne1}\chi(t)$ 出发，用 Lemma 2 证明 $\sum_{t\ne0,t\ne1}\chi(t)=-1$，从而得到 $|G|^2=q$。

> 提示：从 $\sum_{t\ne0}\chi(t)=0$ 中减去 $t=1$ 的一项 $\chi(1)=1$。

**练习 4【特征态的制备】**（→ [第 5 节](#character-state-preparation)）

1. 写出特征态 $|\chi_s\rangle$ 的表达式并验证其归一化，再按顺序列出制备它的四个步骤及每步得到的态。
2. 第一步需要在 $q-1$（一般不是 $2$ 的幂）个基矢上做均匀叠加：解释"先在 $2^{\lceil\log_2(q-1)\rceil}$ 个基矢上叠加、再测量比较标志位"的单次成功概率为何 $\ge\frac12$，并说明期望重复次数为 $O(1)$。

> 提示：比较 $2^{\lceil\log_2(q-1)\rceil}$ 与 $2(q-1)$ 的大小，用成功概率的倒数估计期望次数。

**练习 5【加法 QFT 与关键恒等式】**（→ [第 6 节](#fourier-key-identity)）

1. 写出 $F_\psi|x\rangle$ 的定义式，并验证当 $x_1\ne x_2$ 时两个不同列的内积为零（即 $F_\psi$ 酉）。
2. 补全第 6.2 节换元 $z=xy$ 的全部细节：说明为什么 $x$ 遍历 $\mathbb F_q^\times$ 时 $z$ 也恰好遍历 $\mathbb F_q^\times$，并逐步验证系数中出现的是 $\chi(y)^{-1}$ 而不是 $\chi(y)$。
3. 第 6 节末尾指出，$F_\psi$ 的酉性"要求"$|G(\chi,\psi)|=\sqrt q$。把这句话写成一个严格的论证：假设第 6.2 节恒等式成立，由 $\|F_\psi|\chi\rangle\|=1$ 推出 $|G|=\sqrt q$，并说明这与 Theorem 3 的证明互为印证而非循环论证。

> 提示：对 $F_\psi|\chi\rangle=\frac{G}{\sqrt q}|\chi^{-1}\rangle$ 两边取范数，并利用 $|\chi^{-1}\rangle$ 已归一化。

**练习 6【逆元置换与本征化】**（→ [第 7 节](#eigenization-inverse-permutation)）

1. 写出 $J$ 的定义，说明 $J$ 是计算基上的置换从而是酉算子，并解释单独约定 $J|0\rangle=|0\rangle$ 的必要性。
2. 说明为什么只测量 $F_\psi|\chi\rangle$ 的计算基分布看不到 $\gamma$，而受控相位估计可以。
3. 对二次特征（$\chi^2=\chi_0$、$\chi$ 非平凡），证明 $|\chi\rangle$ 本身就是 $F_\psi$ 的本征态，并说明此时第 7 节的逆元置换 $J$ 可以省略；这与第 9 节 $\mathbb F_5$ 例子的哪一步对应？

> 提示：分别写出计算基测量概率 $\big|\frac{G}{\sqrt{q(q-1)}}\chi(y)^{-1}\big|^2=\frac{1}{q-1}$ 与 $U$ 的本征方程；二次特征满足 $\chi=\chi^{-1}$。

**练习 7【相位估计与复杂度分析】**（→ [第 8 节](#phase-estimation-complexity)）

1. 列出总门数账本的三项（受控 $U$ 调用次数、单次受控 $U$ 的成本、本征态制备），并写出总门数 $O\big(\frac{1}{\epsilon}\cdot\operatorname{poly}(\log q)\big)$。
2. 解释为什么 $t=O(\log\frac1\epsilon)$ 个辅助比特导致受控 $U$ 的调用次数为 $\sum_{k=0}^{t-1}2^k=O(\frac1\epsilon)$；若有人把复杂度误写成 $O(\log\frac1\epsilon\cdot\operatorname{poly}(\log q))$，指出错在哪里。

> 提示：把 $\epsilon$ 取成 $2^{-n}$，比较两种表达式随 $n$ 的增长速度。

**练习 8【手算二次 Gauss 和】**（→ [第 9 节](#quadratic-gauss-sum-example)）

1. 对 $\mathbb F_5$ 列出二次剩余集合与 $\chi$ 的取值，并按定义把 $G=\psi(1)-\psi(2)-\psi(3)+\psi(4)$ 用配对技巧化简为 $2\cos\frac{2\pi}{5}-2\cos\frac{4\pi}{5}$。
2. 对 $\mathbb F_3$ 计算二次 Gauss 和（取 $\psi(x)=e^{2\pi i x/3}$），验证结果为 $i\sqrt3$，即归一化相位为 $i$；对照第 9 节 $p=5$ 的情形，说明 $p\bmod 4$ 如何影响相位。

> 提示：$\psi(5-x)=\overline{\psi(x)}$ 的配对在 $\mathbb F_3$ 上是 $\psi(3-x)=\overline{\psi(x)}$，即 $G=\psi(1)-\overline{\psi(1)}=2i\operatorname{Im}\psi(1)$。

## 参考文献

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