# 权枚举式量子算法：线性码、Quadratic Signs 与 Ising 高温展开

线性码的 weight enumerator 统计每种 Hamming weight 有多少码字。它连接编码性能、Tutte/Ising 配分函数与量子电路路径和。一般精确系数计算困难；量子算法可估计带二次相位的 signed enumerator 的归一化值，某些 cyclic code 又因 Gauss sums 与整性而可恢复 exact 结果。

## 1. 普通权枚举式

二元线性码

$$
C=\{uG:u\in\mathbb F_2^k\}
\subseteq\mathbb F_2^n
$$

的二变量 weight enumerator 为

$$
W_C(x,y)=
\sum_{c\in C}x^{n-|c|}y^{|c|}
=\sum_{w=0}^nA_wx^{n-w}y^w,
$$

$A_w$ 是 weight-$w$ 码字数。它包含 minimum distance（最小 $w>0$ 且 $A_w>0$）以及误码分析所需谱。

例：长度 3 repetition code

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

有

$$
W_C(x,y)=x^3+y^3.
$$

精确列举需 $2^k$ 码字；输出虽只有 $n+1$ 个系数，每个系数的计数仍可 #P-hard。

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

对偶码

$$
C^\perp=\{z:z\cdot c=0, \forall c\in C\}
$$

满足

$$
W_{C^\perp}(x,y)
=\frac1{|C|}W_C(x+y,x-y).
$$

证明在 $\mathbb F_2^n$ 上插入 character orthogonality：

$$
1[z\in C^\perp]
=\frac1{|C|}\sum_{c\in C}(-1)^{z\cdot c},
$$

再逐坐标求和。这个恒等式显示 weight enumerator 本质上是 Hamming scheme 中的 Fourier/Krawtchouk 变换，也解释量子相位干涉为何自然出现。

## 3. Quadratically Signed Weight Enumerator

量子电路不只产生正计数，还产生相消相长。一个常见 QSWE 形式是

$$
S(A,Q;x,y)=
\sum_{b\in\mathbb F_2^m:\,Ab=0}
(-1)^{Q(b)}x^{m-|b|}y^{|b|},
$$

其中 $A$ 给线性约束，$Q(b)$ 是二次 Boolean form（具体文献约定可把线性项/三角矩阵并入 $Q$）。普通 enumerator 是 $Q=0$ 的特例；二次符号允许指数项强烈抵消。

Knill--Laflamme 证明某些 promise-normalized QSWE 估计与量子计算多项式等价：

- 受约束版本可由 one-bit/量子电路高效估计；
- 合适参数下是 canonical BQP-complete 问题；
- 放宽 promise 的版本可能比 BQP 更强，不能一概而论。

## 4. 从量子电路展开得到 QSWE

把量子电路写成 Hadamard、CNOT、phase/controlled-phase 与单比特旋转。每个 Hadamard 插入中间 bit 的求和：

$$
\langle z|H|x\rangle
=2^{-1/2}(-1)^{xz}.
$$

CNOT 等可逆线性门给路径 bits 的线性约束

$$
Ab=0\pmod2.
$$

Controlled-$Z$ 与 phase 门累积

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

旋转矩阵元按选择的路径 bit 贡献 $x$ 或 $y$。所以某个电路振幅形如

$$
\langle0|U|0\rangle
=\mathcal N^{-1}S(A,Q;x,y),
$$

归一化 $\mathcal N$ 是 Hadamard 数与门尺度的已知乘积。Hadamard test 估计左侧，就估计 QSWE 的加性归一化值。

BQP-hardness 的反向归约正是把任意电路编成 $(A,Q,x,y)$；因此“signed weight enumerator”并非只是编码计数，而是量子路径积分的离散形式。

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

无外场 Ising model：

$$
Z=\sum_{\sigma_v=\pm1}
\prod_{e=(u,v)}e^{K_e\sigma_u\sigma_v}.
$$

用

$$
e^{K\sigma_u\sigma_v}
=\cosh K\,(1+\sigma_u\sigma_v\tanh K)
$$

展开边子集。对顶点 spins 求和后，只有每个顶点 incident 选边数为偶数的 $A\subseteq E$ 保留：

$$
Z=2^{|V|}
\prod_e\cosh K_e
\sum_{A:\,\partial A=0}
\prod_{e\in A}\tanh K_e.
$$

$\partial A=0$ 是 incidence matrix mod 2 的 kernel，即图的 cycle code。均匀耦合时最后一项正是该码的单变量 weight enumerator 在 $z=\tanh K$ 的取值。复耦合可引入 quadratic signs，连接 QSWE 与量子电路振幅。

## 6. Irreducible cyclic codes 与 Gauss sums

Cyclic code 可用有限域 trace 表示码字。某些 irreducible cyclic code 的码字 weight 由 multiplicative character sums 决定：

$$
w(c_a)=\text{已知主项}
+\sum_\chi c_\chi G(\chi,\psi_a).
$$

[Gauss 和算法](../ch09-algebra-number-theory/gauss-sums.md)以 $\operatorname{poly}(\log q,1/\epsilon)$ 资源估计归一化相位。若可能 weight 间隔为整数且误差小于 $1/2$，可舍入恢复 weight，再统计少量 orbit/character 类型获得完整 enumerator。

Geraci--Lidar 利用 cycle-code graph 的 Potts partition function 与该 enumerator 的已知变换，得到高度结构化 graph family 的 exact/高精度结果。限制在“irreducible cyclic、特定参数、可控 weight 类型”不可省略。

## 7. 误差与复杂度边界

Hadamard test 给

$$
S/\mathcal N
$$

的加性误差。若 $|S|\ll\mathcal N$，相对误差可能毫无信息。Exact 系数只有在额外整性、间隔与足够精度使舍入可行时得到。

普通 weight enumerator、QSWE、Ising partition function 虽相互归约，但参数可能变成复数、归一化可能指数放大；不能从某一可解点推出所有物理温度都易算。

## 8. 小结与习题

- Weight enumerator 是码字 Hamming weight 的生成函数，MacWilliams identity 是 finite Fourier transform。
- 量子路径的二次相位产生 QSWE，归一化估计可 BQP-complete。
- Ising 高温展开只保留偶子图，即 cycle code。
- 特殊 cyclic code 用 Gauss sums 与整性可恢复精确 weight/partition values。

1. 验证 repetition code 与其对偶的 MacWilliams identity。
2. 从 Ising 边因子展开证明奇度子图项相消。
3. 对两 qubit CZ--Hadamard 电路写出路径 bits 的 quadratic phase。
4. 解释加性归一化误差何时可通过整数舍入变成 exact。

## 参考文献

- Zoo 编号 65：Knill 与 Laflamme, [Quantum Computation and Quadratically Signed Weight Enumerators](https://arxiv.org/abs/quant-ph/9909094).
- Zoo 编号 45--46：Geraci 及 Geraci--Van Bussel 的 Ising/cyclic-code enumerator 工作。
- Zoo 编号 67：Lidar 关于 Ising spin-glass partition function 与 knot invariants 的复杂度联系。