QAOA最大切割問題的類Dijkstra優(yōu)化及實(shí)現(xiàn)

摘 要：最大切割問題是可以用量子近似優(yōu)化算法（QAOA）來解決的典型問題，Ansatz線路構(gòu)造為該算法的重要組成部分。為了減少多種圖結(jié)構(gòu)在QAOA中的構(gòu)造代價和提高其穩(wěn)定性，從線路的可優(yōu)化性出發(fā)進(jìn)行分析，結(jié)合 Dijkstra算法的點(diǎn)邊存放特點(diǎn)，提出了該線路的類Dijkstra優(yōu)化算法，并將其應(yīng)用于QAOA最大切割問題。使用Qiskit量子框架來模擬優(yōu)化算法的正確性，并用IBM Quantum Composer的真實(shí)環(huán)境進(jìn)行對比實(shí)驗來驗證優(yōu)化的穩(wěn)定性。與未優(yōu)化的線路相比，此優(yōu)化算法下的CNOT門能減少約40%，其穩(wěn)定性也得到了明顯的提高。結(jié)果表明類Dijkstra優(yōu)化算法可以適用于QAOA最大切割問題的多種圖結(jié)構(gòu)優(yōu)化。

關(guān)鍵詞：量子信息；量子近似優(yōu)化算法；量子線路；最大切割問題；IBM Quantum

中圖分類號：TP301 文獻(xiàn)標(biāo)志碼：A 文章編號：1001-3695（2023）02-010-0378-05

doi： 10.19734/j.issn.1001-3695.2022.06.0328

QAOA maximum cutting problem analogous to Dijkstra optimization and implementation

Pan Wenjie， Li Zhiqiang， Yang Hui

（College of Information Engineering， Yangzhou University， Yangzhou Jiangsu 225100， China）

Abstract：The maximum cut problem is a typical problem in the quantum approximate optimization algorithm （QAOA）， and Ansatz circuit is an important part of the algorithm. In order to reduce the construction cost of various graph structures in QAOA and improve its stability， this paper analyzed the optimizability of the circuit， combined the point edge storage characteristics of Dijkstra algorithm， proposed a Dijkstra-like optimization algorithm for the circuit， and applied it to the QAOA maximum cut problem. The paper used the Qiskit quantum framework to simulate the correctness of the optimization algorithm and used the real environment of IBM Quantum Composer to perform comparative experiments to verify the stability of the optimization. After comparing with the initial algorithm， the proposed algorithm reduced the CNOT gate by about 40% and significantly improves its stability. The results show that the Dijkstra-like optimization algorithm can optimize the QAOA maximum cut pro-blem of multiple graph structures.

Key words：quantum information; QAOA; quantum circuit; max-cut; IBM Quantum

0 引言

量子近似優(yōu)化算法（QAOA）是近期被廣泛研究的量子算法之一，該算法提出的目的是為了解決組合優(yōu)化問題［1］。一般來說，組合優(yōu)化問題都是NP-hard問題，而對于給定的NP-hard問題，QAOA是一種多項式時間算法，該算法以期望的質(zhì)量來保證解決每個問題實(shí)例，能很好地展示量子霸權(quán)的潛力［2］。最大切割問題是組合優(yōu)化問題的一種，也是目前QAOA最熱門的研究。在現(xiàn)今的NISQ量子技術(shù)中，與單量子比特門相比，CNOT門是其關(guān)鍵誤差的來源之一［3］，所以CNOT門數(shù)的減少可以降低噪聲，增強(qiáng)線路運(yùn)行的穩(wěn)定性。

QAOA又分為量子運(yùn)算部分和經(jīng)典運(yùn)算部分［4］，本文則基于QAOA最大切割問題量子部分中最重要的Ansatz線路［5］構(gòu)造來展開研究。在QAOA最大切割問題中，線路構(gòu)造存在減少CNOT門以達(dá)到優(yōu)化的可能性。目前，QAOA線路已有Majumdar等人［6］提出了優(yōu)化推導(dǎo)并使用了深度優(yōu)化［7］來應(yīng)用于查找可優(yōu)化邊，其找到的邊可以刪去線路中對應(yīng)的第一個CNOT門，此優(yōu)化方法在無噪聲下與初始線路運(yùn)算相比能保證結(jié)果相同，并減少CNOT門的數(shù)量，但是其應(yīng)用只能處理單個簡單圖，處理不了多種圖的情況，有其局限性。本文通過分析多種圖的不同場景，結(jié)合Dijkstra點(diǎn)邊存放的特點(diǎn)來設(shè)計線路優(yōu)化算法，該算法可以尋找多種圖的可優(yōu)化邊，不再局限于查找單個簡單圖的優(yōu)化邊。文中對所用到的基本概念進(jìn)行介紹，對QAOA最大切割問題的CNOT門優(yōu)化推導(dǎo)進(jìn)行回顧和總結(jié)，并對多種圖結(jié)構(gòu)提出類Dijkstra優(yōu)化算法來查找可優(yōu)化邊，最后將優(yōu)化算法應(yīng)用于查找可優(yōu)化邊，并據(jù)此搭建量子線路來模擬計算和在真實(shí)環(huán)境進(jìn)行測試。文中的線路參數(shù)均用Qiskit中COBYLA優(yōu)化器優(yōu)化后的參數(shù)［8］來代入實(shí)驗研究：

a）根據(jù)QAOA解決最大切割問題的線路構(gòu)造來分析線路的可優(yōu)化性。

b）從減少CNOT門數(shù)量，綜合考慮不同類型圖的優(yōu)化，提出了類Dijkstra的線路優(yōu)化算法。

c）把提出的優(yōu)化算法應(yīng)用在QAOA最大切割問題的線路，并通過Qiskit量子模擬包實(shí)驗，驗證了此優(yōu)化算法的可行性。

d）在IBM Q［9］真實(shí)的量子系統(tǒng)ibm_oslo下進(jìn)行實(shí)驗，驗證優(yōu)化后的穩(wěn)定性。

1 基本概念

1.1 量子門運(yùn)算

CNOT門是一種2 bit量子門［10］，其對量子位的變換如下：

Hadamard門可將基態(tài)變?yōu)榫鶆虔B加態(tài)［11］，單個Hadamard門作用如下：

對于n bit用Hadamard制備疊加態(tài)［12］如下：

當(dāng)制備疊加態(tài)后如果有其他門操作令量子比特間發(fā)生作用，則需要用ei（xS）來表示相位作用算子，以表示之前作用過的算子對當(dāng)前運(yùn)算的影響，S為作用過的基態(tài)集合，此時|ψ〉在其當(dāng)前狀態(tài)下可以表示為

RZ門和RX門對應(yīng)的算子分別為［13］Rz（θ）=e－iθz2，Rx（θ）=e－iθx2，其中z為Pauli-Z門作用，x為Pauli-X門作用。文中為了方便運(yùn)算，使用2rl來代替θ，則為Rz（θ）=e－irlz。

1.2 QAOA最大切割問題線路結(jié)構(gòu)

QAOA線路構(gòu)造描述：初始的線路構(gòu)造先通過Hadamard門制備疊加態(tài)，然后進(jìn)行邊映射到線路構(gòu)造，兩點(diǎn)構(gòu)成的邊Efg映射到量子線路中為兩個CNOT門和一個RZ構(gòu)成，其中點(diǎn)f為控制點(diǎn)，點(diǎn)g為目標(biāo)點(diǎn)，邊構(gòu)造完需用RX門來放在尾部。單邊構(gòu)造線路如圖1［14］所示，全圖構(gòu)造如圖2所示。

最大切割問題也是一個對稱問題［15］，而在量子領(lǐng)域一個量子比特的基態(tài)分別是|0〉和|1〉，這正好可以表示分組的情況，|0〉和|1〉表示為兩個不同的組。若兩頂點(diǎn)在不同的組，即為可切割邊，用01或10表示。在4.3節(jié)中的實(shí)驗結(jié)果成功次數(shù)就以此判定。

1.3 Dijkstra算法簡述

首先把頂點(diǎn)集合V分成兩組集合：

a）Visited：已求出的頂點(diǎn)集合（初始時只含有源點(diǎn)V0）。

b）V-Remain=Visited：尚未確定的頂點(diǎn)集合。

將Remain中的頂點(diǎn)按遞增的次序加入到Visited中，其條件如下：

a）從源點(diǎn)V0到Visited中其他各頂點(diǎn)的長度都不大于從V0到Remain中任何頂點(diǎn)的最短路徑長度。

b）每個頂點(diǎn)對應(yīng)一個距離值。

Visited中頂點(diǎn)：從V0到此頂點(diǎn)的長度。

Remain中頂點(diǎn)：從V0到此頂點(diǎn)的只包括Visited中頂點(diǎn)作為中間頂點(diǎn)的最短路徑長度。

頂點(diǎn)Visited中的集合即為最短路徑集合［16］。

1.4 圖的生成樹

對連通圖進(jìn)行遍歷，在遍歷所經(jīng)過的邊和所有頂點(diǎn)的組合可看做是一棵樹，通常稱為生成樹。連通圖中，由于任意兩頂點(diǎn)之間可能含有多條通路，遍歷連通圖的方式有多種，在一張連通圖中會有多種不同的生成樹與之對應(yīng)。連通圖中的生成樹必須滿足以下兩個條件：a）樹包含連通圖中所有的頂點(diǎn)；b）任意兩頂點(diǎn)之間有且僅有一條通路。

連通圖頂點(diǎn)為n的生成樹的邊數(shù)為n-1，在3.3節(jié)中需要用到邊數(shù)相等來證明最大不成環(huán)的邊數(shù)。

2 QAOA的線路可優(yōu)化推導(dǎo)過程

上一章介紹了本文中所用到的基本概念，本章主要使用上一章的公式變換來對CNOT的可刪除性進(jìn)行推導(dǎo)，并進(jìn)行總結(jié)。

2.1 線路優(yōu)化推導(dǎo)

假設(shè)有等式如下：

其中：|ψ〉為其疊加態(tài)，由變化式（1）和（4）代入。這里方便運(yùn)算去掉歸一化作用的1/2n，運(yùn)算過程中的比特需要進(jìn)行作用的疊加運(yùn)算，之前疊加運(yùn)算用算子ei（xS）表示，S則表示為之前運(yùn)行過的比特集合。

U1|ψ〉的運(yùn)算推導(dǎo)如下：

2.2 推導(dǎo)總結(jié)

比較式（10）和（13），如果xg為圖中邊未操作過的頂點(diǎn)即描繪邊作用中未運(yùn)行的比特索引，那么xgS，所以xg運(yùn)行到最后未對之前疊加效應(yīng)的相位算子ei（xS）造成影響，所以式（10）和（13）等價。從另一種角度來說Hadamard門的疊加態(tài)是以{0，1}的等概率制備，所以xb與xg結(jié)果為0或1的概率都是50%［17］，不影響兩者的運(yùn)算結(jié)果。綜上所述，U1|ψ〉就與U2|ψ〉等價，在此情況下就可以刪除第一個CNOT門。

綜合以上推導(dǎo)，滿足以下條件的目標(biāo)比特即可優(yōu)化：

a）如果為操作邊起始點(diǎn)比特位，那么此比特位在之前運(yùn)算中已經(jīng)作為CNOT門的控制位或者作為目標(biāo)位。

b）操作邊的目標(biāo)比特位未在之前作為CNOT門的控制點(diǎn)和受控點(diǎn)運(yùn)算過。

c）如果為第一條邊則ei（xS）影響算子不作用即為0，對目標(biāo)操作不會對其當(dāng)前的操作算子造成影響，此邊必可以優(yōu)化。

結(jié)論：映射到圖上可以為找圖中不成環(huán)的最大邊數(shù)的邊。其三種不同的可優(yōu)化場景如圖3所示。

由于圖中的點(diǎn)fgk形成的圖為環(huán)路，所以有一條邊無法優(yōu)化。3.1節(jié)基于此來分析多種不同的圖場景。

3 Dijkstra線路優(yōu)化算法構(gòu)造

本章根據(jù)第2章中得出的可優(yōu)化條件來結(jié)合多種圖結(jié)構(gòu)進(jìn)行分析，并利用Dijkstra點(diǎn)邊存放的特點(diǎn)提出適用多圖的線路優(yōu)化算法。

3.1 圖結(jié)構(gòu)的綜合分析

本文著重解決多圖情況，把圖分為四種不同的情況：a）如圖4連通圖可用一般找路徑算法去尋找；b）如圖5有圖有分支則不能停止查找；c）如圖6有游離點(diǎn)就刪除；d）如圖7為兩個子圖構(gòu)成的非連通圖，因此需要分別尋找邊優(yōu)化。

通過尋找線路來構(gòu)造需要滿足2.2節(jié)中的條件：當(dāng)路徑找到一條邊和之前邊構(gòu)成環(huán)，那這條邊不能優(yōu)化，因為在線路構(gòu)造中形成環(huán)了就說明成環(huán)邊所連的點(diǎn)必是之前作為控制位或者受控位的點(diǎn)，所以這條邊不能被優(yōu)化。換而言之，需要得到最多能優(yōu)化的邊，就是要找最多不成環(huán)的邊數(shù)，也就是圖中所有連通子圖的生成樹。而Dijkstra算法是一般用來求最短路徑的，但是Dijkstra中的點(diǎn)和距離存放特點(diǎn)正好能避免尋找邊成環(huán)，且其中的距離存放也適應(yīng)多種四種圖點(diǎn)的訪問變化，利用此特點(diǎn)來設(shè)計具體算法。

3.2 線路優(yōu)化算法設(shè)計

暫時考慮無權(quán)圖，每條邊的代價即為1，算法設(shè)計如下：

a）3.1節(jié)中已經(jīng)分析過需要找不成環(huán)的最大邊數(shù)，可以使用點(diǎn)和距離存放的特點(diǎn)，設(shè)置集合Visited［（vertex1，distance1）］存放已訪問的頂點(diǎn)vertex1和當(dāng)時訪問頂點(diǎn)的距離。初始化為空。設(shè)置集合Remain［（vertex2，distance2）］存放未訪問過的頂點(diǎn)vertex2和到Visited第一個頂點(diǎn)的距離distance2，初始化時distance2都為-∞。

b）每當(dāng)集合Visited增加頂點(diǎn)時Remain就得刪除相應(yīng)的頂點(diǎn)以達(dá)到不成環(huán)的頂點(diǎn)，為了適應(yīng)四種圖類型，可以通過距離的變化來判斷。因為Visited中頂點(diǎn)依次加入，若一個頂點(diǎn)的距離與前相鄰頂點(diǎn)距離相比變小，那頂點(diǎn)肯定為另一條路徑。

c）每次計算Remain中需要取加1的距離作為路徑的下一頂點(diǎn)，若當(dāng)前路徑?jīng)]有下一頂點(diǎn)則找之前最近的分支點(diǎn)或者另一圖的起始點(diǎn)。而此時離路徑當(dāng)前頂點(diǎn)最近的分支點(diǎn)即為Remain中距離最大的點(diǎn)。而如果下一頂點(diǎn)為另一圖的起始點(diǎn)，每次就通過找距離-∞中的任一個頂點(diǎn)將其距離置0，因為在連通圖中，若頂點(diǎn)數(shù)為k，則從任一頂點(diǎn)遍歷到最后生成樹的邊數(shù)中都是k-1，所以如果發(fā)現(xiàn)Remain中距離相同，可以換選任一點(diǎn)作為新起點(diǎn)，這里通過頂點(diǎn)順序來選擇第一個，然后加入Visited并更新計算Remain。

d）最后當(dāng)Remain為空時，則生成全Visited，若為distance1為0時，那么此頂點(diǎn)要么是全圖第一個頂點(diǎn)，要么就是圖中一個子圖的頂點(diǎn)。如果Visited中的distance1小于之前相鄰頂點(diǎn)且distance1不為0，那此頂點(diǎn)必為之前比它小的頂點(diǎn)的分支點(diǎn)。

算法步驟如下：

a）初始化Visited，Remain，用來存放訪問過的頂點(diǎn)和距離，初始化為空，Remain存放未訪問過的頂點(diǎn)和Visited第一個頂點(diǎn)的距離，Remain中的距離初始化為-∞。

b）選取Remain中距離最大值的頂點(diǎn)和距離，如果距離都相等則選取最大距離中的第一個頂點(diǎn)和其距離，記做方法getMax（）。

c）若為第一次選取，則v=getMax（Remain）開始訪問圖，把頂點(diǎn)v放入Visited，Remain中刪除頂點(diǎn)v，并通過reduceV中的距離計算Remain中頂點(diǎn)到Visited第一個頂點(diǎn)的距離。

d）取Remain中距離最大值reduceV=getMax（Remain）， 并使reduceV替代v重復(fù)步驟c）。

e）頂點(diǎn)遍歷完，得到全集合Visited，若Visited滿足distance遞增的相鄰頂點(diǎn)則構(gòu)成可優(yōu)化邊edge。若距離為0且相鄰下一個距離也為0，則此點(diǎn)為游離點(diǎn)，刪除；否則作為圖中的另一子圖重新構(gòu)成可優(yōu)化邊。若發(fā)現(xiàn)Visited中頂點(diǎn)v′的距離變小并且不為0，則在Visited中從此頂點(diǎn)v′向前查找到距離比v′小的第一個頂點(diǎn)，v′即為此頂點(diǎn)的分支，則也構(gòu)成可優(yōu)化邊edge，這個向前查找的方法記做searchLess（）。最后得到可優(yōu)化邊集合optV。

偽代碼如下：其中1～10為生成Visited，11～20為對Visited距離的判斷生成可優(yōu)化邊集合optV。此算法的時間復(fù)雜度為O（n2）。

算法1 類Dijkstra搜索線路構(gòu)造法

輸入： G為圖矩陣，n為圖的頂點(diǎn)數(shù)。

輸出：Visited為輸出訪問集合，optV為能優(yōu)化的邊集合。

1 Visited ← ［（）］，Remain［（v1，-∞），（v2，-∞），…，（vn，-∞）］

2 for i ← 0 to n：

3 reduceV ← getMax（Remain）

4 Visited.Add（reduceV） and Remain.Remove（reduceV）

5 for j ← 0 to n：

6 if G［reduceV.v］［j］ ！=0 and isExist（Remain.v） then

7 Remain［j］.distance←Visited［i］.distance+1

8 end if

9 end for

10 end for

11 for k ← 0 to Visited.length：

12 if k gt; 1 do：

13 if Visited［k］.distance == 0 then

14 continue

15 end if

16 if Visited［k-1］.distancelt;Visited［k］.distance then

17 optV.Add（［［Visited［i-1］.v，Visited［k］.v］）

18 end if

19 else optV.Add（［searchLess（Visited［k］，k），Visited ［k］.v）

20 end if

21 end for

22 return Visited，optV

3.3 優(yōu)化算法證明

證明 因為此優(yōu)化算法所形成的邊含連通圖中所有的頂點(diǎn)，且每兩個頂點(diǎn)的通路有且僅有一條，所以optV邊集合構(gòu)成生成樹。而有頂點(diǎn)k的單個子連通圖記錄到的所有邊構(gòu)成的生成樹邊數(shù)只能是k-1，所以最大邊數(shù)也為k-1。假設(shè)其圖中由n個不相連的子連通圖構(gòu)成，每個子連通圖的最大邊數(shù)為{Num1，Num2，Num3，…，Numn}，則整個圖的最大邊數(shù)Numall= Num1 +Num2+Num3+Numn，即最多可優(yōu)化邊數(shù)。

此算法是由所有非游離頂點(diǎn)構(gòu)成的不成環(huán)邊數(shù)，即為最大邊數(shù)。如果圖由多個子圖構(gòu)成，則根據(jù)距離在此算法13行中的distance為0作為另一圖的最大邊數(shù)的起始點(diǎn)，若為分支則由算法中的16、17行來判斷記錄。算法最終通過距離判斷記錄組成最大邊數(shù)的邊集合。

4 優(yōu)化算法的應(yīng)用及實(shí)驗

本章使用第3章的線路優(yōu)化算法，據(jù)此尋找圖的可優(yōu)化邊，然后在量子框架中模擬運(yùn)算并生成線路和參數(shù)，最后在真實(shí)量子環(huán)境中進(jìn)行測試。由此來驗證優(yōu)化算法的優(yōu)勢。

4.1 實(shí)驗說明

實(shí)驗分為兩部分。第一部分為4.2節(jié)，編寫優(yōu)化算法代碼和結(jié)合Qiskit框架模擬生成線路，然后輸入任意參數(shù)來與初始線路進(jìn)行模擬運(yùn)算，最后使用其COBYLA優(yōu)化器來生成優(yōu)化后的參數(shù)。 4.2節(jié)用來證明算法優(yōu)化同一圖時參數(shù)無論輸入值為多少，與初始線路對比，結(jié)果都可以保持一致，即通過本文算法，驗證無噪聲環(huán)境下刪除CNOT門是否會影響運(yùn)算結(jié)果，據(jù)此來證明算法優(yōu)化的可行性。第二部分為4.3節(jié)，在IBM Q真實(shí)環(huán)境測試，使用4.2節(jié)生成的線路和參數(shù)來代入IBM Q的ibm_oslo系統(tǒng)環(huán)境進(jìn)行線路構(gòu)造，目的是為了證明在真實(shí)環(huán)境下，優(yōu)化后的方法成功率相比初始線路更具有優(yōu)勢。

4.2 應(yīng)用多頂點(diǎn)圖及線路生成

圖7為n=10的非連通有分支圖，其能代表有分支圖，也能代表多子圖構(gòu)成，所以這里應(yīng)用此圖，由算法1所生成的可優(yōu)化邊opV，若加入線路構(gòu)造對應(yīng)的邊在opV里存在，即可以刪除第一個CNOT門。如果Visited中有距離為0，下個距離點(diǎn)也為0或者沒有頂點(diǎn)，那這個點(diǎn)即為游離點(diǎn)，刪除不帶入線路。構(gòu)造如下線路模擬使用的是Qiskit框架，并且這里目的在于驗證線路的可優(yōu)化性，所以通過優(yōu)化前后的數(shù)據(jù)對比來判斷是否優(yōu)化后能達(dá)到一樣的結(jié)果，所以給線路的Rz和Rx門設(shè)置任意參數(shù)來進(jìn)行線路模擬驗證無噪聲情況下優(yōu)化前后結(jié)果的正確性，若圖由多個圖構(gòu)成，則每個子圖其邊構(gòu)造線路參數(shù)設(shè)置為不同值。

圖7的點(diǎn)和點(diǎn)構(gòu)成邊表示（v，v′）：［（3，7），（8，5），（4，6），（4，0），（6，5），（6，9），（2，5），（2，0），（1，5），（0，9）］。

生成的Visited點(diǎn)和該點(diǎn)到此點(diǎn)出發(fā)點(diǎn)的距離表示（v，distance）：［（0，0），（2，1），（5，2），（1，3），（6，3），（4，4），（9，4），（8，3），（3，0），（7，1）］。

生成可優(yōu)化邊opV點(diǎn)和點(diǎn)構(gòu)成邊表示（v，v′）：［（0，2），（2，5），（5，1），（5，6），（6，4），（6，9），（5，8），（3，7）］。

由于頂點(diǎn)（3，7）為另一圖，則其邊構(gòu)造參數(shù)與其他不同，初始線路如圖8所示。優(yōu)化后的線路如圖9所示。

通過0～π隨機(jī)參數(shù)的輸入，優(yōu)化前后結(jié)果一致，證明了算法的可行性，并且在此圖中優(yōu)化后CNOT門數(shù)減少了40%。

4.3 IBM Q真實(shí)環(huán)境下的測試

現(xiàn)今的量子技術(shù)有限，還不能實(shí)驗多頂點(diǎn)圖，圖10正好包括多圖情況，所以用此圖來實(shí)驗，這里無噪聲下選擇的是ibmq_qasm_simulator模擬器，噪聲環(huán)境下使用目前IBM可存取的最新量子比特系統(tǒng)ibm_oslo來測試，該系統(tǒng)能直觀體現(xiàn)現(xiàn)有的NISQ量子技術(shù)，其系統(tǒng)配置如下： CNOT門平均誤差8.751E-3，線路平均讀數(shù)誤差1.699E-2，測量次數(shù)10 000。參數(shù)均使用Qiskit量子模擬包中優(yōu)化器優(yōu)化后的參數(shù)。

當(dāng)滿足最大切割時，因為有兩個游離點(diǎn)，所以理想結(jié)果為圖01234的結(jié)果，即為10101或01010為最大切割，圖矩陣G=［（0，1），（1，2），（2，3），（3，0），（3，4），（5，1），（6，1）］，通過算法后去除5和6，求出Visited=［（0，0），（1，1），（2，2），（3，3），（4，4）］，opV=［（0，1），（1，2），（2，3），（3，4）］，則線路中（0，1），（1，2），（2，3），（3，4）的第一個CNOT門可以優(yōu)化如圖11、12所示。使用QAOA最大切割兩子圖的參數(shù)均為Qiskit優(yōu)化器優(yōu)化后的參數(shù)，為（2lz=-0.765，2lx =7.11）分別代入線路實(shí)驗。

QAOA在p=1時的噪聲環(huán)境模擬對比：首先無噪聲環(huán)境下10 000次測量的成功次數(shù)為3 616，即36.16%。其結(jié)果如圖13所示。

實(shí)驗得出無噪聲環(huán)境下運(yùn)算成功率為36.16%，優(yōu)化前的成功次數(shù)為1 361，即成功率為13.61%，優(yōu)化后的成功次數(shù)為2 545，即成功率為25.45%，表明了優(yōu)化后的線路在真實(shí)量子環(huán)境下的成功率明顯更高，證明了其穩(wěn)定性更接近無噪聲環(huán)境下的運(yùn)算。

4.4 優(yōu)化及實(shí)驗代碼可獲取

以上只是列舉實(shí)驗的部分例子，文章代碼可運(yùn)行操作自定義n bit下的圖優(yōu)化，并模擬驗證計算，實(shí)驗代碼均放在GitHub上，獲取鏈接為https：//github.com/PWJ1900/ QAOAPaperUse/。

5 結(jié)束語

本文從QAOA最大切割問題的線路優(yōu)化出發(fā)，提出了類Dijkstra算法來尋找圖中可優(yōu)化的邊，并解決四種不同場景下的邊可優(yōu)化問題。使用Qiskit量子模擬包將優(yōu)化算法運(yùn)用在線路并模擬運(yùn)算來驗證優(yōu)化的可行性。通過此優(yōu)化QAOA最大切割問題在深度p=1下CNOT門能減少40%左右，在真實(shí)的量子環(huán)境下，其誤差明顯降低。本文著重從QAOA最大切割問題的線路入手提出QAOA在p=1時的優(yōu)化方法，之后的研究也可以從pgt;1展開。此優(yōu)化方法有助于啟發(fā)QAOA解決其他組合優(yōu)化問題的線路Ansatz設(shè)計，對量子框架模擬與量子分布式計算等也有其研究意義。

參考文獻(xiàn)：

［1］Farhi E，Goldstone J，Gutmann S. A quantum approximate optimization algorithm ［EB/OL］. （2014）. https：//arxiv.org/abs/1411.4028.

［2］Moussa C，Calandra H，Dunjko V. To quantum or not to quantum： towards algorithm selection in near-term quantum optimization ［J］. Quantum Science and Technology，2020，5（4）： 3-20.

［3］Ahsan M，Naqvi S A Z，Anwer H. Quantum circuit engineering for correcting coherent noise ［J］. Physical Review A，2022，105（2）： 022428.

［4］Shaydulin R，Hadfield S，Hogg T，et al. Classical symmetries and the quantum approximate optimization algorithm ［J］. Quantum Information Processing，2021，20（11）： 1-28.

［5］Zhu Linghua，Tang H L，Barron G S，et al. Adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer ［J］. Physical Review Research，2022，4（3）： 033029.

［6］Majumdar R，Madan D，Bhoumik D，et al. Optimizing ansatz design in QAOA for max-cut ［EB/OL］. （2021-06-28）. http：//doi.org/10.48550/arxiv.2106.02812.

［7］Majumdar R，Bhoumik D，Madan D，et al. Depth optimized ansatz circuit in QAOA for max-cut［EB/OL］. （2021-10-09）. http：//doi.org/10.48550/arxiv.2110.04637.

［8］Kunal M. Solving combinatorial optimization problems using QAOA，The Jupyter Book Community ［EB/OL］. （2021）. https：//Qiskit. org/textbook/ch-applications/qaoa. html.

［9］IBM Quantum ［EB/OL］. （2021）. https：//quantum-computing. ibm. com/.

［10］Lu Xiaowei，Jiang Nan，Hu Hao，et al. Quantum adder for superposition states ［J］. International Journal of Theoretical Physics，2018，57（9）： 2575-2584.

［11］Raychev N. Universal quantum operators ［J］. International Journal of Scientific and Engineering Research，2015，6（6）： 1369-1371.

［12］Hadfield S，Wang Zhihui，O’Gorman B，et al. From the quantum approximate optimization algorithm to a quantum alternating operator ansatz ［EB/OL］.（2019-02-28）.http：//doi.org/10.3390/a120-20034.

［13］Shen Pu，Chen Tao，Xue Z Y. Ultrafast holonomic quantum gates ［J］. Physical Review Applied，2021，16（4）： 044004.

［14］Fuchs F G，Kolden H ，Aase N H，et al. Efficient encoding of the weighted max k-cut on a quantum computer using QAOA ［J］. SN Computer Science，2021，2（2）： 1-14.

［15］Shaydulin R，Hadfield S，Hogg T，et al. Classical symmetries and the quantum approximate optimization algorithm ［J］. Quantum Information Processing，2021，20（11）： 2-28.

［16］劉小玲，李輝，郭治國. 基于狄克斯特拉算法的車間動態(tài)生產(chǎn)能力評估與實(shí)現(xiàn)［J］. 微計算機(jī)信息，2006（12）： 96-98. （Liu Xiao-ling，Li Hui，Guo Zhiguo. Evaluation and realization of workshop dynamic production capability based on Dijkstra’s algorithm ［J］. Microcomputer Information，2006（12）： 96-98.）

［17］Yurtalan M A，Shi J，Kononenko M，et al. Implementation of a Walsh-Hadamard gate in a superconducting qutrit ［J］. Physical Review Letters，2020，125（18）： 180504.

收稿日期：2022-06-02；修回日期：2022-08-22 基金項目：國家自然科學(xué)基金資助項目（61070240）；江蘇省高校基金資助項目（10KJB520021）

作者簡介：潘文杰（1998-），男，江蘇南通人，碩士研究生，主要研究方向為量子電路（940731286@qq.com）；李志強(qiáng)（1974-），男，江蘇揚(yáng)州人，教授，碩導(dǎo)，博士，主要研究方向為量子計算、量子可逆電路；楊輝（1998-），男，江蘇淮安人，碩士研究生，主要研究方向為量子電路.