1282
在文章開始之前，小編想和大家一起做個小游戲。游戲規(guī)則如下：對于給定的圖形，只畫一條線，在一條邊只能被經過一次的條件下，使得筆畫經過的邊的數量最多。比如對于三角形，圖示的畫法就是經過邊數量最多的畫法（對稱的畫法算一種）。
再比如對于四邊形，其割值最大的分割方法是如下圖所示的。
那么對于下圖，怎樣才能使經過的邊最多呢？
上面的游戲就是著名的最大割問題。最大割問題（Maximum Cut， Max-Cut）的描述是，給定一張圖，求一種分割方法，將所有頂點分割成兩群，同時使得被切斷的邊數量最大[1]。該問題是一個NP完備問題（注：NP問題是指不能在多項式時間內求解的問題）。
Max-Cut問題在現實生活中有很多應用，比如電路設計、交通優(yōu)化、社交網絡分析等。類似的組合優(yōu)化問題廣泛地出現在我們生活的方方面面，而這些問題中很多一部分問題是像最大割問題一樣的NP問題，解決其所需要的時間隨著問題的規(guī)模增大而指數地增加，導致我們很難獲得精確解。而現有的基于馮諾依曼體系的算法，使得我們只能在精確度和時間之間進行取舍。除了探索研究更好的算法，探索非馮諾依曼計算體系也成為研究的方向之一。
而伊辛機便是在這種需求下應運而生。所謂的伊辛機是將組合優(yōu)化問題映射到我們小學二年級就學過的伊辛模型上，通過物理退火搜索最優(yōu)值的一種方法。要想理解伊辛機，首先得了解什么是伊辛模型。
01、伊辛模型簡介
伊辛模型是以德國物理學家恩斯特·伊辛命名的數學模型，用以描述物質的鐵磁性[2]。其基本思想是想象鐵磁物質是由一個個小磁針構成，小磁針只能有兩個朝向，向上或者向下，磁針的朝向稱為自旋，磁針之間會有相互作用。
圖1：伊辛模型示意圖
在沒有外磁場的情況下，系統(tǒng)的哈密頓量為：
其中是磁針之間的耦合系數，是自旋，只能取或者-1。在自旋相互作用的作用下，整個系統(tǒng)的磁針排列方式會朝著使系統(tǒng)伊辛能量最低的方向演化，這也符合能量最低原理。例如下面兩幅圖是二維伊辛模型的模擬結果，隨著自旋組合的變化，系統(tǒng)的伊辛能量逐漸降低。
圖2：2D伊辛模型模擬變化圖
圖3：2D伊辛模型能量變化
伊辛模型雖然簡單，但卻很有效，除了用以描述物質的鐵磁性，也被應用到股票市場、種族隔離、政治選擇等不同的問題[3]。今年獲得諾貝爾物理學獎的霍普菲爾德神經網絡也是啟發(fā)自伊辛模型，可以視為伊辛模型的變種。由于篇幅限制，小編在這里就不再做過多介紹，想了解更多有關伊辛模型的同學請自行查看有關的資料哦。
02、伊辛機是什么
了解了什么是伊辛模型，接下來介紹一下什么是伊辛機，以及如何用伊辛機去解決最大割問題。所謂的伊辛機一種模擬伊辛模型的特殊物理裝置，通過自旋間的相互作用其自然地趨于系統(tǒng)的最低能量狀態(tài)，可以被用來解決一些組合優(yōu)化問題。具體來說，我們將問題的參數映射到自旋的取值上，然后利用物理退火的方式去搜尋伊辛模型的基態(tài)，伊辛模型的基態(tài)對應著組合優(yōu)化問題的最優(yōu)值。
達到基態(tài)后，我們只需要將基態(tài)對應的自旋取值轉換成組合優(yōu)化問題對應的參數，就得到了組合優(yōu)化問題的最優(yōu)方案[4][5]。舉個例子，如圖所示，我們假設給定圖的頂點處有個小磁針，我們分別給它編號，邊代表小磁針之間的耦合強度，這里假定所有的磁針之間的耦合強度都是-1，且沒有外磁場。那么請同學們認真思考，小磁針怎樣排布可以使系統(tǒng)的能量最低呢？
我們可以計算圖此時的伊辛能量，由于沒有外磁場，伊辛能量只有第一項，我們代入公式：
注意耦合強度是-1，得到伊辛能量為-4，我們會發(fā)現這就是這幅圖伊辛能量的最低值。小磁針的取值使得頂點被分為兩類，我們試著用筆分開不同類別的頂點，就得到了如下所示的結果。
同學們可以發(fā)現，這樣的割法得到的割值就是最大的，是不是非常的amazing！伊辛能量的最低值竟然恰好和最大割問題的最優(yōu)值對應，這是巧合嗎？對于最大割問題，我們的目標函數為:
對上面的式子稍加變形，引入自旋變量，就可以得到如下的式子:
上式中，可以看到這個表達式的第二項正是伊辛能量，于是若伊辛能量達到最小值，整個式子便達到了最大值，也就意味著找到了最大割。
03、結語
在大數據人工智能背景下，隨著摩爾定律極限的逼近，探索非馮諾依曼計算架構對于滿足日益增長的算力需求具有重要意義，而伊辛機作為一種新型的計算架構，以其解決組合優(yōu)化問題的出色表現，具有重要的研究價值和廣闊的應用前景。盡管目前有關伊辛機的研究，例如相干伊辛機[4][5]、微波光子伊辛機[6]等尚停留在實驗室階段，但可以預見，隨著研究的深入，伊辛機將會為解決算力瓶頸提供新思路和解決方案。
參考文獻
[1]https://zh.wikipedia.org/wiki/%E6%9C%80%E5%A4%A7%E5%89%B2%E5%95%8F%E9%A1%8C
[2]Onsager L. Crystal statistics. I. A two-dimensional model with an order-disorder transition[J]. Physical Review, 1944, 65(3-4): 117.
[3]https://wiki.swarma.org/index.php/%E4%BC%8A%E8%BE%9B%E6%A8%A1%E5%9E%8B_Ising_Model
[4]Honjo T, Sonobe T, Inaba K, et al. 100,000-spin coherent Ising machine[J]. Science advances, 2021, 7(40): eabh0952.
[5]nagaki T, Haribara Y, Igarashi K, et al. A coherent Ising machine for 2000-node optimization problems[J]. Science, 2016, 354(6312): 603-606.
[6]Cen Q, Ding H, Hao T, et al. Large-scale coherent Ising machine based on optoelectronic parametric oscillator[J]. Light: Science & Applications, 2022, 11(1): 333.
編輯：Max
責編：六塊錢的魚
