摘要：自旋玻璃是一类特殊的磁性材料，其特征在于无序（disordered）的磁相互作用（或外场）和“阻挫”（Frustration）现象，导致在低温下磁矩既不像铁磁体那样有序排列，也不像反铁磁体那样规则交错，而是被“冻结”在一种看似随机却又高度关联的复杂状态，缺乏长

自旋玻璃是一类特殊的磁性材料，其特征在于无序（disordered）的磁相互作用（或外场）和“阻挫”（Frustration）现象，导致在低温下磁矩既不像铁磁体那样有序排列，也不像反铁磁体那样规则交错，而是被“冻结”在一种看似随机却又高度关联的复杂状态，缺乏长程磁有序。理解自旋玻璃的物理性质对于统计物理、凝聚态物理乃至组合优化、神经网络等领域都具有重要意义。

1975年，S.F. Edwards 和 P.W. Anderson 提出了一个简洁的理论模型——EA模型，用以描述自旋玻璃的特性。

我们考虑一个二维正方晶格，每个格点 上有一个Ising自旋变量 ，它只能取两个方向：向上或向下。 自旋之间的相互作用通常被限制在晶格最近邻的自旋对 之间。每个这样的自旋对之间的相互作用强度由一个耦合常数 描述。

EA模型的关键之处在于， 的值是随机的。例如，它可以从一个高斯分布 中抽取，或者以一定概率取 （铁磁性，倾向于使自旋平行）和 （反铁磁性，倾向于使自旋反平行）。这种随机性是“淬火”（quenched）的，意味着一旦为每对相互作用的 选定了值，它们就固定不变了，不会随时间或温度而改变，也不依赖于自旋的构型。这就像材料在制造过程中形成的内部缺陷和杂质是固定的一样。

系统的总能量，即哈密顿量 ，由所有相互作用的能量加总而成：

其中 表示对所有最近邻自旋对求和。这个公式的含义是：当 时，能量降低，系统更稳定；反之，能量升高。

自旋玻璃的核心特征是阻挫。当系统中的相互作用无法同时被满足时，就会产生阻挫。

在二维正方晶格中，我们可以通过考察最小的闭合回路——“小方格”（plaquette）来理解阻挫。对于一个小方格 ，我们计算其边界上四个键的耦合常数之积的符号：

其中 表示小方格 的边界上的键集合。

如果 ，该小方格是“非阻挫”的。这意味着小方格内有偶数个反铁磁键，我们可以通过合适地配置自旋方向，使得所有四个键的能量贡献都为负（即所有键都被“满足”），从而达到局部能量最低。

如果 ，该小方格是“阻挫”的。这意味着小方格内有奇数个反铁磁键。此时，无论我们如何配置四个角的自旋，都不可能让所有四个键同时被满足。必然至少有一个键处于“不满足”状态，即其能量项 为正值，对总能量造成“惩罚”。

图示：非阻挫小方格（左）与阻挫小方格（右）。

阻挫的存在，使得系统的能量景观变得异常崎岖，充满了大量的局部极小值（亚稳态），这正是自旋玻璃动力学缓慢、性质复杂的原因。

物理学家最关心的问题之一是找到系统的基态——即能量最低的自旋构型 。然而，对于一个有 个自旋的系统，存在 种可能的构型。通过穷举来寻找基态的计算量随 指数增长，这在计算上是不可行的。

事实上，寻找三维EA模型（以及许多其他自旋玻璃模型）的基态已被证明是一个NP-hard问题。通俗地说，对于NP问题而言，这意味着我们目前无法找到一个通用的高效算法，能够在多项式时间内（即计算时间按 增长，而非）精确求解该问题（除非P=NP成立）。 NP-complete 问题是NP问题中最困难的一类，但其特点是验证解的正确性相对简单。而NP-hard问题的计算难度至少与NP-complete问题相当，但它本身不一定属于NP问题。这意味着NP-hard问题不仅难以找到解，甚至可能连"快速验证给定解的正确性"都无法做到。

然而，当我们将目光投向二维平面时，情况出现了转机。对于没有外磁场、且相互作用仅限于平面晶格（planar graph）上的最近邻的二维EA模型，其基态求解问题是可以在多项式时间内精确解决的！这使得二维EA模型成为了一个既能体现自旋玻璃核心复杂性（无序与阻挫），又能进行精确计算的理想“玩具模型”。

其求解方法，是物理学与图论精妙结合的典范，它将寻找基态的问题巧妙地转化为了一个经典的图论问题——最小权完美匹配（Minimum Weight Perfect Matching）。这个方法主要由Bieche等人 (1980) 以及后续Barahona, Maynard, Rammal, Uhry (1982) 等人发展和完善。

一个图的完美匹配（Perfect Matching）是指图的一个边子集，其中图的每个顶点都恰好是这个子集中一条边的端点。而最小权完美匹配就是所有完美匹配中，边的权重之和最小的那个。这个问题属于著名的 P 类问题（即存在多项式时间算法），可以被高效求解。

蓝线代表下图的一个完美匹配：

图示：所有蓝线标记的边构成此图的一个完美匹配。

我们的目标是最小化哈密顿量 。一个键 的理想能量贡献是 ，这发生在该键被“满足”时（即 ）。如果系统没有阻挫，基态能量将是 。

然而，阻挫的存在迫使一些键处于“不满足”的状态。一个不满足的键 的能量贡献是 ，相比理想状态，这带来了 的能量惩罚。因此，寻找基态等价于：选择一个自旋构型，使得总的能量惩罚 不满足的键 最小。

这里的关键约束来自阻挫。可以严格证明：

在任何自旋构型下，一个非阻挫小方格的边界上，必然有偶数个不满足的键。

在任何自旋构型下，一个阻挫小方格的边界上，必然有奇数个不满足的键。

这是因为，如果我们定义一个变量 ，那么当 时，键 得到满足，而当 时，键 处于不满足的状态。对于任意一个小方格 ，我们有 (因为每个自旋在小方格边界上出现两次，其影响抵消)。 因此，。 这个简单的代数关系蕴含了深刻的几何约束：如果 (阻挫小方格)，则小方格上必须有奇数个不满足的键；如果 (非阻挫小方格)，则必须有偶数个不满足的键。

现在，让我们换一个视角来思考。引入原始晶格的对偶晶格（Dual Lattice）：原始晶格的每个小方格，成为对偶晶格的一个顶点；原始晶格中每条相邻小方格共享的边，对应一条连接这两个对偶顶点的对偶边。

图示：灰线代表原始晶格的边，而蓝线代表对偶晶格的边。

在这个对偶晶格上，我们可以将“不满足的键”想象成一条被“激活”的对偶边。上述的奇偶约束就变成了一个非常直观的图论规则：

在代表“阻挫小方格”的对偶顶点处，必须汇集奇数条激活的对偶边。

在代表“非阻挫小方格”的对偶顶点处，必须汇集偶数条激活的对偶边。

在图论中，一个顶点的“度”（degree）是指连接到它的边的数量。因此，我们寻找的“不满足键”的集合，在对偶图上构成了一个子图，其中所有“阻挫对偶顶点”的度为奇数，所有“非阻挫对偶顶点”的度为偶数。

一个基本的图论事实是：任何图中，奇度顶点的数量必然是偶数。在我们的问题中，这些奇度顶点就是所有的“阻挫对偶顶点”。因此，由“不满足的键”对应的激活对偶边构成的子图，必然是由若干条连接这些奇度顶点（阻挫小方格）的“路径”和若干个“闭合回路”组成。为了让总能量惩罚（即激活边的总权重）最小，我们显然不应引入任何不必要的闭合回路。

举一个简单的例子，位点 和 代表两个阻挫对偶顶点（必须汇集奇数条激活边），而位点 代表非阻挫对偶顶点（必须汇集偶数条激活边）。不满足的键在原始晶格上用红边表示，其对应的激活对偶边用蓝色表示。假如我们只激活路径 和 ，那么在对偶顶点处： 和 的度为1（奇数），满足约束； 和 的度也为1（奇数），但这违反了它们作为非阻挫顶点必须有偶数度的约束。

图示：位点 和 代表两个阻挫对偶顶点。不满足的键在原始晶格上用红边表示，其对应的激活对偶边用蓝色表示。

为了修正这个问题，我们必须引入更多的激活边。例如，再激活 和 。这样一来，图中所有顶点的度都满足了奇偶性约束： 和 的度仍为1（奇数），而 的度都变为了2（偶数）。最终，对偶点 和 通过一条路径 被“匹配”了起来，其代价是引入了4条不满足的键。

图示：阻挫对偶顶点 和 通过一条路径 被“匹配”了起来。

下图展示了一个耦合常数遵循标准高斯分布的EA模型的原始晶格（浅灰色网格，正耦合为直线，负耦合为波浪线）及其对偶晶格（蓝色）。蓝色圆圈标记出所有“阻挫对偶顶点”。这些顶点是最小权完美匹配问题图的节点。蓝色实线代表连接每一对阻挫对偶顶点的最短路径（不同的路径可能会重合在一起）。这些路径共同构成了一个完全图。为了找到总能量惩罚最小的方案，我们需要找到一种配对方式，使得连接每对顶点的最短路径（路径权重由定义）的总长度最小。

图示：一个耦合常数遵循标准高斯分布的EA模型的原始晶格（浅灰色网格，其中正耦合为直线，负耦合为波浪线）及其对偶晶格（蓝色）。蓝色圆圈标记出所有阻挫对偶顶点。蓝色实线代表连接每一对阻挫对偶顶点的最短路径（不同的路径可能会重合在一起）。所有阻挫对偶顶点及其之间的最短路径构成一个完全图 。

图 通常是一个完全图，因为任意两个阻挫小方格（对应的对偶顶点）之间都存在至少一条对偶路径。计算所有这些权重需要运行全源最短路径算法（例如在对偶晶格 上运行Floyd-Warshall 算法，其复杂度为 ，其中 是对偶晶格中顶点的总数，即原始晶格中小方格的总数）。

因此，最优解必然是由一系列连接“阻挫对偶顶点”的路径构成，我们必须将所有的“阻挫对偶顶点”两两配对，并用最短路径将它们连接起来（在对偶晶格上，路径长度由穿过的原始键的 之和定义）。整个问题由此转化为寻找一种最优的配对方式。

这正是最小权完美匹配问题：

构造图：构建一个新图 ，其顶点集合就是所有“阻挫对偶顶点”。

定义权重：这是一个带权重的完全图。连接 中任意两个顶点 的边的权重 ，定义为它们在对偶晶格中对应的两个对偶顶点之间的最短路径距离。这里的路径距离是以穿过的原始键的 之和来计算的。

求解：找到这个图 的一个最小权完美匹配，即找到一种配对方式，使得所有配对边的权重之和（也就是所有最短路径的总长度）最小。

幸运的是，图论中已经存在解决最小权完美匹配问题的高效多项式时间算法。最著名的是 Jack Edmonds 在1965年提出的“blossom 算法”。它是第一个被证明能在多项式时间内解决一般图（非二分图）的最小权完美匹配问题的算法。它的核心思想极具创造性，巧妙地处理了在一般图中寻找匹配时最棘手的障碍——奇数长度的环（odd cycles）。对于一个有 个顶点（这里 是阻挫小方格的数量，即图 的顶点数，不包括可能的额外顶点，或指实际参与匹配的顶点数）和 条边的图 ，这些算法的复杂度大约是 ，这远好于指数级。值得注意的是，（阻挫小方格的数量）通常远小于系统总自旋数 。因此，即使对于规模很大的晶格，只要阻挫小方格的数量在可控范围内，我们依然能够高效地求得精确基态。

在图论中，许多匹配问题是通过寻找“增广路径”（Augmenting Path）来解决的。对于一个已有的匹配 （图的边的一个子集，其中没有两条边共享同一个顶点），一条增广路径是一条连接两个未匹配顶点的路径，其路径上的边交替地属于 和不属于 。

图示：一条增广路径。黑边不在当前匹配M中，蓝边在M中。通过沿着此路径将“在M中”和“不在M中”的边互换，我们可以得到一个更大的匹配（3条蓝边），从而使未匹配的顶点减少两个。

找到一条增广路径，我们就可以通过“翻转”路径上边的匹配状态（将路径上原属于 的边移出 ，并将原不属于 的边加入 ），使得匹配的规模增加1，从而向完美匹配更近一步。

这个策略的理论基石是图论中的一个基本定理——贝尔热引理（Berge's Lemma）。它指出：一个匹配 是最大匹配，当且仅当图中不存在 -增广路径。这个引理告诉我们一个非常清晰的事实：任何一个匹配，要么它已经是最大匹配，要么它就一定能被一条增广路径所扩大。

这个引理为我们指明了方向：寻找最大匹配的过程，就是不断寻找增广路径并扩大当前匹配的过程。从一个空匹配开始，反复执行“寻找-翻转”操作，直到图中再也找不到任何增广路径，此时得到的匹配就一定是最大匹配。

对于没有奇数长度环的二分图，上述寻找增广路径的策略（例如使用广度优先或深度优先搜索）可以被直接有效地执行。然而，当图含有奇数长度的环（Odd Cycle）时，情况变得异常棘手。

当增广路径的搜索算法进入一个奇数环时，会遇到一个无法用简单交替规则处理的“逻辑死结”。想象我们从一个未匹配的顶点出发，构建一棵交替路径树（树根是未匹配点，第一层边是非匹配边，第二层是匹配边，以此类推）。如果搜索过程中，我们发现一条非匹配边连接了树上两个已经存在的、且处于同一层的顶点，那么一个奇数环就被发现了。

这个奇数环就像是匹配算法中的“阻挫”：你无法沿着它走一圈并保持“非匹配-匹配-非匹配...”的完美交替模式回到起点。这使得简单的搜索算法在此处碰壁，无法确定下一步该如何扩展路径，从而导致算法失效。

Jack Edmonds的贡献在于他找到了处理奇数环的方法。他的想法是：既然奇数环是麻烦的根源，那我们就暂时把它“捏”成一个点，让它在更高层次上消失！这个被收缩的奇数环，就被称为“花朵”（Blossom）。

Blossom算法的精髓可以分解为以下几个步骤：

1. 构建交替路径树: 从一个未匹配的顶点开始，通过广度优先搜索构建一棵交替路径树，尝试找到通往另一个未匹配顶点的增广路径。

2. 发现并收缩“花朵”: 在搜索过程中，一旦发现上述连接同层顶点的非匹配边，从而识别出一个奇数环（花朵），算法就立即执行收缩（Contraction）操作。它将花朵中的所有顶点视为一个单一的“超级顶点”，并将所有原本连接到花朵内部的边，重新连接到这个超级顶点上。这样，我们就得到了一个规模更小、且暂时消除了那个特定奇数环的新图。算法接着在这个收缩后的图上继续寻找增广路径。这个过程可以递归进行，一个大花朵内部可能还包含着被收缩的小花朵。

图示：搜索交替路径时，发现一条非匹配边（红色虚线）连接了树上同一分支的两个顶点，形成了一个奇数环（5个顶点）。这个环就是一个“花朵”。 Blossom算法将整个环收缩成一个单一的“超级顶点”。

3. 路径提升与“花朵”展开: 算法的真正威力体现在它如何处理在收缩图上找到的路径。

如果在收缩后的图中找到了增广路径，我们需要将这条路径“提升”（Lift）回原始图。

如果路径不经过超级顶点，那么它在原始图中也有效。

如果路径穿过了超级顶点，我们就需要“展开”（Expand）这个花朵。这意味着我们需要在原始的奇数环中，找到一条合适的内部路径片段，来连接进入和离开超级顶点的那两条边。由于奇数环的结构特性——它有一个顶点是“柄”（stem，路径进入花朵的地方），内部有一条匹配边——我们总能从柄出发，沿着环的两个方向选择其一，构造出一条能保持整条路径“交替”性质的子路径。

图示：如果在收缩图（上）中找到了经过超级顶点的增广路径，我们需要将其提升回原始图（中，下）。通过展开花朵，我们可以沿着环找到一条正确的交替路径（红色路径)，从而将进入和离开的路径片段无缝连接成一条完整的增广路径。

4. 迭代与终止: 重复“寻找-收缩-提升-翻转”的完整过程，直到图中再也找不到任何增广路径。根据贝尔热引理，此时得到的匹配即为最大匹配。

以上描述的是寻找最大匹配（unweighted）的基本思想。而我们面对的物理问题，是更复杂的最小权完美匹配。加权版本的Blossom算法在此基础上，引入了线性规划中的“对偶理论”。它不仅仅是寻找任意一条增广路径，而是通过维护一套精巧的“对偶变量”（可以看作是分配给每个顶点的潜在成本），来寻找能使总权重改善最大的“负成本”增广路径。

尽管技术细节（如对偶变量的更新、花朵收缩时权重的处理）要复杂得多，但其算法的骨架——通过收缩和展开“花朵”来动态处理奇数环——是完全一致的。正是这一核心机制，使得算法能够在一般图的复杂结构中，依然高效地找到最优解。

一旦通过算法找到了这个最小权完美匹配，其总权重（即所有匹配路径的 权重之和）设为 ，我们就得到了基态的信息。基态能量 可以通过以下简洁的公式计算：

第一项是系统在没有任何阻挫、所有键都被满足的情况下的理想能量。

第二项是为满足所有阻挫约束所必须付出的最小能量惩罚。因子 的来源是，每个不满足的键的能量从 变为 ，能量惩罚为 。 正是这些路径上所有 的最小总和。

通过这一系列巧妙的转化，一个看似棘手的统计物理问题，被优雅地归结为一个可以在计算机上高效求解的图论问题。研究这些基态特性，有助于我们理解无序系统在低温下的独特性质。例如，我们可以研究系统对微小扰动的响应（如改变某个 的值，基态构型会如何变化），进而计算其刚度系数，并确定其相变的临界维度。

此外，这种“物理问题图论化”的思想也出现在其他领域，例如任意维随机场伊辛模型的基态能够转化为最小割（minimal cut）问题，任意维超立方晶格上的硬球模型基态能够转化为最大匹配（maximum matching）问题等。

参考文献（滑动查看）

[1] Edwards, Samuel Frederick, and Phil W. Anderson. "Theory of spin glasses." Journal of Physics F: Metal Physics 5.5 (1975): 965.

[2] Barahona, F., Maynard, R., Rammal, R. & Uhry, J. P. Morphology of ground states of two-dimensional frustration model. Journal of Physics A: Mathematical and General **15**, 673 (1982).

[3] Barahona, F. On the computational complexity of Ising spin glass models. Journal of Physics A: Mathematical and General **15**, 3241 (1982).

[4] Hartmann, A. K., Bray, A. J., Carter, A. C., Moore, M. A. & Young, A. P. Stiffness exponent of two-dimensional Ising spin glasses for nonperiodic boundary conditions using aspect-ratio scaling. Phys. Rev. B **66**, 224401 (2002).

[5] Edmonds, J. Paths, trees, and flowers. Canadian Journal of Mathematics **17**, 449–467 (1965).

[6] Cook, W. & Rohe, A. Computing minimum-weight perfect matchings. INFORMS Journal on Computing **11**, 138–148 (1999).

[7] Hartmann, H., Alexander and H. Rieger. Optimization algorithms in physics ||. **10.1002/3527600876**, (2001).

[8] Rychkov, S. Lectures on the Random Field Ising Model: From Parisi-Sourlas Supersymmetry to Dimensional Reduction. IX + 64 (Springer Cham, 2023). doi:[10.1007/978-3-031-42000-9](https://doi.org/10.1007/978-3-031-42000-9).

[9] [Blossom 算法 - 维基百科 --- Blossom algorithm - Wikipedia](https://en.wikipedia.org/wiki/Blossom_algorithm)

来源：中科院物理所一点号