权枚举式量子算法

线性码的权枚举式 (weight enumerator) 统计每种 Hamming 重量有多少个码字。它是编码理论中最基本的生成函数：最小距离、错误概率、码的等价性判据都要从它读出。出人意料的是，同一个数学对象还出现在另外两处看似无关的地方：一是统计物理——Ising 模型的高温展开恰好是图上某个线性码（cycle code）的权枚举式；二是量子计算——量子线路振幅按”路径”展开后，自然写成一个带二次符号的权枚举式 (quadratically signed weight enumerator, QSWE)。

本词条要回答的问题是：量子计算机能为”计算权枚举式”做什么、不能做什么。先把结论摆在这里：

• 精确计算一般系数的权枚举式是 $\#\mathsf{P}$-hard 的，量子计算机也不被认为能普遍做到；
• 量子算法可以高效估计归一化后的 QSWE 数值（加性误差），Knill 与 Laflamme 证明这类问题在合适的 promise 下恰是 BQP-complete 的——也就是说，它不多不少正好刻画了量子计算的能力；
• 对一类特殊结构（irreducible cyclic code），借助 Gauss 和算法 与重量的整性（可能取值之间有整数间隔），可以把加性估计”舍入”成精确值，进而恢复完整的枚举式。

这三条结论放在一起，恰好展示了本词条反复强调的图景：一个 $\#\mathsf{P}$-hard 的精确量，其归一化版本可以是量子计算机的”本职”，而精确版本只有在额外的代数结构（整性、间隔、对称性）在场时才能被量子算法触及。

历史脉络。经典一侧，MacWilliams 在 1963 年证明了联系码与其对偶码权枚举式的恒等式，它是编码论的基石之一，本词条第 2 节会看到它本质上是有限群 ${\mathbb{F}}_2^n$ 上的一次 Fourier 变换；Ising 模型配分函数的高温展开（只保留偶度子图）则是统计物理中更古老的技巧。量子一侧，Knill 与 Laflamme（arXiv:quant-ph/9909094，Zoo 编号 65）提出 QSWE 并证明其归一化估计与量子计算多项式等价；Lidar（Zoo 编号 67）讨论了 Ising spin-glass 配分函数与纽结不变量的计算复杂度联系；Geraci 以及 Geraci–Van Bussel（Zoo 编号 45–46）发展了 Ising/cyclic-code 枚举式的量子求值工作，其中 Geraci–Lidar 利用 cycle-code 图上 Potts 配分函数与枚举式的已知变换，得到一类高度结构化图族的精确/高精度结果。本词条的组织顺序是：先定义普通权枚举式（第 1 节），证明 MacWilliams 恒等式（第 2 节），引入 QSWE 并陈述 Knill–Laflamme 定理（第 3 节），推导”量子线路振幅 = 归一化 QSWE”（第 4 节），推导 Ising 高温展开（第 5 节），讲 cyclic code 与 Gauss sums 的精确化路线（第 6 节），最后讨论误差与复杂度边界（第 7 节）。

预备知识。本词条默认读者熟悉前面的词条的内容：量子态与测量、Hadamard 门与常用门（）、振幅放大与振幅估计（）、量子线路模型与 BQP（）。用到这些工具的步骤我们会复述结论，但不重新推导。编码理论与有限域的基本概念则在用到时现场定义。

1. 普通权枚举式

定义 1（二元线性码）。设 $G$ 是一个 $k\times n$、秩为 $k$ 的 ${\mathbb{F}}_2$ 矩阵（称为生成矩阵 (generator matrix)）。由 $G$ 生成的二元线性码 (binary linear code) 是行空间

$C=\{uG:u\in {\mathbb{F}}_2^k\}\subseteq {\mathbb{F}}_2^n.$

$n$ 称为码长，$k$ 称为维数，$C$ 中的元素称为码字 (codeword)。注意 $C$ 恰好含 $|C|=2^k$ 个码字：映射 $u\mapsto uG$ 是单射，因为 $G$ 行满秩（若 $uG=0$ 而 $u\ne 0$，则 $G$ 的行线性相关，矛盾）。

定义 2（Hamming 重量与权枚举式）。码字 $c=(c_1,\dots ,c_n)$ 的 Hamming 重量是它非零分量的个数：

$|c|=\#\{i:c_i=1\}.$

码 $C$ 的二变量权枚举式是生成函数

$W_C(x,y)={\sum }_{c\in C}{x}^{n-|c|}{y}^{|c|}={\sum }_{w=0}^n{A}_w{x}^{n-w}{y}^w,$

其中

$A_w=\#\{c\in C:|c|=w\}$

是重量恰好为 $w$ 的码字数。第二个等号只是把求和按重量归类：每个重量-$w$ 码字贡献单项式 $x^{n-w}{y}^w$，同类合并后系数就是 $A_w$。

权枚举式编码了码的全部重量谱 (weight spectrum) $\{A_w\}$。最重要的两个用途：

• 最小距离。线性码的最小距离 (minimum distance) $d=\min \{|c|:c\in C,c\ne 0\}$，即最小的 $w>0$ 使得 $A_w>0$。它决定码的纠错能力（能纠正 $\lfloor (d-1)/2\rfloor$ 个错误），而从 $W_C$ 中读 $d$ 只需要看最低次的非平凡项。
• 误码分析。在二元对称信道上，“未检出错误”的概率等量可以写成 $W_C$ 在信道参数处的取值，因此完整的谱（而不仅是 $d$）进入性能分析。

例 1（长度 3 的 repetition code）。取生成矩阵 $G=(111)$（$k=1$），则

$C=\{000,111\}.$

两个码字的重量分别为 $0$ 和 $3$，所以 $A_0=1$、$A_3=1$、其余 $A_w=0$：

$W_C(x,y)=x^{3-0}{y}^0+x^{3-3}{y}^3=x^3+y^3.$

最小距离 $d=3$，能纠正 $1$ 个错误——这正是”重复三遍取多数”的直觉。

经典计算的瓶颈。按定义直接列举需要枚举全部 $2^k$ 个码字：当码率 $k/n$ 为常数时，这是输入规模（矩阵 $G$ 的 $kn$ 个比特）的指数。能不能绕开枚举？注意输出其实只有 $n+1$ 个系数 $A_0,\dots ,A_n$，表示规模很小——但这并不带来多项式算法：单个系数的计数问题仍是 $\#\mathsf{P}$-hard 的。粗略地说，“给定重量 $w$，问有多少个重量-$w$ 码字”包含了足够难的组合计数结构，以至于人们普遍认为不存在通用的多项式时间（甚至多项式时间随机）算法，无论经典还是量子。这条复杂度边界是本词条一切”近似 vs 精确”讨论的出发点：我们必须放弃”通用 + 精确”的组合，转而在”归一化数值的加性近似”（第 3–4 节）或”受限码族的精确值”（第 6 节）中寻找量子算法的用武之地。

2. MacWilliams identity 是一次有限群 Fourier 变换

定义 3（对偶码）。码 $C\subseteq {\mathbb{F}}_2^n$ 的对偶码 (dual code) 是

$C^{\perp }=\{z\in {\mathbb{F}}_2^n:z\cdot c=0\text{ 对所有 }c\in C\},$

其中 $z\cdot c={\sum }_i{z}_i{c}_i(\mathrm{mod}2)$ 是 ${\mathbb{F}}_2$ 上的标准内积。若 $C$ 的维数是 $k$，则 $C^{\perp }$ 的维数是 $n-k$（它是线性方程组 $G{z}^T=0$ 的解空间，$G$ 秩 $k$），从而 $|C^{\perp }|=2^{n-k}$ 且 $|C|\cdot |C^{\perp }|=2^n$。

定理 2（MacWilliams identity）。

$W_{C^{\perp }}(x,y)=\frac{1}{|C|}{W}_C(x+y,x-y).$

这个恒等式非常惊人：它说对偶码的整个重量谱由原码的谱线性决定。证明分两步：先把”属于对偶码”这一指示函数写成 ${\mathbb{F}}_2^n$ 上的 Fourier（character）展开，再逐坐标求和。

引理 3（character 正交性 / 对偶码的指示函数）。对任意 $z\in {\mathbb{F}}_2^n$，

$1[z\in C^{\perp }]=\frac{1}{|C|}{\sum }_{c\in C}(-1{)}^{z\cdot c}.$

证明。分两种情形。

情形 1：$z\in C^{\perp }$。此时每个 $c\in C$ 都满足 $z\cdot c=0$，故 $(-1{)}^{z\cdot c}=1$，求和得 $|C|$，除以 $|C|$ 得 $1$，与左端一致。

情形 2：$z\notin C^{\perp }$。此时存在 $c_0\in C$ 使 $z\cdot c_0=1$。映射 $c\mapsto c+c_0$ 是 $C$ 到自身的双射（线性码对加法封闭，且该映射有逆 $c\mapsto c+c_0$ 自身，因为 ${\mathbb{F}}_2$ 中 $c_0+c_0=0$）。于是

${\sum }_{c\in C}(-1{)}^{z\cdot c}={\sum }_{c\in C}(-1{)}^{z\cdot (c+c_0)}=(-1{)}^{z\cdot c_0}{\sum }_{c\in C}(-1{)}^{z\cdot c}=-{\sum }_{c\in C}(-1{)}^{z\cdot c},$

其中第二个等号用了指数加法法则 $(-1{)}^{a+b}=(-1{)}^a(-1{)}^b$。一个数等于自己的相反数，故该和为 $0$，与左端一致。Q.E.D.

引理 3 正是”群 ${\mathbb{F}}_2^n$ 的子群 $C$ 上的 Fourier 反演”：$(-1{)}^{z\cdot c}$ 是加法群 ${\mathbb{F}}_2^n$ 的 character（由 $z$ 指标），而指示函数被展开成 character 的线性组合。

定理 2 的证明。从定义出发，把引理 3 代入：

$W_{C^{\perp }}(x,y)={\sum }_{z\in {\mathbb{F}}_2^n}1[z\in C^{\perp }]x^{n-|z|}{y}^{|z|}=\frac{1}{|C|}{\sum }_{c\in C}{\sum }_{z\in {\mathbb{F}}_2^n}(-1{)}^{z\cdot c}{x}^{n-|z|}{y}^{|z|}.$

关键一步是对内层的 $z$ 求和做逐坐标分解。注意 $x^{n-|z|}{y}^{|z|}={\prod }_{i=1}^n{x}^{1-z_i}{y}^{z_i}$（重量为 $|z|$ 的坐标贡献 $y$，其余 $n-|z|$ 个坐标贡献 $x$），且 $(-1{)}^{z\cdot c}={\prod }_i(-1{)}^{z_i{c}_i}$（因为 $z\cdot c={\sum }_i{z}_i{c}_i\mathrm{mod}2$）。于是内层和是一个”和之积”的完全展开，由分配律可以收回成”积之和”：

${\sum }_{z\in {\mathbb{F}}_2^n}{\prod }_{i=1}^n(-1{)}^{z_i{c}_i}{x}^{1-z_i}{y}^{z_i}={\prod }_{i=1}^n\left({\sum }_{z_i\in \{0,1\}}(-1{)}^{z_i{c}_i}{x}^{1-z_i}{y}^{z_i}\right).$

（把右端的乘积展开：从每个因子中各取一项，取法由 $z=(z_1,\dots ,z_n)$ 的 $2^n$ 种选择穷尽，恰好还原左端。）对单个坐标，$z_i=0$ 的项是 $x$，$z_i=1$ 的项是 $(-1{)}^{c_i}y$，故

${\sum }_{z_i\in \{0,1\}}(-1{)}^{z_i{c}_i}{x}^{1-z_i}{y}^{z_i}=x+(-1{)}^{c_i}y.$

代回：若 $c_i=0$ 该因子为 $x+y$，若 $c_i=1$ 为 $x-y$。$c$ 有 $n-|c|$ 个零分量、$|c|$ 个非零分量，所以

${\prod }_{i=1}^n\left(x+(-1{)}^{c_i}y\right)=(x+y{)}^{n-|c|}(x-y{)}^{|c|}.$

最后对 $c\in C$ 求和：

$W_{C^{\perp }}(x,y)=\frac{1}{|C|}{\sum }_{c\in C}(x+y{)}^{n-|c|}(x-y{)}^{|c|}=\frac{1}{|C|}{W}_C(x+y,x-y).$

Q.E.D.

例 2（repetition code 与其对偶）。长度 3 repetition code $C=\{000,111\}$ 的对偶是偶校验码

$C^{\perp }=\{z:z_1+z_2+z_3=0\}=\{000,011,101,110\},$

其重量谱为 $A_0=1$、$A_2=3$，故 $W_{C^{\perp }}(x,y)=x^3+3x{y}^2$。用定理 2 独立验证：由例 1 的 $W_C=x^3+y^3$ 与 $|C|=2$，

$\frac{1}{2}{W}_C(x+y,x-y)=\frac{1}{2}\left[(x+y{)}^3+(x-y{)}^3\right]=\frac{1}{2}\left[2x^3+6x{y}^2\right]=x^3+3x{y}^2,$

其中展开时奇次交叉项（$x^{2}y$ 与 $x{y}^2$ 中的 $x^{2}y$ 部分）两两抵消：$(x+y{)}^3=x^3+3x^{2}y+3x{y}^2+y^3$，$(x-y{)}^3=x^3-3x^{2}y+3x{y}^2-y^3$，相加后只剩 $2x^3+6x{y}^2$。两边一致。$✓$

为什么这是一次 Fourier 变换？ 把 $W_C(x+y,x-y)$ 按 $y^w$ 展开并比较系数，可以得到 $A_w^{\perp }=\frac{1}{|C|}{\sum }_v{A}_v{K}_w(v)$，其中 $K_w(v)$ 是 Krawtchouk 多项式——它正是 Hamming 方案（${\mathbb{F}}_2^n$ 按重量分层得到的结合方案）中 character 的取值。因此 MacWilliams 恒等式表明：权枚举式本质上是 Hamming scheme 中的 Fourier/Krawtchouk 变换。这个观察对理解量子算法的出现至关重要：Fourier 变换天然由相位干涉实现（读者在 QFT 中已见过同一现象），而权枚举式既然是一次伪装起来的 Fourier 变换，那么”用相位干涉去估计与权枚举式有关的量”就不是巧合，而是结构使然。第 3–4 节会把这一点坐实。

3. Quadratically Signed Weight Enumerator

普通权枚举式的每一项都是正整数——它在计数。量子线路则不同：振幅是复数，不同”路径”之间可以相消。为了描述量子线路产生的和式，我们需要允许每项带符号的枚举式。

定义 4（二次符号权枚举式，QSWE）。设 $A$ 是 ${\mathbb{F}}_2$ 上的一个 $r\times m$ 矩阵，$Q:{\mathbb{F}}_2^m\to {\mathbb{F}}_2$ 是一个二次 Boolean 函数，即

$Q(b)={\sum }_{i<j}{q}_{ij}{b}_i{b}_j(\text{部分文献约定还允许并入线性项 }{\sum }_i{\ell }_i{b}_i),$

系数 $q_{ij}\in {\mathbb{F}}_2$（把线性项并入 $Q$ 时还有 ${\ell }_i\in {\mathbb{F}}_2$）。定义

$S(A,Q;x,y)={\sum }_{b\in {\mathbb{F}}_2^m:Ab=0}(-1{)}^{Q(b)}{x}^{m-|b|}{y}^{|b|}.$

与普通权枚举式逐项对照：

• 求和范围 $\{b:Ab=0\}$ 仍是一个线性码（$A$ 的零空间），与普通枚举式中”对所有码字求和”一致；
• 单项式 $x^{m-|b|}{y}^{|b|}$ 的形式完全一样；
• 唯一的区别是系数 $(-1{)}^{Q(b)}$：它依赖码字本身的二次函数值，允许相邻项强烈抵消。普通枚举式正是 $Q=0$（且取 $A$ 为校验矩阵使零空间等于 $C$）的特例。

由于存在抵消，$|S|$ 可以远小于求和项数 $2^{m-\mathrm{rank}(A)}$。这在计数问题中是坏消息（失去了”和 $\ge$ 任一项”之类的估计），但在量子计算中却是常态：量子振幅本来就是大规模相消干涉的结果。量子计算机能高效估计的不是 $S$ 本身，而是归一化值 $S/\mathcal{N}$（$\mathcal{N}$ 是某个已知的大数，例如 $2^{m/2}$ 量级），因为这正是一个量子线路振幅的尺度（$|\text{振幅}|\le 1$）。下一节会推导这个对应。

Knill–Laflamme 定理的内容（arXiv:quant-ph/9909094；此处只陈述结论与定性含义，证明思路见第 4 节末）：

• 高效方向：受约束版本的归一化 QSWE 可以由 one-bit/量子线路高效估计——即存在多项式规模的量子线路，其某个振幅恰好等于 $S/\mathcal{N}$，于是 Hadamard 检验（第 4 节）给出加性估计；
• 困难方向：在合适的参数范围下，promise-normalized QSWE 估计是 BQP-complete 的——任意 BQP 线路都可以被归约为某个 $(A,Q,x,y)$ 实例的估计问题，因此 QSWE 估计恰好（而非仅仅”至多”）刻画了量子多项式时间的能力；
• 保留条款：以上结论都带 promise（对 $|S|/\mathcal{N}$ 的大小或参数范围的承诺）。放宽 promise 的版本可能比 BQP 更强，不能一概而论——BQP-completeness 是对特定规范化问题族的陈述，不是说”一切形如定义 4 的和式都在 BQP 中”。

这三个要点的信息量很大，值得停下来消化。第一、二条合起来说：“归一化 QSWE 估计”这个数值问题就是量子计算的完备问题——这为量子算法研究提供了一种组合学的语言：任何量子线路的能力问题都可以翻译成”带二次符号的枚举式在该参数点有多大”。第三条则是护栏：它提醒我们，把 promise 拿掉之后问题会跳到未知甚至更难的复杂度地带，所以后文凡引用 Knill–Laflamme 结论时，promise 与归一化都不可省略。

4. 从量子线路展开得到 QSWE

本节推导核心对应：一个量子线路的振幅等于一个归一化的 QSWE。这既解释了第 3 节”高效方向”的来源（Hadamard 检验估计振幅），也是”困难方向”归约的骨架（把任意线路编成 $(A,Q,x,y)$）。

4.1 路径展开：逐门分析

取一个由以下门组成的线路：Hadamard $H$、CNOT、受控相位门（CZ、$S=\mathrm{diag}(1,i)$ 之类的相位门）以及一类单比特”旋转”门（其矩阵元取两个符号值 $x,y$，例如 $\left(\begin{array}{cc}x& y\\ y& -x\end{array}\right)$ 型的门）。我们要计算 $⟨0|U|0⟩$（初态、末态都是全零；一般情形同理）。

方法是在每两个门之间插入计算基的完备性关系 $I={\sum }_{b\in \{0,1\}}|b⟩⟨b|$。这样振幅被写成对所有”中间比特串路径”的求和，每条路径的贡献是沿途各门矩阵元的乘积。设路径比特总数为 $m$。逐门看每种门贡献什么：

Hadamard 门。由 $H=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)$，其矩阵元统一写成

$⟨z|H|x⟩=2^{-1/2}(-1{)}^{xz},x,z\in \{0,1\}.$

也就是说，每个 $H$ 给路径和贡献一个因子 $2^{-1/2}$（只与门的个数有关）和一个相位 $(-1{)}^{xz}$——注意 $xz$ 是两个路径比特的二次单项式，它将并入 $Q$。

可逆线性门（CNOT 等）。CNOT 作用为 $|a,b⟩\mapsto |a,a\oplus b⟩$。在路径展开中，CNOT 的矩阵元 $⟨a^{\prime },b^{\prime }|\mathrm{CNOT}|a,b⟩$ 等于 $1$（若 $a^{\prime }=a$ 且 $b^{\prime }=a\oplus b$）否则为 $0$。因此它的效果是不引入求和、只引入约束：路径比特之间必须满足一个 ${\mathbb{F}}_2$ 线性方程。把所有这类约束收集起来，就是定义 4 中的

$Ab=0(\mathrm{mod}2).$

受控相位与相位门。CZ 作用为 $|a,b⟩\mapsto (-1{)}^{ab}|a,b⟩$；单比特相位门（如 $Z$、$S$ 的平方部分）贡献 $(-1{)}^{\ell (b)}$ 之类的线性相位。合起来，路径 $b$ 累积的总相位形如

$(-1{)}^{Q(b)},$

其中 $Q$ 是二次 Boolean 函数：$H$ 的 $xz$ 项、CZ 的 $ab$ 项是二次部分，单比特相位门给出线性部分（按第 3 节的约定可并入 $Q$）。

旋转门。设某个单比特旋转门的矩阵元按”输入比特与输出比特是否相同”分别取值 $x$ 或 $y$（不相同则取 $y$）。那么对一条路径，每个这样的门按该处的路径比特贡献一个 $x$ 或一个 $y$；把整条路径上所有旋转门的贡献收集起来，恰好是按”路径比特中 $1$ 的个数”分类的单项式

$x^{m-|b|}{y}^{|b|}$

（$m$ 个路径比特位置中，$|b|$ 个取 $y$、其余取 $x$；这里为书写简便把旋转门数与路径比特数对齐，一般情形只是多了些已知因子）。

4.2 汇总：振幅 = 归一化 QSWE

把四类因子乘在一起，对所有满足约束的路径求和：

$⟨0|U|0⟩=2^{-h/2}{\sum }_{b:Ab=0}(-1{)}^{Q(b)}{x}^{m-|b|}{y}^{|b|}={\mathcal{N}}^{-1}S(A,Q;x,y),$

其中 $h$ 是 Hadamard 门的个数（每个贡献 $2^{-1/2}$），归一化因子

$\mathcal{N}=2^{h/2}\times (\text{各旋转门与相位门的已知尺度})$

是线路的已知函数——它只数门、不求和，因此可以多项式时间算出来。这就是”量子线路振幅 = 归一化 QSWE”的精确含义：等式左端是物理上可测的量，右端是组合对象在特定参数点的值，两者的桥梁是路径展开。

例 3（两比特 CZ–Hadamard 线路）。取线路

$|00⟩\stackrel{H\otimes H}{\to }\stackrel{\mathrm{CZ}}{\to }\stackrel{H\otimes H}{\to }⟨00|,$

即计算 $⟨00|(H\otimes H)\mathrm{CZ}(H\otimes H)|00⟩$。第一层 $H\otimes H$ 后插入完备基 ${\sum }_{b_1,b_2}|b_1{b}_2⟩⟨b_1{b}_2|$（两个路径比特，$m=2$）：

• 第一层 $H$：$⟨b_1{b}_2|H\otimes H|00⟩=2^{-1}(-1{)}^{0\cdot b_1+0\cdot b_2}=1/2$（每个 $H$ 贡献 $2^{-1/2}$）；
• CZ：贡献 $(-1{)}^{b_1{b}_2}$；
• 第二层 $H$：$⟨00|H\otimes H|b_1{b}_2⟩=2^{-1}(-1{)}^{b_1\cdot 0+b_2\cdot 0}=1/2$。

没有 CNOT，故约束 $Ab=0$ 为空（对所有 $b$ 求和）；没有旋转门，故 $x=y=1$。于是

$⟨00|U|00⟩=\frac{1}{4}{\sum }_{b_1,b_2\in \{0,1\}}(-1{)}^{b_1{b}_2}.$

逐项列出：

$(b_1,b_2)$	$(0,0)$	$(0,1)$	$(1,0)$	$(1,1)$
$(-1{)}^{b_1{b}_2}$	$+1$	$+1$	$+1$	$-1$

求和得 $1+1+1-1=2$，所以振幅 $=2/4=1/2$。按 QSWE 的语言：$A$ 为空、$Q(b)=b_1{b}_2$、$\mathcal{N}=4$、$S=2$、$S/\mathcal{N}=1/2$。注意这里已经出现了抵消：四项中有一项为负。若把 CZ 换成作用三次（或在两比特间再加结构），抵消会更剧烈——$|S|\ll \mathcal{N}$ 正是量子振幅的典型情形。

4.3 用 Hadamard 检验读出 $S/\mathcal{N}$

有了”振幅 $=S/\mathcal{N}$“，剩下的就是标准的振幅读出。读者已学过相关工具，这里只复述结论并对接参数：

• Hadamard 检验：对受控-$U$ 线路作用辅助比特，测量辅助比特得到 $0$ 的概率为 $\frac{1+\mathrm{Re}⟨0|U|0⟩}{2}$。重复采样 $T$ 次、取频率估计，由 Hoeffding 不等式，以高概率把 $\mathrm{Re}⟨0|U|0⟩$ 估计到加性误差 $ϵ$ 需要 $T=O(1/{ϵ}^2)$ 次采样。换一条线路（初态加相位门）同理得到虚部。
• 振幅估计（）：把对精度的依赖从 $O(1/{ϵ}^2)$ 改善到 $O(1/ϵ)$，代价是线路深度乘以 $O(1/ϵ)$。

因此，“估计归一化 QSWE $S/\mathcal{N}$ 到加性误差 $ϵ$“的量子代价是 $\mathrm{poly}(\text{线路规模})\times O(1/{ϵ}^2)$（或振幅估计的 $O(1/ϵ)$）。复杂度的每个因子来源清楚：$\mathrm{poly}(\text{规模})$ 来自实现 $U$ 本身；$1/{ϵ}^2$ 来自采样的统计涨落（标准差 $\sim 1/\sqrt{T}$）；换成 $1/ϵ$ 则来自相位估计的二次加速。

BQP-hardness 的方向是上述展开的逆用：给定任意 BQP 线路，按 4.1 节的规则逐项读出它的 $(A,Q,x,y)$ 与 $\mathcal{N}$（这本身是多项式时间的经典计算），则该线路的接受概率由 $S(A,Q;x,y)/\mathcal{N}$ 决定。于是”估计 promise-normalized QSWE”至少和整个 BQP 一样难；结合 4.3 节的高效方向，就得到第 3 节陈述的 BQP-completeness。这也揭示了一个视角：带符号权枚举式并非只是编码计数，而是量子路径积分的离散形式——QSWE 之”难”与量子计算之”难”是同一件事。

5. Ising 配分函数是 cycle-code enumerator

本节做第三个对应：经典 Ising 模型的配分函数，经过高温展开，恰好是图的 cycle code 的权枚举式。这把统计物理接进了前面的编码—量子框架。

5.1 高温展开的推导

定义 5（无外场 Ising 模型）。设 $G=(V,E)$ 是有限图，每条边 $e=(u,v)$ 带耦合常数 $K_e$（物理上 $K_e=\beta J_e$，即耦合强度乘逆温度）。每个顶点 $v$ 上有一个自旋 ${\sigma }_v\in \{+1,-1\}$。配分函数是对全部 $2^{|V|}$ 种自旋构型的求和：

$Z={\sum }_{\sigma \in \{\pm 1{\}}^V}{\prod }_{e=(u,v)}{e}^{K_e{\sigma }_u{\sigma }_v}.$

引理 6（边因子的线性化）。对 $s\in \{+1,-1\}$，

$e^{Ks}=\cosh K(1+s\tanh K).$

证明。分别验证 $s$ 的两个取值。$s=+1$：右端 $=\cosh K(1+\tanh K)=\cosh K+\sinh K=e^K$（用 $\tanh K=\sinh K/\cosh K$ 与 $e^K=\cosh K+\sinh K$）。$s=-1$：右端 $=\cosh K-\sinh K=e^{-K}$。两端在两个取值上都相等，恒等式成立。Q.E.D.

引理 6 的价值在于：它把指数函数写成了 $s$ 的一次多项式，于是 $n$ 个自旋的乘积展开变成有限的多项式代数。

定理 7（高温展开）。

$Z=2^{|V|}\left({\prod }_e\cosh K_e\right){\sum }_{A\subseteq E:\partial A=0}{\prod }_{e\in A}\tanh K_e,$

其中 $\partial A=0$ 表示：$A$ 中每个顶点的关联边数为偶数（这样的 $A$ 称为偶子图 (even subgraph) 或 Eulerian 子图）。

证明。把引理 6 代入 $Z$ 的每条边：

$Z=\left({\prod }_e\cosh K_e\right){\sum }_{\sigma }{\prod }_{e=(u,v)}\left(1+{\sigma }_u{\sigma }_v\tanh K_e\right).$

把 ${\prod }_e(1+{\sigma }_u{\sigma }_v\tanh K_e)$ 展开：对每条边选择”取 $1$“或”取 ${\sigma }_u{\sigma }_v\tanh K_e$“。选择方案由边子集 $A\subseteq E$（选了第二项的边）穷尽，故

${\prod }_{e=(u,v)}\left(1+{\sigma }_u{\sigma }_v\tanh K_e\right)={\sum }_{A\subseteq E}\left({\prod }_{e\in A}\tanh K_e\right){\prod }_{e=(u,v)\in A}{\sigma }_u{\sigma }_v.$

现在对自旋求和。注意 ${\prod }_{e=(u,v)\in A}{\sigma }_u{\sigma }_v={\prod }_v{\sigma }_v^{d_A(v)}$，其中 $d_A(v)$ 是 $A$ 中与 $v$ 关联的边数（每条含 $v$ 的边贡献一个 ${\sigma }_v$ 因子）。由于 ${\sigma }_v=\pm 1$，

${\sigma }_v^{d_A(v)}=\{\begin{array}{ll}1,& d_A(v)\text{ 偶},\\ {\sigma }_v,& d_A(v)\text{ 奇}.\end{array}$

而 ${\sum }_{{\sigma }_v=\pm 1}{\sigma }_v=0$、${\sum }_{{\sigma }_v=\pm 1}1=2$。各顶点求和独立，故

${\sum }_{\sigma \in \{\pm 1{\}}^V}{\prod }_v{\sigma }_v^{d_A(v)}={\prod }_v\left({\sum }_{{\sigma }_v}{\sigma }_v^{d_A(v)}\right)=\{\begin{array}{ll}{2}^{|V|},& \text{所有 }v\text{ 满足 }{d}_A(v)\text{ 偶},\\ 0,& \text{否则}.\end{array}$

也就是说，凡含奇度顶点的子图 $A$ 贡献恰好相消（这正是”干涉”在经典统计物理中的化身），只有偶子图幸存。代回即得定理。Q.E.D.

“高温展开”的名字来自参数尺度：$K=\beta J$ 小（高温）时 $\tanh K\approx K$ 也小，幸存项按边数 $|A|$ 逐级压低，展开自然按 $\tanh K$ 的幂组织。

5.2 偶子图 = cycle code 的码字

把边子集 $A$ 用它的指示向量 $b\in {\mathbb{F}}_2^{|E|}$ 表示（$b_e=1\iff e\in A$）。图的关联矩阵 (incidence matrix) $M$ 是一个 $|V|\times |E|$ 的 ${\mathbb{F}}_2$ 矩阵，$(M{)}_{v,e}=1$ 当且仅当 $v$ 是 $e$ 的端点。则

$(Mb{)}_v={\sum }_{e\ni v}{b}_e(\mathrm{mod}2)=d_A(v)\mathrm{mod}2.$

因此条件”$\partial A=0$（每个顶点度数为偶）“恰好是线性方程组 $Mb=0$。偶子图全体构成 ${\mathbb{F}}_2^{|E|}$ 的一个线性子空间——图的 cycle code（也叫环空间 cycle space，因为它的基可以取为基本回路）。于是定理 7 的最后一项就是”对 cycle code 的码字 $b$ 求和、每项权重 ${\prod }_e(\tanh K_e{)}^{b_e}$”。

均匀耦合情形（所有 $K_e=K$）：令 $z=\tanh K$，则 ${\prod }_{e\in A}\tanh K=z^{|A|}=z^{|b|}$，求和只依赖码字的重量：

$Z=2^{|V|}{\cosh }^{|E|}K{\sum }_{b:Mb=0}{z}^{|b|}=2^{|V|}{\cosh }^{|E|}K\cdot W_{\text{cycle}}^{\mathrm{ev}}(z),$

其中 $W_{\text{cycle}}^{\mathrm{ev}}(z)={\sum }_w{A}_w{z}^w$ 是 cycle code 的单变量权枚举式在 $z=\tanh K$ 处的取值。这就完成了对应：计算 Ising 配分函数（均匀耦合）= 求值 cycle code 的权枚举式。

复耦合与二次符号。若允许耦合取复数值（或把模型接到更一般的边上结构上），展开项会获得相位，自然出现带符号乃至带二次相位的和式——这正是 QSWE 的形状。所以”Ising 配分函数—权枚举式—量子线路振幅”三点之间并不是松散的类比，而是有显式归约相连的同一个计算家族。

例 4（三角形上的 Ising 模型）。取 $G=K_3$（三个顶点、三条边的三角形），均匀耦合 $K$。先算 cycle code：偶子图要求每个顶点度数为偶。空集 $\varnothing$ 满足；三条边全取时每个顶点度数为 $2$，满足；取一条或两条边都会产生奇度顶点。故 cycle code $=\{000,111\}\subseteq {\mathbb{F}}_2^3$，恰是长度 3 repetition code！枚举式为 $1+z^3$。定理 7 给出

$Z=2^3{\cosh }^{3}K\left(1+{\tanh }^{3}K\right).$

直接枚举验证：$2^3=8$ 种自旋构型分两类——三自旋全同（$2$ 种）：三个 ${\sigma }_u{\sigma }_v$ 全为 $+1$，贡献 $e^{3K}$；两同一异（$6$ 种）：三个乘积为 $(+1,-1,-1)$ 的某种排列，和为 $-1$，贡献 $e^{-K}$。故 $Z=2e^{3K}+6e^{-K}$。另一方面，

$8{\cosh }^{3}K+8{\sinh }^{3}K=8\cdot \frac{e^{3K}+3e^K+3e^{-K}+e^{-3K}}{8}+8\cdot \frac{e^{3K}-3e^K+3e^{-K}-e^{-3K}}{8}=2e^{3K}+6e^{-K},$

两法一致。$✓$ 这个例子还展示了码的世界与图的世界如何互换：三角形的 cycle code 就是 repetition code，其 MacWilliams 对偶（例 2 的偶校验码）则对应”割”的结构——这正是 Tutte 多项式语言下”圈—割对偶”的影子。

6. Irreducible cyclic codes 与 Gauss sums

第 4–5 节给出的是”归一化数值的加性估计”。本节讲一条不同的路线：对一类带强烈代数结构的码——irreducible cyclic code——可以把量子估计舍入成精确值。这条路线依赖两个成分：码字重量的 Gauss 和表示，以及重量取值的整性间隔。

6.1 Cyclic code 与 trace 表示

定义 8（cyclic code）。码 $C\subseteq {\mathbb{F}}_2^n$ 称为循环码，若它对循环移位封闭：$(c_0,c_1,\dots ,c_{n-1})\in C$ 蕴含 $(c_{n-1},c_0,\dots ,c_{n-2})\in C$。把码字等同于多项式 $c(X)={\sum }_i{c}_i{X}^i\in {\mathbb{F}}_2[X]/(X^n-1)$，循环移位就是乘 $X$，因此循环码恰好是商环 ${\mathbb{F}}_2[X]/(X^n-1)$ 中的理想，由某个生成多项式 $g(X)\mid X^n-1$ 的倍式组成。

Irreducible cyclic code 是其中结构最刚性的一类：其校验多项式在 ${\mathbb{F}}_2$ 上不可约。这类码的码字可以用有限域的 trace 显式写出。设 $q=2^k$，$\xi$ 是 ${\mathbb{F}}_q$ 中的 $n$ 阶元（要求 $n\mid q-1$），$\mathrm{Tr}:{\mathbb{F}}_q\to {\mathbb{F}}_2$ 为迹映射，则（在适当的参数对应下）码字可以指标化为

$c_a=\left(\mathrm{Tr}(a),\mathrm{Tr}(a\xi ),\mathrm{Tr}(a{\xi }^2),\dots ,\mathrm{Tr}(a{\xi }^{n-1})\right),a\in {\mathbb{F}}_q.$

trace 表示的好处是把”第 $i$ 个坐标是否为 $1$“变成一个有限域上的加法特征值：$\mathrm{Tr}(a{\xi }^i)$ 是 ${\mathbb{F}}_2$ 元素，$(-1{)}^{\mathrm{Tr}(a{\xi }^i)}$ 是加法特征（additive character）在 $a{\xi }^i$ 处的取值。

6.2 重量 = 主项 + 乘性特征和

码字 $c_a$ 的重量是取值为 $1$ 的坐标数。用指示函数写法 $|c_a|={\sum }_i\mathrm{Tr}(a{\xi }^i)$ 的实数值，或等价地

$|c_a|=\frac{n}{2}-\frac{1}{2}{\sum }_{i=0}^{n-1}(-1{)}^{\mathrm{Tr}(a{\xi }^i)}$

（每个坐标贡献 $\frac{1-(-1{)}^{\mathrm{Tr}}}{2}\in \{0,1\}$，对 $i$ 求和即重量；展开括号就得到上式）。由于 $n\mid q-1$，指标 $i$ 可以通过离散对数与 ${\mathbb{F}}_q^{\times }$ 的乘性结构挂钩，于是上式右端的加法特征和可以展开为乘性特征 (multiplicative character) 的 Gauss 和的线性组合：

$w(c_a)=(\text{已知主项})+{\sum }_{\chi }{c}_{\chi }G(\chi ,{\psi }_a),$

其中 $\chi$ 跑过若干乘性特征，$G(\chi ,{\psi }_a)$ 是相应的 Gauss 和，系数 $c_{\chi }$ 已知。精确的形状取决于码的参数，但结构性结论是关键：计算重量归结为求值有限域上的 Gauss 和。

6.3 量子求值与整性舍入

这正是 Gauss 和算法 的用武之地：该算法以 $\mathrm{poly}(\log q,1/ϵ)$ 的资源估计 Gauss 和的归一化相位/数值到加性误差 $ϵ$。把它用到上式的每一项上，设共有 $r$ 个特征类型，每项估计误差不超过 $ϵ$，则重量的总误差不超过 $rϵ$（三角不等式：和的误差 $\le$ 误差之和）。

现在整性登场：重量 $w(c_a)$ 是一个整数（事实上对某些码族，可能取值之间还有更大的已知间隔）。只要总误差严格小于间隔的一半——在上述逐特征估计的方案中取

$ϵ=\frac{1}{2r}(\text{间隔为 }1\text{ 时}),$

即 $rϵ=1/2$ 达到临界、再取略小的值留有余量——就可以把实数估计值舍入到最近的整数，得到精确的重量。每个特征估计的代价是 $\mathrm{poly}(\log q,r)$，对 $r$ 个特征求和仍是 $\mathrm{poly}(\log q,r)$；当特征类型数 $r$ 只随参数多项式增长时，整个过程是高效的。最后，cyclic 结构的进一步红利是：码字在乘法群作用下分成少数 orbit/特征类型，同一轨道上的码字重量相同，因此只需对每个类型求一次重量、乘以类型大小，就拼出完整的权枚举式 $\{A_w\}$。

Geraci–Lidar 的图论版本走的是同一条逻辑的另一端：利用 cycle-code 图上的 Potts 配分函数与该枚举式之间的已知变换（Fortuin–Kasteleyn 随机簇表示把 $q$ 态 Potts 配分函数写成边上求和，与第 5 节的高温展开同源），把”结构化图族上的 Potts 求值”翻译成”cyclic code 枚举式求值”，从而对一类高度结构化的图族得到 exact/高精度结果。

保留条款（不可省略）。这条路线的全部结论都限于：irreducible cyclic、特定参数范围、重量类型数可控的码族。去掉其中任何一条——例如换成一般线性码——Gauss 和表示、整性间隔、轨道计数三者至少垮掉一个，“舍入成精确值”的逻辑立即失效。这是第 7 节一般原则的特例。

7. 误差与复杂度边界

本词条出现了三种不同强度的”计算”，把它们并排摆清楚，才能看懂每条量子结论的准确含义。

（a）加性归一化估计（BQP 的本职）。Hadamard 检验（第 4.3 节）给出 $S/\mathcal{N}$ 的加性误差估计：以 $O(1/{ϵ}^2)$ 次采样（或振幅估计 $O(1/ϵ)$ 次受控调用）把 $S/\mathcal{N}$ 定到 $\pm ϵ$。这把任何量子线路振幅——也即任何 promise-normalized QSWE——装进了 BQP。

（b）加性估计何时没有信息量。若真值满足 $|S|\ll \mathcal{N}$（强抵消，量子振幅的典型情形），则固定 $ϵ$ 的加性估计给出的相对误差为

$\frac{ϵ}{|S|/\mathcal{N}}=\frac{ϵ\mathcal{N}}{|S|},$

它可以远大于 $1$，此时估计可能毫无信息（连符号都定不了）。想恢复常数相对误差，需要 $ϵ\sim |S|/\mathcal{N}$，采样数随之涨到 $O((\mathcal{N}/|S|{)}^2)$——若比值指数小，这就是指数代价。这与经典一侧的 $\#\mathsf{P}$-hardness 遥相呼应，并不矛盾：BQP-complete 的是”归一化量本身的加性估计”，而不是”任意有用的相对近似”。

（c）精确系数的条件。只有当额外的整性、间隔与足够精度同时在场，使舍入可行时，加性估计才能升级为 exact 值。第 6 节的方案演示了充要链条：可能取值是整数（间隔 $1$）→ 需要总误差 $<1/2$ → 逐特征误差 $ϵ=\Theta (1/r)$ → 每个 Gauss 和估计代价 $\mathrm{poly}(\log q,r)$。注意这个链条里每一项代价因子的来源都被显式追踪：$r$ 个特征来自乘性特征展开的项数，$1/r$ 来自三角不等式下的误差分配，$\mathrm{poly}(\log q)$ 来自 Gauss 和算法本身。若某码族的 $r$ 超多项式增长，或重量间隔为 $0$（可能取值稠密），链条断裂，exact 化失败。

归约不改变难度。普通权枚举式、QSWE、Ising/Potts 配分函数之间存在显式归约（第 4、5、6 节各建立了一座桥），但归约过程中参数可能变成复数、归一化因子可能指数放大。因此：从”某图族在某温度点可高效求值”推不出”该模型所有物理温度都易算”；从”归一化 QSWE 可估计”也推不出”普通枚举式的系数可近似”。每个可解性结论都绑定它自己的参数点、归一化与 promise——这是使用本词条所有结果时必须核对的清单。

8. 小结与习题

• 权枚举式 $W_C(x,y)={\sum }_w{A}_w{x}^{n-w}{y}^w$ 是码字 Hamming 重量的生成函数，包含最小距离与误码分析所需的整个谱；一般系数的精确计数是 $\#\mathsf{P}$-hard 的。
• MacWilliams 恒等式 $W_{C^{\perp }}(x,y)=\frac{1}{|C|}{W}_C(x+y,x-y)$ 是 ${\mathbb{F}}_2^n$ 上的有限 Fourier 变换（Krawtchouk 变换）——这解释了量子相位干涉为何自然地与权枚举式发生关系。
• 量子线路按路径展开产生二次符号 $(-1{)}^{Q(b)}$：Hadamard 与受控相位门给出二次相位、CNOT 给出线性约束 $Ab=0$、旋转门给出单项式 $x^{m-|b|}{y}^{|b|}$。振幅 $={\mathcal{N}}^{-1}S(A,Q;x,y)$，其归一化估计在合适 promise 下是 BQP-complete 的。
• Ising 配分函数的高温展开只保留偶子图（$\partial A=0$），即图的 cycle code；均匀耦合时 $Z$ 正比于该码枚举式在 $z=\tanh K$ 处的取值。
• 特殊的 irreducible cyclic code 中，码字重量可写成主项加 Gauss 和；Gauss 和算法 估计每一项，重量的整性间隔允许舍入恢复精确重量，少量轨道类型拼出完整枚举式。该路线严格限于特定码族。
• 三条边界：加性估计在 $|S|\ll \mathcal{N}$ 时可以没有信息量；exact 化需要整性 $+$ 间隔 $+$ 精度三者齐备；归约可能引入复参数与指数归一化，可解点不可外推。

习题。

1. （基础）验证引理 6：对 $s=\pm 1$ 分别计算 $\cosh K(1+s\tanh K)$ 并核对等于 $e^{Ks}$。然后仅用”${\sum }_{{\sigma }_v=\pm 1}{\sigma }_v^d=2$（$d$ 偶）或 $0$（$d$ 奇）“这一事实，重新论证高温展开中所有含奇度顶点的子图贡献相消。
2. （基础）长度 $4$ 的偶校验码 $C=\{x\in {\mathbb{F}}_2^4:|x|\text{ 为偶}\}$。先直接数出它的重量谱并写出 $W_C(x,y)$；再求出 $C^{\perp }$，并用 MacWilliams 恒等式独立计算 $W_{C^{\perp }}$，与直接计数的结果核对。（提示：$C^{\perp }$ 是长度 4 的 repetition code。）
3. （中等）把例 3 的线路改为 $H\otimes H\to (S\otimes I)\cdot \mathrm{CZ}\to H\otimes H$，其中 $S=\mathrm{diag}(1,i)$。写出路径比特的完整相位（注意 $S$ 贡献的因子 $i^{b_1}$ 不是 $\pm 1$：说明此时相位落出定义 4 的 $(-1{)}^Q$ 框架，需要把 $Q$ 推广到 ${\mathbb{Z}}_4$ 值的二次形式），并计算振幅 $⟨00|U|00⟩$。
4. （中等）对正方形（4-圈）图 $C_4$ 上的均匀耦合 Ising 模型：(i) 列出 cycle code 的全部码字；(ii) 用定理 7 写出 $Z$ 的封闭表达式；(iii) 对 $\beta \to 0$（$K\to 0$）的极限，验证你的表达式给出 $Z\to 2^{|V|}=16$，并解释这个极限为什么显然。
5. （较难）设某 irreducible cyclic code 的重量展开含 $r$ 个 Gauss 和项，每项系数的模不超过 $c_{\chi }\le B$。若要保证重量的总估计误差严格小于 $1/2$，每个 Gauss 和需要估计到什么精度 $ϵ$？把结论写成 $ϵ$ 关于 $r,B$ 的函数，并说明为什么总代价仍是 $\mathrm{poly}(\log q,r,B)$。（提示：用三角不等式分配误差预算。）
6. （较难，概念题）第 3 节说 promise-normalized QSWE 估计是 BQP-complete 的，第 1 节又说权枚举式系数的精确计数是 $\#\mathsf{P}$-hard 的。这两件事为什么不矛盾？请从”归一化因子 $\mathcal{N}$ 的尺度""promise 的角色”与”加性 vs 相对 vs 精确三种任务的区别”三个角度组织你的回答。

参考文献

• Zoo 编号 65：Knill 与 Laflamme, Quantum Computation and Quadratically Signed Weight Enumerators.
• Zoo 编号 45—46：Geraci 及 Geraci—Van Bussel 的 Ising/cyclic-code enumerator 工作。
• Zoo 编号 67：Lidar 关于 Ising spin-glass partition function 与 knot invariants 的复杂度联系。

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch13-topology-statistical-physics/weight-enumerators
• 内容遵循 CC BY-NC-SA 4.0 许可协议