段孟環(huán) 李志強(qiáng) 郭玲玲

摘 要：最大獨(dú)立集問(wèn)題是著名的NP問(wèn)題，并且在許多場(chǎng)景中都有應(yīng)用。傳統(tǒng)的精確算法解決最大獨(dú)立集問(wèn)題需要指數(shù)級(jí)的時(shí)間復(fù)雜度。為更高效地解決最大獨(dú)立集問(wèn)題，提出了一種基于量子近似優(yōu)化算法的量子線(xiàn)路解決方案。該方案由最大獨(dú)立集的數(shù)學(xué)模型，推導(dǎo)出最大獨(dú)立集問(wèn)題的哈密頓量表達(dá)式；設(shè)計(jì)了基于量子近似優(yōu)化算法的量子線(xiàn)路，采用COBYLA經(jīng)典優(yōu)化算法對(duì)參數(shù)量子門(mén)中的參數(shù)進(jìn)行優(yōu)化，并使用IBM提供的量子開(kāi)發(fā)框架Qiskit進(jìn)行仿真實(shí)驗(yàn)。仿真結(jié)果表明，使用量子近似優(yōu)化算法可以在多項(xiàng)式時(shí)間以高概率內(nèi)獲得最大獨(dú)立集問(wèn)題的解，實(shí)現(xiàn)了指數(shù)加速。量子近似優(yōu)化算法對(duì)解決最大獨(dú)立集問(wèn)題有一定的可行性和有效性。

關(guān)鍵詞：最大獨(dú)立集； 量子近似優(yōu)化算法； 量子線(xiàn)路； Qiskit

中圖分類(lèi)號(hào)：O4?? 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695（2023）09-013-0000-00

doi：10.19734/j.issn.1001-3695.2023.02.0031

Application of quantum approximate optimization algorithm in

max independent set problem

Duan Menghuan， Li Zhiqiang， Guo Lingling

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

Abstract：The max independent set problem is a well-known NP problem and has applications in many scenarios. Traditional exact algorithms need exponential time complexity to solve the max independent set problem. In order to solve the max independent set problem more efficiently， this paper proposed a quantum circuit solution based on the quantum approximate optimization algorithm. In this scheme， derived the Hamiltonian expression of the max independent set problem from the mathematical model of the max independent set， designed the quantum circuit based on the quantum approximation optimization algorithm. It used the COBYLA classical optimization algorithm to optimize the parameters in the parameter quantum gate， and used the quantum development framework Qiskit provided by IBM to conduct simulation experiments. Simulation results show that the solution of the max independent set problem can be obtained in polynomial time with high probability using the quantum approximate optimization algorithm， achieving an exponential speedup. Quantum approximate optimization algorithm is feasible and effective for solving the max independent set problem.

Key words：max independent set problem; quantum approximate optimization algorithm; quantum circuit; Qiskit

0 引言

1972年，Karp提出了21個(gè)NP完全問(wèn)題［1］，最大獨(dú)立集問(wèn)題（max independent set problem，MISP）就是其中之一。最大獨(dú)立集問(wèn)題是一個(gè)經(jīng)典的組合優(yōu)化問(wèn)題［1，2］，數(shù)十年來(lái)受到了大量學(xué)者的關(guān)注，并且將其應(yīng)用于各個(gè)場(chǎng)景中［3，4］。文獻(xiàn)[5，6]提出了一系列基于分支定界策略（branch and bound strategy）的精確算法來(lái)解決最大獨(dú)立集問(wèn)題，這些精確算法解決最大獨(dú)立集問(wèn)題需要指數(shù)級(jí)的時(shí)間。

隨著量子計(jì)算［7～9］的發(fā)展，量子計(jì)算有望成為一種具有顛覆性影響的計(jì)算方式。量子計(jì)算基于量子態(tài)的連貫性和糾纏性，可以輕松完成并行計(jì)算。某些在經(jīng)典處理器上難以解決的問(wèn)題，在量子處理器上可以實(shí)現(xiàn)指數(shù)加速或二次加速［10，11］。2014年，F(xiàn)arhi等人［12］提出了量子近似優(yōu)化算法（quantum approximate optimization algorithm，QAOA）并將其應(yīng)用于解決最大割問(wèn)題。量子近似優(yōu)化算法是一種啟發(fā)式的量子經(jīng)典混合算法，主要用于解決組合優(yōu)化問(wèn)題。相比于經(jīng)典算法，量子近似優(yōu)化算法對(duì)解決組合優(yōu)化問(wèn)題有指數(shù)加速。根據(jù)相關(guān)文獻(xiàn)［13，14］，量子近似優(yōu)化算法是在近期的量子計(jì)算機(jī)上實(shí)現(xiàn)的最有前途的顯示量子優(yōu)勢(shì)的算法之一。近年來(lái)，量子近似優(yōu)化算法被用于精確覆蓋［15］、漢密爾頓路［16］、背包問(wèn)題等問(wèn)題［17］。

在本文中，提出了一種基于量子近似優(yōu)化算法的量子線(xiàn)路解決方案用于解決最大獨(dú)立集問(wèn)題。首先，根據(jù)最大獨(dú)立集問(wèn)題的數(shù)學(xué)模型構(gòu)建相應(yīng)的二次無(wú)約束二元優(yōu)化（quadratic unconstrained binary optimization，QUBO）模型。其次，根據(jù)量子系統(tǒng)理論，由QUBO模型推導(dǎo)出量子Ising模型和問(wèn)題哈密頓量。第三，基于QAOA原理，得到基于初始哈密頓量和問(wèn)題哈密頓量的參數(shù)酉變換。參數(shù)主要與量子門(mén)的旋轉(zhuǎn)角度有關(guān)。交替使用酉變換可以得到最終的量子態(tài)。最后，根據(jù)初始量子態(tài)和參數(shù)酉變換設(shè)計(jì)量子門(mén)，生成可以在量子計(jì)算機(jī)上執(zhí)行的量子線(xiàn)路。在演化過(guò)程中，采用經(jīng)典優(yōu)化算法對(duì)量子線(xiàn)路的參數(shù)進(jìn)行優(yōu)化，通過(guò)調(diào)整問(wèn)題的哈密頓量的期望，從而提高解的概率。該方案可以有效地解決最大獨(dú)立集問(wèn)題。

1 問(wèn)題模型

在無(wú)向圖G=（V，E）中，其中V表示無(wú)向圖G的頂點(diǎn)集，E表示無(wú)向圖G的邊集。

圖G=（V，E）中兩兩互不相鄰的頂點(diǎn)構(gòu)成的集合稱(chēng)為獨(dú)立集。最大獨(dú)立集是具有最大尺寸的獨(dú)立集。

假設(shè)S是無(wú)向圖G=（V，E）的獨(dú)立集。|S|表示獨(dú)立集中頂點(diǎn)的個(gè)數(shù)。最大獨(dú)立集問(wèn)題的目標(biāo)函數(shù)可以由F1表示，其中xi對(duì)應(yīng)于第i個(gè)頂點(diǎn)的取值，當(dāng)vi∈S時(shí)，xi=1；viS時(shí)，xi=0。

3 仿真與結(jié)果分析

使用QAOA解決最大獨(dú)立集問(wèn)題時(shí)，首先需要將圖的頂點(diǎn)映射至量子比特。然后根據(jù)圖中的邊和第2章中所示方案生成QAOA量子線(xiàn)路，對(duì)量子比特進(jìn)行測(cè)量并計(jì)算哈密頓量的期望值，在經(jīng)典部分使用經(jīng)典參數(shù)優(yōu)化器對(duì)量子線(xiàn)路中的參數(shù)進(jìn)行優(yōu)化。重復(fù)上述步驟，直到收斂。最終得到的量子比特的測(cè)量值組成的字符串就是最大獨(dú)立集所對(duì)應(yīng)的解。本文對(duì)圖3中的示例進(jìn)行實(shí)驗(yàn)仿真。因?yàn)樵撌纠?個(gè)頂點(diǎn)，在初始化時(shí)需要準(zhǔn)備6個(gè)量子比特，每個(gè)量子比特對(duì)應(yīng)于一個(gè)頂點(diǎn)。然后根據(jù)第三部分的內(nèi)容構(gòu)造量子線(xiàn)路。最后對(duì)最終狀態(tài)進(jìn)行測(cè)量可以得到由“0”和“1”組成的6位字符串，其中“0”表示該頂點(diǎn)未被選中，“1”表示該頂點(diǎn)被選中。算法1給出了該方案的主要偽代碼。

算法1 基于QAOA的最大獨(dú)立集算法

輸入：無(wú)向圖G=（V，E），演化步數(shù)p。

輸出： 最優(yōu)解S。

nqubits←|V|

qc←QuantumCircuit（nqubits） //初始化量子線(xiàn)路

γ，β←1.0 ?//初始化2p個(gè)參數(shù)

for i←0： nqubits do //制備初始疊加態(tài)

qc.h（i）

end for

while stop criterion is no satisfied do

for k←1：p do

qc.append（U（HC，γk）） //式（17）

qc.append（U（HM，βk）） //式（20）

end for

計(jì)算期望值Fp（γ，β） //式（11）

使用經(jīng)典優(yōu)化器優(yōu)化參數(shù)γ和β

end while

測(cè)量量子態(tài)

S←具有最高概率的量子態(tài)對(duì)應(yīng)的比特串

輸出S

3.1 仿真結(jié)果與分析

本文主要使用IBM開(kāi)發(fā)的量子軟件開(kāi)發(fā)工具Qiskit［22］在Python 3中模擬和實(shí)現(xiàn)所設(shè)計(jì)的量子線(xiàn)路?？梢灾?，圖3中的示例，其最大獨(dú)立集S={0，1，4，5}。相應(yīng)地，在QAOA下，獲得字符串“110011”的概率應(yīng)該最大。本文選取了演化步數(shù)為1至11進(jìn)行仿真實(shí)驗(yàn)。

在使用QAOA求解圖2的最大獨(dú)立集時(shí)，在不限制迭代次數(shù)的情況下，當(dāng)演化步數(shù)為1～11時(shí)，得到正確解“110011”的概率如圖5所示。

從圖5可以看出，當(dāng)p=1時(shí)，QAOA算法獲得正確解的概率為21.4%，當(dāng)p=2時(shí)，獲得正確解的概率顯著增加，并且隨著演化步數(shù)的增加，獲得的問(wèn)題解的正確率總體呈現(xiàn)上升趨勢(shì)。但并不是所有的演化結(jié)果都比之前的演化結(jié)果好，它是會(huì)有波動(dòng)的。在達(dá)到一定數(shù)量的進(jìn)化步驟后，其正確率可能會(huì)下降，但仍保持在較高水平，這與文獻(xiàn)［12］的結(jié)論一致。從圖4可以看出，當(dāng)演化步數(shù)p為1到11時(shí)，在p=7時(shí)的結(jié)果最好，正確率達(dá)到94.5%。

圖6顯示了當(dāng)p=7時(shí)，QAOA算法所得到的結(jié)果及其對(duì)應(yīng)的概率。圖7給出了在p=7的結(jié)果空間下，p分別為1，3，5，7，9時(shí)獲得各個(gè)結(jié)果的概率。

從圖7中可以看出，當(dāng)演化步數(shù)p為3， 5， 7， 9時(shí)，正確解的概率非常顯著。因此，結(jié)果表明，本文提出的基于QAOA的解決方案可以用于解決最大獨(dú)立集問(wèn)題。

3.2 迭代與優(yōu)化結(jié)果與分析

在實(shí)驗(yàn)過(guò)程中，為了使QAOA得到較好的結(jié)果，需要在經(jīng)典計(jì)算部分采用優(yōu)化算法來(lái)優(yōu)化參數(shù)（γ，β）以得到較優(yōu)的（γ，β）。常用的優(yōu)化方法有CG算法［23］、BFGS算法［24］、Nelder-Mead算法［25］和COBYLA算法［26］等。各經(jīng)典優(yōu)化算法在p=1時(shí)，獲得正確解的概率如表1所示?？梢钥闯觯褂肅OBYLA經(jīng)典優(yōu)化算法能以更高的概率獲得正確解。因此，本文使用COBYLA經(jīng)典優(yōu)化算法來(lái)優(yōu)化參數(shù)（γ，β）。

圖8顯示了當(dāng)演化步數(shù)為1到11時(shí)，經(jīng)典優(yōu)化算法COBYLA獲得最佳參數(shù)所需的迭代次數(shù)?？梢钥闯?，隨著演化步數(shù)的增加，所需迭代次數(shù)也會(huì)增加。因?yàn)樗枰獌?yōu)化的參數(shù)的數(shù)量會(huì)隨著演化步數(shù)的增加而增加，參數(shù)的優(yōu)化更加復(fù)雜，獲得最優(yōu)參數(shù)的迭代次數(shù)也會(huì)增加。

圖8顯示了當(dāng)演化步數(shù)為1到11時(shí)，經(jīng)典優(yōu)化算法COBYLA獲得最佳參數(shù)所需的迭代次數(shù)。可以看出，隨著演化步數(shù)的增加，所需迭代次數(shù)也會(huì)增加。因?yàn)樗枰獌?yōu)化的參數(shù)的數(shù)量會(huì)隨著演化步數(shù)的增加而增加，參數(shù)的優(yōu)化更加復(fù)雜，獲得最優(yōu)參數(shù)的迭代次數(shù)也會(huì)增加。

圖9顯示了當(dāng)演化步數(shù)為1，3，5，7，9時(shí)，隨著迭代次數(shù)的增加，損失值的變化過(guò)程。從圖9可以看出，在演化步數(shù)一定時(shí)，迭代次數(shù)越多，損失值的絕對(duì)值越大。但在達(dá)到某個(gè)值后，損失值變化很小或根本沒(méi)有變化。這是因?yàn)楫?dāng)目標(biāo)函數(shù)接近局部最優(yōu)解或目標(biāo)函數(shù)已達(dá)到最優(yōu)且優(yōu)化已完成時(shí)，目標(biāo)函數(shù)的收斂速度減慢。當(dāng)演化步數(shù)分別為5和9時(shí)，它們的損失值相差不大，圖5的結(jié)果也表明它們之間的差異僅為1.9%。因此，當(dāng)獲得正確解的概率相差不大時(shí)，本文可以?xún)?yōu)先選擇較少的演化步數(shù)，同時(shí)選擇適當(dāng)?shù)牡螖?shù)，以節(jié)省時(shí)間和空間開(kāi)銷(xiāo)。

3.3 QAOA復(fù)雜度分析

本文采用混合量子—經(jīng)典算法QAOA求解最大獨(dú)立集問(wèn)題。它主要包括兩部分：經(jīng)典處理器部分和量子處理器部分。在經(jīng)典處理器中，使用COBYLA算法來(lái)優(yōu)化參數(shù)。COBYLA算法的時(shí)間復(fù)雜度是O（poly（m）），其中m是迭代次數(shù)，可以自己設(shè)置。poly（m）是m的多項(xiàng)式函數(shù)，這意味著COBYLA算法的計(jì)算復(fù)雜度是多項(xiàng)式級(jí)別的。在量子處理器中，主要完成量子態(tài)從量子初始態(tài)到量子最終態(tài)的演化，并測(cè)量量子最終態(tài)。結(jié)合相關(guān)文獻(xiàn)［27］，量子態(tài)的演化是最耗時(shí)的，幾乎相當(dāng)于整個(gè)量子電路的時(shí)間復(fù)雜度。因此，量子部分的時(shí)間復(fù)雜度是O（poly（p）），為多項(xiàng)式級(jí)別，其中p演化步數(shù)。因此，本文提出的量子線(xiàn)路求解方案的時(shí)間復(fù)雜度為O［poly（m）+poly（p）］。而求解最大獨(dú)立集問(wèn)題的精確算法的時(shí)間復(fù)雜度是指數(shù)級(jí)的。由此，可以得出結(jié)論，基于QAOA的求解算法的時(shí)間復(fù)雜度優(yōu)于傳統(tǒng)的求解算法，尤其是當(dāng)問(wèn)題規(guī)模較大時(shí)。

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

本文針對(duì)最大獨(dú)立集問(wèn)題，提出了一種基于QAOA量子線(xiàn)路的解決方案。根據(jù)最大獨(dú)立集問(wèn)題的性質(zhì)，建立了最大獨(dú)立集的問(wèn)題模型。推導(dǎo)出了最大獨(dú)立集的問(wèn)題哈密頓量，并且根據(jù)其哈密頓量，設(shè)計(jì)了一個(gè)基于QAOA的量子線(xiàn)路，使用經(jīng)典優(yōu)化算法來(lái)優(yōu)化參數(shù)，并在IBM開(kāi)發(fā)的Qiskit框架中進(jìn)行了仿真。仿真結(jié)果表明，本文提出的基于QAOA算法的量子線(xiàn)路求解方案能夠有效地獲得最大獨(dú)立集問(wèn)題的解。與經(jīng)典的精確算法相比，本文方案實(shí)現(xiàn)了指數(shù)加速，大大提高了效率。

本文提出的方案仍需改進(jìn)，主要包括兩個(gè)方面：

a）經(jīng)典優(yōu)化器的優(yōu)化效果不太理想;b）可以進(jìn)一步優(yōu)化所設(shè)計(jì)的量子線(xiàn)路。

為了解決上述兩個(gè)問(wèn)題，今后主要關(guān)注以下工作：a）研究參數(shù)酉變換的參數(shù)特性，選擇或設(shè)計(jì)一個(gè)更好的經(jīng)典優(yōu)化器，以提高優(yōu)化效率和效果;b）設(shè)計(jì)一個(gè)QAOA線(xiàn)路的編譯方案用于優(yōu)化QAOA的線(xiàn)路，減少量子門(mén)的數(shù)量，提高QAOA線(xiàn)路的執(zhí)行效率。

參考文獻(xiàn)：

[1]Karp R M，Miller R E，Thatcher J W.Reducibility among combinatorial problems［J］.The Journal of Symbolic Logic，1975，40：618-619.

［2]Shen Yunzhuang，Sun Yuan，Li Xiaodong，et al.Multi-shot solution prediction for combinatorial optimization［EB/OL］.（2022）［2023-03-31］.https：//arxiv.org/abs/2204.08700.

［3]Li Lianjie，Huang Wenqian，Wang Zheli，et al.Calibration transfer between developed portable Vis/NIR devices for detection of soluble solids contents in apple［J］.Postharvest Biology and Technology，2022，183：111720.

［4]Davoudi M，Moosavi M R，Sadreddini M H.DSS：a hybrid deep model for fake news detection using propagation tree and stance network［J］.Expert Systems with Applications，2022，198：116635.

［5]Dai Jinyu，Wu Zhengtia，Karimi H R，et al.An approximation lagrangian-based algorithm for the maximum clique problem via deterministic annealing neural network［J］.Journal of the Franklin Institute，2022，359（12）：6080-6098.

［6]Forget N，Gadegaard S L，Klamroth K，et al.Branch-and-bound and objective branching with three or more objectives［J］.Computers & Operations Research，2022，148：106012.

［7]Zhong Hansen，Wang Hui，Deng Yuhao，et al.Quantum computational advantage using photons［J］.Science，2020，370（6523）：1460-1463.

［8]Arute F，Arya K，Babbush R，et al.Quantum supremacy using a programmable superconducting processor［J］.Nature，2019，574（7779）：505-510.

［9]李曉巍，付祥，燕飛，等.量子計(jì)算研究現(xiàn)狀與未來(lái)發(fā)展［J］.中國(guó)工程科學(xué)，2022，24（4）：133-144.（Li Xiaowei，F(xiàn)u Xiang，Yan Fei，et al.Current status and future development of quantum computation［J］.Strategic Study of CAE，2022，24（4）：133-144.）

［10]Ahnefeld F，Theurer T，Egloff D，et al.Coherence as a resource for Shors algorithm［J］.Physical Review Letters，2022，129（12）：120501.

［11]吳希，李志強(qiáng)，楊東晗.Grover量子搜索算法的線(xiàn)路優(yōu)化［J］.計(jì)算機(jī)工程與科學(xué)，2023，45（3）：420-425.（Wu Xi，Li Zhiqiang，Yang Donghan.Circuit optimization of Grover quantum search algorithm［J］.Computer Engineering & Science，2023，45（3）：420-425.）

［12]Farhi E，Goldstone J，Gutmann S.A quantum approximate optimization algorithm［EB/OL］.（2014）［2022-05-31］.http：//arxiv.org/abs/1411.4028.

［13]Bechtold M，Barzen J，Leymann F，et al.Investigating the effect of circuit cutting in QAOA for the MaxCut problem on NISQ devices［EB/OL］.（2023）［2023-03-31］.https：//arxiv.org/abs/2302.01792.

［14]Preskill J.Quantum computing in the NISQ era and beyond［J］.Quantum，2018，2：79.

［15]Vikstl P，Grnkvist M，Svensson M，et al.Applying the quantum approximate optimization algorithm to the tail-assignment problem［J］.Physical Review Applied，2020，14（3）：034009.

［16]Gong Changqing，Wang Ting，He Wanying，et al.A quantum approximate optimization algorithm for solving Hamilton path problem［J］.The Journal of Supercomputing，2022，78（13）：15381-15403.

［17]Roch C，Impertro A，Phan T，et al.Cross entropy hyperparameter optimization for constrained problem Hamiltonians applied to QAOA［C］// Proc of International Conference on Rebooting Computing.Piscataway，NJ：IEEE Press，2020：50-57.

［18]Lucas A.Ising formulations of many NP problems［J］.Frontiers in Physics，2014，2：5.

［19]Schmitt M，Rams M M，Dziarmaga J，et al.Quantum phase transition dynamics in the two-dimensional transverse-field Ising model［J］.Science Advances，2022，8（37）：eabl6850.

［20]Choi J，Oh S，Park S，et al.Proper cost hamiltonian design for combinatorial optimization problems：a boolean function approach［C］//Proc of International Conference on Information Networking.Piscataway，NJ：IEEE Press，2021：469-472.

［21]Majumdar R，Bhoumik D，Madan D，et al.Depth optimized ansatz circuit in QAOA for max-cut［EB/OL］.（2021）［2022-06-30］.https：//arxiv.org/abs/2110.04637.

［22]https：//qiskit.org/［EB/OL］.

［23]Wasi H A，Shiker M A K.Proposed CG method to solve unconstrained optimization problems［J］.Journal of Physics：Conference Series，2021，1804（1）：012024.

［24]Liu Qiancheng，Beller S，Lei Wenjie，et al.Pre-conditioned BFGS-based uncertainty quantification in elastic full-waveform inversion［J］.Geophysical Journal International，2022，228（2）：796-815.

［25]Liu Yun，Chong Guoshuang，Heidari A A，et al.Horizontal and vertical crossover of Harris hawk optimizer with Nelder-Mead simplex for parameter estimation of photovoltaic models［J］.Energy Conversion and Management，2020，223：113211.

［26]Pellow-Jarman A，Sinayskiy I，Pillay A，et al.A comparison of various classical optimizers for a variational quantum linear solver［J］.Quantum Information Processing，2021，20（6）：202.

［27]Zhou L，Wang Shengtao，Choi S，et al.Quantum approximate optimization algorithm：Performance，mechanism，and implementation on near-term devices［J］.Physical Review X，2020，10（2）：021067.

收稿日期：2023-02-16；

修回日期：2023-04-03

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目（61070240，62071240）；江蘇省高?；鹳Y助項(xiàng)目（10KJB520021）

作者簡(jiǎn)介：段孟環(huán)（2000-），女，湖南衡陽(yáng)人，碩士研究生，主要研究方向?yàn)榱孔铀惴?、量子電路；李志?qiáng)（1974-），男（通信作者），江蘇揚(yáng)州人，教授，碩導(dǎo)，博士研究生，主要研究方向?yàn)榱孔佑?jì)算、量子可逆電路（yzqqlzq@163.com）；郭玲玲（1999-），女，江蘇鹽城人，碩士研究生，主要研究方向?yàn)榱孔铀惴?、量子電?