什么是伊辛機(jī)？

在文章開(kāi)始之前，小編想和大家一起做個(gè)小游戲。游戲規(guī)則如下：對(duì)于給定的圖形，只畫(huà)一條線，在一條邊只能被經(jīng)過(guò)一次的條件下，使得筆畫(huà)經(jīng)過(guò)的邊的數(shù)量最多。比如對(duì)于三角形，圖示的畫(huà)法就是經(jīng)過(guò)邊數(shù)量最多的畫(huà)法（對(duì)稱的畫(huà)法算一種）。

再比如對(duì)于四邊形，其割值最大的分割方法是如下圖所示的。

那么對(duì)于下圖，怎樣才能使經(jīng)過(guò)的邊最多呢？

上面的游戲就是著名的最大割問(wèn)題。最大割問(wèn)題（Maximum Cut， Max-Cut）的描述是，給定一張圖，求一種分割方法，將所有頂點(diǎn)分割成兩群，同時(shí)使得被切斷的邊數(shù)量最大[1]。該問(wèn)題是一個(gè)NP完備問(wèn)題（注：NP問(wèn)題是指不能在多項(xiàng)式時(shí)間內(nèi)求解的問(wèn)題）。

Max-Cut問(wèn)題在現(xiàn)實(shí)生活中有很多應(yīng)用，比如電路設(shè)計(jì)、交通優(yōu)化、社交網(wǎng)絡(luò)分析等。類似的組合優(yōu)化問(wèn)題廣泛地出現(xiàn)在我們生活的方方面面，而這些問(wèn)題中很多一部分問(wèn)題是像最大割問(wèn)題一樣的NP問(wèn)題，解決其所需要的時(shí)間隨著問(wèn)題的規(guī)模增大而指數(shù)地增加，導(dǎo)致我們很難獲得精確解。而現(xiàn)有的基于馮諾依曼體系的算法，使得我們只能在精確度和時(shí)間之間進(jìn)行取舍。除了探索研究更好的算法，探索非馮諾依曼計(jì)算體系也成為研究的方向之一。

而伊辛機(jī)便是在這種需求下應(yīng)運(yùn)而生。所謂的伊辛機(jī)是將組合優(yōu)化問(wèn)題映射到我們小學(xué)二年級(jí)就學(xué)過(guò)的伊辛模型上，通過(guò)物理退火搜索最優(yōu)值的一種方法。要想理解伊辛機(jī)，首先得了解什么是伊辛模型。

01、伊辛模型簡(jiǎn)介

伊辛模型是以德國(guó)物理學(xué)家恩斯特·伊辛命名的數(shù)學(xué)模型，用以描述物質(zhì)的鐵磁性[2]。其基本思想是想象鐵磁物質(zhì)是由一個(gè)個(gè)小磁針構(gòu)成，小磁針只能有兩個(gè)朝向，向上或者向下，磁針的朝向稱為自旋，磁針之間會(huì)有相互作用。

圖1：伊辛模型示意圖

在沒(méi)有外磁場(chǎng)的情況下，系統(tǒng)的哈密頓量為：

其中是磁針之間的耦合系數(shù)，是自旋，只能取或者-1。在自旋相互作用的作用下，整個(gè)系統(tǒng)的磁針排列方式會(huì)朝著使系統(tǒng)伊辛能量最低的方向演化，這也符合能量最低原理。例如下面兩幅圖是二維伊辛模型的模擬結(jié)果，隨著自旋組合的變化，系統(tǒng)的伊辛能量逐漸降低。

圖2：2D伊辛模型模擬變化圖

圖3：2D伊辛模型能量變化

伊辛模型雖然簡(jiǎn)單，但卻很有效，除了用以描述物質(zhì)的鐵磁性，也被應(yīng)用到股票市場(chǎng)、種族隔離、政治選擇等不同的問(wèn)題[3]。今年獲得諾貝爾物理學(xué)獎(jiǎng)的霍普菲爾德神經(jīng)網(wǎng)絡(luò)也是啟發(fā)自伊辛模型，可以視為伊辛模型的變種。由于篇幅限制，小編在這里就不再做過(guò)多介紹，想了解更多有關(guān)伊辛模型的同學(xué)請(qǐng)自行查看有關(guān)的資料哦。

02、伊辛機(jī)是什么

了解了什么是伊辛模型，接下來(lái)介紹一下什么是伊辛機(jī)，以及如何用伊辛機(jī)去解決最大割問(wèn)題。所謂的伊辛機(jī)一種模擬伊辛模型的特殊物理裝置，通過(guò)自旋間的相互作用其自然地趨于系統(tǒng)的最低能量狀態(tài)，可以被用來(lái)解決一些組合優(yōu)化問(wèn)題。具體來(lái)說(shuō)，我們將問(wèn)題的參數(shù)映射到自旋的取值上，然后利用物理退火的方式去搜尋伊辛模型的基態(tài)，伊辛模型的基態(tài)對(duì)應(yīng)著組合優(yōu)化問(wèn)題的最優(yōu)值。

達(dá)到基態(tài)后，我們只需要將基態(tài)對(duì)應(yīng)的自旋取值轉(zhuǎn)換成組合優(yōu)化問(wèn)題對(duì)應(yīng)的參數(shù)，就得到了組合優(yōu)化問(wèn)題的最優(yōu)方案[4][5]。舉個(gè)例子，如圖所示，我們假設(shè)給定圖的頂點(diǎn)處有個(gè)小磁針，我們分別給它編號(hào)，邊代表小磁針之間的耦合強(qiáng)度，這里假定所有的磁針之間的耦合強(qiáng)度都是-1，且沒(méi)有外磁場(chǎng)。那么請(qǐng)同學(xué)們認(rèn)真思考，小磁針怎樣排布可以使系統(tǒng)的能量最低呢？

我們可以計(jì)算圖此時(shí)的伊辛能量，由于沒(méi)有外磁場(chǎng)，伊辛能量只有第一項(xiàng)，我們代入公式：

注意耦合強(qiáng)度是-1，得到伊辛能量為-4，我們會(huì)發(fā)現(xiàn)這就是這幅圖伊辛能量的最低值。小磁針的取值使得頂點(diǎn)被分為兩類，我們?cè)囍霉P分開(kāi)不同類別的頂點(diǎn)，就得到了如下所示的結(jié)果。

同學(xué)們可以發(fā)現(xiàn)，這樣的割法得到的割值就是最大的，是不是非常的amazing！伊辛能量的最低值竟然恰好和最大割問(wèn)題的最優(yōu)值對(duì)應(yīng)，這是巧合嗎？對(duì)于最大割問(wèn)題，我們的目標(biāo)函數(shù)為:

對(duì)上面的式子稍加變形，引入自旋變量，就可以得到如下的式子:

上式中，可以看到這個(gè)表達(dá)式的第二項(xiàng)正是伊辛能量，于是若伊辛能量達(dá)到最小值，整個(gè)式子便達(dá)到了最大值，也就意味著找到了最大割。

03、結(jié)語(yǔ)

在大數(shù)據(jù)人工智能背景下，隨著摩爾定律極限的逼近，探索非馮諾依曼計(jì)算架構(gòu)對(duì)于滿足日益增長(zhǎng)的算力需求具有重要意義，而伊辛機(jī)作為一種新型的計(jì)算架構(gòu)，以其解決組合優(yōu)化問(wèn)題的出色表現(xiàn)，具有重要的研究?jī)r(jià)值和廣闊的應(yīng)用前景。盡管目前有關(guān)伊辛機(jī)的研究，例如相干伊辛機(jī)[4][5]、微波光子伊辛機(jī)[6]等尚停留在實(shí)驗(yàn)室階段，但可以預(yù)見(jiàn)，隨著研究的深入，伊辛機(jī)將會(huì)為解決算力瓶頸提供新思路和解決方案。

參考文獻(xiàn)

[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

責(zé)編：六塊錢的魚(yú)