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

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

1 概述

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

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

2 基于量子絕熱算法的最大割問(wèn)題求解程序

2.1 最大割問(wèn)題

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

圖1 最大割問(wèn)題及完全無(wú)向圖示意圖

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

2.2 程序求解步驟

下文以3個(gè)頂點(diǎn)無(wú)向圖為例,如圖2(a),說(shuō)明程序求解步驟.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖2 程序?qū)? 頂點(diǎn)無(wú)向圖的求解情況

2.4 檢驗(yàn)演化

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

3 期望值變化曲線(xiàn)分析

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

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

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

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

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

3.2 耦合強(qiáng)度對(duì)量子絕熱近似求解最大割的影響

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

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

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

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

3.3 普遍情況下的完全無(wú)向圖求解情況

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

圖4 不同耦合強(qiáng)度下期望值變化情況

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

圖5 耦合強(qiáng)度調(diào)整前后對(duì)比

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

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