配分函数量子算法：退火比值、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，特定参数可编入拓扑/张量网络量子电路。
加性误差尺度和输入模型决定算法是否给实际相对信息。

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

参考文献与 Zoo 覆盖¶

Zoo 121--122、265、471：Gibbs/annealing partition-function 算法与近无偏 sublinear 方法。
Zoo 3、112--113：Potts/Tutte、tensor network 与 spin-model circuit 映射。
Zoo 45、47、67：Ising、cyclic-code exact Potts 与 knot 关联。