# 配分函数量子算法：退火比值、Gibbs 态、Tensor Network 与 Potts/Tutte 本课研究一个横跨统计物理与组合计数的核心对象——**配分函数 (partition function)** $$ Z(\beta) = \sum_{x \in \Omega} e^{-\beta E(x)}, $$ 其中 $\Omega$ 是一个有限但指数大的构型空间（例如 $n$ 个格点上自旋的所有 $2^n$ 种取值），$E : \Omega \to \mathbb{R}$ 是每个构型的**能量 (energy)**，$\beta \ge 0$ 是**逆温度 (inverse temperature)**（物理学中 $\beta = 1/(k_{\mathrm B}T)$，$T$ 为温度，$k_{\mathrm B}$ 为 Boltzmann 常数；本课取 $k_{\mathrm B} = 1$）。 配分函数之所以重要，是因为它同时扮演三个角色： - **归一化常数**：Gibbs 分布 $\pi_\beta(x) = e^{-\beta E(x)}/Z(\beta)$ 描述温度为 $1/\beta$ 的热平衡态，而 $Z(\beta)$ 正是让这个分布归一的那个数； - **热力学量的生成函数**：自由能、期望能量、比热等量都是 $\log Z$ 对 $\beta$ 的各阶导数（见第 1 节）； - **组合计数**：在适当的参数极限下，$Z$ 退化为图的着色数、独立集数、匹配数等经典计数对象，因此它的计算复杂性与 $\#\mathsf{P}$ 理论紧密相连。 直接按定义求和需要枚举 $|\Omega|$ 项，对 $n$ 个格点的系统这是 $2^n$（或 $q^n$）量级，完全不可行。**经典算法能做到什么程度？** 对许多有"正权重"结构的模型，Markov chain Monte Carlo（MCMC）配合退火技巧可以在多项式时间内给出**相对误差近似**（数学上称为 FPRAS，fully polynomial randomized approximation scheme）；但对一般的反铁磁/受挫系统、一般图上的 Ising 模型，精确计算是 $\#\mathsf{P}$-hard 的，多项式时间相对近似甚至与 $\mathsf{NP}$ 完全性纠缠，普遍认为不存在通用高效算法。经典方法的两大瓶颈是：Markov 链的**混合时间**（反比于谱隙 $\delta$）和蒙特卡洛估计的**精度**（方差反比于样本数，故样本数 $\sim 1/\epsilon^2$）。 量子算法有两条主线来突破这两个瓶颈： 1. **退火比值路线**：把 $Z(\beta)$ 分解为一条"冷却路径"上相邻配分函数比值的乘积，用**量子 Markov 链**（Szegedy 量子游走）把对谱隙的依赖从 $1/\delta$ 改善到 $1/\sqrt{\delta}$，用**振幅估计**把对精度的依赖从 $1/\epsilon^2$ 改善到 $1/\epsilon$； 2. **振幅编码路线**：对特定模型（Potts 模型、张量网络）把归一化的收缩值直接编成一个量子线路的**振幅**，用 Hadamard 检验或振幅估计读出——此时得到的是**加性近似**，其是否有用取决于误差相对于量的自然尺度有多大。 本课依次推导这两条路线，并反复强调一个容易混淆的区分：**相对近似、加性近似与复参数值**是三种不同的承诺，一个算法在一种意义下高效，绝不意味着在另一种意义下也高效。这正是本章 index 页强调的："一个 $\#\mathsf{P}$-hard 精确量不因存在某种加性量子估计就变得普遍易算。" **历史脉络**。这条问题线的经典一侧始于 1953 年 Metropolis 等人的 MCMC 采样方法——既然 $Z$ 算不出来，就绕开它直接对 $\pi_\beta$ 采样（Metropolis 转移规则只用到能量差，比值中的 $Z$ 自动消去）；1989 年 Jerrum 与 Sinclair 对铁磁 Ising 模型给出了第一个多项式时间相对近似（FPRAS），随后人们意识到"估计 $Z$"与"沿退火路径估计一串比值"等价，自适应退火 schedule 的构造也随之成熟。量子一侧，2008 年 Wocjan 与 Abeyesinghe 把 Szegedy 量子游走嵌入退火框架，给出了对谱隙的平方根改善；Montanaro 等人随后把振幅估计引入，补上精度维度的平方根改善；2022–2023 年的近无偏估计器工作（arXiv:2207.08643）解决了中间态反复重制备的问题。与此平行，Aharonov、Arad、Eban、Landau 等人自 2006 年起发展了另一条"振幅编码"路线：Jones 多项式、Potts/Tutte 点值与张量网络收缩都可以编成量子线路振幅并做加性估计。本课即按这两条主线组织。 **预备知识**。本课默认读者熟悉本站前几章的内容：量子态与测量（ch01）、振幅放大与振幅估计（ch03）、相位估计（ch03）、量子游走的基本概念（ch06）以及 block-encoding 的思想（ch05）。涉及这些工具的步骤我们会复述其结论，但不重新推导。 :::{admonition} 本课知识点 :class: tip 1. **[配分函数三重角色与 Gibbs 分布](#gibbs-free-energy)**——能写出 Gibbs 分布、自由能的定义与免费锚点 $Z(0)=|\Omega|$，推导 $-\frac{d}{d\beta}\log Z=\mathbb{E}_{\pi_\beta}[E]$，并各举一例说明配分函数如何退化为着色计数与独立集计数。 2. **[退火乘积恒等式](#annealing-product-identity)**——能证明相邻比值恒等式并推出望远镜乘积 $Z(\beta)=Z(0)\prod_i\mu_i$，能对四构型小例子手算各步比值，并通过计算相对方差判断一条 schedule 的步长是否过粗。 3. **[量子 Markov 链的双重平方加速](#szegedy-phase-gap)**——能解释 Szegedy 量子化的相位隙 $\Delta=\Theta(\sqrt\delta)$ 与振幅估计的 $1/\epsilon$ 各自的来源，并写出经典与量子的总复杂度账目加以比较。 4. **[相邻 Gibbs 态的 overlap 与比值提取](#gibbs-overlap-identity)**——能推导相邻 Gibbs 态的 overlap 恒等式并用 $\log Z$ 的凸性检验，能构造把 $Y_i$ 编入 ancilla 振幅的受控旋转使 $\mu_i$ 成为成功概率，并说明近无偏估计器为何让中间态可复用。 5. **[Fortuin–Kasteleyn 展开与 Tutte/Jones](#fortuin-kasteleyn)**——能证明随机簇展开 $Z_{\mathrm{Potts}}=\sum_A q^{k(A)}v^{|A|}$ 并对小图双向核对，能说明 Potts–Tutte–Jones 联系链与"加性近似 + 特定参数曲线"保留条款的准确范围。 6. **[张量网络振幅编码与误差尺度](#tensor-network-amplitude)**——能用 block-encoding 把收缩值编成线路振幅并计算归一化收缩值，能解释估计是否有意义取决于收缩值相对尺度乘积 $\prod_j\alpha_j$ 的比例。 7. **[整性承诺与精确结果](#integrality-promise)**——能解释整性承诺如何把半整数精度的加性近似舍入为精确值，并推导其 $O(1/M)$ 相对精度的代价、说明它只在特殊结构上真正高效。 ::: (gibbs-free-energy)= ## 1. 从 Gibbs 分布到自由能 固定能量函数 $E$。**Gibbs 分布 (Gibbs distribution)**（也称 Boltzmann 分布）是 $\Omega$ 上的概率分布 $$ \pi_\beta(x) = \frac{e^{-\beta E(x)}}{Z(\beta)}. $$ 物理直觉是：温度越低（$\beta$ 越大），概率越向低能量构型集中；$\beta \to \infty$ 时 $\pi_\beta$ 集中在基态（能量最低的构型）上；$\beta = 0$ 时 $\pi_0$ 是均匀分布，且 $$ Z(0) = \sum_{x \in \Omega} e^{0} = |\Omega|. $$ 这一点非常关键：$\beta = 0$ 处的配分函数就是构型总数，**通常有封闭表达式且无需计算**（例如 $n$ 个 $q$ 态自旋时 $Z(0) = q^n$）。我们的目标是在某个目标逆温度 $\beta_L = \beta$ 处估计 $Z(\beta)$，而 $\beta = 0$ 提供了一个免费的锚点——第 2 节的退火路径正是从已知点走向未知点。 **自由能 (free energy)** 定义为 $$ F(\beta) = -\frac{1}{\beta}\log Z(\beta). $$ 统计物理中几乎全部热力学量都可由 $\log Z$ 导出。作为热身，我们推导**期望能量**的表达式，它将告诉我们"$\log Z$ 的一阶导数是什么"： **命题 1**（期望能量）。 $$ -\frac{d}{d\beta}\log Z(\beta) = \mathbb{E}_{\pi_\beta}[E]. $$ **证明**。由链式法则，$\frac{d}{d\beta}\log Z = \frac{Z'(\beta)}{Z(\beta)}$。对 $Z$ 的定义逐项求导（有限和可以交换求和与求导）： $$ Z'(\beta) = \frac{d}{d\beta}\sum_x e^{-\beta E(x)} = \sum_x \big(-E(x)\big) e^{-\beta E(x)}. $$ 代回并把 $1/Z(\beta)$ 吸收进求和： $$ -\frac{Z'(\beta)}{Z(\beta)} = \frac{1}{Z(\beta)}\sum_x E(x)\, e^{-\beta E(x)} = \sum_x E(x)\,\frac{e^{-\beta E(x)}}{Z(\beta)} = \sum_x E(x)\,\pi_\beta(x) = \mathbb{E}_{\pi_\beta}[E]. $$ Q.E.D. 同样的方法对二阶导数给出 $\frac{d^2}{d\beta^2}\log Z = \mathrm{Var}_{\pi_\beta}[E]$（能量涨落，即比热的 $\beta^2$ 倍），留给读者作为习题。这个推导的精神贯穿全课：**$\log Z$ 的各阶导数都是 Gibbs 期望**，因此只要能对 Gibbs 分布采样并估计期望，就能获得热力学信息；反过来说，估计 $Z$ 本身比估计期望更难，而第 2 节的退火技巧正是把"估计 $Z$"降解为"估计一串期望"。 **配分函数还是计数对象**。第三个角色需要两个例子来坐实： - **图的正当着色**：取 $q$-state Potts 模型（第 5 节详述）的反铁磁零温极限 $\beta J \to -\infty$。此时任何一条边两端同色的构型都被因子 $e^{\beta J} \to 0$ 杀死，幸存构型恰好是图 $G$ 的**正当 $q$-着色**（相邻顶点不同色），且每个幸存构型权重相同——于是配分函数就**等于**正当 $q$-着色数，即 $G$ 的色多项式在 $q$ 处的值。计数正当着色是经典的 $\#\mathsf{P}$-complete 问题。 - **独立集**：硬核心模型 (hard-core model) 中每个构型是顶点集的一个子集，被占据的顶点不能相邻（相邻即能量无穷），每个合法构型权重 $\lambda^{|S|}$（$\lambda$ 称 fugacity）。配分函数 $Z(\lambda) = \sum_{S \text{ 独立集}} \lambda^{|S|}$ 是图的独立集生成多项式；$\lambda = 1$ 时它就是独立集的总数，同样是 $\#\mathsf{P}$-complete。 这两个例子的教训是双向的：一方面，它们说明配分函数算法的影响面远超物理——一个通用的配分函数估计器就是一个通用的组合计数器；另一方面，由于精确计数 $\#\mathsf{P}$-hard，**任何"通用、精确、多项式时间"的配分函数算法都不该被期待存在**（无论经典还是量子）。所有现实的算法都必须在某处让步：限定模型与参数范围（铁磁、正温度）、放宽精度（相对或加性近似）、或限定图族（第 7 节的结构化情形）。本课后半部分的"保留条款"全部源于这条复杂度边界。 ## 2. Annealing schedule 的乘积恒等式 (annealing-product-identity)= ### 2.1 恒等式的推导 选择一条从 $0$ 到目标逆温度的单调路径，称为 **annealing schedule（退火时间表）** 或 cooling schedule： $$ 0 = \beta_0 < \beta_1 < \cdots < \beta_L = \beta. $$ 对每一步定义步长 $\Delta\beta_i := \beta_{i+1} - \beta_i$，并记 $\pi_i := \pi_{\beta_i}$ 为第 $i$ 个逆温度处的 Gibbs 分布。 **命题 2**（相邻比值 = Gibbs 期望）。对每个 $i = 0, \dots, L-1$, $$ \frac{Z(\beta_{i+1})}{Z(\beta_i)} = \mathbb{E}_{\pi_i}\!\left[e^{-\Delta\beta_i E}\right]. $$ **证明**。从右端的定义出发，把 $\pi_i$ 展开： $$ \mathbb{E}_{\pi_i}\!\left[e^{-\Delta\beta_i E}\right] = \sum_x \pi_{\beta_i}(x)\, e^{-\Delta\beta_i E(x)} = \sum_x \frac{e^{-\beta_i E(x)}}{Z(\beta_i)}\, e^{-\Delta\beta_i E(x)}. $$ 指数相加：$e^{-\beta_i E} \cdot e^{-\Delta\beta_i E} = e^{-(\beta_i + \Delta\beta_i)E} = e^{-\beta_{i+1}E}$（这里用了 $\beta_i + \Delta\beta_i = \beta_{i+1}$，这正是步长的定义）。于是 $$ \sum_x \frac{e^{-\beta_{i+1} E(x)}}{Z(\beta_i)} = \frac{1}{Z(\beta_i)}\sum_x e^{-\beta_{i+1} E(x)} = \frac{Z(\beta_{i+1})}{Z(\beta_i)}. $$ Q.E.D. 把 $L$ 个比值连乘，所有中间项望远镜式消去，得到全课的核心恒等式： $$ Z(\beta) = Z(0)\prod_{i=0}^{L-1} \mu_i, \qquad \mu_i := \frac{Z(\beta_{i+1})}{Z(\beta_i)} = \mathbb{E}_{\pi_i}[Y_i], $$ 其中我们定义了随机变量 $$ Y_i(x) := e^{-\Delta\beta_i E(x)}. $$ **通过平移能量（即给所有 $E(x)$ 加上同一个常数）可以保证 $E(x) \ge 0$**，从而 $Y_i(x) \in (0, 1]$。注意平移能量只给 $Z$ 乘上一个已知的整体因子 $e^{-\beta c}$，不影响任何算法结论；而 $Y_i \in [0,1]$ 使得后文"把 $Y_i$ 编成 ancilla 振幅"的操作合法（振幅必须模长不超过 1）。 这一步的意义值得停下来体会。先看**为什么直接估计不可行**：注意到 $Z(\beta)/Z(0) = \mathbb{E}_{\pi_0}[e^{-\beta E}]$（命题 2 取 $\beta_i = 0$ 的特例），所以理论上可以从均匀分布 $\pi_0$ 采样、对 $e^{-\beta E}$ 取平均来一步得到 $Z(\beta)$。问题在于信噪比：$e^{-\beta E}$ 在绝大多数构型上小到天文数字级别（典型构型的能量在 $\beta$ 大时被压制到接近 $0$），只有极少数低能构型贡献几乎全部均值——要采到一个这样的构型就得等指数长的时间，相对方差随 $\beta$ 爆炸。这正是经典拒绝采样"对 $\Omega$ 均匀采样、按 $e^{-\beta E}$ 接受"在低温下失效的同一个现象。 退火分解的对策是**化整为零**：把一步跨越几十个数量级的比值拆成 $L$ 个**期望的乘积**，每个期望 $\mu_i$ 都是某个 $[0,1]$ 值随机变量在某个 Gibbs 分布下的均值——这是采样算法最擅长处理的对象。每一步只需要让分布"移动一点点"，而每次移动都可以用前一步的分布作为热启动。这是物理学中热力学积分 (thermodynamic integration) 思想在算法中的化身，也是"模拟退火"一词的来源。 ### 2.2 一个可手算的小例子 取一个四构型系统 $\Omega = \{x_1, x_2, x_3, x_4\}$，能量 $$ E(x_1) = 0,\quad E(x_2) = E(x_3) = 1,\quad E(x_4) = 2. $$ 取 schedule 为 $\beta_0 = 0$，$\beta_1 = \ln 2$，$\beta_2 = 2\ln 2$。因为 $e^{-\ln 2} = 1/2$，所有量都是分数，可以完全手算。 **锚点**：$Z(\beta_0) = Z(0) = |\Omega| = 4$。 **第一个比值**。$\Delta\beta_0 = \ln 2$，故 $Y_0 = e^{-(\ln 2) E}$ 在四个构型上取值 $(1, \tfrac12, \tfrac12, \tfrac14)$。$\pi_0$ 是均匀分布，所以 $$ \mu_0 = \mathbb{E}_{\pi_0}[Y_0] = \frac{1}{4}\left(1 + \frac12 + \frac12 + \frac14\right) = \frac{9}{16}. $$ 验证：$Z(\beta_1) = 1 + \frac12 + \frac12 + \frac14 = \frac94$，确实 $\frac{Z(\beta_1)}{Z(\beta_0)} = \frac{9/4}{4} = \frac{9}{16}$。✓ **第二个比值**。$\Delta\beta_1 = \ln 2$，$Y_1$ 取值同样为 $(1, \tfrac12, \tfrac12, \tfrac14)$。但现在 $\pi_1$ 不再均匀：其未归一化权重是 $e^{-\beta_1 E} = (1, \tfrac12, \tfrac12, \tfrac14)$，即整数化的权重 $(4, 2, 2, 1)$，归一化常数 $Z(\beta_1) = \frac94$。因此 $$ \mu_1 = \mathbb{E}_{\pi_1}[Y_1] = \frac{4\cdot 1 + 2\cdot\frac12 + 2\cdot\frac12 + 1\cdot\frac14}{4+2+2+1} = \frac{4 + 1 + 1 + \frac14}{9} = \frac{25}{36}. $$ 验证：$Z(\beta_2) = 1 + \frac14 + \frac14 + \frac{1}{16} = \frac{25}{16}$，确实 $\frac{Z(\beta_2)}{Z(\beta_1)} = \frac{25/16}{9/4} = \frac{25}{36}$。✓ **乘积检验**： $$ Z(\beta_0)\,\mu_0\,\mu_1 = 4 \cdot \frac{9}{16}\cdot\frac{25}{36} = \frac{900}{576} = \frac{25}{16} = Z(\beta_2). \quad\checkmark $$ 这个例子还展示了估计的相对误差如何在乘积中累积：若每个 $\mu_i$ 被估计到相对精度 $\epsilon'$，则 $\prod \mu_i$ 的相对误差大约按 $L\epsilon'$ 累积（小误差下相对误差近似相加）。因此要让最终相对误差为 $\epsilon$，每个比值需要 $\epsilon' = O(\epsilon/L)$ 的精度——这是后文复杂度分析中 $L$ 进入精度预算的原因。 ### 2.3 Schedule 不能太粗：overlap 条件 恒等式对任何 schedule 都成立，但**估计的效率**强烈依赖 schedule 的选取。若某一步 $\Delta\beta_i$ 太大，则 $\pi_i$ 与 $\pi_{i+1}$ 的"主力区域"错开：$Y_i(x)$ 在 $\pi_i$ 的典型构型上频繁取到接近 $0$ 的值，导致 $\mu_i$ 极小且相对方差巨大。定量地说，用独立同分布样本估计 $\mu_i$ 的相对误差为 $\epsilon'$ 所需样本数约为 $$ \frac{\mathrm{Var}_{\pi_i}[Y_i]}{\epsilon'^2 \mu_i^2} \le \frac{\mathbb{E}_{\pi_i}[Y_i^2]}{\epsilon'^2 \mu_i^2}. $$ 注意 $\mathbb{E}[Y_i^2] = \mathbb{E}[e^{-2\Delta\beta_i E}] = Z(2\beta_{i+1} - \beta_i)/Z(\beta_i)$（与命题 2 同理，把 $\Delta\beta_i$ 换成 $2\Delta\beta_i$），所以样本复杂度由相邻配分函数的某种"比率"控制。 用 2.2 节的小例子做个体检。第一步：$Y_0 = (1, \tfrac12, \tfrac12, \tfrac14)$，$\mu_0 = \tfrac{9}{16}$，而 $\mathbb{E}_{\pi_0}[Y_0^2] = \frac14(1 + \tfrac14 + \tfrac14 + \tfrac{1}{16}) = \tfrac{25}{64}$，故相对方差 $$ \frac{\mathbb{E}[Y_0^2]}{\mu_0^2} - 1 = \frac{25/64}{81/256} - 1 = \frac{100}{81} - 1 = \frac{19}{81} \approx 0.23, $$ 是常数级——这一步 schedule 很健康。若贪心一步从 $\beta = 0$ 跳到 $\beta = 2\ln 2$，则 $Y = (1, \tfrac14, \tfrac14, \tfrac1{16})$，$\mu = \tfrac{25}{64}$，$\mathbb{E}[Y^2] = \frac14(1 + \tfrac1{16} + \tfrac1{16} + \tfrac1{256}) = \tfrac{289}{1024}$，相对方差变为 $\frac{289/1024}{625/4096} - 1 = \frac{531}{625} \approx 0.85$——翻了近四倍，而且趋势随能量范围扩大而恶化。这就是"多走几步小步"优于"一步到位"的定量原因。 **cooling schedule 的设计准则就是让相邻 Gibbs 分布有足够的 overlap**，常用的可检验条件是每一步的相对方差（或等价地上述配分函数比率）有常数上界。对物理上"正常"的系统，这样的 schedule 长度 $L$ 是 $\widetilde{O}(\sqrt{\log|\Omega|})$ 量级的多项式小量；经典文献中已有自适应构造 schedule 的算法。本课把"存在长度 $L$、相邻 overlap 有常数界的 schedule"作为前提假设，不再展开其构造。 ## 3. 经典 MCMC 与量子 Markov 链 ### 3.1 经典瓶颈的两个来源 经典退火算法对每个 $i$ 做两件事： 1. **采样**：构造一个以 $\pi_i$ 为稳态分布的**可逆 Markov 链 (reversible Markov chain)** $P_i$（例如 Metropolis–Hastings 或 Glauber 动力学），从某个初分布出发走 $t$ 步使分布接近 $\pi_i$。若 $P_i$ 的**谱隙 (spectral gap)** 为 $\delta_i$（即转移矩阵 $1$ 与次大特征值之差），则混合时间典型为 $\widetilde{O}(1/\delta_i)$ 步，其中 $\widetilde{O}$ 隐藏对数因子。 2. **估计**：用 $m$ 个（近似）独立样本平均估计 $\mu_i = \mathbb{E}_{\pi_i}[Y_i]$，由 Chebyshev 或 Chernoff 不等式，达到加性误差 $\epsilon$ 需要 $m = O(1/\epsilon^2)$ 个有效样本。 合起来，每一步的代价约为 $\widetilde{O}\!\left(\frac{1}{\delta_i}\cdot\frac{1}{\epsilon^2}\right)$：谱隙一次方、精度平方。**量子算法对这两个因子各取一次平方根。** 补一句术语：第 2 节的退火分解加上上述采样与估计，正是经典文献中 **FPRAS（fully polynomial randomized approximation scheme，全多项式随机近似格式）** 的标准构造——输出 $\hat Z$ 以至少 $3/4$ 概率满足 $(1-\epsilon)Z \le \hat Z \le (1+\epsilon)Z$，运行时间是问题规模与 $1/\epsilon$ 的多项式。FPRAS 的存在性对模型有苛刻要求（正权重、链要混合得动、schedule 要存在），这正是引言说的"经典算法能做到的程度"；量子版本在同一框架内逐项替换采样器与估计器。 (szegedy-phase-gap)= ### 3.2 Szegedy quantization：把谱隙开根号 量子加速的第一个来源是 **Szegedy quantization**：任何可逆 Markov 链 $P_i$ 都可以升格为一个作用在两份构型寄存器上的**量子游走 (quantum walk)** 算子 $W_i$（其构造细节见 ch06 量子游走教程）。其谱性质与 $P_i$ 精确对应：$P_i$ 的谱隙 $\delta_i$ 对应 $W_i$ 的**相位隙 (phase gap)** $$ \Delta_i = \Theta(\sqrt{\delta_i}), $$ 即 $W_i$ 的零相位本征方向与最近非零相位本征值之间的角度距离是 $\sqrt{\delta_i}$ 量级。这个"开根号"的来源值得说清楚：可逆 Markov 链的转移矩阵经相似变换对称化后有实谱，其判别算子 (discriminant operator) 的本征值落在 $[-1, 1]$ 内，记最大非平凡本征值为 $1 - \delta_i$；Szegedy 构造把每个经典本征值 $\lambda$ 升级为量子游走的一对共轭相位 $e^{\pm i\arccos\lambda}$——经典谱被"弯"到了单位圆上。当 $\lambda = 1 - \delta$ 接近 $1$ 时，由小角度展开 $\arccos(1-\delta) = \sqrt{2\delta}\,(1 + O(\delta))$，相位到 $0$ 的距离就是 $\Theta(\sqrt{\delta})$。一次相位估计分辨角度 $\Delta$ 需要 $O(1/\Delta)$ 次受控 $W_i$ 调用（ch03 相位估计的标准结论），于是经典谱隙的 $1/\delta$ 被换成了量子相位隙的 $1/\sqrt{\delta}$——这与 Grover 搜索中"$N$ 个条目、$\sqrt{N}$ 次查询"的开根号是同一种收益，只是发生在一个更一般的谱框架里。 与 $W_i$ 相配的核心态是 Gibbs 分布的**相干编码 (coherent encoding)**，也称量子 Gibbs 态： $$ |\pi_i\rangle = \sum_x \sqrt{\pi_i(x)}\,|x\rangle. $$ 它把概率分布编码为振幅（故对 $x$ 测量恰好以 $\pi_i(x)$ 的概率得到 $x$，且测量 $Y_i$ 型可观测量即给出均值估计所需的样本），并且它是 $W_i$ 的**零相位本征态**：$W_i|\pi_i\rangle = |\pi_i\rangle$。 相位隙 $\Delta_i$ 的直接后果是：用相位检测（phase detection，即以 $W_i$ 为酉算子的相位估计，见 ch03）可以在 $\widetilde{O}(1/\Delta_i) = \widetilde{O}(1/\sqrt{\delta_i})$ 次游走调用内，以高概率把任意态**投影到** $|\pi_i\rangle$ 上，或者实现关于 $|\pi_i\rangle$ 的**反射** $R_i = I - 2|\pi_i\rangle\langle\pi_i|$。对比一下：经典世界"得到 $\pi_i$ 的一个样本"需要 $\widetilde{O}(1/\delta_i)$ 步混合；量子世界"制备/识别 $|\pi_i\rangle$"只需 $\widetilde{O}(1/\sqrt{\delta_i})$ 次调用。这是第一重平方加速。 ### 3.3 振幅估计：把精度开根号 第二重加速来自**振幅估计 (amplitude estimation)**（ch03）：若一个酉子程序以成功概率 $\mu$ 制备目标态，则把 $\mu$ 估计到加性误差 $\epsilon$ 只需 $O(1/\epsilon)$ 次调用，而经典蒙特卡洛需要 $O(1/\epsilon^2)$ 个样本。回忆其机制：成功概率 $\mu$ 决定 Grover 型迭代算子的旋转角 $2\omega$（$\sin^2\omega = \mu$），对迭代算子做相位估计、把 $\omega$ 定到精度 $\epsilon$，即把 $\mu$ 定到同阶精度；相位估计把角度定到 $\epsilon$ 需要 $O(1/\epsilon)$ 次受控迭代——平方收益同样来自"振幅→相位→相位估计"这条链。第 4 节将说明 $\mu_i$ 恰好可以被编成一个"成功概率"，因此估计每个比值的精度依赖从 $1/\epsilon^2$ 降到 $1/\epsilon$。 ### 3.4 合起来的复杂度 把退火结构、量子游走和振幅估计组装起来，估计 $Z(\beta)$ 的总量子代价（忽略对数因子）为 $$ \sum_{i=0}^{L-1} \widetilde{O}\!\left(\frac{1}{\sqrt{\delta_i}}\cdot\frac{1}{\epsilon_i}\right), \qquad \epsilon_i = O\!\left(\frac{\epsilon\,\mu_i}{L}\right), $$ 其中 $\epsilon_i$ 的选取正是 2.2 节末尾说的"把总相对误差 $\epsilon$ 均摊到 $L$ 步"：每步需要相对精度 $\epsilon/L$，即加性精度 $\mu_i \epsilon / L$。 **参数如何平衡**。为看清各因子的来源，设所有步的谱隙相同 $\delta_i = \delta$、比值同阶 $\mu_i = \Theta(\mu)$。把 $\epsilon_i = \Theta(\epsilon\mu/L)$ 代回： - 经典：每步代价 $\widetilde{O}\!\left(\frac{1}{\delta}\cdot\frac{1}{\epsilon_i^2}\right) = \widetilde{O}\!\left(\frac{L^2}{\delta\,\epsilon^2\mu^2}\right)$，乘 $L$ 步得总量 $\widetilde{O}\!\left(\frac{L^3}{\delta\,\epsilon^2\mu^2}\right)$； - 量子：每步代价 $\widetilde{O}\!\left(\frac{1}{\sqrt{\delta}}\cdot\frac{1}{\epsilon_i}\right) = \widetilde{O}\!\left(\frac{L}{\sqrt{\delta}\,\epsilon\mu}\right)$，乘 $L$ 步得总量 $\widetilde{O}\!\left(\frac{L^2}{\sqrt{\delta}\,\epsilon\mu}\right)$。 逐项对照：$L$ 的幂次差（$L^3 \to L^2$）来自精度预算被均摊后，每步估计代价对 $1/\epsilon_i$ 的依赖从平方降为线性；$\delta$ 的幂次差（$1/\delta \to 1/\sqrt{\delta}$）来自 Szegedy 相位隙；$\epsilon$ 的幂次差（$1/\epsilon^2 \to 1/\epsilon$）来自振幅估计。这就是"双重平方改善"（外加 schedule 长度上的一次改善）的完整账目。 若进一步代入满足 overlap 条件的 schedule 长度 $L = \widetilde{O}(\sqrt{\log|\Omega|})$ 与物理系统中常见的谱隙行为，总复杂度对问题规模的依赖是对构型空间对数的多项式——这正是"指数大空间上多项式时间"的意义。 ## 4. 从一个 Gibbs 态移动到下一个 上一节解决的是"在一个固定 $\beta_i$ 处如何高效制备 $|\pi_i\rangle$ 并估计期望"。退火算法还要求**把整条路径走通**：从 $|\pi_0\rangle$（均匀叠加，免费制备）出发，依次穿过 $|\pi_1\rangle, |\pi_2\rangle, \dots, |\pi_L\rangle$，并在沿途读出每个比值 $\mu_i$。本节解决两个技术问题：相邻量子 Gibbs 态之间有多像？如何从一个走到另一个同时提取比值？ (gibbs-overlap-identity)= ### 4.1 相邻 Gibbs 态的 overlap **命题 3**（overlap 恒等式）。 $$ \langle\pi_i|\pi_{i+1}\rangle = \frac{Z\!\left(\frac{\beta_i + \beta_{i+1}}{2}\right)}{\sqrt{Z(\beta_i)\,Z(\beta_{i+1})}}. $$ **证明**。由定义直接展开： $$ \langle\pi_i|\pi_{i+1}\rangle = \sum_x \sqrt{\pi_i(x)}\,\sqrt{\pi_{i+1}(x)} = \sum_x \sqrt{\frac{e^{-\beta_i E(x)}}{Z(\beta_i)}}\sqrt{\frac{e^{-\beta_{i+1} E(x)}}{Z(\beta_{i+1})}}. $$ 根号相乘得 $\sqrt{e^{-(\beta_i+\beta_{i+1})E(x)}} = e^{-\frac{\beta_i+\beta_{i+1}}{2}E(x)}$（能量实数，指数运算合法），分母提出： $$ \frac{1}{\sqrt{Z(\beta_i)Z(\beta_{i+1})}}\sum_x e^{-\frac{\beta_i+\beta_{i+1}}{2}E(x)} = \frac{Z\!\left(\frac{\beta_i+\beta_{i+1}}{2}\right)}{\sqrt{Z(\beta_i)Z(\beta_{i+1})}}. $$ Q.E.D. 注意右端分子是中点逆温度处的配分函数。若 $Z$ 在区间 $[\beta_i, \beta_{i+1}]$ 上变化平缓（这正是 2.3 节 overlap 条件的另一面），则分子分母接近，overlap 接近 $1$。例如对 2.2 节的小例子，$\langle\pi_0|\pi_1\rangle = Z(\tfrac{\ln 2}{2})/\sqrt{Z(0)Z(\ln 2)} = \frac{\frac32 + \sqrt2}{3} \approx 0.971$——相邻态几乎重合。 这个恒等式还允许一个更精细的解读。由命题 1 与习题 2，$\log Z$ 是 $\beta$ 的递减凸函数（一阶导为 $-\mathbb{E}[E] \le 0$，二阶导为 $\mathrm{Var}[E] \ge 0$）。凸性给出 $$ \log Z\!\left(\tfrac{\beta_i+\beta_{i+1}}{2}\right) \le \frac{\log Z(\beta_i) + \log Z(\beta_{i+1})}{2}, $$ 即分子不超过分母，overlap $\le 1$——这正是 Cauchy–Schwarz 不等式要求的自洽性检查，恒等式通过。更进一步，overlap 与 $1$ 的差距由 $\log Z$ 在区间上的**曲率**（即能量方差 $\mathrm{Var}_{\pi}[E]$）控制：能量涨落越小、schedule 越细，相邻 Gibbs 态贴得越紧。这把第 2 节"相对方差有界"的经典判据与第 4 节"量子态 overlap 大"的量子判据统一成了同一句话。 ### 4.2 态转移：Zeno、固定点放大与游走反射 有了"相邻态 overlap 接近 1"，从 $|\pi_i\rangle$ 到 $|\pi_{i+1}\rangle$ 的转移有三种等效视角的实现： - **量子 Zeno 式逐次投影**：把 schedule 取得足够细，使每步 overlap 极高；依次向 $|\pi_{i+1}\rangle$ 做投影测量（用 3.2 节的相位检测实现），由 Zeno 效应，整条链上的投影几乎总是成功。定量地说：若每步 $|\langle\pi_i|\pi_{i+1}\rangle|^2 \ge 1 - \eta$，则单次投影失败概率不超过 $\eta$，整条 $L$ 步链上"每次都成功"的概率至少约 $1 - L\eta$（union bound），故把 schedule 加密到 $\eta = O(1/L)$ 即可——这与 2.3 节"相邻分布要有常数级 overlap"的设计准则互相呼应，只是常数级 overlap 下改用下面的放大手段更省； - **固定点振幅放大 (fixed-point amplitude amplification)**：把 $|\pi_i\rangle$ 到 $|\pi_{i+1}\rangle$ 看作一次"成功概率为 $|\langle\pi_i|\pi_{i+1}\rangle|^2$"的制备，用固定点振幅放大把成功率提到接近 1。普通振幅放大要求预先知道成功概率以选择迭代次数，而"固定点"版本（ch03 振幅放大的变体）不需要——它对一段角度区间内的任何未知成功概率都把终态压向目标，调用数为 overlap 倒数的量级； - **游走反射**：直接用 3.2 节关于 $|\pi_{i+1}\rangle$ 的反射构造旋转，把态确定性地转过去。这一步的本质仍是"两个反射复合成旋转"的 Grover 几何：一个反射关于当前态、一个反射关于目标态，复合旋转把前者拨向后者，每次相位检测代价 $\widetilde{O}(1/\sqrt{\delta_{i+1}})$。 三条路线的代价都由 overlap（进而由 schedule 细度与谱隙）控制，本节不再区分。 ### 4.3 把比值编成 ancilla 的振幅 现在提取 $\mu_i$。由于 $Y_i(x) = e^{-\Delta\beta_i E(x)} \in [0, 1]$（2.1 节已约定能量非负），可以相干地计算 $E(x)$、进而计算 $Y_i(x)$，并据此旋转一个辅助比特（ancilla）： $$ |x\rangle|0\rangle \mapsto |x\rangle\left(\sqrt{Y_i(x)}\,|1\rangle + \sqrt{1 - Y_i(x)}\,|0\rangle\right). $$ （这是标准的"相干概率加载"：先算 $Y_i$ 到一个工作寄存器，做受控旋转，再反算工作寄存器复位。）把这个映射作用在 $|\pi_i\rangle \otimes |0\rangle$ 上，ancilla 测得 $|1\rangle$ 的概率恰好是 $$ \sum_x \pi_i(x)\, Y_i(x) = \mathbb{E}_{\pi_i}[Y_i] = \mu_i, $$ 即第 $i$ 个配分函数比值。于是**振幅估计以 $O(1/\epsilon_i)$ 次调用给出 $\mu_i$ 的 $\epsilon_i$ 加性估计**——3.3 节的第二重加速在此落地。 ### 4.4 近无偏估计器与态的复用 上面的叙述掩盖了一个长期存在的障碍：**测量会破坏态**。早期的退火量子算法每估计一个 $\mu_i$ 都要重新制备 $|\pi_i\rangle$，而制备本身要经过整条路径的前 $i$ 步，代价随路径位置累积，使总复杂度对 schedule 长度 $L$ 的依赖变差。 2022–2023 年前后发展的**近无偏 (near-unbiased) 量子相位/振幅/均值估计器**解决了这一问题。这里"近无偏"的准确含义是：估计器输出的随机变量 $\hat\mu$ 满足 $|\mathbb{E}[\hat\mu] - \mu| \le b$（偏倚 $b$ 可控），同时方差也可被独立压缩到目标水平——普通振幅估计给出的是一个"大致落在区间里的数"，而近无偏版本给出的是一个统计性质干净的随机变量，可以像经典样本一样被平均、被串联进下游估计。更关键的是其实现方式**近似不破坏输入态**：估计完成后输入的量子 Gibbs 态仍可继续沿路径使用。效果是同一串 annealing state 可以被"读"很多次而不必反复重头来，从而改善了复杂度对 $L$ 的依赖，并给出了对 $\log|\Omega|$（构型空间维数的对数）**次线性 (sublinear)** 依赖的结果。本课只引用这一结论，其构造涉及对相位估计线路的精细随机化处理，超出范围；有兴趣的读者可沿文末 Zoo 条目追溯原文（arXiv:2207.08643）。 至此退火路线完整：**命题 2 把 $Z$ 分解为期望的乘积；量子游走把混合代价开根号；振幅估计把精度代价开根号；近无偏估计器让中间态可复用。** 对满足常数 overlap 条件的 schedule，整条链以相对误差 $\epsilon$ 输出 $Z(\beta)$ 的估计是多项式资源的。 ## 5. Potts、Random Cluster 与 Tutte 退火路线适用于"正温度、铁磁型、可采样"的模型。另一条路线从**模型的代数展开**出发，把特定参数点的配分函数直接编成量子线路振幅。这条路线的起点是 Potts 模型。 (fortuin-kasteleyn)= ### 5.1 Potts 模型与 Fortuin–Kasteleyn 展开 **$q$-state Potts 模型**定义在图 $G = (V, E)$ 上：每个顶点 $v$ 取一个自旋 $\sigma_v \in [q] = \{1, \dots, q\}$，每条边 $(u, v)$ 有耦合 $J_{uv}$，配分函数为 $$ Z_{\mathrm{Potts}} = \sum_{\sigma : V \to [q]}\ \prod_{(u,v) \in E} e^{\beta J_{uv}\,[\sigma_u = \sigma_v]}, $$ 其中 $[\sigma_u = \sigma_v]$ 是指示函数（自旋相同取 $1$，否则取 $0$）。$q = 2$ 时它就是 Ising 模型：把 $\sigma_v \in \{1, 2\}$ 换成 $s_v \in \{+1, -1\}$，则 $[\sigma_u = \sigma_v] = (1 + s_u s_v)/2$，每条边贡献 $e^{\beta J/2}\cdot e^{(\beta J/2) s_u s_v}$，提出常数因子后正是标准的 Ising 形式 $Z_{\mathrm{Ising}} = \sum_s e^{\beta' \sum s_u s_v}$。 **命题 4**（Fortuin–Kasteleyn 随机簇展开）。令 $v_{uv} := e^{\beta J_{uv}} - 1$，并设所有耦合相同 $J_{uv} = J$、记 $v = e^{\beta J} - 1$。则 $$ Z_{\mathrm{Potts}} = \sum_{A \subseteq E} q^{k(A)}\, v^{|A|} =: Z_G(q, v), $$ 其中 $k(A)$ 是子图 $(V, A)$（保留所有顶点、只保留 $A$ 中的边）的连通分量个数。 **证明**。关键一步是把每条边的因子拆成"断开"与"连接"两项之和： $$ e^{\beta J [\sigma_u = \sigma_v]} = 1 + \left(e^{\beta J} - 1\right)[\sigma_u = \sigma_v] = 1 + v\,[\sigma_u = \sigma_v], $$ 验证：当 $\sigma_u = \sigma_v$ 时右端为 $1 + v = e^{\beta J}$，当 $\sigma_u \neq \sigma_v$ 时右端为 $1$，与左端一致。 把它代入配分函数并把 $E$ 条边的乘积展开（每条边独立地选"$1$"或"$v[\cdot]$"）： $$ Z_{\mathrm{Potts}} = \sum_{\sigma} \prod_{(u,v) \in E}\left(1 + v\,[\sigma_u = \sigma_v]\right) = \sum_{\sigma}\sum_{A \subseteq E} v^{|A|}\prod_{(u,v) \in A}[\sigma_u = \sigma_v]. $$ 现在交换两个求和。对固定的 $A$，乘积 $\prod_{(u,v)\in A}[\sigma_u = \sigma_v]$ 为 $1$ 当且仅当自旋在 $A$ 的每条边上两端相同，即 $\sigma$ 在子图 $(V, A)$ 的每个连通分量上取常数值；这样的着色恰有 $q^{k(A)}$ 种（每个分量独立选 $q$ 色之一）。对其余 $\sigma$ 该乘积为 $0$。故 $$ \sum_{\sigma}\prod_{(u,v) \in A}[\sigma_u = \sigma_v] = q^{k(A)}, $$ 代回即得 $Z_{\mathrm{Potts}} = \sum_{A \subseteq E} q^{k(A)} v^{|A|}$。Q.E.D. **最小例子（一条边）**。取 $G$ 为两个顶点一条边。直接按自旋求和：$q$ 种同色构型各贡献 $e^{\beta J} = 1+v$，$q(q-1)$ 种异色构型各贡献 $1$，故 $Z = q(1+v) + q(q-1) = q^2 + qv$。按子图求和：$A = \varnothing$ 时 $k = 2$ 贡献 $q^2$；$A = E$ 时 $k = 1$ 贡献 $qv$。两者一致。读者可在习题中对三角形图做同样的双向核对。 右端的 $Z_G(q, v)$ 称为**随机簇模型 (random cluster model)** 的配分函数。注意一个深刻的转变：左端是对 $q^{|V|}$ 个自旋构型求和，右端是对 $2^{|E|}$ 个子图求和——两者指数级相等，但右端中 $q$ 和 $v$ 可以作为**形式变量**出现，$q$ 甚至不必是正整数。 ### 5.2 Tutte 多项式与 Jones 多项式 $Z_G(q, v)$ 是图论中最重要的不变量之一——**Tutte 多项式 (Tutte polynomial)** $T_G(x, y)$——的一条参数曲线：沿双曲线 $(x-1)(y-1) = q$ 取适当的变量替换即可互化。这意味着"估计 Potts 配分函数"与"求 Tutte 多项式的点值"本质上是同一族问题，而 Tutte 多项式在一般点上的精确求值是 $\#\mathsf{P}$-hard 的，只有少数特殊曲线（如 $(x-1)(y-1) = 1$、$(x-1)(y-1) = 2$ 的部分点）有多项式时间算法。 另一条线通向拓扑：Aharonov、Jones、Landau 等人的工作表明，**Jones 多项式 (Jones polynomial)**——纽结理论的核心不变量——在特定根的单位值处与平面图经 medial link 构造得到的 Tutte 多项式点值相联系，而 Jones 多项式在根的单位处的加性近似恰是量子计算机天然擅长的问题（详见本章 knot-invariants 教程）。由此，**对某些复参数点**，可以把 Tutte/Potts 量经 deletion–contraction 递推与 Temperley–Lieb 代数表示编成酉或近酉的 tensor maps，用量子线路估计其归一化收缩值，得到**加性**近似。 这段话里的构造可以拆开理解。**deletion–contraction 递推**是 Tutte 多项式的定义性恒等式：任选一条边 $e$，则 $T_G$ 等于"删掉 $e$ 的图"与"收缩 $e$ 的图"上 Tutte 多项式的线性组合。沿递推展开，$Z_G(q, v)$ 被写成对一系列"平面编织"（strands 的各种连接方式）的加权求和；而 **Temperley–Lieb 代数**正是这些连接方式在乘积（上下拼接）下生成的代数，它有一族用 $\mathsf{SU}(2)$ 型量子线路实现的表示——当参数 $q$ 取与根的单位相关的特定值时，这些表示中的生成元是酉或近酉的。于是一条边的"删/缩"对应一个酉门，整个递推树对应一个量子线路，配分函数的点值变成该线路的某个振幅。这就是"编成酉或近酉 tensor maps"的含义，也是第 6 节一般框架的一个具体化身。 **保留条款（务必读）**：这类算法的复杂度与图的树宽/路径宽、边数以及局部算子范数的乘积有关；其输出是相对于某个自然尺度的加性近似。它**不等于**正温度铁磁 Potts 配分函数的通用 FPRAS（相对近似），也不解决一般点上 Tutte 多项式的相对近似——那被认为超出量子多项式时间。量子加速存在于"加性近似 + 特定参数曲线"这个精确的缝隙里，夸大或缩小这个范围都是误读。 (tensor-network-amplitude)= ## 6. Tensor network contraction 作为振幅 第 5 节的"编成振幅"思想可以完全一般化到任意**张量网络 (tensor network)**。一个张量网络收缩值 $\mathrm{Contr}(\mathcal{T})$（所有内部指标求和后的标量）在选定收缩顺序后，总可以写成一串线性映射的乘积作用在边界上的形式 $$ T = T_m \cdots T_1, $$ 其中每个 $T_j$ 是某个中间切割空间上的线性算子（例如把一条"切片"的张量并进来）。若每个 $T_j$ 都是酉的，收缩值就是一个量子线路的振幅；问题是它们一般不是酉的。 补救办法是 ch05 的 **block-encoding**：对每个非酉的 $T_j$，选一个缩放因子 $\alpha_j \ge \|T_j\|$（算子范数），把归一化后的 $T_j/\alpha_j$ 嵌入一个更大的酉矩阵 $U_j$ 的左上角： $$ (\langle 0| \otimes I)\, U_j\, (|0\rangle \otimes I) = \frac{T_j}{\alpha_j}. $$ （直觉：任何模长不超过 1 的矩阵块都可以通过补空间扩张成酉矩阵， ancilla 寄存器提供了这块补空间。）把 $m$ 个 $U_j$ 依次作用，所有 ancilla 初始为 $|0\rangle$，则**所有 ancilla 后选择 (postselection) 到全 $0$** 的振幅为 $$ \frac{\mathrm{Contr}(\mathcal{T})}{\prod_j \alpha_j}. $$ 推导：每次 block-encoding 在与目标块相乘时贡献因子 $1/\alpha_j$ 与一个 ancilla 的 $|0\rangle$ 分量；$m$ 次相乘后，全 $0$ ancilla 分支上的算子恰好是 $\prod_j T_j/\alpha_j = T/\prod_j\alpha_j$，取适当的输入输出基矢矩阵元即得收缩值除以尺度乘积。 **一个小例子**。取 $m = 2$、中间空间维数 $2$, $$ T_1 = T_2 = \begin{pmatrix} 2 & 0\\ 0 & \tfrac12 \end{pmatrix}, \qquad \mathrm{Contr}(\mathcal{T}) = \langle 0|T_2 T_1|0\rangle. $$ 每个 $T_j$ 的算子范数是 $2$，取 $\alpha_1 = \alpha_2 = 2$，尺度乘积为 $4$。而 $$ T_2 T_1 = \begin{pmatrix} 4 & 0\\ 0 & \tfrac14 \end{pmatrix}, \qquad \mathrm{Contr}(\mathcal{T}) = 4, $$ 故归一化振幅为 $4/4 = 1$：block-encoding 后的"成功"分支几乎必然发生，估计毫不费力。对比之下，若目标换成 $\langle 1|T_2T_1|1\rangle = \frac14$，归一化振幅只有 $\frac{1}{16}$：要把它测到 $10\%$ 相对精度，振幅估计需要加性精度约 $\frac{1}{160}$，调用数 $\sim 160$——而真正想要的数只有 $\frac14$。这个对照就是下一段"误差尺度"的具体化：信息量取决于**收缩值占尺度乘积的比例**，而不是收缩值的绝对大小。 于是用 Hadamard 检验（ch01/ch03 的标准工具）或振幅估计可以读出这个振幅，得到**归一化收缩值** $\mathrm{Contr}(\mathcal{T})/\prod_j\alpha_j$ 的加性估计。 **误差尺度分析（关键）**。设振幅估计以加性误差 $\varepsilon$ 读出归一化值，则还原到原收缩值时的误差是 $$ \varepsilon \cdot \prod_j \alpha_j. $$ 若 $\prod_j \alpha_j$ 随系统规模指数增长（对一般张量网络确实如此——每个 $\alpha_j \ge \|T_j\|$ 而范数随切割维度增长），则相对于 $\mathrm{Contr}(\mathcal{T})$ 本身的典型大小，这个"加性"误差可能同阶甚至更大，此时估计不携带有效信息。因此这类算法的**"非平凡精度"必须相对于 $\prod_j \alpha_j$ 这个自然尺度来陈述**：只有当收缩值本身接近这个尺度（例如由西性较好的张量、受限宽度的网络组成）时，多项式资源的估计才有意义。这与第 5 节末尾对 Potts/Tutte 算法的保留条款是同一个现象的不同面貌。 (integrality-promise)= ## 7. 特殊 exact 结果与权枚举 前两条路线给出的都是近似。在某些高度结构化的情形下，量子算法还能给出**精确 (exact)** 值，机制值得单独说明。 经典编码理论中，某些**不可约循环码 (irreducible cyclic codes)** 的**权枚举子 (weight enumerator)**——按 Hamming 重量统计码字数目的生成函数——可以通过有限域上的 **Gauss 和 (Gauss sums)** 高效估计或重构（Gauss 和有封闭表达式与精确的绝对值，且与有限域特征和的量子算法相通，见 ch09 的 Gauss sums 教程）。另一方面，Potts 配分函数与对应的 cocycle-code 图的权枚举子之间存在恒等式联系，于是一端的高效估计传递到另一端。 把高精度近似升级为精确值靠的是一个**整性承诺 (integrality promise)**：若事先知道目标量取值于整数（或某个离散集合），且近似误差严格小于半个整数，则**四舍五入即得精确值**——误差 $< 1/2$ 时最近整数唯一。这把"近似算法"变成了"精确算法"，但代价是必须同时满足两个条件：(i) 目标量确有离散结构；(ii) 近似精度推进到半整数以内。 注意条件 (ii) 的代价不可忽略：若目标整数值本身可达 $M$，则"绝对误差 $< 1/2$"相当于**相对精度** $O(1/M)$，在振幅编码框架下意味着振幅估计的调用数正比于 $M$ 的尺度——对指数大的配分函数这通常就是指数资源。所以整性舍入只在两类情形下真正高效：目标量的尺度被结构（如 Gauss 和的精确绝对值）提前归一化，或者问题本身只要求中等精度。这再次呼应全课主题：**承诺 (promise) 的内容决定了算法的成色**。 **保留条款**：这只覆盖高度结构化的图族（与循环码/特征和相通的那些），**不应推广成任意 Potts 模型的精确算法**。同理，Ising 配分函数与量子线路振幅之间的各种映射常落在复耦合或特定图族上；其计算困难性和可模拟的门集随参数取值而变化，不存在"Ising 配分函数普遍量子易算"这类结论。 ## 8. 本课小结 **小结**。 - 配分函数同时归一化 Gibbs 分布、生成全部热力学量（$F = -\beta^{-1}\log Z$，$-\frac{d}{d\beta}\log Z = \mathbb{E}[E]$），并在参数极限下编码组合计数；一般情形精确计算是 $\#\mathsf{P}$-hard 的。 - **退火路线**：$Z(\beta) = Z(0)\prod_i \mu_i$，$\mu_i = \mathbb{E}_{\pi_i}[e^{-\Delta\beta_i E}]$；schedule 的相邻 overlap 条件决定估计的可行性。 - **双重平方加速**：量子游走把 Markov 链谱隙依赖 $1/\delta \to 1/\sqrt{\delta}$（Szegedy quantization 的相位隙 $\Delta = \Theta(\sqrt{\delta})$）；振幅估计把精度依赖 $1/\epsilon^2 \to 1/\epsilon$；近无偏估计器进一步让中间 Gibbs 态可复用，得到对 $\log|\Omega|$ 次线性依赖的结果。 - **振幅编码路线**：Potts 模型经 Fortuin–Kasteleyn 展开化为随机簇/Tutte 多项式，特定（含复）参数点可编入酉或近酉 tensor maps；一般张量网络经 block-encoding 把收缩值编成振幅，读出的是相对于尺度乘积 $\prod_j\alpha_j$ 的**加性**近似。 - **误差尺度与输入模型决定一切**：加性近似 ≠ 相对近似 ≠ 精确值；整性承诺 + 半整数精度才能在特殊结构上把近似舍入为精确。 ## 练习题 **练习 1【配分函数三重角色与 Gibbs 分布】**（→ [第 1 节](#gibbs-free-energy)） 1. 基础：列出配分函数 $Z(\beta)$ 的三重角色，并写出 $n$ 个 $q$ 态自旋系统在 $\beta = 0$ 处的配分函数 $Z(0)$，说明为什么这个锚点通常无需计算。 2. 基础：取三构型系统 $E = (0, 0, 1)$、$\beta = \ln 2$，计算 $Z(\beta)$、Gibbs 分布 $\pi_\beta$ 与期望能量 $\mathbb{E}_{\pi_\beta}[E]$，再用 $-Z'(\beta)/Z(\beta)$ 数值验证命题 1。 3. 进阶：证明 $\frac{d^2}{d\beta^2}\log Z(\beta) = \mathrm{Var}_{\pi_\beta}[E]$，并由此解释为什么 $\log Z$ 是 $\beta$ 的凸函数。 > 提示：对 $Z'(\beta) = -\sum_x E(x)\, e^{-\beta E(x)}$ 再求导一次，除以 $Z$ 后凑出 $\mathbb{E}[E^2] - \mathbb{E}[E]^2$。 **练习 2【退火乘积恒等式】**（→ [2.1 节](#annealing-product-identity)） 1. 基础：对 2.2 节的四构型例子手算第一个比值 $\mu_0 = \mathbb{E}_{\pi_0}[Y_0]$，并验证 $Z(\beta_1) = Z(0)\,\mu_0$。 2. 进阶：不查书推导命题 2：$\frac{Z(\beta_{i+1})}{Z(\beta_i)} = \mathbb{E}_{\pi_i}[e^{-\Delta\beta_i E}]$，并说明若不做能量平移，$Y_i$ 可能跑出 $[0,1]$ 会在 4.3 节的哪一步造成麻烦。 3. 进阶：计算同一例子第二步的相对方差 $\mathbb{E}_{\pi_1}[Y_1^2]/\mu_1^2 - 1$，并与"一步跳到 $2\ln 2$"的相对方差（约 $0.85$）比较，定量说明"多走几步小步"的价值。 > 提示：把 $\pi_i(x) = e^{-\beta_i E(x)}/Z(\beta_i)$ 代入后合并指数；ancilla 受控旋转要求 $Y_i(x) \le 1$。 **练习 3【量子 Markov 链的双重平方加速】**（→ [3.2 节](#szegedy-phase-gap)） 1. 基础：用 $\cos\theta \approx 1 - \theta^2/2$ 验证 $\arccos(1-\delta) = \sqrt{2\delta}\,(1 + O(\delta))$，并取 $\delta = 10^{-4}$ 做数值检验；再写出 Gibbs 态相干编码 $|\pi_i\rangle$ 的定义，说明对它测量即得 $\pi_i$ 的样本。 2. 进阶：解释"相位隙 $\Delta_i = \Theta(\sqrt{\delta_i})$ + 相位估计 $O(1/\Delta_i)$"为何把制备/识别 $|\pi_i\rangle$ 的代价降到 $\widetilde{O}(1/\sqrt{\delta_i})$，并说明这与 Grover 搜索的开根号收益是同一种机制。 3. 进阶：设退火链每步的谱隙均为 $\delta$、比值 $\mu_i$ 均为常数、schedule 长为 $L$、总相对误差预算为 $\epsilon$。写出经典与量子的总调用数（含 $L$、$\delta$、$\epsilon$），并指出当 $\epsilon = \Theta(1)$ 常数时量子优势体现在哪些因子上。 > 提示：每步需要相对精度 $\epsilon/L$，把它代入 3.4 节每步代价公式后再乘以 $L$ 步。 **练习 4【相邻 Gibbs 态的 overlap 与比值提取】**（→ [4.1 节](#gibbs-overlap-identity)） 1. 基础：取两构型系统 $E = (0, 1)$、$\beta_0 = 0$、$\beta_1 = \ln 2$，直接按 $\sum_x \sqrt{\pi_0(x)\,\pi_1(x)}$ 计算 $\langle\pi_0|\pi_1\rangle$，再用命题 3 的恒等式核对。 2. 进阶：写出 4.3 节把 $Y_i$ 编入 ancilla 的受控旋转映射，并证明作用在 $|\pi_i\rangle \otimes |0\rangle$ 上后 ancilla 测得 $|1\rangle$ 的概率恰为 $\mu_i$；说明这一步为何让 3.3 节的振幅估计"落地"。 3. 进阶：推导命题 3 的 overlap 恒等式，并对 2.2 节的小例子数值验证 $\langle\pi_1|\pi_2\rangle$（计算 $Z$ 在 $\frac{3}{2}\ln 2$ 处的值）。 > 提示：$e^{-\frac{3}{2}\ln 2} = 2^{-3/2} = \frac{\sqrt{2}}{4}$，故 $Z(\frac{3}{2}\ln 2) = \frac{9}{8} + \frac{\sqrt{2}}{2}$。 **练习 5【Fortuin–Kasteleyn 展开与 Tutte/Jones】**（→ [5.1 节](#fortuin-kasteleyn)） 1. 基础：对两个顶点一条边的图取 $q = 3$、$v = 1$，分别按自旋求和与按子图求和两种方式计算 $Z_{\mathrm{Potts}}$，核对相等。 2. 进阶：沿命题 4 的步骤，把三角形图 $K_3$（3 顶点 3 条边）的 $Z_{\mathrm{Potts}}$ 分别按自旋求和与按子图求和两种方式算出来，核对相等。 3. 进阶：说明"Potts 配分函数 $\leftrightarrow$ 随机簇/Tutte 点值 $\leftrightarrow$ Jones 多项式"这条联系链，并解释为什么相关量子算法只承诺"特定参数曲线上的加性近似"，而不提供通用相对近似。 > 提示：$K_3$ 的 $2^3$ 个子图按 $|A| = 0, 1, 2, 3$ 分组时，连通分量数 $k(A)$ 分别为 $3, 2, 1, 1$。 **练习 6【张量网络振幅编码与误差尺度】**（→ [第 6 节](#tensor-network-amplitude)） 1. 基础：写出 block-encoding 的定义式 $(\langle 0| \otimes I)\, U_j\, (|0\rangle \otimes I) = T_j/\alpha_j$，并对正文例子 $T_1 = T_2 = \mathrm{diag}(2, \tfrac{1}{2})$ 计算 $\langle 0|T_2 T_1|0\rangle$ 与 $\langle 1|T_2 T_1|1\rangle$ 的归一化振幅，说明估计后者为何需要更多调用。 2. 进阶：一个张量网络收缩成 $m = n$ 个算子的乘积，每个 $\|T_j\| = 2$，而收缩值本身为 $1$。若要求最终绝对误差不超过 $0.1$，归一化振幅需要多高的加性精度？振幅估计的调用数随 $n$ 如何增长？这个例子说明了什么？ 3. 进阶：为什么"振幅估计是 $1/\epsilon$"不自动意味着"任何张量网络收缩都能量子多项式时间求到相对精度"？请结合第 6 节的误差尺度分析与第 5 节的保留条款作答。 > 提示：把归一化振幅的误差还原到原收缩值时要乘上尺度乘积 $\prod_j \alpha_j$。 **练习 7【整性承诺与精确结果】**（→ [第 7 节](#integrality-promise)） 1. 基础：复述整性承诺：若已知目标量取整数值且近似误差严格小于 $1/2$，解释为什么四舍五入给出唯一的精确值，并举出正文中依赖这一机制的结构化对象。 2. 进阶：解释为什么对可取值至 $M$ 的整数量，"绝对误差 $< 1/2$"相当于相对精度 $O(1/M)$，从而在振幅编码框架下调用数正比于 $M$ 的尺度；并说明整性舍入在哪两类情形下才真正高效。 > 提示：误差 $1/2$ 相对于量程 $M$ 即 $1/(2M)$；振幅估计的调用数是加性精度的倒数。 ## 参考文献与 Zoo 覆盖 - Zoo 121--122、265、471：Gibbs/annealing partition-function 算法与 [近无偏 sublinear 方法](https://arxiv.org/abs/2207.08643)。 - Zoo 3、112--113：Potts/Tutte、tensor network 与 spin-model circuit 映射。 - Zoo 45、47、67：Ising、cyclic-code exact Potts 与 knot 关联。