我们给出在阈值秩低或环长大的图上对自旋模型进行近似计数和抽样的算法。设 $G$ 为 $n$ 节点图，记 $k_\eta(G)$ 为归一化拉普拉斯特征值严格小于 $\eta$ 的个数。
若 $\varepsilon>0$，$\varepsilon$‑近似计数算法输出 $\widehat Z$ 满足 $(1-\varepsilon)Z\le \widehat Z\le(1+\varepsilon)Z$，成功概率至少 $3/4$。$\varepsilon$‑近似抽样算法产生的配置与目标分布的全变差距离不超过 $\varepsilon$。
结果概述
(a) 强磁性 Potts 模型。固定 $q\ge2$ 与 $\eta\in(0,1]$，存在 $\beta_0(q,\eta)$，当逆温 $\beta\ge\beta_0$ 时，零场 $q$‑状态 Potts 模型可近似计数与抽样：
- 任意图上时间 $\exp(O(k_\eta))\operatorname{poly}(n,1/\varepsilon)$；
- 对任意 $\Delta\ge3$，在 $\Delta$‑正则、环长为 $g$ 的图上时间 $\exp(O(n e^{-g}))\operatorname{poly}(n,1/\varepsilon)$。
(b) 二分图硬核模型。固定 $\Delta\ge3$ 与 $\eta\in(0,1]$，存在 $\lambda_0(\Delta,\eta)$，当活度 $\lambda\ge\lambda_0$ 时，硬核模型可近似计数与抽样：
- 在 $\Delta$‑正则、顶点传递的二分图上时间 $\exp(O(k_\eta))\operatorname{poly}(n,1/\varepsilon)$；
- 在 $\Delta$‑正则、环长为 $g$ 的二分图上时间 $\exp(O(n e^{-g}))\operatorname{poly}(n,1/\varepsilon)$。
所有四个结果均来源于新框架 C‑3PO 的假设验证。C‑3PO 的核心思路是枚举小割并通过簇展开重构原始测度，底层利用主动回归改进子空间枚举方法。
点评