劉 暢,張學(xué)鋒

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

1 引 言

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

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

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

2 最小頂點覆蓋問題

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

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

|x*|=minimize∑i∈Vxi

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

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

3.1 絕熱量子計算

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

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

HB=HB1+HB2+…+HBM

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

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

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

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

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

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

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

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

(1)

(2)

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

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

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

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

4 基于QAOA的MVC問題求解

4.1 提出方法的算法描述

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

算法1: 求解最小頂點覆蓋問題輸入:圖G=(V,E),迭代次數(shù)p輸出:最小頂點覆蓋集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(|ψβ→,γ→()〉 //測量ψβ→,γ→()中最大概率對應(yīng)的二進(jìn)制向量A11) return A

(3)

(4)

4.2 對比方法的算法描述

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

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

(5)

(6)

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

4.3 實驗結(jié)果與討論

(a) 一個最小頂點覆蓋問題實例

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

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

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

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

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

提出的方法優(yōu)于經(jīng)典方法,因為提出的方法的演化空間更小,收斂到最優(yōu)解的迭代次數(shù)減少。所以在圖4中,可以看到提出的算法的性能非常優(yōu)異。

5 結(jié) 論

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

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