張洪濤, 代永濤, 凃玲英

(1. 湖北工業(yè)大學(xué) 納米電子技術(shù)與微系統(tǒng)實(shí)驗(yàn)室, 湖北 武漢 430068;

2. 湖北工業(yè)大學(xué) 電氣與電子工程學(xué)院, 湖北 武漢 430068)

?

采用橫向鐵磁交互作用的隨機(jī)場(chǎng)伊辛模型的量子退火算法

張洪濤1,2, 代永濤1,2, 凃玲英1,2

(1. 湖北工業(yè)大學(xué) 納米電子技術(shù)與微系統(tǒng)實(shí)驗(yàn)室, 湖北 武漢 430068;

2. 湖北工業(yè)大學(xué) 電氣與電子工程學(xué)院, 湖北 武漢 430068)

摘要：通過(guò)數(shù)值對(duì)角化分析瞬時(shí)基態(tài)和第一激發(fā)態(tài)，提出基于橫向鐵磁交互的量子退火的優(yōu)勢(shì).采用貝特近似作為實(shí)際執(zhí)行的算法，給出相應(yīng)的模擬結(jié)果，并對(duì)傳統(tǒng)量子退火、基于橫向鐵磁交互作用的量子退火和模擬退火算法的剩余誤差進(jìn)行比較.結(jié)果表明：所提算法能有效提高傳統(tǒng)量子退火在隨機(jī)場(chǎng)伊辛模型中的收斂速度；利用量子波動(dòng)的選擇空間可以有效實(shí)現(xiàn)量子退火的最佳性能.

關(guān)鍵詞：橫向鐵磁交互作用； 隨機(jī)場(chǎng)伊辛模型； 量子退火； 模擬退火

模擬退火算法(SA)[1]是基于Monte carlo迭代求解策略的一種隨機(jī)尋優(yōu)算法，已在生產(chǎn)調(diào)度、圖像處理、控制工程等領(lǐng)域得到廣泛應(yīng)用[2-4].然而，經(jīng)典模擬退火算法要跳出局部最小點(diǎn)A,到達(dá)全局最優(yōu)點(diǎn)B，只能采用翻越勢(shì)壘的方式實(shí)現(xiàn).量子退火算法(QA)在其基礎(chǔ)上，通過(guò)引入一個(gè)假的溫度變量，實(shí)現(xiàn)在狀態(tài)空間中搜索目標(biāo)函數(shù)的最小值問(wèn)題.它利用量子隧穿效應(yīng),直接從點(diǎn)A穿透勢(shì)壘到達(dá)點(diǎn)B.因此，量子波動(dòng)的性質(zhì)被引入以伊辛(Ising)模型[5]為代表的經(jīng)典優(yōu)化問(wèn)題中.與模擬退火算法相比，量子退火算法在退火收斂速度和避免陷入局部極小等方面具有一定優(yōu)勢(shì)，且適用于其他領(lǐng)域非線性最優(yōu)化問(wèn)題的求解.目前，實(shí)施量子退火有多種方式，如薛定諤方程的精確數(shù)值分析、量子蒙特卡羅模擬[6-7]和格林函數(shù)蒙特卡羅方法[8]等.然而，在一些研究中，常規(guī)量子態(tài)的量子退火在某些情況下已被證明不能有效地執(zhí)行[9].本文研究一種基于橫向鐵磁交互作用的隨機(jī)場(chǎng)伊辛模型的量子退火算法.

1橫向鐵磁交互作用

1.1　常規(guī)量子退火

量子退火[10-12]利用量子波動(dòng)構(gòu)建優(yōu)化算法，使量子具有穿透比它自身能量高的勢(shì)壘的能力,即量子隧穿效應(yīng).量子退火通過(guò)模擬這一過(guò)程實(shí)現(xiàn)對(duì)目標(biāo)系統(tǒng)的優(yōu)化.量子系統(tǒng)的演化公式為

式(1)，(2)中：H(t)為含時(shí)哈密頓量; |Ψ(t)〉為量子系統(tǒng)狀態(tài);為方便起見(jiàn)，取?=1；Hlc對(duì)應(yīng)勢(shì)能項(xiàng)；Hkin(t)為適合系統(tǒng)的含時(shí)量子動(dòng)能項(xiàng)，其初值比較大，對(duì)應(yīng)較大的量子波動(dòng)，并按照某一進(jìn)度表逐漸減小為零.

1.1.1橫向隨機(jī)場(chǎng)Ising模型橫向隨機(jī)場(chǎng)Ising模型[13-14]常被作為量子退火算法的測(cè)試模型, 其哈密爾頓量為

式(5)中:τ為退火時(shí)間.

1.1.2絕熱演化絕熱演化[12-17]的定量準(zhǔn)則為

式(6)中:τc為特征時(shí)間；t/τ為時(shí)間參數(shù)；Ψ0和Ψ1分別為瞬時(shí)基態(tài)和第一激發(fā)態(tài)，其對(duì)應(yīng)的能量分別記為E0(t)，E1(t)；εmin為瞬時(shí)基態(tài)與第一激發(fā)態(tài)間能量間隔的最小值，即εmin=[E1(t)-E0(t)]max.

式(7)中:I為N維單位矩陣；量子系統(tǒng)的初態(tài)|Φ0〉為所有可能狀態(tài)的等幅疊加態(tài)，即

式(8)中：N=2n對(duì)應(yīng)于量子系統(tǒng)的Hilbert空間的維數(shù)，n為量子數(shù).

1.2　橫向鐵磁交互作用

此時(shí)，時(shí)變哈密頓量為

(a) 橫向鐵磁交互作用 (b) 常規(guī)橫向場(chǎng)作用圖1　基態(tài)與第一激發(fā)態(tài)之間的瞬時(shí)能量間隙Fig.1　Instantaneous energy gaps between the ground state and first excited state

(a) 橫向鐵磁交互作用 (b) 常規(guī)橫向場(chǎng)作用圖2 　矩陣元素的絕對(duì)值Fig.2　Absolute values of the matrix elements

(a) 橫向鐵磁交互作用 (b) 常規(guī)橫向場(chǎng)作用圖3　基態(tài)與第一、二激發(fā)態(tài)之間的瞬時(shí)能量間隙Fig.3　Instantaneous energy gap between the ground state and the first and second excited states

(a) 橫向鐵磁交互作用 (b) 常規(guī)橫向場(chǎng)作用圖4　矩陣元素的絕對(duì)值Fig.4　Absolute values of the matrix elements

2貝特近似的平均場(chǎng)退火

為了用平均場(chǎng)類型的方法實(shí)現(xiàn)最佳結(jié)果，采用貝特近似[18-19]代替簡(jiǎn)單的單體平均場(chǎng)理論.此時(shí)，其含時(shí)哈密頓量、勢(shì)能項(xiàng)和量子動(dòng)能項(xiàng)分別為

線性退火表T=T0·(1-t/τ).其中，T0是一個(gè)足夠高的初始溫度.將上述方法應(yīng)用到100×100的二維隨機(jī)場(chǎng)伊辛模型中，通過(guò)近似能量與一個(gè)完善算法而估計(jì)的真正的基態(tài)能量之間的差異計(jì)算剩余能量[20].基于橫向鐵磁交互作用的量子退火算法(TF)、模擬退火算法(Thermal)和常規(guī)橫向場(chǎng)量子退火算法(FI)等3種退火算法在橫向場(chǎng)隨機(jī)Ising模型下的剩余能量，如圖5所示.由圖5(a)可知：基于橫向鐵磁交互作用的量子退火算法遠(yuǎn)遠(yuǎn)優(yōu)于模擬退火算法和常規(guī)橫向場(chǎng)量子退火算法;模擬退火算法與常規(guī)橫向場(chǎng)量子退火的執(zhí)行效果幾乎相似，但前者略優(yōu)于后者，可能是由于熱近似和量子退火影響的差異造成的.由圖5(b)可知：3種退火算法執(zhí)行效果的差異性明顯減少.

(a) J=2.0 (b) J=0.6圖5　3種退火算法在橫向場(chǎng)隨機(jī)Ising模型下的剩余能量Fig.5　Residual energy of 3 kinds of annealing algorithm in the random transverse field Ising model

綜上所述，當(dāng)耦合常數(shù)J較大時(shí)，基于橫向鐵磁交互作用的量子退火算法更加有效，其中，真正的基態(tài)是完全或接近的鐵磁性狀態(tài).橫向鐵磁交互作用的引入不一定改善了無(wú)序基態(tài)的結(jié)果.

3結(jié)束語(yǔ)

對(duì)橫向鐵磁交互作用的隨機(jī)場(chǎng)伊辛模型的量子退火算法進(jìn)行研究.結(jié)果表明：當(dāng)J值較大時(shí)，基于橫向鐵磁交互作用的量子退火的效率高于其他兩種方案.這意味著先前報(bào)道的鐵磁基態(tài)的常規(guī)量子退火效率降低不是量子退火的一個(gè)內(nèi)在特征，利用適當(dāng)?shù)牧孔有?yīng)可以得到比模擬退火更高的效率.利用量子波動(dòng)的選擇空間提取量子退火中的最佳性能非常重要，這種靈活性是量子退火的一個(gè)突出特性.

參考文獻(xiàn)：

[1]杜衛(wèi)林，李斌，田宇.量子退火算法研究進(jìn)展[J].計(jì)算機(jī)研究與發(fā)展，2008,45(9):1501-1508.

[2]王凌.智能優(yōu)化算法及其應(yīng)用[M].北京:清華大學(xué)出版社,2004:17-35.

[3]張德富,彭煜，朱文興，等.求解三維裝箱問(wèn)題的混合模擬退火算法[J].計(jì)算機(jī)學(xué)報(bào),2009,32(11)：2147-2156.

[4]KIRKPATRICK S C,GELATT C D,VECCHI M P,et al.Optimizationby simulated annealing[J].Science,1983,220(4598):671- 680.

[5]HOPFIELD J J,TANK D W.Computation of decisions: A model[J].Science,1986,233(4764):625-633.

[6]KADOWAKI T.Study of optimization problems by quantum annealing[D].Tokyo:Tokyo Institute of Technology,2002:15-40.

[7]MARTONAK R,SANTORO G E,TOSATTI E.Quantum annealing by the path-integral Monte carlo method: The two-dimensional random Ising model[J].Physical Review B,2002,66(9):351-363.

[8]LORENZO S,SANTORO G E.Quantum annealing of an Ising spin-glass by Green′s function Monte carlo[J].Physical Review E,2007,75(3):036703.

[9]SARJALA M,PETAJA V,ALAVA M.Optimization in random field Ising models by quantum annealing[J].Journal of Statistical Mechanics:Theory and Experiment,2006,16(1):79-107.

[10]KADOWAKI T,NISHIMORI H.Quantum annealing in the transverse Ising model[J].Physical Review E,1998,58(5):5355.

[11]BOIXO S,ALBASH T,SPEDALIERI F M,et al.Experimental signature of programmable quantum annealing[J].Nature Communications,2012,4(3):131-140.

[12]BOIXO S,RONNOW T F,ISAKO S V,et al.Evidence for quantum annealing with more than one hundred qubits[J].Nature Physics,2014,10(3):218-224.

[13]FYTAS N G,MARTIN-MAYOR V.Universality in the three-dimensional random-field Ising model[J].Phys Rev Lett,2013,110(1):019903.

[14]黃純青，鄧紹軍.三維Ising模型的蒙特卡羅模擬[J].計(jì)算物理,2009,26(6):937-941.

[15]張映玉,付樟華.絕熱量子優(yōu)化算法研究進(jìn)展[J].計(jì)算機(jī)工程與科學(xué)，2015，37(3):429-433.

[16]曹懷信，王素媛.量子絕熱定理研究[J].紡織高?；A(chǔ)科學(xué)學(xué)報(bào),2015,28(2):131-138.

[17]CAO Huaixin,GUO Zhihua,CHEN Zhengli.CPT-frames for non-Hermitian Hamiltonians[J].Commun TheorPhys,2013,60(9):328-334.

[18]SEMKIN S V,SMAGIN V P.Bethe approximation in the Ising model with mobile impurities[J].Physics of the Solid State,2015,57(5):943-948.

[19]MEILIKHOV E Z,FARZETDINOVA R M.Effective field theory for disordered magnetic alloys[J].Physics of the Solid State,2014,56(4):707-714.

[20]ALAVAl M,DUXBURY P,MOUKARAEL C,et al.Exact combinatorial algorithms: Ground states of disordered systems[M].New York:Phase Transitions and Critial Phenomena,2001:143-317.

(責(zé)任編輯： 錢(qián)筠英文審校： 吳逢鐵)

Quantum Annealing of the Random-Field Ising Model

Based on Transverse Ferromagnetic Interactions

ZHANG Hongtao1,2, DAI Yongtao1,2, TU Lingying1,2

(1. Nanoelectron Technology and Micro-system Laboratory, Hubei University of Technology, Wuhan 430068, China;

2. School of Electrical and Electronic Engineering, Hubei University of Technology, Wuhan 430068, China)

Abstract：Through the numerical analysis of the instantaneous ground state and the first excited state, the advantages of quantum annealing based on the transverse ferromagnetic interactions are presented. Using the Bethe approximation as an algorithm for practical implementation, the simulation results are given accordingly. Then the residual errors of conventional quantum annealing, quantum annealing by transverse ferromagnetic interactions, and simulated annealing are compared. The results show that the proposed algorithm can effectively improve the convergence speed of traditional quantum annealing in the random-field Ising model. And the best performance of quantum annealing can be achieved by using the choice space of the quantum fluctuation.

Keywords：transverse ferromagnetic interactions; random-field Ising model; quantum annealing； simulated annealing

基金項(xiàng)目：湖北省武漢市科技局“十城千輛新動(dòng)力汽車計(jì)劃”基金資助項(xiàng)目(2013011801010600)

通信作者：張洪濤(1963-)，男，教授，博士，主要從事量子通信及計(jì)算技術(shù)、嵌入式視頻監(jiān)控系統(tǒng)和數(shù)字信號(hào)處理的研究.E-mail:zhanght@mail.hbut.edu.cn.

收稿日期：2015-09-18

中圖分類號(hào)：TP 301

文獻(xiàn)標(biāo)志碼：A

doi:10.11830/ISSN.1000-5013.2016.01.0007

文章編號(hào)：1000-5013(2016)01-0007-05