权枚举式量子算法：线性码、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 和算法 与重量的整性（可能取值之间有整数间隔），可以把加性估计"舍入"成精确值，进而恢复完整的枚举式。

这三条结论放在一起，恰好展示了本章反复强调的图景：一个 \(\#\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）。用到这些工具的步骤我们会复述结论，但不重新推导。编码理论与有限域的基本概念则在用到时现场定义。

本课知识点

  1. 普通权枚举式与重量谱——能由生成矩阵写出线性码、Hamming 重量与权枚举式 \(W_C(x,y)\)，对小码算出重量谱 \(\{A_w\}\) 并读出最小距离，说明为何输出虽只有 \(n+1\) 个系数、计数仍是 \(\#\mathsf{P}\)-hard。

  2. MacWilliams 恒等式——能证明 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 定理——能写出二次符号权枚举式 \(S(A,Q;x,y)\) 的定义并比较它与普通权枚举式的异同，准确陈述归一化 QSWE 估计的 BQP-completeness 及其 promise 保留条款。

  4. 量子线路的路径展开——能对 H、CNOT、受控相位与旋转门逐门写出路径和中的贡献，汇总推导 \(\langle 0|U|0\rangle=\mathcal N^{-1}S(A,Q;x,y)\)，并对小线路完成数值验证。

  5. Hadamard 检验读出与 BQP 归约——能用 Hadamard 检验或振幅估计把 \(S/\mathcal N\) 估计到加性误差 \(\epsilon\)，追踪 \(O(1/\epsilon^2)\) 与 \(O(1/\epsilon)\) 两个代价因子的来源，并解释 BQP-hardness 归约的方向。

  6. Ising 高温展开与 cycle code——能推导高温展开（奇度子图相消、偶子图幸存），并用关联矩阵把偶子图等同于 cycle code 的码字，把均匀耦合配分函数写成权枚举式在 \(z=\tanh K\) 处的取值。

  7. Cyclic code、Gauss 和与整性舍入——能用 trace 表示把 irreducible cyclic code 的码字重量写成主项加 Gauss 和，并推导"整性间隔 → 误差分配 → 舍入"链条如何把加性估计升级为精确枚举式，同时界定其适用范围。

  8. 误差与复杂度边界——能比较加性、相对、精确三种估计任务的信息量与代价，解释 \(|S|\ll\mathcal N\) 时加性估计为何失效，以及归约为何不可外推可解性。

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 节）中寻找量子算法的用武之地。

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 节会把这一点坐实。

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 与归一化都不可省略。

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\) 正是量子振幅的典型情形。

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

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\)，

\[\begin{split} \sigma_v^{d_A(v)} = \begin{cases} 1, & d_A(v) \text{ 偶}, \\ \sigma_v, & d_A(v) \text{ 奇}. \end{cases} \end{split}\]

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

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

也就是说，凡含奇度顶点的子图 \(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 多项式语言下"圈—割对偶"的影子。

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 和算法 的用武之地：该算法以 \(\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 节一般原则的特例。

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 和算法 估计每一项，重量的整性间隔允许舍入恢复精确重量，少量轨道类型拼出完整枚举式。该路线严格限于特定码族。

  • 三条边界：加性估计在 \(|S| \ll \mathcal N\) 时可以没有信息量；exact 化需要整性 \(+\) 间隔 \(+\) 精度三者齐备；归约可能引入复参数与指数归一化，可解点不可外推。

练习题

练习 1【普通权枚举式与重量谱】（→ 第 1 节）

  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 节）

  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 节）

  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 节）

  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 节）

  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 节）

  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 节）

  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 节）

  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) 三种任务逐条比较。

参考文献