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

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

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

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

这三条结论放在一起，恰好展示了本章反复强调的图景：一个 $\#\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 门与常用门（ch01）、振幅放大与振幅估计（ch03）、量子线路模型与 BQP（ch01、ch03）。用到这些工具的步骤我们会复述结论，但不重新推导。编码理论与有限域的基本概念则在用到时现场定义。

:::{admonition} 本课知识点
:class: tip

1. **[普通权枚举式与重量谱](#weight-enumerator-spectrum)**——能由生成矩阵写出线性码、Hamming 重量与权枚举式 $W_C(x,y)$，对小码算出重量谱 $\{A_w\}$ 并读出最小距离，说明为何输出虽只有 $n+1$ 个系数、计数仍是 $\#\mathsf{P}$-hard。
2. **[MacWilliams 恒等式](#macwilliams-identity)**——能证明 character 正交性引理并推导 $W_{C^\perp}(x,y)=\frac{1}{|C|}W_C(x+y,\,x-y)$，说明它本质上是 $\mathbb F_2^n$ 上的 Fourier/Krawtchouk 变换。
3. **[QSWE 与 Knill–Laflamme 定理](#qswe-kl-theorem)**——能写出二次符号权枚举式 $S(A,Q;x,y)$ 的定义并比较它与普通权枚举式的异同，准确陈述归一化 QSWE 估计的 BQP-completeness 及其 promise 保留条款。
4. **[量子线路的路径展开](#circuit-path-expansion)**——能对 H、CNOT、受控相位与旋转门逐门写出路径和中的贡献，汇总推导 $\langle 0|U|0\rangle=\mathcal N^{-1}S(A,Q;x,y)$，并对小线路完成数值验证。
5. **[Hadamard 检验读出与 BQP 归约](#hadamard-test-readout)**——能用 Hadamard 检验或振幅估计把 $S/\mathcal N$ 估计到加性误差 $\epsilon$，追踪 $O(1/\epsilon^2)$ 与 $O(1/\epsilon)$ 两个代价因子的来源，并解释 BQP-hardness 归约的方向。
6. **[Ising 高温展开与 cycle code](#ising-cycle-code)**——能推导高温展开（奇度子图相消、偶子图幸存），并用关联矩阵把偶子图等同于 cycle code 的码字，把均匀耦合配分函数写成权枚举式在 $z=\tanh K$ 处的取值。
7. **[Cyclic code、Gauss 和与整性舍入](#gauss-sum-rounding)**——能用 trace 表示把 irreducible cyclic code 的码字重量写成主项加 Gauss 和，并推导"整性间隔 → 误差分配 → 舍入"链条如何把加性估计升级为精确枚举式，同时界定其适用范围。
8. **[误差与复杂度边界](#error-complexity-bounds)**——能比较加性、相对、精确三种估计任务的信息量与代价，解释 $|S|\ll\mathcal N$ 时加性估计为何失效，以及归约为何不可外推可解性。

:::

(weight-enumerator-spectrum)=
## 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 \neq 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 \neq 0\}$，即最小的 $w > 0$ 使得 $A_w > 0$。它决定码的纠错能力（能纠正 $\lfloor (d-1)/2 \rfloor$ 个错误），而从 $W_C$ 中读 $d$ 只需要看最低次的非平凡项。
- **误码分析**。在二元对称信道上，"未检出错误"的概率等量可以写成 $W_C$ 在信道参数处的取值，因此完整的谱（而不仅是 $d$）进入性能分析。

**例 1**（长度 3 的 repetition code）。取生成矩阵 $G = (1\ 1\ 1)$（$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 节）中寻找量子算法的用武之地。

(macwilliams-identity)=
## 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 \pmod 2$ 是 $\mathbb F_2$ 上的标准内积。若 $C$ 的维数是 $k$，则 $C^\perp$ 的维数是 $n - k$（它是线性方程组 $Gz^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$，

$$ \mathbb 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} \mathbb 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 \bmod 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 + 3xy^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 + 6xy^2\right] = x^3 + 3xy^2, $$

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

**为什么这是一次 Fourier 变换？** 把 $W_C(x+y, x-y)$ 按 $y^w$ 展开并比较系数，可以得到 $A^\perp_w = \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 变换天然由**相位干涉**实现（读者在 ch03 的 QFT 中已见过同一现象），而权枚举式既然是一次伪装起来的 Fourier 变换，那么"用相位干涉去估计与权枚举式有关的量"就不是巧合，而是结构使然。第 3–4 节会把这一点坐实。

(qswe-kl-theorem)=
## 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 \quad (\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 与归一化都不可省略。

(circuit-path-expansion)=
## 4. 从量子线路展开得到 QSWE

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

### 4.1 路径展开：逐门分析

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

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

**Hadamard 门**。由 $H = \frac{1}{\sqrt 2}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$，其矩阵元统一写成

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

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

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

$$ Ab = 0 \pmod 2. $$

**受控相位与相位门**。CZ 作用为 $|a, b\rangle \mapsto (-1)^{ab}|a, b\rangle$；单比特相位门（如 $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

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

$$ \langle 0 | U | 0 \rangle = 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\rangle \xrightarrow{H \otimes H} \xrightarrow{\mathrm{CZ}} \xrightarrow{H \otimes H} \langle 00 |, $$

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

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

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

$$ \langle 00 | U | 00 \rangle = \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_1b_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$ 正是量子振幅的典型情形。

(hadamard-test-readout)=
### 4.3 用 Hadamard 检验读出 $S/\mathcal N$

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

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

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

**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 之"难"与量子计算之"难"是同一件事。

(ising-cycle-code)=
## 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{cases} 1, & d_A(v) \text{ 偶}, \\ \sigma_v, & d_A(v) \text{ 奇}. \end{cases} $$

而 $\sum_{\sigma_v = \pm 1} \sigma_v = 0$、$\sum_{\sigma_v = \pm 1} 1 = 2$。各顶点求和独立，故

$$ \sum_{\sigma \in \{\pm1\}^V} \prod_v \sigma_v^{d_A(v)} = \prod_v \left( \sum_{\sigma_v} \sigma_v^{d_A(v)} \right) = \begin{cases} 2^{|V|}, & \text{所有 } v \text{ 满足 } d_A(v) \text{ 偶}, \\ 0, & \text{否则}. \end{cases} $$

也就是说，**凡含奇度顶点的子图 $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 \Leftrightarrow 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 \pmod 2 = d_A(v) \bmod 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^{\mathrm{ev}}_{\text{cycle}}(z), $$

其中 $W^{\mathrm{ev}}_{\text{cycle}}(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}, $$

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

(gauss-sum-rounding)=
## 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), \qquad 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 和算法](../ch09-algebra-number-theory/gauss-sums.md) 的用武之地：该算法以 $\operatorname{poly}(\log q, 1/\epsilon)$ 的资源估计 Gauss 和的**归一化相位/数值**到加性误差 $\epsilon$。把它用到上式的每一项上，设共有 $r$ 个特征类型，每项估计误差不超过 $\epsilon$，则重量的总误差不超过 $r\epsilon$（三角不等式：和的误差 $\le$ 误差之和）。

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

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

即 $r\epsilon = 1/2$ 达到临界、再取略小的值留有余量——就可以把实数估计值**舍入到最近的整数**，得到**精确的**重量。每个特征估计的代价是 $\operatorname{poly}(\log q, r)$，对 $r$ 个特征求和仍是 $\operatorname{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 节一般原则的特例。

(error-complexity-bounds)=
## 7. 误差与复杂度边界

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

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

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

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

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

**（c）精确系数的条件**。只有当额外的**整性、间隔与足够精度**同时在场，使舍入可行时，加性估计才能升级为 exact 值。第 6 节的方案演示了充要链条：可能取值是整数（间隔 $1$）→ 需要总误差 $< 1/2$ → 逐特征误差 $\epsilon = \Theta(1/r)$ → 每个 Gauss 和估计代价 $\operatorname{poly}(\log q, r)$。注意这个链条里**每一项代价因子的来源都被显式追踪**：$r$ 个特征来自乘性特征展开的项数，$1/r$ 来自三角不等式下的误差分配，$\operatorname{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 和算法](../ch09-algebra-number-theory/gauss-sums.md) 估计每一项，重量的整性间隔允许舍入恢复精确重量，少量轨道类型拼出完整枚举式。该路线严格限于特定码族。
- 三条边界：加性估计在 $|S| \ll \mathcal N$ 时可以没有信息量；exact 化需要整性 $+$ 间隔 $+$ 精度三者齐备；归约可能引入复参数与指数归一化，可解点不可外推。

## 练习题

**练习 1【普通权枚举式与重量谱】**（→ [第 1 节](#weight-enumerator-spectrum)）

1. 基础：取生成矩阵 $G=\begin{pmatrix}1&1&0\\0&1&1\end{pmatrix}$（$k=2$、$n=3$），列出全部码字，写出 $W_C(x,y)$ 并读出最小距离 $d$。
2. 进阶：权枚举式的输出只有 $n+1$ 个系数 $A_0,\dots,A_n$。解释为什么"输出规模小"并不给出多项式时间算法，并结合"给定 $w$ 求 $A_w$ 是 $\#\mathsf{P}$-hard"说明"通用 + 精确"的组合为何必须放弃。

> 提示：把"输出不长"与"算出单个输出分量的代价"分开讨论。

**练习 2【MacWilliams 恒等式】**（→ [第 2 节](#macwilliams-identity)）

1. 基础：长度 $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。）
2. 进阶：证明把 MacWilliams 恒等式应用两次恰好复原原式：$W_{(C^\perp)^\perp}(x,y)=W_C(x,y)$。

> 提示：利用 $|C|\cdot|C^\perp|=2^n$，并注意两次代入 $(x,y)\mapsto(x+y,\,x-y)$ 把 $(x,y)$ 变为 $(2x,2y)$，而 $W_C(2x,2y)=2^n W_C(x,y)$。

**练习 3【QSWE 与 Knill–Laflamme 定理】**（→ [第 3 节](#qswe-kl-theorem)）

1. 基础：取 $m=2$、$A$ 为空（无约束）、$Q(b)=b_1b_2$，写出 $S(A,Q;x,y)$ 的四项展开并在 $x=y=1$ 处与例 3 核对；再取 $Q=0$ 对照，指出两者的差别只在系数符号。
2. 进阶：构造一个 $(A,Q)$ 实例，使 $S(1,1)=0$（四项完全抵消），并解释这种抵消为何使"和 $\ge$ 任一项"一类经典下界估计失效、却正是量子振幅的常态。

> 提示：线性项可并入 $Q$，试试 $Q(b)=b_1$。

**练习 4【量子线路的路径展开】**（→ [第 4 节](#circuit-path-expansion)）

1. 基础：把 H、CNOT、受控相位门与旋转门四类门在路径展开中的贡献各写成一个因子，并说明它们分别进入 QSWE 的哪个成分（二次相位 $Q$、约束 $Ab=0$、单项式 $x^{m-|b|}y^{|b|}$、归一化因子 $\mathcal N$）。
2. 进阶：把例 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$ 值的二次形式），并计算振幅 $\langle 00 | U | 00 \rangle$。

> 提示：对固定的 $b_1$，先对 $b_2$ 求和 $1+(-1)^{b_1}$。

**练习 5【Hadamard 检验读出与 BQP 归约】**（→ [4.3 节](#hadamard-test-readout)）

1. 基础：写出 Hadamard 检验中辅助比特测得 $0$ 的概率公式；要把 $\mathrm{Re}\langle 0|U|0\rangle$ 估计到 $\pm 0.01$，按 Hoeffding 不等式需要多少量级的重复采样？
2. 进阶：解释振幅估计如何把精度依赖从 $O(1/\epsilon^2)$ 改善到 $O(1/\epsilon)$、代价是什么；再说明为什么"任意 BQP 线路都能按 4.1 节的规则读出 $(A, Q, x, y)$ 与 $\mathcal N$"给出了 promise-normalized QSWE 估计的 BQP-hardness。

> 提示：线路的接受概率由 $S(A, Q; x, y)/\mathcal N$ 决定。

**练习 6【Ising 高温展开与 cycle code】**（→ [第 5 节](#ising-cycle-code)）

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_4$ 上的均匀耦合 Ising 模型：(i) 列出 cycle code 的全部码字；(ii) 用定理 7 写出 $Z$ 的封闭表达式；(iii) 对 $\beta \to 0$（$K \to 0$）的极限，验证你的表达式给出 $Z \to 2^{|V|} = 16$，并解释这个极限为什么显然。

> 提示：$K\to0$ 时每个边因子 $e^{K\sigma_u\sigma_v}\to1$。

**练习 7【Cyclic code、Gauss 和与整性舍入】**（→ [第 6 节](#gauss-sum-rounding)）

1. 基础：设某 irreducible cyclic code 的重量展开含 $r=5$ 个 Gauss 和项、重量间隔为 $1$。要保证舍入正确，每个 Gauss 和需估计到什么加性误差？总共需要估计多少个 Gauss 和？
2. 进阶：设重量展开含 $r$ 个 Gauss 和项，每项系数的模不超过 $c_\chi \le B$。若要保证重量的总估计误差严格小于 $1/2$，每个 Gauss 和需要估计到什么精度 $\epsilon$？把结论写成 $\epsilon$ 关于 $r, B$ 的函数，并说明为什么总代价仍是 $\operatorname{poly}(\log q, r, B)$。（提示：用三角不等式分配误差预算。）

**练习 8【误差与复杂度边界】**（→ [第 7 节](#error-complexity-bounds)）

1. 基础：设 $|S|/\mathcal N = 10^{-3}$。用加性误差 $\epsilon = 0.1$ 做估计，相对误差是多少？为什么说此时"连符号都定不了"？要恢复常数相对误差，采样数应是什么量级？
2. 进阶：第 3 节说 promise-normalized QSWE 估计是 BQP-complete 的，第 1 节又说权枚举式系数的精确计数是 $\#\mathsf{P}$-hard 的。这两件事为什么不矛盾？请从"归一化因子 $\mathcal N$ 的尺度""promise 的角色"与"加性 vs 相对 vs 精确三种任务的区别"三个角度组织你的回答。

> 提示：对照第 7 节 (a)(b)(c) 三种任务逐条比较。

## 参考文献

- 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 的复杂度联系。