引言
这篇内容，继续物理中的计算理论部分。这次我们要给出任意不含外磁场的2维经典自旋模型的多项式时间的解。也就是说对于 size 为 n 的系统，不论是配分函数，基态能量都可以在 n 的多项式时间内给出。而这一结论和格点结构，相互作用的距离，大小等都无关，对于任意的 planar graph 都成立，因此是相当普适也相当非平庸的结论。下面的思路主要参考了 [1] 的第三部分。
对偶图上的对应
考虑 planar graph 上每个格点上的自旋自由度 \(S_i=\pm 1\)，定义系统的哈密顿量为 \(H=-\sum_{(i,j)\in E}J_{ij}S_iS_j\)。我们将尝试求出该系统的基态能量和配分函数。容易看出，如果给定一个构型，将所有的自旋反转，其能量是简并的。我们称其为一对等价构型。如果某边对应的 coupling J 为负，则称该边有 negative interaction。对于某边，如果自旋的构型使得该边贡献的能量为正，则称该边 unsatisfied，反之，称为 satisfied。
容易证明，一个具有奇（偶）数个 negative interaction 的 cycle，具有奇（偶）数个 unsatisfied 边。证明很简单，只需首先考虑该 cycle 上所有的自旋都同向，决定了 unsatisfied 边的奇偶性和 cycle 上 negative interaction 边奇偶性相同。之后不管怎么反转自旋，cycle 上 unsatisfied 边的奇偶性都保持不变。这种具有奇数个 negative interaction 边的 face，由于无法简单的满足所有边能量为负来实现基态，因此被称为 frustration。
[2] 给出了关于这种系统顶点上的自旋构型和 unsatisfied 边的一一对应关系。
一对自旋的等价构型和一组如下 unsatisfied 边的选取一一对应：边的选取满足，每个奇（偶）数个 negative interaction 的 cycle 上，有奇（偶）数个 unsatisfied 边。
更强的版本，只要求属于 cycle generating family 的 cycle 满足以上奇偶性要求即可。
证明前先看一些事实：
- 奇（偶）数个 frustrated 的 face 和若干 unfrustrated 的 face 组成的 (symmetry difference 意义下) cycle，是 (un)frustrated。
- 给定自旋构型，若干个 face 组成的 cycle 上的 unsatisfied 边数目的奇偶性，和原来这些 face 对应 cycle 的 unsatisfied 边总数的奇偶性相同。
证明充分性，给定自旋构型后，按照自旋标示出能量贡献为正的边作为 unsatisfied 边。这些边根据前边的说明，一定满足定理中的条件。反之必要性，给定一组满足条件的 unsatisfied 边，从随意指定第一个顶点的自旋出发，按照边的满足性，可以确定出所有顶点的自旋取向。这样自旋的相容性，可以通过上篇类似 FKT 定理的证明来保证。只不过这次，每删除一条对偶图上的边，需要对应删除顶点的 face 来保证对应原图该边的自洽性。根据事实1，2，每个 face 上的条件满足时，所有 cycle 上奇偶性条件自然得到满足。
有了这一对应的定理，我们就可以将二维系统顶点上自旋的构型，转换到对应的满足条件的 unsatisfied 边的集合的选取。而考虑格点图的对偶图，如果我们只在对偶图上保留对应原图 unsatisfied 边的话，我们就得到了如下图虚线所示的部分。图中的粗线表示负的 coupling，星和虚线都是对偶图的一部分。虚线横穿的都是 unsatisfied 边。
注意这些虚线构成的对偶图表示的是一个原图上的自旋构型，而不再是原图格点的意义。此时对应一个自旋构型解的限制条件变为， (un)frustrated 的 face 对应的顶点有奇（偶）数条边。
格点图的变换
我们将上小节得到的和自旋构型一一对应的满足限制条件的对偶图，转化为一个更容易处理的图。这个转化的起点是完整的对偶图，而非只有上节所示的虚线部分，我们把虚线对应的边依然叫做 unsatisfied 边。我们把对偶图中和 (un)frustrated face 对应的顶点，记为偶（奇）顶点。这一图的处理转化包括以下步骤。
-
变为 at most cubic 图。将所有度数大于3的顶点，做以下图所示的处理。如果被展开的顶点为偶顶点，那么展开后的顶点均为偶顶点；反之，则指定任意一个展开后的顶点为奇顶点。
注意这样操作后，对于每个新的顶点，依然保持了奇顶点发出奇数条 unsatisfied 边，偶顶点发出偶数条 unsatisfied 边的条件。
-
现在对于度数为3的奇顶点，做如下图的变换。
考虑到对于奇顶点，本来有奇数个 unsatisfied 边从此发出，那么每一种情形都会对应一个 perfect matching 如下图。
-
对于度数为3的偶顶点，做如下图的变换。
同样的对于偶顶点，perfect matching 与 unsatisfied 边的情况一一对应如下图。
-
类似的对于原图度数为2的偶顶点，一个顶点，变为一条路径连接的四个顶点；度数为2的奇顶点不变。关于原图度数为2的偶顶点的变形，[1] 并未提及，但似乎只有包括在内才正确。
通过以上四个步骤，原来的格点对偶图转变为了新图 \(G^\star\)，新图中有些边对应原来对偶图的边，我们在这些边上添加权重 \(\vert J_{ij}\vert\) （对偶边 cross 的原格点图的边为(i,j)），其他4步转换操作额外增加的边，我们将其权重记为0。那么我们就将二维任意图\(G\)上的2维自旋构型和图\(G^\star\)上的 perfect matching 建立起了一一对应。其中\(G^\star\)的非零权重 matching 边和\(G\)的 unsatisfied 边一一对应。
考虑到系统总能量为 \(H=-\sum_{(i,j)\in E} \vert J_{ij}\vert+2\sum_{(i,j)\in unsatisfied~edges} \vert J_{ij}\vert\)。这样对于求基态能量和构型的问题，我们只需最小化 \(G^\star\) 的 perfect matching 的 matching 边总权重即可。也即 Minimum weight perfect matching 问题。回忆无向图的最大权重匹配算法中提到的 Maximum weight matching 问题的多项式解决算法。想利用那里的 blossom 算法解决现在的问题，需要两个转换。第一是 Maximum 到 Minimum，这个比较容易，只需要把所有边的权重取相反数即可。第二是添加 perfect matching 的限制。回忆以前我们说过的 max weight matching 不代表是 max cardinality matching。想解决这一点，只需在每个边上的权重额外加上现在所有边的权重和。那么在新权重下分析 max weight matching，自动保证了是 max weight perfect matching。就此，我们解决了二维自旋系统的基态能量问题，所有的步骤都具有多项式时间复杂度算法。如果不嫌麻烦，也可以重新从 [3] 的 primary algorithm 来解决 max weight perfect matching 的问题。这一问题从 LP 对偶的 primary problem 这边先满足来推进，因此从算法初始就是 perfect matching，运行细节和 Edmonds‘ 算法异曲同工。
最后再看配分函数问题的多项式时间解决。令 \(G^\star\) 上的每边对应邻接矩阵中的项为 \(\pm e^{-\beta w_{ij}}\)，其中的正负号，由平面图 \(G^\star\) 上的 Pfaffian Orientation 决定。那么根据上篇内容，易知在这样定义的邻接矩阵 B 上求 Pfaffian，就正好得出了配分函数。事实上 Pfaffian 展开项 \(e^{-\beta E}\) 前边的系数，就代表了 perfect matching 权重为 \(E\) 的构型的总数目。而配分函数为
\[Z(\beta)=2e^{-\beta\sum_{(i,j)\in E}\vert J_{ij}\vert}Pf(B)\]至此我们完全解决了二维自旋系统的统计问题。
一些讨论
周期性边界条件
同样的自旋系统也可以定义在周期性边界条件的格子上。这时需要额外注意 unsatisfied edge 和自旋构型一一对应的条件。条件中的来自 cycle generating family 的 (un)frustrated cycle，多出了两个 topological nontrivial loop。不失一般性，假设对应的哈密顿量在这两个 cycle 上都是 unfrustrated，那么根据一一对应的条件，这两个 cycle 的 unsatisfied edge 也就是对偶图上穿过这两个 cycle 的 unsatisfied 边都是偶数。用上篇内容的语言，只有 (e,e) 构型中的 perfect matching 才和自旋构型一一对应。其对应的配分函数是\(Z\propto \frac{1}{4} \sum_{i=1}^4Pf(B_i)\) ([1] 中这里的计算似乎也有些问题，其计算进了两个 nontrivial cycle 是否 satisfied 的所有情况)。
NP 完全问题的分析
我们看一下对于之前分析的两个NP完全的物理系统，以上算法如何 break down。对于有外磁场的系统，从 unsatisfied 边和自旋构型的一一对应就开始不成立，因此以上所有的分析都不适用。而对于三维自旋系统，由于其无法实现 Pfaffian orientation，因此无法在多项式的时间内计算出 perfect matching 可能的数目或者是配分函数。另一方面，在图的转换中，topological nontrivial cycle 又给 perfect matching 加入了进一步的限制，使得多项式时间的 Edmonds’ 算法无法在这种有大量额外限制的 perfect min weight matching 问题中使用。因此基态能量判别问题也是 NP 完全的。
Reference
- F. Barahona, On the computational complexity of Ising spin glass models, J. Phys. A: Math. Gen 15, 3241 (1982).
- I. Bieche, R. Maynard, R Rammal, and J. P. Uhry, Frustration model by graph matching method , J. Phys. A: Math. Gen. 13 2553 (1980).
- W. H. Cunningham and A. B. Marsh, A primal algorithm for optimum matching , Mathematical Programming Study, 8 50 (1978).
EOF