量子近似優(yōu)化算法在約束優(yōu)化問(wèn)題中的應(yīng)用

劉 暢,張學(xué)鋒

安徽工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,安徽 馬鞍山 243000

1 引 言

量子近似優(yōu)化算法(Quantum Approximate Optimization Algorithm,QAOA)是一種可變量子算法,旨在為組合優(yōu)化問(wèn)題提供解決方案。由于量子近似優(yōu)化算法的核心問(wèn)題是計(jì)算目標(biāo)哈密頓量期望值,在一般的淺層量子電路上,能否找到一種求解量子期望值的有效經(jīng)典算法以便快速獲取最佳可變參數(shù)對(duì)于在含噪聲的中型量子硬件上展示潛在的量子優(yōu)勢(shì)至關(guān)重要。在量子近似優(yōu)化算法背景下求解帶約束的組合優(yōu)化問(wèn)題時(shí),需要找到一種將問(wèn)題的約束編碼到方案中的方法。對(duì)于約束問(wèn)題,在QAOA中有兩種處理約束的方法。

第一種是二次無(wú)約束二元優(yōu)化方法,是當(dāng)有約束違反時(shí),在目標(biāo)算符中加入懲罰項(xiàng)[1-3],將不符合解的期望值降低,但初始時(shí)需要在全部解集上迭代,使得迭代次數(shù)變多。另一種方法是量子交替擬設(shè)方法,主要思想是重新設(shè)計(jì)編碼了約束條件的演化算符,使得量子態(tài)演化限制在可行解范圍內(nèi)[4-6],雖然初始時(shí)混合操作被限制在可行解空間中,但向目標(biāo)函數(shù)演化時(shí),最優(yōu)解的期望值不一定是最優(yōu)的,使得用該方法求解出問(wèn)題的最優(yōu)解不一定是問(wèn)題的最優(yōu)解,準(zhǔn)確性較低。

對(duì)于約束優(yōu)化問(wèn)題融合了二次無(wú)約束二元優(yōu)化方法和量子交替擬設(shè)方法這兩種方法,通過(guò)將約束問(wèn)題中不符合約束條件的解剔除,只留下可行解作為量子近似優(yōu)化算法框架的初始基態(tài),使得混合操作在初始基態(tài)上進(jìn)行。數(shù)值證明了這可以提供更高質(zhì)量的解。并在目標(biāo)函數(shù)中添加懲罰項(xiàng),將對(duì)角線中不符合解的期望降低。將一個(gè)約束問(wèn)題轉(zhuǎn)變成一個(gè)無(wú)約束問(wèn)題,從而高質(zhì)量解決一般約束問(wèn)題。

2 最小頂點(diǎn)覆蓋問(wèn)題

最小頂點(diǎn)覆蓋(Minimum Vertex Cover,MVC)問(wèn)題是一個(gè)著名的NP-hard問(wèn)題[7]。最小頂點(diǎn)覆蓋問(wèn)題描述為:給定一個(gè)圖G=(V,E),其中V是圖的頂點(diǎn)集,E是邊集。A為V的子集,若G中的每一條邊都至少接觸集合A中的一個(gè)頂點(diǎn),則稱A為覆蓋集,包含頂點(diǎn)最少的A則稱為最小頂點(diǎn)覆蓋集。

A中的頂點(diǎn)可用一個(gè)取值為0或1的變量xi表示,xi=1表示圖中對(duì)應(yīng)的頂點(diǎn)i在覆蓋集A中,xi=0表示頂點(diǎn)i不在A中。那么,A可以用向量x表示,x=(xi)∈{0,1}|V|,并滿足約束:任意的(i,j)∈E,xi=1或者xj=1。由此,該問(wèn)題即是尋找x*:

|x*|=minimize∑i∈Vxi

subject to all(i,j)∈E,thenxi=1∨xj=1

3 量子近似優(yōu)化算法

3.1 絕熱量子計(jì)算

絕熱量子計(jì)算(Adiabatic Quantum Computation,AQC)是一種通過(guò)連續(xù)絕熱量子演化的方式來(lái)解決計(jì)算問(wèn)題的量子計(jì)算模型。對(duì)于一個(gè)物理系統(tǒng),其哈密頓量是可以調(diào)控的。針對(duì)一個(gè)給定的問(wèn)題,找到目標(biāo)哈密頓量,在準(zhǔn)備一個(gè)具有簡(jiǎn)單哈密頓量的系統(tǒng)并初始化為基態(tài),簡(jiǎn)單的哈密頓量絕熱地演化為期望的目標(biāo)哈密頓量。最后系統(tǒng)的狀態(tài)描述了問(wèn)題的解決方案。

絕熱量子計(jì)算是通過(guò)以下過(guò)程解決特定問(wèn)題和其他組合搜索問(wèn)題。通常這種問(wèn)題就是尋找一種狀態(tài)滿足C1∧C2∧…∧CM,表達(dá)式包含可滿足條件的M個(gè)子問(wèn)題,每個(gè)子問(wèn)題Ci值為True或 False,并且可能包含n位,這里的每一位都是一個(gè)變量xj∈{0,1} 所以Ci是一個(gè)關(guān)于x1,x2,…,xn的布爾值函數(shù),絕熱量子算法利用量子絕熱演化解決了這類問(wèn)題。它以初始哈密頓量HB開(kāi)始:

HB=HB1+HB2+…+HBM

這里HBi對(duì)應(yīng)于該子問(wèn)題Ci的哈密頓量,通常選擇的HBi不會(huì)依賴于其他的子問(wèn)題。然后經(jīng)歷絕熱演化,以問(wèn)題的哈密頓量Hp結(jié)束:

這里HP,C是滿足問(wèn)題C的哈密頓量,它有特征值0和1。如果子問(wèn)題C滿足條件,則特征值為1,不滿足則特征值為0。對(duì)于一個(gè)簡(jiǎn)單的絕熱演化路徑,如圖1所示。

這就是算法的絕熱演化哈密頓量。

圖1 絕熱演化路徑Fig.1 Adiabatic evolutionary path

根據(jù)絕熱定理,從哈密頓量的基態(tài)開(kāi)始HB,首先,經(jīng)歷一個(gè)絕熱過(guò)程,最后以問(wèn)題哈密頓量的基態(tài)結(jié)束HP;然后測(cè)量最終狀態(tài)n個(gè)自旋的z分量,這將產(chǎn)生一個(gè)字符串Z1,Z2,…,Zn這很可能就是問(wèn)題的結(jié)果。

3.2 量子近似優(yōu)化算法

量子近似優(yōu)化算法是由Farhi等提出的一種啟發(fā)式算法,作為一種近似算法,它并不是給出最好的結(jié)果,而是給出一個(gè)“足夠好”的結(jié)果。量子近似優(yōu)化算法是一種利用經(jīng)典和量子資源尋找組合優(yōu)化問(wèn)題近似解的算法框架[8-10],從量子絕熱算法的近似推導(dǎo)而來(lái)。在求解具有約束的組合優(yōu)化問(wèn)題時(shí),需要找到一種將問(wèn)題約束編碼到方案中的方法,并通過(guò)期望的質(zhì)量來(lái)解決每個(gè)問(wèn)題實(shí)例。

圖2 QAOA的工作流程Fig.2 Work flow of quantum approximate optimization algorithm(QAOA)

(1)

(2)

3.3 二次無(wú)約束二元優(yōu)化方法

二次無(wú)約束二元優(yōu)化方法是對(duì)量子近似優(yōu)化算法的改進(jìn)算法,現(xiàn)已被廣泛研究,并被用于建模和解決許多類別的優(yōu)化問(wèn)題。約束優(yōu)化問(wèn)題的目標(biāo)是最小化或最大化一個(gè)代價(jià)函數(shù),這個(gè)代價(jià)函數(shù)在物理上可以解釋為找到一個(gè)典型的伊辛哈密頓函數(shù)的基態(tài)。二次無(wú)約束二元優(yōu)化方法通過(guò)預(yù)處理將問(wèn)題的約束條件轉(zhuǎn)換到代價(jià)函數(shù)中,從而提高解的質(zhì)量和運(yùn)行時(shí)間。二次無(wú)約束二元優(yōu)化的一個(gè)主要優(yōu)點(diǎn)是它提供了一個(gè)統(tǒng)一的算法框架,適用于解決許多類型的問(wèn)題。

3.4 量子交替擬設(shè)方法

HADFIELD等擴(kuò)展了量子近似優(yōu)化算法框架,根據(jù)不同問(wèn)題設(shè)置了不同的基態(tài)代替了固定的初始基態(tài),將全集均勻疊加態(tài)轉(zhuǎn)化為可行解均勻疊加態(tài),這個(gè)擴(kuò)展的實(shí)質(zhì)被稱為量子交替算符擬設(shè)方法。對(duì)于只需要在期望的子空間內(nèi)進(jìn)行混合的情況,初始哈密頓量在可行解子空間基態(tài)上混合運(yùn)行能夠得到比在原始框架中更高效的結(jié)果。這種方法對(duì)于具有約束的優(yōu)化問(wèn)題特別有用,將滿足約束條件的集合定義為一個(gè)可行解子空間。使得在量子近似優(yōu)化算法的框架下更高效地得到問(wèn)題的最好結(jié)果。

4 基于QAOA的MVC問(wèn)題求解

4.1 提出方法的算法描述

根據(jù)最小頂點(diǎn)覆蓋問(wèn)題的定義,給出了在量子近似優(yōu)化算法框架中的解決方案。求解的過(guò)程如算法1所示:

算法1: 求解最小頂點(diǎn)覆蓋問(wèn)題輸入:圖G=(V,E),迭代次數(shù)p輸出:最小頂點(diǎn)覆蓋集A1) A←satisfy_constraints(G) //satisfy_constraints為求解出圖G的滿足約束的所有解,A為可行解集合2) Ω←x∈binary_systemA(){} //binary_system為將集合A轉(zhuǎn)化為二進(jìn)制集合,x為二進(jìn)制向量3) 初始化:β→,γ→←rand-π,π()4) |s〉←Ω5) B^←∑ni=1σ(xiσxi+1+σyiσyi+1)6) C^←∑2n-1x=0x→·e→|x〉〈x|+2?∑i,j()∈Eσzi+12?σzj+127) ψβ→,γ→()〉←e-iβpB^e-iγpC^…e-iβ1B^e-iγ1C^s〉8) fβ→,γ→()←〈ψβ→,γ→()C^ψβ→,γ→()〉9) β?,γ?←Simplex_optimize(argmaxβ→ ,γ→f(β→,γ→)) //Simplex_optimize為單純性優(yōu)化方法10) A←measure_max(|ψβ→,γ→()〉 //測(cè)量ψβ→,γ→()中最大概率對(duì)應(yīng)的二進(jìn)制向量A11) return A

(3)

(4)

4.2 對(duì)比方法的算法描述

在本節(jié)中,將討論一些對(duì)比方法。

(3) 熱啟動(dòng)量子近似優(yōu)化算法。Egger等[14]對(duì)經(jīng)典算法做了兩個(gè)主要的修改。首先,初始的疊加態(tài)如式(5)所示:

(5)

(6)

連續(xù)松弛解c*可以等于0或1,但最優(yōu)離散解可以分別為1或0。在實(shí)驗(yàn)中,將設(shè)置為0.25(與原作者一致)。

4.3 實(shí)驗(yàn)結(jié)果與討論

(a) 一個(gè)最小頂點(diǎn)覆蓋問(wèn)題實(shí)例

(b) 提出方法的連接結(jié)構(gòu)

(c) 提出方法運(yùn)行得到的期望值圖3 提出方法在實(shí)例運(yùn)行下的結(jié)果Fig.3 The results of the proposed method running in an example

圖4給出了在10個(gè)隨機(jī)圖上運(yùn)行各種方法得到的近似比。從圖4可以看出,隨著p的增加,所有方案平均解的質(zhì)量都有所提高。提出的方法優(yōu)于經(jīng)典方法,QAOA+,熱啟動(dòng)量子近似優(yōu)化算法,提出的方法在p=3時(shí),就已經(jīng)趨于最高近似比。

圖4 隨演化步數(shù)增大時(shí)的近似比Fig.4 The approximate ratio as the number of evolutionary steps increases

圖4中QAOA+算法的性能相比其他3種方法得到的近似比收斂效果最差。因?yàn)镕arhi等提出QAOA+,這是為了為通過(guò)解析的方式分析每一步的效果,并不是為了提高算法的性能。經(jīng)典方法優(yōu)于熱啟動(dòng)量子近似優(yōu)化算法,熱啟動(dòng)量子近似優(yōu)化算法是將離散的初始解變?yōu)檫B續(xù)的初始解狀態(tài),一個(gè)好的松弛初始解可以縮短到最優(yōu)解的進(jìn)化距離。但實(shí)驗(yàn)結(jié)果可以看出,使用連續(xù)解得到的最終最優(yōu)解與問(wèn)題最優(yōu)解相差甚遠(yuǎn)。反之,無(wú)偏差的均勻疊加狀態(tài)更有利于后續(xù)進(jìn)化到最終最優(yōu)狀態(tài)。

提出的方法優(yōu)于經(jīng)典方法,因?yàn)樘岢龅姆椒ǖ难莼臻g更小,收斂到最優(yōu)解的迭代次數(shù)減少。所以在圖4中,可以看到提出的算法的性能非常優(yōu)異。

5 結(jié) 論

研究提出了新的方法并回顧了現(xiàn)有的方法,將這些方法應(yīng)用到帶有約束的最小頂點(diǎn)覆蓋問(wèn)題中。提出的方法中,先確定可行解空間,使初始態(tài)為可行解的均勻疊加態(tài)。這樣做縮小了初始態(tài)的范圍,使混合操作限定在可行解空間內(nèi), 對(duì)混合算子進(jìn)行了約束,將一個(gè)不等式約束問(wèn)題轉(zhuǎn)化為等式約束問(wèn)題。再在目標(biāo)函數(shù)中添加懲罰項(xiàng),將對(duì)角線中不符合解的期望降低。將一個(gè)約束問(wèn)題轉(zhuǎn)變成一個(gè)無(wú)約束問(wèn)題。同其他方法相比較,方案可高效率、高準(zhǔn)確性地解決問(wèn)題。

在未來(lái)的工作中,計(jì)劃將提出的方案變成量子線路。并將應(yīng)用于其他約束組合優(yōu)化問(wèn)題,如最大割問(wèn)題、旅行商問(wèn)題等。這些問(wèn)題在許多學(xué)科中都有重要的應(yīng)用,并將研究基于機(jī)器學(xué)習(xí)的量子近似優(yōu)化算法方法應(yīng)用于約束組合優(yōu)化問(wèn)題中。