量子絕熱近似求解最大割問題的最優解

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

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

0 概述

求解最大割問題是指對給定的無向加權圖求取一個最大分割解,使橫跨2個割集的所有邊權重之和最大。最大割問題是圖論中典型的NP困難組合優化問題,在圖像處理[1]、信道分配[2]等工程問題中廣泛存在。雖然理論上該問題可由窮舉法找到最優解,但是因為運行時間隨圖中頂點個數或邊的條數增加呈指數級增長,問題的搜索空間也急劇擴大,即使用當前最先進的計算機來計算,求解時間也極長[3]。因此,研究者一般使用近似算法計算該問題,以犧牲一定的準確率為代價來縮短運行時間[4]。

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

在物理絕熱過程中,隨系統哈密頓量緩慢變化,初始系統哈密頓量的基態也會緩慢演化到最終系統哈密頓量的基態[7]。結合該定理和量子算法疊加性[8]而設計的量子絕熱算法,通過設計初始哈密頓量Hb與待解問題的哈密頓量Hp之間的演化路徑,構造一個緩慢變化的系統哈密頓量來求解相關問題[9-10]。

本文利用量子絕熱近似算法求解最大割問題。基于Python語言的ProjectQ量子編程軟件[11-13],根據圖中頂點個數以及邊的條數編寫求解程序,其執行順序對應于量子算法線路[14]中量子邏輯門的順序。在此基礎上,測量量子寄存器中量子比特的狀態獲得實驗結果[15]。本文在求解最大割問題時采用線性演化路徑,即初始哈密頓量的比例線性減小、最大割問題哈密頓量的比例線性增大,以提高求解準確率。

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

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

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

(1)

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

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

(2)

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

(3)

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

(4)

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

根據上述定理構造系統哈密頓量H(t):

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

(5)

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

2 量子絕熱算法求解最大割問題的理論分析

2.1 最大割問題的數學描述

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

(6)

(7)

2.2 最大割問題哈密頓量的構造

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

(8)

(9)

圖中每條邊所對應的哈密頓量為Hpei,j,定義為:

(10)

(11)

當最大割解為|z1〉|z2〉…|zn〉時,下式成立:

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

(12)

其中,hmin為最小本征值也是最大割解值,|z1〉|z2〉…|zn〉為基態也對應最大割解。

2.3 初始哈密頓量的構造

量子絕熱算法需要從一個初始哈密頓量開始演化。這個初始哈密頓量應是簡單的并且其基態也是容易獲得的,定義:

(13)

2.4 量子絕熱算法邏輯線路

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

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

(14)

其中,s∈[0,1]單調遞增,增量為Δs。

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

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

(15)

根據具體無向圖構造演化算子Up和Ub,算法描述如下:

算法1Up(graph,qureg,s)

輸入最大割問題graph,待處理量子寄存器qureg,演化時間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)

輸入最大割問題graph,待處理量子寄存器qureg,演化時間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)

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

|z1〉|z2〉…|zn〉=

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

(16)

演化路徑對應的算法描述如下:

算法3EvolutionPath(graph,qureg,T)

輸入最大割問題graph,待處理量子寄存器qureg,演化次數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

采用量子算法求解最大割問題的哈密頓量基態的過程,可用圖1中量子邏輯門排列所得到的量子線路模型[18-19]表示。

圖1 最大割問題量子線路示意圖

采用上述量子線路模型的量子邏輯門順序,用ProjectQ軟件框架對該算法進行模擬的偽代碼如下:

算法4CreateCircuit(graph,T)

輸入最大割問題graph,待處理量子寄存器qureg,演化次數T

輸出graph實驗結果的最優解

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 量子絕熱算法求解最大割問題的數值分析

上文給出了量子絕熱算法求解最大割問題的理論模型和具體步驟,下面分別舉3個頂點和6個頂點的例子,從系統哈密頓量期望值的變化曲線入手分析量子絕熱算法求解最大割問題的數值結果。

3.1 3個頂點的無向圖

3個頂點作為最簡單的示例構建無向圖,3個頂點分別標號為0、1和2,將頂點0和頂點1分別與頂點2相連構成由3個頂點2條邊組成的無向連通圖。如果將頂點0和1與頂點2之間的邊全部切割開就會得到該圖的最大割解,如圖2所示。

圖2 3個頂點的無向圖及其最大割解

對于3個頂點的圖,需要用3個量子比特|z1〉|z2〉|z3〉來表示相應頂點0、1、和2的狀態。將實驗最后測得量子比特狀態,|0〉態標同一種顏色,|1〉態標另一種顏色。

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

(17)

Hp為經計算得到對角矩陣,其對角線元素依次為0、-2、-1、-1、-1、-1、-2、0。

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

圖3 3個頂點無向圖最大割問題的哈密頓量期望值變化曲線

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

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

3.2 6個頂點的稀疏無向圖

為驗證量子絕熱算法能夠解決一些更復雜圖的最大割問題,將問題規模進一步復雜化,取6個頂點,分別標號0、1、2、3、4和5,構造稀疏無向圖。稀疏圖即表示有很少條邊(|E|?|V|2)的圖,構建稀疏圖及其最大割解如圖4所示。

圖4 6個頂點的稀疏無向圖及其最大割解Fig.4 6-vertex undirected sparse graph and its max-cut solution

圖4顯示，對條邊劃分后最多有7條邊被切割,因此,最大割解值為-7。同理,對于6個頂點的圖需要6個量子比特來表示頂點所屬集合狀態。由式(10)和式(11)可得,最大割問題的哈密頓量Hp為26×26的對角矩陣,其對角元素為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為基態能量,對應最大割哈密頓量期望理論測量值也為-7。

對于線性演化路徑下的增量Δs,分別取0.2、0.1、0.01來分析增量取值大小對最大割問題哈密頓量期望值〈Hp〉的影響,如圖5所示。

圖5 不同增量Δs下6個頂點稀疏無向圖最大割問題的哈密頓量期望值變化曲線

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

由圖5可知,當增量Δs取值越趨向于0時,演化到最終基態的最大割問題哈密頓量期望值越小,即表明有越大的概率得到最大割問題的最優解,準確率越高。對于取較大增量時,參數s從0增加到0.5時最大割問題哈密頓量的期望值有更快的下降速率,這意味著較大的增量在初期可以提高算法的效率。

當Δs=0.01時,量子絕熱算法求解6個頂點稀疏圖的最大割問題的準確率為0.999 9。

3.3 6個頂點的完全無向圖

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

圖6 6個頂點的完全圖及其最大割解

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

圖6中共有15條邊,對應最大割問題的哈密頓量Hp對角元素為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的對角矩陣,基態能量為-9,對應最大割哈密頓量期望理論測量值也為-9。根據稀疏圖例子將增量Δs取0.01,對最大割問題哈密頓量的期望值〈Hp〉變化曲線如圖7所示。

圖7 6個頂點完全圖的最大割哈密頓量期望值變化曲線

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

由圖7可以看出,在參數s從0增加到1的過程中,最大割問題哈密頓量的期望值總體呈下降趨勢,量子絕熱算法計算出最大割問題最優解的概率較高,測量結果的準確率為0.969 6。

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

4 結束語

本文利用量子絕熱算法求解無向圖最大割問題,結合量子近似的思想設計算法中的演化算子,從而求解最大割問題的哈密頓量。與傳統近似算法相比,該算法的時間復雜度不依賴于圖的頂點個數以及邊的條數,僅與增量Δs的取值相關,并可通過量子比特門的邏輯組合實現。本文列舉了3個最大割問題的實例,并用ProjectQ進行編程模擬。數值分析結果表明,在頂點數較少的最大割問題中,量子絕熱近似算法準確率高于文獻[5]算法和隨機近似算法。針對最大割問題的哈密頓量期望值隨參數s變化導致曲線不平滑的問題,下一步將根據具體無向圖來調整變化的增量Δs,減少無向圖復雜度對計算準確率的影響。