量子絕熱近似求解最大割問(wèn)題的最優(yōu)解

王富民,倪 明,周 明,吳永政

(中國(guó)電子科技集團(tuán)公司第三十二研究所,上海 201808)

0 概述

求解最大割問(wèn)題是指對(duì)給定的無(wú)向加權(quán)圖求取一個(gè)最大分割解,使橫跨2個(gè)割集的所有邊權(quán)重之和最大。最大割問(wèn)題是圖論中典型的NP困難組合優(yōu)化問(wèn)題,在圖像處理[1]、信道分配[2]等工程問(wèn)題中廣泛存在。雖然理論上該問(wèn)題可由窮舉法找到最優(yōu)解,但是因?yàn)檫\(yùn)行時(shí)間隨圖中頂點(diǎn)個(gè)數(shù)或邊的條數(shù)增加呈指數(shù)級(jí)增長(zhǎng),問(wèn)題的搜索空間也急劇擴(kuò)大,即使用當(dāng)前最先進(jìn)的計(jì)算機(jī)來(lái)計(jì)算,求解時(shí)間也極長(zhǎng)[3]。因此,研究者一般使用近似算法計(jì)算該問(wèn)題,以犧牲一定的準(zhǔn)確率為代價(jià)來(lái)縮短運(yùn)行時(shí)間[4]。

最大割問(wèn)題可以通過(guò)構(gòu)造簡(jiǎn)單的隨機(jī)近似算法來(lái)解決。該算法隨機(jī)初始化一個(gè)頂點(diǎn)割集,檢查每個(gè)頂點(diǎn),若發(fā)現(xiàn)某個(gè)頂點(diǎn)所連接的所有邊中有多于一半的邊的頂點(diǎn)屬于同一子集,則將其移到另一子集中,重復(fù)尋找直到找不到此類(lèi)頂點(diǎn),算法終止。易證該算法最大割至少是邊總數(shù)的一半,因此,其是一個(gè)0.5近似比的近似算法。Geomans-Williamson算法是著名的求解最大割問(wèn)題的近似算法[5],其將半正定規(guī)劃用于近似求解中,通過(guò)證明可知該算法近似比為0.878 6[6]。

在物理絕熱過(guò)程中,隨系統(tǒng)哈密頓量緩慢變化,初始系統(tǒng)哈密頓量的基態(tài)也會(huì)緩慢演化到最終系統(tǒng)哈密頓量的基態(tài)[7]。結(jié)合該定理和量子算法疊加性[8]而設(shè)計(jì)的量子絕熱算法,通過(guò)設(shè)計(jì)初始哈密頓量Hb與待解問(wèn)題的哈密頓量Hp之間的演化路徑,構(gòu)造一個(gè)緩慢變化的系統(tǒng)哈密頓量來(lái)求解相關(guān)問(wèn)題[9-10]。

本文利用量子絕熱近似算法求解最大割問(wèn)題?；赑ython語(yǔ)言的ProjectQ量子編程軟件[11-13],根據(jù)圖中頂點(diǎn)個(gè)數(shù)以及邊的條數(shù)編寫(xiě)求解程序,其執(zhí)行順序?qū)?yīng)于量子算法線(xiàn)路[14]中量子邏輯門(mén)的順序。在此基礎(chǔ)上,測(cè)量量子寄存器中量子比特的狀態(tài)獲得實(shí)驗(yàn)結(jié)果[15]。本文在求解最大割問(wèn)題時(shí)采用線(xiàn)性演化路徑,即初始哈密頓量的比例線(xiàn)性減小、最大割問(wèn)題哈密頓量的比例線(xiàn)性增大,以提高求解準(zhǔn)確率。

1 絕熱定理與量子絕熱算法

對(duì)于物理絕熱過(guò)程中的哈密頓量H(t),考慮單參數(shù)s的平滑哈密頓量H*(s)(0≤s≤1),取:

H(t)=H*(t/T)

(1)

其中,T控制H(t)的變化率[16-17]。定義H*(s)的瞬時(shí)本征值Eα(s)和本征態(tài)|ψα(s)〉為:

H*(s)|ψα(s)〉=Eα(s)|ψα(s)〉

(2)

其中,α表示能級(jí)。根據(jù)絕熱定理,如果最低能級(jí)之間的縫隙為:

(3)

則對(duì)于所有0 ≤s≤1嚴(yán)格大于0,有式(4)存在。

(4)

這意味能級(jí)間大于0的縫隙可以確保|ψα(t)〉在遵循薛定諤方程的同時(shí),|ψα(t)〉隨著t從0變化到T的過(guò)程中無(wú)限接近于|ψα(1)〉的瞬時(shí)本征態(tài)。

根據(jù)上述定理構(gòu)造系統(tǒng)哈密頓量H(t):

H(t)=(1-t/T)Hb+(t/T)Hp

(5)

其中,Hb為易于計(jì)算出基態(tài)的初始哈密頓量,Hp為基態(tài)未知的問(wèn)題哈密頓量。系統(tǒng)的初態(tài)為H(t=0)=Hb的基態(tài)|ψ0(0)〉,系統(tǒng)哈密頓量隨t的增加演化到t=T時(shí),處于終態(tài)H(t=T)=Hp的基態(tài)|ψ0(1)〉。

2 量子絕熱算法求解最大割問(wèn)題的理論分析

2.1 最大割問(wèn)題的數(shù)學(xué)描述

設(shè)無(wú)向圖G(V,E),其中,V={1,2,…,n}為頂點(diǎn)的集合,E?V×V為邊的集合。

(6)

(7)

2.2 最大割問(wèn)題哈密頓量的構(gòu)造

對(duì)于無(wú)向圖G(V,E),其中|V|=n、|E|=m表示該圖有n個(gè)頂點(diǎn)和m條邊,定義任意一個(gè)解:|Ψ〉=|ψ1〉|ψ2〉…|ψn〉,其中:

(8)

(9)

圖中每條邊所對(duì)應(yīng)的哈密頓量為Hpei,j,定義為:

(10)

(11)

當(dāng)最大割解為|z1〉|z2〉…|zn〉時(shí),下式成立:

Hp|z1〉|z2〉…|zn〉=hmin|z1〉|z2〉…|zn〉

(12)

其中,hmin為最小本征值也是最大割解值,|z1〉|z2〉…|zn〉為基態(tài)也對(duì)應(yīng)最大割解。

2.3 初始哈密頓量的構(gòu)造

量子絕熱算法需要從一個(gè)初始哈密頓量開(kāi)始演化。這個(gè)初始哈密頓量應(yīng)是簡(jiǎn)單的并且其基態(tài)也是容易獲得的,定義:

(13)

2.4 量子絕熱算法邏輯線(xiàn)路

根據(jù)式(1)和式(5)可得:

H*(s)=(1-s)Hb+sHp

(14)

其中,s∈[0,1]單調(diào)遞增,增量為Δs。

定義Ub(s)和Up(s)對(duì)應(yīng)(1-s)Hb和sHp的演化算子為:

Ub(s)=e-iHb(1-s),Up(s)=e-iHps

(15)

根據(jù)具體無(wú)向圖構(gòu)造演化算子Up和Ub,算法描述如下:

算法1Up(graph,qureg,s)

輸入最大割問(wèn)題graph,待處理量子寄存器qureg,演化時(shí)間s

1.n ← graph.vertexnum

2.m ← graph.edgenum

3.edges[ ] ← graph.edges

4.hamiltonian ← 0

5.for i = 0 → m-1 do

6.subhamil[ ] ← 0

7.for j = 0 → n-1 do

8.if j ∈ edges[i] then

9.subhamil[j] ← σz(j)

10.else

11.subhamil[j] ← I(j)

12.end if

13.end for

14.hamil ← subhamil[0]

15.for k = 1 → n-1 do

16.hamil ← hamil ? subhamil[k]

17.end for

18.hamiltonian ← hamiltonian+0.5(hamil-I)

19.end for

20.qureg←TimeEvolution(time=s,hamiltonian=hamiltonian)

算法2Ub(graph,qureg,s)

輸入最大割問(wèn)題graph,待處理量子寄存器qureg,演化時(shí)間s

1.n←graph.vertexnum

2.hamiltonian←1

3.for i=0→n-1 do

5.end for

6.qureg←TimeEvolution(time=s,hamiltonian=hamiltonian)

在該線(xiàn)性演化路徑下可以求出最大割解|z1>|z2>…|zn>:

|z1〉|z2〉…|zn〉=

Ub(1)Up(1)…Ub(Δs)Up(Δs)Ub(0)Up(0)|+〉?n

(16)

演化路徑對(duì)應(yīng)的算法描述如下:

算法3EvolutionPath(graph,qureg,T)

輸入最大割問(wèn)題graph,待處理量子寄存器qureg,演化次數(shù)T

1.Δs ← 1.0/T

2.for i = 0 → T do

3.s ← i × Δs

4.Up(graph,qureg,s)

5.Ub(graph,qureg,1-s)

6.qureg.engine.flush()

7.end for

采用量子算法求解最大割問(wèn)題的哈密頓量基態(tài)的過(guò)程,可用圖1中量子邏輯門(mén)排列所得到的量子線(xiàn)路模型[18-19]表示。

圖1 最大割問(wèn)題量子線(xiàn)路示意圖

采用上述量子線(xiàn)路模型的量子邏輯門(mén)順序,用ProjectQ軟件框架對(duì)該算法進(jìn)行模擬的偽代碼如下:

算法4CreateCircuit(graph,T)

輸入最大割問(wèn)題graph,待處理量子寄存器qureg,演化次數(shù)T

輸出graph實(shí)驗(yàn)結(jié)果的最優(yōu)解

1.n ← graph.vertexnum

2.eng ← MainEngine(Simulator())

3.qureg ← eng.allocate_qureg(n)

4.qureg ← Tensor(H)

5.EvolutionPath(graph,qureg,T)

6.qureg ← All(Measure)

7.return qureg

3 量子絕熱算法求解最大割問(wèn)題的數(shù)值分析

上文給出了量子絕熱算法求解最大割問(wèn)題的理論模型和具體步驟,下面分別舉3個(gè)頂點(diǎn)和6個(gè)頂點(diǎn)的例子,從系統(tǒng)哈密頓量期望值的變化曲線(xiàn)入手分析量子絕熱算法求解最大割問(wèn)題的數(shù)值結(jié)果。

3.1 3個(gè)頂點(diǎn)的無(wú)向圖

3個(gè)頂點(diǎn)作為最簡(jiǎn)單的示例構(gòu)建無(wú)向圖,3個(gè)頂點(diǎn)分別標(biāo)號(hào)為0、1和2,將頂點(diǎn)0和頂點(diǎn)1分別與頂點(diǎn)2相連構(gòu)成由3個(gè)頂點(diǎn)2條邊組成的無(wú)向連通圖。如果將頂點(diǎn)0和1與頂點(diǎn)2之間的邊全部切割開(kāi)就會(huì)得到該圖的最大割解,如圖2所示。

圖2 3個(gè)頂點(diǎn)的無(wú)向圖及其最大割解

對(duì)于3個(gè)頂點(diǎn)的圖,需要用3個(gè)量子比特|z1〉|z2〉|z3〉來(lái)表示相應(yīng)頂點(diǎn)0、1、和2的狀態(tài)。將實(shí)驗(yàn)最后測(cè)得量子比特狀態(tài),|0〉態(tài)標(biāo)同一種顏色,|1〉態(tài)標(biāo)另一種顏色。

由式(4)可得該圖最大割問(wèn)題的哈密頓量為:

(17)

Hp為經(jīng)計(jì)算得到對(duì)角矩陣,其對(duì)角線(xiàn)元素依次為0、-2、-1、-1、-1、-1、-2、0。

取增量Δs=0.01,可以得到最大割問(wèn)題的哈密頓量期望值〈ψ(s)|Hp|ψ(s)〉(簡(jiǎn)寫(xiě)為〈Hp〉)的變化曲線(xiàn)如圖3所示。

圖3 3個(gè)頂點(diǎn)無(wú)向圖最大割問(wèn)題的哈密頓量期望值變化曲線(xiàn)

Fig.3 Expected value variation curve of Hamiltonian for max-cut problem of 3-vertex undirected graph

由圖3可以看出,量子態(tài)在演化算子的作用下,從|+〉?3逐漸演化到最大割問(wèn)題的哈密頓量基態(tài),相應(yīng)的最大割問(wèn)題哈密頓量的期望值從-1平滑地下降到-2。選用哈密頓量期望的數(shù)值模擬值與理論分析的比值作為問(wèn)題求解準(zhǔn)確率,則對(duì)于該無(wú)向圖最大割問(wèn)題，量子絕熱近似求解的準(zhǔn)確率為0.999 9。

3.2 6個(gè)頂點(diǎn)的稀疏無(wú)向圖

為驗(yàn)證量子絕熱算法能夠解決一些更復(fù)雜圖的最大割問(wèn)題,將問(wèn)題規(guī)模進(jìn)一步復(fù)雜化,取6個(gè)頂點(diǎn),分別標(biāo)號(hào)0、1、2、3、4和5,構(gòu)造稀疏無(wú)向圖。稀疏圖即表示有很少條邊(|E|?|V|2)的圖,構(gòu)建稀疏圖及其最大割解如圖4所示。

圖4 6個(gè)頂點(diǎn)的稀疏無(wú)向圖及其最大割解Fig.4 6-vertex undirected sparse graph and its max-cut solution

圖4顯示，對(duì)條邊劃分后最多有7條邊被切割,因此,最大割解值為-7。同理,對(duì)于6個(gè)頂點(diǎn)的圖需要6個(gè)量子比特來(lái)表示頂點(diǎn)所屬集合狀態(tài)。由式(10)和式(11)可得,最大割問(wèn)題的哈密頓量Hp為26×26的對(duì)角矩陣,其對(duì)角元素為0、-3、-3、-4、-3、-6、-6,-7、-3、-6、-4、-5、-4、-7、-5、-6、-4、-5、-5、-4、-5、-6、-6、-5、-5、-6、-4、-3、-4、-5、-3、-2、-2、-3、-5、-4、-3、-4、-6、-5、-5、-6、-6、-5、-4、-5、-5、-4、-6、-5、-7、-4、-5、-4、-6、-3、-7、-6、-6、-3、-4、-3、-3、0。其中,-7為基態(tài)能量,對(duì)應(yīng)最大割哈密頓量期望理論測(cè)量值也為-7。

對(duì)于線(xiàn)性演化路徑下的增量Δs,分別取0.2、0.1、0.01來(lái)分析增量取值大小對(duì)最大割問(wèn)題哈密頓量期望值〈Hp〉的影響,如圖5所示。

圖5 不同增量Δs下6個(gè)頂點(diǎn)稀疏無(wú)向圖最大割問(wèn)題的哈密頓量期望值變化曲線(xiàn)

Fig.5 Expected value variation curve of Hamiltonian for max-cut problem of 6-vertex undirected sparse graph under different incremental Δs

由圖5可知,當(dāng)增量Δs取值越趨向于0時(shí),演化到最終基態(tài)的最大割問(wèn)題哈密頓量期望值越小,即表明有越大的概率得到最大割問(wèn)題的最優(yōu)解,準(zhǔn)確率越高。對(duì)于取較大增量時(shí),參數(shù)s從0增加到0.5時(shí)最大割問(wèn)題哈密頓量的期望值有更快的下降速率,這意味著較大的增量在初期可以提高算法的效率。

當(dāng)Δs=0.01時(shí),量子絕熱算法求解6個(gè)頂點(diǎn)稀疏圖的最大割問(wèn)題的準(zhǔn)確率為0.999 9。

3.3 6個(gè)頂點(diǎn)的完全無(wú)向圖

稠密圖與稀疏圖恰好相反,它是由很多條邊組成的圖,完全圖是一種最復(fù)雜的稠密圖,圖中任意2個(gè)頂點(diǎn)之間都有邊相連。將6個(gè)頂點(diǎn)的稀疏圖擴(kuò)展成完全圖及其最大割解如圖6所示。

圖6 6個(gè)頂點(diǎn)的完全圖及其最大割解

Fig.66-vertex undirected complete graph and its max-cut solution

圖6中共有15條邊,對(duì)應(yīng)最大割問(wèn)題的哈密頓量Hp對(duì)角元素為0、-5、-5、-8、-5、-8、-8、-9、-5、-8、-8、-9、-8、-9、-9、-8、-5、-8、-8、-9、-8、-9、-9、-8、-8、-9、-9、-8、-9、-8、-8、-5、-5、-8、-8、-9、-8、-9、-9、-8、-8、-9、-9、-8、-9、-8、-8、-5、-8、-9、-9、-8、-9、-8、-8、-5、-9、-8、-8、-5、-8、-5、-5、0的對(duì)角矩陣,基態(tài)能量為-9,對(duì)應(yīng)最大割哈密頓量期望理論測(cè)量值也為-9。根據(jù)稀疏圖例子將增量Δs取0.01,對(duì)最大割問(wèn)題哈密頓量的期望值〈Hp〉變化曲線(xiàn)如圖7所示。

圖7 6個(gè)頂點(diǎn)完全圖的最大割哈密頓量期望值變化曲線(xiàn)

Fig.7 Expected value variation curve of Hamiltonian for max-cut problem of 6-vertex undirected complete graph

由圖7可以看出,在參數(shù)s從0增加到1的過(guò)程中,最大割問(wèn)題哈密頓量的期望值總體呈下降趨勢(shì),量子絕熱算法計(jì)算出最大割問(wèn)題最優(yōu)解的概率較高,測(cè)量結(jié)果的準(zhǔn)確率為0.969 6。

由于實(shí)驗(yàn)在設(shè)計(jì)絕熱演化路徑時(shí),采用初始哈密頓量Hb與最大割問(wèn)題哈密頓量Hp之間固定的參數(shù)增量Δs,并未考慮具體無(wú)向圖中邊與增量Δs的關(guān)系,因此,增加無(wú)向圖中邊的條數(shù)會(huì)降低求解最大割問(wèn)題的準(zhǔn)確率,并且得到最大割問(wèn)題哈密頓量期望值的變化曲線(xiàn)也不再平滑[20]。

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

本文利用量子絕熱算法求解無(wú)向圖最大割問(wèn)題,結(jié)合量子近似的思想設(shè)計(jì)算法中的演化算子,從而求解最大割問(wèn)題的哈密頓量。與傳統(tǒng)近似算法相比,該算法的時(shí)間復(fù)雜度不依賴(lài)于圖的頂點(diǎn)個(gè)數(shù)以及邊的條數(shù),僅與增量Δs的取值相關(guān),并可通過(guò)量子比特門(mén)的邏輯組合實(shí)現(xiàn)。本文列舉了3個(gè)最大割問(wèn)題的實(shí)例,并用ProjectQ進(jìn)行編程模擬。數(shù)值分析結(jié)果表明,在頂點(diǎn)數(shù)較少的最大割問(wèn)題中,量子絕熱近似算法準(zhǔn)確率高于文獻(xiàn)[5]算法和隨機(jī)近似算法。針對(duì)最大割問(wèn)題的哈密頓量期望值隨參數(shù)s變化導(dǎo)致曲線(xiàn)不平滑的問(wèn)題,下一步將根據(jù)具體無(wú)向圖來(lái)調(diào)整變化的增量Δs,減少無(wú)向圖復(fù)雜度對(duì)計(jì)算準(zhǔn)確率的影響。