# 配分函数量子算法：退火比值、Gibbs 态、Tensor Network 与 Potts/Tutte

配分函数

$$
Z(\beta)=\sum_{x\in\Omega}e^{-\beta E(x)}
$$

同时归一化 Gibbs 分布、编码自由能并计数组合对象。直接求和有指数项；量子算法有两条主线：沿退火路径估计相邻 $Z$ 比值，或把特定模型/张量网络的归一化 contraction 编成量子振幅。本课推导两条路线，并区分相对近似、加性近似和复参数值。

## 1. 从 Gibbs 分布到自由能

Gibbs 分布

$$
\pi_\beta(x)=\frac{e^{-\beta E(x)}}{Z(\beta)}.
$$

自由能 $F=-\beta^{-1}\log Z$，期望能量

$$
-\frac{d}{d\beta}\log Z(\beta)
=\mathbb E_{\pi_\beta}[E].
$$

若 $\beta=0$，$Z(0)=|\Omega|$ 通常已知；目标是在 $\beta_L=\beta$ 估计 $Z(\beta)$。

## 2. Annealing schedule 的乘积恒等式

选择

$$
0=\beta_0<\beta_1<\cdots<\beta_L=\beta.
$$

相邻比值

$$
\frac{Z(\beta_{i+1})}{Z(\beta_i)}
=\sum_x\pi_{\beta_i}(x)
e^{-(\beta_{i+1}-\beta_i)E(x)}
=\mathbb E_{\pi_i}[Y_i],
$$

其中 $Y_i=e^{-\Delta\beta_iE}\in[0,1]$（能量平移后）。于是

$$
Z(\beta)=Z(0)
\prod_{i=0}^{L-1}\mu_i,\qquad
\mu_i=\mathbb E_{\pi_i}[Y_i].
$$

若 schedule 太粗，$\mu_i$ 极小、方差爆炸；cooling schedule 要保证相邻 Gibbs 分布 overlap 足够大，常用条件是比值或相对方差有常数界。

## 3. 经典 MCMC 与量子 Markov 链

经典算法用以 $\pi_i$ 为稳态的可逆 Markov chain $P_i$ 采样。若 spectral gap 为 $\delta_i$，mixing 典型需 $\widetilde O(1/\delta_i)$ 步；估计均值误差 $\epsilon$ 还需 $O(1/\epsilon^2)$ 有效样本。

Szegedy quantization 把 $P_i$ 变成量子 walk $W_i$，其 phase gap

$$
\Delta_i=\Theta(\sqrt{\delta_i}).
$$

稳态 coherent encoding

$$
|\pi_i\rangle
=\sum_x\sqrt{\pi_i(x)}|x\rangle
$$

是零相位本征态。Phase detection/reflection 可在 $\widetilde O(1/\sqrt{\delta_i})$ walk calls 内投影/反射稳态；amplitude estimation 把均值精度从 $1/\epsilon^2$ 降到 $1/\epsilon$。这产生 gap 与精度上的双重平方改善。

## 4. 从一个 Gibbs 态移动到下一个

相邻 coherent Gibbs states overlap

$$
\langle\pi_i|\pi_{i+1}\rangle
=\frac{Z((\beta_i+\beta_{i+1})/2)}
{\sqrt{Z(\beta_i)Z(\beta_{i+1})}}.
$$

平滑 schedule 使其不太小。可用一系列投影（quantum Zeno）、固定点振幅放大或 walk reflection，将 $|\pi_i\rangle$ 转成 $|\pi_{i+1}\rangle$。同时相干计算 $Y_i(x)$ 并旋转 ancilla：

$$
|x\rangle|0\rangle
\mapsto|x\rangle
(\sqrt{Y_i(x)}|1\rangle+\sqrt{1-Y_i(x)}|0\rangle),
$$

ancilla 成功概率就是 $\mu_i$，amplitude estimation 给比值。

旧方法测量后会破坏 $|\pi_i\rangle$，导致每次重新制备。2023 年近无偏 phase/amplitude/mean estimator 控制 bias 与方差，并近似不破坏输入态，使同一 annealing state 可复用，改善 schedule 长度依赖并得到 sublinear-in-log-state-space 结果。

## 5. Potts、Random Cluster 与 Tutte

$q$-state Potts model 在图 $G=(V,E)$ 上

$$
Z_{\rm Potts}
=\sum_{\sigma:V\to[q]}
\prod_{(u,v)\in E}
e^{\beta J_{uv}[\sigma_u=\sigma_v]}.
$$

Fortuin--Kasteleyn 展开把它写成

$$
Z_G(q,v)
=\sum_{A\subseteq E}
q^{k(A)}v^{|A|},
$$

其中 $k(A)$ 是子图 $(V,A)$ 的连通分量数。这是 Tutte polynomial 的一条参数曲线；Jones polynomial 也在平面图/medial link 构造下连接 Tutte 点。

对某些复参数，Aharonov 等把 deletion--contraction/Temperley--Lieb 表示编成酉或近酉 tensor maps，量子电路估计归一化 contraction，给**加性**近似。复杂度与图宽、边数和局部算子范数乘积有关，不等于正温度 ferromagnetic partition function 的通用 FPRAS。

## 6. Tensor network contraction 作为振幅

一般 tensor network 的 contraction 可排序为线性映射乘积

$$
T=T_m\cdots T_1.
$$

对每个非酉 $T_j$ 选尺度 $\alpha_j\ge\|T_j\|$ 并嵌入 block unitary $U_j$：

$$
(\langle0|\otimes I)U_j(|0\rangle\otimes I)
=T_j/\alpha_j.
$$

连续 postselection ancilla 全 0 的振幅为

$$
\frac{\operatorname{Contr}(\mathcal T)}
{\prod_j\alpha_j}.
$$

Hadamard/amplitude estimation给归一化 contraction 的加性估计。若 $\prod_j\alpha_j$ 指数大，回到原量的误差也指数大；算法的“非平凡精度”必须相对这个自然尺度陈述。

## 7. 特殊 exact 结果与权枚举

某些 irreducible cyclic codes 的 weight enumerator 可由有限域 Gauss sums 高效估计/重构，而 Potts partition function 又与对应 cocycle-code graph 的 weight enumerator 相连。在额外整性与误差小于半个整数的承诺下，可从高精度近似舍入得到 exact 值。

这只覆盖高度结构化图族，不应推广成任意 Potts exact 算法。Ising partition function 与量子电路振幅的映射也常落在复耦合/特定图上，其困难性和可模拟 gate set 随参数变化。

## 8. 小结与习题

- Annealing 把 $Z$ 写成相邻 Gibbs 期望的乘积。
- Quantum walk 将 Markov gap 依赖平方改善，amplitude estimation 改善精度依赖。
- Potts/FK 展开连接 Tutte polynomial，特定参数可编入拓扑/张量网络量子电路。
- 加性误差尺度和输入模型决定算法是否给实际相对信息。

1. 推导相邻 $Z$ 比值与 Gibbs 期望恒等式。
2. 推导 coherent Gibbs states 的 overlap。
3. 从 Potts 边因子展开得到 random-cluster 公式。
4. 解释 block-encoding 尺度乘积为何进入 contraction 误差。

## 参考文献与 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 关联。