1298
在文章開始之前，小編想和大家一起做個小游戲。游戲規(guī)則如下：對于給定的圖形，只畫一條線，在一條邊只能被經(jīng)過一次的條件下，使得筆畫經(jīng)過的邊的數(shù)量最多。比如對于三角形，圖示的畫法就是經(jīng)過邊數(shù)量最多的畫法（對稱的畫法算一種）。
再比如對于四邊形，其割值最大的分割方法是如下圖所示的。
那么對于下圖，怎樣才能使經(jīng)過的邊最多呢？
上面的游戲就是著名的最大割問題。最大割問題（Maximum Cut， Max-Cut）的描述是，給定一張圖，求一種分割方法，將所有頂點分割成兩群，同時使得被切斷的邊數(shù)量最大[1]。該問題是一個NP完備問題（注：NP問題是指不能在多項式時間內(nèi)求解的問題）。
Max-Cut問題在現(xiàn)實生活中有很多應用，比如電路設計、交通優(yōu)化、社交網(wǎng)絡分析等。類似的組合優(yōu)化問題廣泛地出現(xiàn)在我們生活的方方面面，而這些問題中很多一部分問題是像最大割問題一樣的NP問題，解決其所需要的時間隨著問題的規(guī)模增大而指數(shù)地增加，導致我們很難獲得精確解。而現(xiàn)有的基于馮諾依曼體系的算法，使得我們只能在精確度和時間之間進行取舍。除了探索研究更好的算法，探索非馮諾依曼計算體系也成為研究的方向之一。
而伊辛機便是在這種需求下應運而生。所謂的伊辛機是將組合優(yōu)化問題映射到我們小學二年級就學過的伊辛模型上，通過物理退火搜索最優(yōu)值的一種方法。要想理解伊辛機，首先得了解什么是伊辛模型。
01、伊辛模型簡介
伊辛模型是以德國物理學家恩斯特·伊辛命名的數(shù)學模型，用以描述物質(zhì)的鐵磁性[2]。其基本思想是想象鐵磁物質(zhì)是由一個個小磁針構(gòu)成，小磁針只能有兩個朝向，向上或者向下，磁針的朝向稱為自旋，磁針之間會有相互作用。
圖1：伊辛模型示意圖
在沒有外磁場的情況下，系統(tǒng)的哈密頓量為：
其中是磁針之間的耦合系數(shù)，是自旋，只能取或者-1。在自旋相互作用的作用下，整個系統(tǒng)的磁針排列方式會朝著使系統(tǒng)伊辛能量最低的方向演化，這也符合能量最低原理。例如下面兩幅圖是二維伊辛模型的模擬結(jié)果，隨著自旋組合的變化，系統(tǒng)的伊辛能量逐漸降低。
圖2：2D伊辛模型模擬變化圖
圖3：2D伊辛模型能量變化
伊辛模型雖然簡單，但卻很有效，除了用以描述物質(zhì)的鐵磁性，也被應用到股票市場、種族隔離、政治選擇等不同的問題[3]。今年獲得諾貝爾物理學獎的霍普菲爾德神經(jīng)網(wǎng)絡也是啟發(fā)自伊辛模型，可以視為伊辛模型的變種。由于篇幅限制，小編在這里就不再做過多介紹，想了解更多有關(guān)伊辛模型的同學請自行查看有關(guān)的資料哦。
02、伊辛機是什么
了解了什么是伊辛模型，接下來介紹一下什么是伊辛機，以及如何用伊辛機去解決最大割問題。所謂的伊辛機一種模擬伊辛模型的特殊物理裝置，通過自旋間的相互作用其自然地趨于系統(tǒng)的最低能量狀態(tài)，可以被用來解決一些組合優(yōu)化問題。具體來說，我們將問題的參數(shù)映射到自旋的取值上，然后利用物理退火的方式去搜尋伊辛模型的基態(tài)，伊辛模型的基態(tài)對應著組合優(yōu)化問題的最優(yōu)值。
達到基態(tài)后，我們只需要將基態(tài)對應的自旋取值轉(zhuǎn)換成組合優(yōu)化問題對應的參數(shù)，就得到了組合優(yōu)化問題的最優(yōu)方案[4][5]。舉個例子，如圖所示，我們假設給定圖的頂點處有個小磁針，我們分別給它編號，邊代表小磁針之間的耦合強度，這里假定所有的磁針之間的耦合強度都是-1，且沒有外磁場。那么請同學們認真思考，小磁針怎樣排布可以使系統(tǒng)的能量最低呢？
我們可以計算圖此時的伊辛能量，由于沒有外磁場，伊辛能量只有第一項，我們代入公式：
注意耦合強度是-1，得到伊辛能量為-4，我們會發(fā)現(xiàn)這就是這幅圖伊辛能量的最低值。小磁針的取值使得頂點被分為兩類，我們試著用筆分開不同類別的頂點，就得到了如下所示的結(jié)果。
同學們可以發(fā)現(xiàn)，這樣的割法得到的割值就是最大的，是不是非常的amazing！伊辛能量的最低值竟然恰好和最大割問題的最優(yōu)值對應，這是巧合嗎？對于最大割問題，我們的目標函數(shù)為:
對上面的式子稍加變形，引入自旋變量，就可以得到如下的式子:
上式中，可以看到這個表達式的第二項正是伊辛能量，于是若伊辛能量達到最小值，整個式子便達到了最大值，也就意味著找到了最大割。
03、結(jié)語
在大數(shù)據(jù)人工智能背景下，隨著摩爾定律極限的逼近，探索非馮諾依曼計算架構(gòu)對于滿足日益增長的算力需求具有重要意義，而伊辛機作為一種新型的計算架構(gòu)，以其解決組合優(yōu)化問題的出色表現(xiàn)，具有重要的研究價值和廣闊的應用前景。盡管目前有關(guān)伊辛機的研究，例如相干伊辛機[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
責編：六塊錢的魚
