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{split} \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} \end{split}\]

其中第二步令 \(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\) 做相位估计，即可得到 \(\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\)，而受控相位估计可以。

参考文献