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

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

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

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

本课知识点

  1. Gauss 和与相位估计问题——能写出 Gauss 和 \(G(\chi,\psi)\) 的定义，解释"模长已知为 \(\sqrt q\)、相位 \(\gamma\) 未知"的分解，并比较经典 \(O(q\cdot\operatorname{poly}(\log q))\) 与量子 \(\operatorname{poly}(\log q,1/\epsilon)\) 两类成本。

  2. 两类特征与正交关系——能由域迹定义加法特征 \(\psi_a\)、用生成元参数化乘法特征 \(\chi_s\)，并证明非平凡特征的加法与乘法两条正交关系。

  3. Gauss 和的模长定理——能用模方展开、换元 \(x=ty\) 与两条正交关系推导 \(|G(\chi,\psi)|=\sqrt q\)，并计算平凡特征组合下的退化值 \(-1\) 与 \(0\)。

  4. 特征态的制备——能按"均匀叠加—可逆指数—相位写入—离散对数清除"四步构造特征态 \(|\chi\rangle\)，并说明每步成本为 \(\operatorname{poly}(\log q)\)。

  5. 加法 QFT 与关键恒等式——能验证 \(F_\psi\) 的酉性，逐振幅推导 \(F_\psi|\chi\rangle=\frac{G(\chi,\psi)}{\sqrt q}\,|\chi^{-1}\rangle\)，并解释 \(|0\rangle\) 分量为零的原因。

  6. 逆元置换与本征化——能证明 \(J|\chi^{-1}\rangle=|\chi\rangle\)，把 \(U=JF_\psi\) 的本征值与归一化 Gauss 和对应起来，并解释直接测量计算基为何读不到相位。

  7. 相位估计与复杂度分析——能核算读出 \(\gamma\) 的总成本 \(O\big(\frac{1}{\epsilon}\cdot\operatorname{poly}(\log q)\big)\)，区分对 \(\log q\) 与对精度 \(\epsilon\) 的依赖，并说出结论的适用边界。

  8. 手算二次 Gauss 和——能对 \(\mathbb F_5\) 与 \(\mathbb F_3\) 手算二次 Gauss 和，得到 \(\gamma=0\) 与 \(\gamma=\pi/2\)，并归纳相位随 \(p\bmod 4\) 的符号规律。

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\) 估计到加性误差 \(\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\) 的代价——这两个保留条件贯穿全课。

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 和：定义、模长与经典瓶颈

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\) 求和：

\[\begin{split} |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). \end{split}\]

由 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 和）变成相位。

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 算法中求阶子程序相同，作用在 \(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 节做总账时会用到。

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\)，数论定理保证这一点。

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\) 无关——相位信息在干涉中，而不在概率分布里。本征相位必须通过相位估计这类干涉测量才能读出。

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

现在直接对酉算子 \(U\) 和本征态 \(|\chi\rangle\) 做相位估计：制备 \(|\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\) 限制。

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 节）

  1. 写出 Gauss 和 \(G(\chi,\psi)\) 的定义，指出求和范围、项数，并说明为什么每一项 \(\chi(x)\psi(x)\) 都是模长 \(1\) 的复数。

  2. 解释"各项相位随机无关时模长约为 \(\sqrt q\)"的随机行走直觉与"模长恰好等于 \(\sqrt q\)"的严格结论之间的差别，并说明为什么估计问题的难点在相位而不在模长。

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

练习 2【两类特征与正交关系】（→ 第 2 节）

  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 节）

  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 节）

  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 节）

  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 节）

  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 节）

  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 节）

  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)\)。

参考文献