耦合強度對量子絕熱算法求解最大割的影響①

高薪凱,倪 明,周 明,吳永政

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

1 概述

最大割問題(max-cutproblem)是指對給定的無向加權(quán)圖求解出一個最大分割,使得頂點集的互補子集I與R之間所有割邊的權(quán)值之和最大.作為圖論問題中典型的組合優(yōu)化問題,最大割問題被廣泛應(yīng)用于圖像處理、網(wǎng)絡(luò)優(yōu)化,超大規(guī)模集成電路等諸多工程中,研究最大割問題的有效求解算法具有十分重要的應(yīng)用價值[1].在文獻[2,3]中,Khot和Ageev 證明了最大割問題是NP-Hard 問題.從理論上看,最大割問題不存在多項式時間的精確算法.因此發(fā)展出許多以損失精度為代價提高計算效率的啟發(fā)式算法[4],如模擬退火算法,蟻群算法,人工神經(jīng)網(wǎng)絡(luò)等.基于量子效應(yīng)的量子計算是以量子比特作為信息編碼和存儲的基本單元.Deutsch 等人提出在計算方面量子計算的性能要優(yōu)于電子計算[5],選用合適的量子算法可使經(jīng)典計算機中某些NP 問題指數(shù)級加速[6].根據(jù)量子絕熱模型設(shè)計的量子絕熱算法以絕熱定理為基礎(chǔ),可對如同最大割問題、旅行商問題的布爾可滿足性問題(Sat 問題)進行求解[7].量子絕熱算法核心是構(gòu)造一個量子絕熱系統(tǒng),控制系統(tǒng)哈密頓量從初始哈密頓量演化到目標(biāo)哈密頓量,通過求解目標(biāo)哈密頓量的基態(tài)間接獲得待求解問題的近似解[8].

文獻[9]中利用ProjectQ 編程包初步實現(xiàn)了量子絕熱算法對最大割問題的求解程序,并通過計算頂點數(shù)為3和6的無向圖的最大割問題驗證了算法的可行性.但實驗研究的對象為規(guī)模較小的最大割問題,且并未考慮無向圖中邊的權(quán)值對于量子絕熱算法的影響.本文基于文獻[9]的工作,加入量子比特間耦合強度(即無向圖中邊的權(quán)值),通過分析規(guī)模較大的最大割問題的求解情況,研究量子比特間耦合強度對于量子絕熱算法求解最大割問題的影響,并且對算法改進提出一種新思路.由于量子絕熱算法演化過程需保證系統(tǒng)的態(tài)始終為基態(tài),因此需要分析最大割問題哈密頓量的期望值在演化過程中的變化情況.利用程序繪制在演化過程中期望值變化曲線.本文測試量子絕熱算法求解6–13個頂點完全無向圖的最大割問題時期望值的變化情況.對于頂點數(shù)為8、12和13的完全無向圖的最大割問題,當(dāng)耦合強度全部為1 時,量子絕熱算法的期望值變化情況不符合要求.因此調(diào)整耦合強度,分析量子絕熱算法求解最大割問題時期望值收斂對應(yīng)的耦合強度范圍.由此拓展到量子絕熱算法求解一般情形下8、12和13個頂點的最大割問題時的改進方法.

2 基于量子絕熱算法的最大割問題求解程序

2.1 最大割問題

最大割問題如圖1(a)所示.待求解的無向圖有a、b、c、d、e 共5個頂點,每條邊上的數(shù)字為邊的權(quán)重值,如頂點d和e 之間邊的權(quán)重為20.現(xiàn)要求將5個頂點分為兩個互補子集I和R,使得兩個子集間所有邊的權(quán)重之和最大.圖1(b)為該待求解無向圖對應(yīng)的最優(yōu)解,5個頂點分為I={b,e}和R={a,c,d}兩個子集.紅色虛線表示切割線,黑色虛線表示兩個頂點子集之間的邊,即切割邊.該最優(yōu)解的切割邊包含(a,b),(a,e),(b,c),(b,d),(c,e),(d,e),對應(yīng)權(quán)重值總和為2+6+8+5+4+20=45.

圖1 最大割問題及完全無向圖示意圖

對于求解最大割問題,任何無向圖都可以轉(zhuǎn)化為完全無向圖,只需將不存在的邊的權(quán)重值設(shè)為零,使該邊對最大割問題的求解沒有影響.如圖1(c),左側(cè)為原圖,右側(cè)為對應(yīng)的完全圖黑色虛線為添加邊,權(quán)值為0,紅色虛線為切割線,更改前后最優(yōu)解不變.因此本文實驗主要研究對象為完全無向圖.

2.2 程序求解步驟

下文以3個頂點無向圖為例,如圖2(a),說明程序求解步驟.

(1)輸入待求解的完全無向圖;

(2)根據(jù)無向圖構(gòu)造最大割問題哈密頓量Hm,n;

(3)根據(jù)量子絕熱模型構(gòu)造初始哈密頓量Hi,n;

(4)結(jié)合演化路徑,構(gòu)造系統(tǒng)哈密頓量Hs,n;

(5)實現(xiàn)系統(tǒng)哈密頓量按量子算法線路演化,求得最大割問題哈密頓量的基態(tài)|ξ(1)>,即近似解;

(6)記錄每一時刻系統(tǒng)哈密頓量的基態(tài)|ξ(τ)>,繪制演化過程中期望值<ξ(τ)|Hm,n|ξ(τ)>的變化曲線,判斷是否隨演化時間下降并收斂.若不是則需調(diào)整參數(shù)重新計算.

2.3 構(gòu)造量子絕熱系統(tǒng)

量子絕熱算法的核心是構(gòu)建一個量子絕熱系統(tǒng),對應(yīng)程序求解第(2)、(3)、(4)、(5)步.

第(2)步根據(jù)待求解無向圖的邊構(gòu)造最大割問題哈密頓量.定義量子絕熱近似求解n個頂點的完全無向圖最大割問題的任意一個解為|α>=|α0>|α1>…|αn–1>,其中[8,10],

則圖2(a)對應(yīng)的最優(yōu)解為|0>|1>|1>.

以|α>作為基態(tài)構(gòu)造最大割問題哈密頓量為[9]:

其中,n為待求解無向圖的頂點數(shù),ei,j表示完全無向圖中的以頂點i和j為端點的邊(i,j),wi,j為邊(i,j)對應(yīng)的權(quán)重值,對應(yīng)量子比特間的耦合強度,泡利矩陣上標(biāo)(i)表示對量子邏輯線路中第i位量子比特進行操作.表示對于完全無向圖中每一條邊(i,j),在量子算法線路中分別對第i和j位量子比特增加一次泡利矩陣σz門操作,對其他位置的量子比特分別增加一次單位矩陣I門操作.則圖2(a)對應(yīng)的最大割問題哈密頓量為:

第(2)步根據(jù)量子絕熱模型構(gòu)造初始哈密頓量[9,11],定義:

其中,n為待求解無向圖的頂點數(shù),泡利矩陣σx=分別對每一位量子比特進行一次(I–σx)門操作.則圖2(a)對應(yīng)的初始哈密頓量為:

根據(jù)量子絕熱模型,初始哈密頓量的基態(tài)應(yīng)是簡單且容易構(gòu)造的.經(jīng)計算Hi,n的基態(tài)為其中|+>=(|0>+|1>)/√2.在量子算法線路中可將Hadamard 量子邏輯門作用在|0>態(tài)上制得|+>.因此該初始哈密頓量符合要求.

第(4)步結(jié)合上述兩步,構(gòu)造系統(tǒng)哈密頓量[12]:

其中,演化時間t的取值范圍是[0,T],演化路徑p(t)和q(t)滿足邊緣條件:

將式(7)代入式(6)有:

邊緣條件保證了系統(tǒng)哈密頓量Hs,n從初始哈密頓量Hi,n演化到最大割問題哈密頓量Hm,n,使得系統(tǒng)的態(tài)|ξ>從Hi,n的基態(tài)演化到Hm,n的基態(tài).為了方便計算,實驗中采用線性路徑,設(shè)為:

令τ=t/T,Δτ=1/T,可知τ的取值范圍是[0,1].由式(6)和式(9)可得系統(tǒng)哈密頓量為[11,13]:

則圖2(a)對應(yīng)的系統(tǒng)哈密頓量為:

第(5)步根據(jù)量子絕熱模型設(shè)置量子算法線路:

對于圖2(a),程序在第i個Δτ時刻對所有量子比特進行一次Um(i*Δτ)和Ui(i*Δτ)運算[14],使得系統(tǒng)哈密頓量Hs,3(式(11))從初始哈密頓量Hi,3(式(5))向最大割問題哈密頓量Hm,3(式(3))演化.并在每一時刻紀錄各個量子比特的狀態(tài)|ξ(τ)>,最終輸出|ξ(1)>=|0>|1>|1>即為算法所求近似解.

圖2 程序?qū)? 頂點無向圖的求解情況

2.4 檢驗演化

基于量子絕熱算法的最大割求解算法是以犧牲精確度為代價換取計算效率,屬于啟發(fā)式算法.量子絕熱算法需要保證系統(tǒng)在絕熱條件下演化,程序根據(jù)量子絕熱算法模擬絕熱條件,演化過程中系統(tǒng)的最低能級對應(yīng)求解問題的最優(yōu)解.當(dāng)系統(tǒng)哈密頓量的期望值隨演化時間逐漸減小并收斂于某值,此時的系統(tǒng)量子態(tài)對應(yīng)于該問題的最優(yōu)解,收斂值對應(yīng)于該問題的最大割值.在系統(tǒng)哈密頓量演化過程中,程序第(5)步中在每一個Δτ時刻執(zhí)行完量子操作后,紀錄當(dāng)前所有量子比特的狀態(tài),即每一時刻系統(tǒng)哈密頓量的基態(tài)|ξ(τ)>.結(jié)合最大割問題哈密頓量Hm,n,計算并繪制最大割問題哈密頓量的期望值[15]<ξ(τ)|Hm,n|ξ(τ)>的變化曲線,如圖2(b).根據(jù)量子絕熱模型,當(dāng)期望值隨演化時間τ減小并收斂,則所得近似解即為最優(yōu)解.

3 期望值變化曲線分析

3.1 程序?qū)Σ煌旤c數(shù)的完全無向圖的求解情況

本文測試了頂點數(shù)為6–13的完全無向圖最大割求解,最大割問題哈密頓量的期望值變化曲線如圖3所示.量子比特間耦合強度wi,j全部設(shè)置為1,Δτ取0.01.由于完全無向圖中頂點數(shù)目不同,導(dǎo)致量子比特數(shù)不同,Hm,n和|ξ(τ)>的值也不同,因此不同頂點無向圖對應(yīng)的期望值在任一時刻都不同.

由圖3可知,頂點數(shù)為6、7、9、10和11的完全無向圖,最大割問題哈密頓量的期望值隨演化時間τ逐步減小并收斂于最小值,算法所求解即為最優(yōu)解.對于8個頂點完全無向圖,如圖3(c)所示,期望值在演化時間τ取[0,0.5]時從初始值減小到最小值.在演化時間τ=0.5 附近開始增大,并在τ=0.6 附近到達極大值.在0.6<τ<1 范圍內(nèi),期望值在一個大于初始值的區(qū)間內(nèi)振蕩.由圖3(g)和圖3(h)可知,頂點數(shù)為12和13的完全無向圖對應(yīng)的期望值在0<τ<0.2 區(qū)間內(nèi)逐步減小.期望值在0.2<τ<0.6 內(nèi)先增大再減小后繼續(xù)增大,其中當(dāng)演化時間τ=0.4 左右,期望值達到極大值,當(dāng)演化時間τ=0.5 附近,期望值為極小值.從演化時間τ=0.6 開始,期望值分別在–32.3和–37 附近小幅度波動.

結(jié)果表明,當(dāng)頂點數(shù)較多時期望值出現(xiàn)不收斂的情況,并且收斂效果越來越差.因此需要調(diào)整實驗參數(shù),使得頂點數(shù)為8,12和13的完全無向圖對應(yīng)的期望值曲線隨演化時間逐步下降直至收斂.

圖3 不同頂點數(shù)的期望值變化

3.2 耦合強度對量子絕熱近似求解最大割的影響

在量子絕熱算法為數(shù)不多的參數(shù)中,有一個相對重要的參數(shù)——量子比特間耦合強度.耦合強度代表了彼此有關(guān)聯(lián)的量子比特相互作用的強度.兩個量子比特間相互作用越強,這兩個量子比特越容易互相影響.在絕熱演化過程中,系統(tǒng)能量的變化易受量子比特間相互作用影響,從而影響量子絕熱算法的準確率.在求解最大割問題時,算法中每一個量子比特對應(yīng)無向圖中唯一一個頂點,因此兩個量子比特間耦合強度對應(yīng)了無向圖中以這兩個量子比特對應(yīng)頂點為端點的邊的權(quán)重值.權(quán)重值越大,耦合強度越大,量子比特間的相互影響越強.由于耦合強度的存在,導(dǎo)致了在演化過程中系統(tǒng)的態(tài)受到耦合強度的影響從而偏離最低能量變化路徑.并且當(dāng)最大割問題規(guī)模增加時,量子比特數(shù)相應(yīng)增加,與任一量子比特互相耦合的量子比特數(shù)也增加,該量子比特在演化過程中更加容易受到影響,從而導(dǎo)致演化過程中系統(tǒng)的能量受到影響.因此需要研究耦合強度對于量子絕熱算法求解最大割問題的影響,從而使得量子絕熱算法在求解最大割問題時稍加改進.

根據(jù)3.1 節(jié)所得的實驗結(jié)果,采用量子絕熱算法求解最大割問題時,當(dāng)頂點數(shù)目增加時,量子比特的數(shù)目增加,量子比特間的相互作用情況更為復(fù)雜,其計算最優(yōu)解將會更加困難.因此嘗試耦合強度wi,j在0.7 到1 之間變化,每隔0.05 取值,分析耦合強度對于所求解完全無向圖期望值的影響.根據(jù)上述條件,求解頂點數(shù)為8,12,13的完全無向圖的最大割問題,變化情況如圖3所示.

由圖4(a)給出了不同耦合強度下8個頂點的完全無向圖的求解情況.在演化時間小于0.5 時,量子比特間的耦合強度對期望值變化沒有明顯的影響.當(dāng)演化時間在0.5 到1 之間時,當(dāng)耦合強度取0.7,0.75和0.8時,期望值始終處于下降趨勢,并最終收斂.對于12個頂點的完全無向圖,不同耦合強度對期望值的影響如圖4(b)所示.演化時間取0 到0.25 之間時,期望值受耦合強度的影響可忽略不計.當(dāng)演化時間大于0.5 時,相比于耦合強度的其他取值,0.85和0.9 對應(yīng)的期望值曲線沒有上升趨勢,且的收斂效果最好.當(dāng)頂點數(shù)增加到13 時如圖4(c),期望值在演化時間取[0,0.2]區(qū)間內(nèi)不受耦合強度的影響.演化時間在0.2 到1 之間變化時,耦合強度取0.95,期望值走勢最差,而耦合強度為0.7,0.75和0.8 對應(yīng)的期望值曲線始終下降并收斂.

結(jié)合圖4所示的數(shù)據(jù)結(jié)果,當(dāng)完全無向圖的頂點數(shù)為8和13 時,量子比特間的耦合強度取0.7,0.75和0.8,最大割問題哈密頓量的期望值變化趨勢符合算法要求.而對于12個頂點的完全無向圖,耦合強度取0.85和0.9 時,期望值才能較好地收斂.綜合上述結(jié)果分析,耦合強度過高或者過低都會導(dǎo)致系統(tǒng)的態(tài)在演化過程中偏離基態(tài),降低算法的準確度.并且除頂點數(shù)為12的完全無向圖,耦合強度取0.75 時期望值變化效果最好.由此提出一種改進方案,在量子絕熱算法求解最大割問題時,為使期望值收斂得到最優(yōu)解,可將最大割問題的量子比特間耦合強度按比例映射到相應(yīng)區(qū)間,例如將12個頂點的最大割問題的耦合強度按比例映射到0.85–0.9 區(qū)間內(nèi),頂點數(shù)為8和13 對應(yīng)的所有耦合強度按比例映射到以0.75為中值的區(qū)間內(nèi).

3.3 普遍情況下的完全無向圖求解情況

根據(jù)3.2 節(jié)所得結(jié)論,測試頂點數(shù)為8、12、13,且每一個量子比特間耦合強度均不同的完全無向圖,期望值變化曲線如圖5所示.由于耦合強度的變化導(dǎo)致最大割問題哈密頓量變化,因此耦合強度調(diào)整前后期望值曲線的起始值也發(fā)生變化.

圖4 不同耦合強度下期望值變化情況

構(gòu)造一個8 頂點的完全無向圖,其耦合強度為1 到28 依次加1的自然數(shù)列.程序求解過程中期望值變化情況如圖5(a)左圖所示,此時期望值在?200 左右波動,不滿足要求.因此調(diào)整耦合強度,將8個頂點無向圖的耦合強度映射為0.735 到0.762 依次加0.001的等差數(shù)列,期望值變化情況如圖5(a)右圖所示.對于頂?shù)讛?shù)為12的完全無向圖,構(gòu)造耦合強度為1 到66 依次相差1的序列,對應(yīng)的期望值如圖5(b)左圖所示,期望值先增大后減小,不符合要求.根據(jù)3.2 節(jié)得出的結(jié)論,將其耦合強度映射到區(qū)間[0.842,0.908],調(diào)整后的期望值變化如圖5(b)右圖所示.同理將13個頂點對應(yīng)的耦合強度(為1 到78的等差數(shù)列,期望值變化情況如圖5(c)左圖所示)映射到以0.75為中值的區(qū)間上,期望值變化曲線如圖5(c)右圖所示.對比可知調(diào)整前,期望值都是先增大后減小且終值大于初值,演化過程中系統(tǒng)并未一直處于基態(tài),算法不能給出最優(yōu)解.調(diào)整耦合強度以后,期望值曲線明顯處于下降趨勢且最終開始收斂,滿足量子絕熱算法要求.由于耦合強度是按比例映射的,對于最優(yōu)解的選擇沒有影響,因此調(diào)整后算法給出的解即為調(diào)整前對應(yīng)的最優(yōu)解.

圖5 耦合強度調(diào)整前后對比

4 結(jié)束語

本文通過編程模擬量子絕熱算法求解不同頂點的完全無向圖的最大割問題,發(fā)現(xiàn)對于頂點數(shù)量較小的完全圖,例如3 到7個頂點的情形,所得期望值收斂,量子絕熱算法可以表現(xiàn)出較好的求解精確度.當(dāng)頂點數(shù)增加到8、12和13個時,量子絕熱算法所求解對應(yīng)的期望值不收斂.隨著完全無向圖的頂點數(shù)目增加,量子比特間相互作用更加復(fù)雜,造成期望值不收斂的原因也有多種可能.可以通過調(diào)整計算步長,演化路徑,哈密頓量等參數(shù),嘗試使期望值趨于收斂.本文嘗試調(diào)節(jié)量子比特間耦合強度,使多頂點的問題求解的期望值隨演化時間減小并收斂,為量子絕熱算法求解較多頂點數(shù)的最大割問題提供了一個改進思路.