权枚举式量子算法：线性码、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 和算法以 \(\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。

参考文献