－作者簡介－

周健文，中國科學院理論物理研究所 2021級博士研究生

導師：周海軍 研究員

研究方向：統計物理與復雜系統

自旋玻璃是一類特殊的磁性材料，其特征在于無序（disordered）的磁相互作用（或外場）和“阻挫”（Frustration）現象，導致在低溫下磁矩既不像鐵磁體那樣有序排列，也不像反鐵磁體那樣規則交錯，而是被“凍結”在一種看似隨機卻又高度關聯的復雜狀態，缺乏長程磁有序。理解自旋玻璃的物理性質對于統計物理、凝聚態物理乃至組合優化、神經網絡等領域都具有重要意義。

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

EA模型：一個無序的世界

我們考慮一個二維正方晶格，每個格點 上有一個Ising自旋變量 ，它只能取兩個方向：向上（ ）或向下（ ）。 自旋之間的相互作用通常被限制在晶格最近鄰的自旋對 之間。每個這樣的自旋對之間的相互作用強度由一個耦合常數 描述。

EA模型的關鍵之處在于， 的值是隨機的。例如，它可以從一個高斯分布 中抽取，或者以一定概率取 （鐵磁性，傾向于使自旋平行）和 （反鐵磁性，傾向于使自旋反平行）。這種隨機性是“淬火”（quenched）的，意味著一旦為每對相互作用的 選定了值，它們就固定不變了，不會隨時間或溫度而改變，也不依賴于自旋的構型。這就像材料在制造過程中形成的內部缺陷和雜質是固定的一樣。

系統的總能量，即哈密頓量 ，由所有相互作用的能量加總而成：

其中 表示對所有最近鄰自旋對求和。這個公式的含義是：當 時，能量降低，系統更穩定；反之，能量升高。

核心矛盾：“阻挫”現象

自旋玻璃的核心特征是阻挫。當系統中的相互作用無法同時被滿足時，就會產生阻挫。

在二維正方晶格中，我們可以通過考察最小的閉合回路——“小方格”（plaquette）來理解阻挫。對于一個小方格 ，我們計算其邊界上四個鍵的耦合常數之積的符號：

其中 表示小方格 的邊界上的鍵集合。

• 如果 ，該小方格是“非阻挫”的。這意味著小方格內有偶數個反鐵磁鍵，我們可以通過合適地配置自旋方向，使得所有四個鍵的能量貢獻都為負（即所有鍵都被“滿足”），從而達到局部能量最低。

• 如果 ，該小方格是“阻挫”的。這意味著小方格內有奇數個反鐵磁鍵。此時，無論我們如何配置四個角的自旋，都不可能讓所有四個鍵同時被滿足。必然至少有一個鍵處于“不滿足”狀態，即其能量項 為正值，對總能量造成“懲罰”。

圖示：非阻挫小方格（左）與阻挫小方格（右）。

阻挫的存在，使得系統的能量景觀變得異常崎嶇，充滿了大量的局部極小值（亞穩態），這正是自旋玻璃動力學緩慢、性質復雜的原因。

基態求解：一個NP難題？

物理學家最關心的問題之一是找到系統的基態——即能量最低的自旋構型 。然而，對于一個有 個自旋的系統，存在 種可能的構型。通過窮舉來尋找基態的計算量隨 指數增長，這在計算上是不可行的。

事實上，尋找三維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 算法，其復雜度為 ，其中 是對偶晶格中頂點的總數，即原始晶格中小方格的總數）。

因此，最優解必然是由一系列連接“阻挫對偶頂點”的路徑構成，我們必須將所有的“阻挫對偶頂點”兩兩配對，并用最短路徑將它們連接起來（在對偶晶格上，路徑長度由穿過的原始鍵的 之和定義）。整個問題由此轉化為尋找一種最優的配對方式。

這正是最小權完美匹配問題：

1. 構造圖：構建一個新圖 ，其頂點集合就是所有“阻挫對偶頂點”。

2. 定義權重：這是一個帶權重的完全圖。連接 中任意兩個頂點 的邊的權重 ，定義為它們在對偶晶格中對應的兩個對偶頂點之間的最短路徑距離。這里的路徑距離是以穿過的原始鍵的 之和來計算的。

3. 求解：找到這個圖 的一個最小權完美匹配，即找到一種配對方式，使得所有配對邊的權重之和（也就是所有最短路徑的總長度）最小。

幸運的是，圖論中已經存在解決最小權完美匹配問題的高效多項式時間算法。最著名的是 Jack Edmonds 在1965年提出的“blossom 算法”。它是第一個被證明能在多項式時間內解決一般圖（非二分圖）的最小權完美匹配問題的算法。它的核心思想極具創造性，巧妙地處理了在一般圖中尋找匹配時最棘手的障礙——奇數長度的環（odd cycles）。對于一個有 個頂點（這里 是阻挫小方格的數量，即圖 的頂點數，不包括可能的額外頂點，或指實際參與匹配的頂點數）和 條邊的圖 ，這些算法的復雜度大約是 ，這遠好于指數級。值得注意的是， （阻挫小方格的數量）通常遠小于系統總自旋數 。因此，即使對于規模很大的晶格，只要阻挫小方格的數量在可控范圍內，我們依然能夠高效地求得精確基態。

核心障礙：奇數環的困境

在圖論中，許多匹配問題是通過尋找“增廣路徑”（Augmenting Path）來解決的。對于一個已有的匹配 （圖的邊的一個子集，其中沒有兩條邊共享同一個頂點），一條增廣路徑是一條連接兩個未匹配頂點的路徑，其路徑上的邊交替地屬于 和不屬于 。

圖示：一條增廣路徑。黑邊不在當前匹配M中，藍邊在M中。通過沿著此路徑將“在M中”和“不在M中”的邊互換，我們可以得到一個更大的匹配（3條藍邊），從而使未匹配的頂點減少兩個。

找到一條增廣路徑，我們就可以通過“翻轉”路徑上邊的匹配狀態（將路徑上原屬于 的邊移出 ，并將原不屬于 的邊加入 ），使得匹配的規模增加1，從而向完美匹配更近一步。

這個策略的理論基石是圖論中的一個基本定理——貝爾熱引理（Berge's Lemma）。它指出：一個匹配 是最大匹配，當且僅當圖中不存在 -增廣路徑。這個引理告訴我們一個非常清晰的事實：任何一個匹配，要么它已經是最大匹配，要么它就一定能被一條增廣路徑所擴大。

這個引理為我們指明了方向：尋找最大匹配的過程，就是不斷尋找增廣路徑并擴大當前匹配的過程。從一個空匹配開始，反復執行“尋找-翻轉”操作，直到圖中再也找不到任何增廣路徑，此時得到的匹配就一定是最大匹配。

對于沒有奇數長度環的二分圖，上述尋找增廣路徑的策略（例如使用廣度優先或深度優先搜索）可以被直接有效地執行。然而，當圖含有奇數長度的環（Odd Cycle）時，情況變得異常棘手。

當增廣路徑的搜索算法進入一個奇數環時，會遇到一個無法用簡單交替規則處理的“邏輯死結”。想象我們從一個未匹配的頂點出發，構建一棵交替路徑樹（樹根是未匹配點，第一層邊是非匹配邊，第二層是匹配邊，以此類推）。如果搜索過程中，我們發現一條非匹配邊連接了樹上兩個已經存在的、且處于同一層的頂點，那么一個奇數環就被發現了。

這個奇數環就像是匹配算法中的“阻挫”：你無法沿著它走一圈并保持“非匹配-匹配-非匹配...”的完美交替模式回到起點。這使得簡單的搜索算法在此處碰壁，無法確定下一步該如何擴展路徑，從而導致算法失效。

Edmonds的巧思：收縮“花朵”

Jack Edmonds的貢獻在于他找到了處理奇數環的方法。他的想法是：既然奇數環是麻煩的根源，那我們就暫時把它“捏”成一個點，讓它在更高層次上消失！這個被收縮的奇數環，就被稱為“花朵”（Blossom）。

Blossom算法的精髓可以分解為以下幾個步驟：

1. 構建交替路徑樹: 從一個未匹配的頂點開始，通過廣度優先搜索構建一棵交替路徑樹，嘗試找到通往另一個未匹配頂點的增廣路徑。

2. 發現并收縮“花朵”: 在搜索過程中，一旦發現上述連接同層頂點的非匹配邊，從而識別出一個奇數環（花朵），算法就立即執行收縮（Contraction）操作。它將花朵中的所有頂點視為一個單一的“超級頂點”，并將所有原本連接到花朵內部的邊，重新連接到這個超級頂點上。這樣，我們就得到了一個規模更小、且暫時消除了那個特定奇數環的新圖。算法接著在這個收縮后的圖上繼續尋找增廣路徑。這個過程可以遞歸進行，一個大花朵內部可能還包含著被收縮的小花朵。

圖示：搜索交替路徑時，發現一條非匹配邊（紅色虛線）連接了樹上同一分支的兩個頂點，形成了一個奇數環（5個頂點）。這個環就是一個“花朵”。 Blossom算法將整個環收縮成一個單一的“超級頂點”。

3. 路徑提升與“花朵”展開: 算法的真正威力體現在它如何處理在收縮圖上找到的路徑。

• 如果在收縮后的圖中找到了增廣路徑，我們需要將這條路徑“提升”（Lift）回原始圖。

• 如果路徑不經過超級頂點，那么它在原始圖中也有效。

• 如果路徑穿過了超級頂點，我們就需要“展開”（Expand）這個花朵。這意味著我們需要在原始的奇數環中，找到一條合適的內部路徑片段，來連接進入和離開超級頂點的那兩條邊。由于奇數環的結構特性——它有一個頂點是“柄”（stem，路徑進入花朵的地方），內部有一條匹配邊——我們總能從柄出發，沿著環的兩個方向選擇其一，構造出一條能保持整條路徑“交替”性質的子路徑。

圖示：如果在收縮圖（上）中找到了經過超級頂點的增廣路徑，我們需要將其提升回原始圖（中，下）。通過展開花朵，我們可以沿著環找到一條正確的交替路徑（紅色路徑)，從而將進入和離開的路徑片段無縫連接成一條完整的增廣路徑。

4. 迭代與終止: 重復“尋找-收縮-提升-翻轉”的完整過程，直到圖中再也找不到任何增廣路徑。根據貝爾熱引理，此時得到的匹配即為最大匹配。

以上描述的是尋找最大匹配（unweighted）的基本思想。而我們面對的物理問題，是更復雜的最小權完美匹配。加權版本的Blossom算法在此基礎上，引入了線性規劃中的“對偶理論”。它不僅僅是尋找任意一條增廣路徑，而是通過維護一套精巧的“對偶變量”（可以看作是分配給每個頂點的潛在成本），來尋找能使總權重改善最大的“負成本”增廣路徑。

盡管技術細節（如對偶變量的更新、花朵收縮時權重的處理）要復雜得多，但其算法的骨架——通過收縮和展開“花朵”來動態處理奇數環——是完全一致的。正是這一核心機制，使得算法能夠在一般圖的復雜結構中，依然高效地找到最優解。

一旦通過算法找到了這個最小權完美匹配，其總權重（即所有匹配路徑的 權重之和）設為 ，我們就得到了基態的信息。基態能量 可以通過以下簡潔的公式計算：

• 第一項是系統在沒有任何阻挫、所有鍵都被滿足的情況下的理想能量。

• 第二項是為滿足所有阻挫約束所必須付出的最小能量懲罰。因子 的來源是，每個不滿足的鍵的能量從 變為 ，能量懲罰為 。 正是這些路徑上所有 的最小總和。

圖注：EA模型的基態構型。黑點和白點代表自旋向上和向下。紅色粗線標示出能量“不滿足”的鍵。這些紅線構成的路徑（藍色虛線示意）的端點，恰好是成對的“阻挫對偶頂點”（藍色圓圈），完美印證了匹配理論。可以看到，每個阻挫小方格（藍色圓圈）的邊界上都有奇數條不滿足的鍵，而所有非阻挫小方格的邊界上都有偶數條不滿足的鍵。

通過這一系列巧妙的轉化，一個看似棘手的統計物理問題，被優雅地歸結為一個可以在計算機上高效求解的圖論問題。研究這些基態特性，有助于我們理解無序系統在低溫下的獨特性質。例如，我們可以研究系統對微小擾動的響應（如改變某個 的值，基態構型會如何變化），進而計算其剛度系數，并確定其相變的臨界維度。

此外，這種“物理問題圖論化”的思想也出現在其他領域，例如任意維隨機場伊辛模型的基態能夠轉化為最小割（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)

本文轉載自《中國科學院理論物理研究所》微信公眾號

《物理》50年精選文章