求解整數(shù)線(xiàn)性規(guī)劃問(wèn)題的量子近似優(yōu)化算法

戚 晗，何婉瑩，邱 濤，Abdullah Gani

（1. 沈陽(yáng)航空航天大學(xué) 計(jì)算機(jī)學(xué)院，沈陽(yáng) 110136；2. 馬來(lái)西亞沙巴大學(xué) 計(jì)算機(jī)與信息學(xué)院，亞庇 87000）

近年來(lái)，物聯(lián)網(wǎng)、移動(dòng)邊緣計(jì)算、車(chē)載自組織網(wǎng)絡(luò)（vehicular ad hoc network，VANET）發(fā)展迅速，隨之而來(lái)的一些基站和服務(wù)器選址、資源分配調(diào)度等問(wèn)題受到廣泛關(guān)注。這些問(wèn)題可以理解為在有限的可供選擇的方案中，尋找滿(mǎn)足一定約束的最好方案，因此類(lèi)似此類(lèi)問(wèn)題可以歸結(jié)為整數(shù)線(xiàn)性規(guī)劃問(wèn)題［1］。整數(shù)線(xiàn)性規(guī)劃問(wèn)題屬于線(xiàn)性規(guī)劃中的一種，其中又分為二元整數(shù)線(xiàn)性規(guī)劃、混合整數(shù)線(xiàn)性規(guī)劃等。隨著問(wèn)題規(guī)模的擴(kuò)大，在約束條件的限制下尋找到整數(shù)線(xiàn)性規(guī)劃問(wèn)題最優(yōu)解的時(shí)間復(fù)雜度較高。

隨著“噪聲中尺度量子”時(shí)代［2］的快速發(fā)展，量子優(yōu)化算法逐漸受到關(guān)注，量子近似優(yōu)化算法（quantum approximate optimization algo‐rithm， QAOA）在2014 年由Farhi 等提出［3］，被認(rèn)為是在近年可以實(shí)現(xiàn)量子霸權(quán)的算法之一［4］。Willsch 等［5］、Herrman 等［6］以最大切割問(wèn)題和2-SAT 問(wèn)題為例分析了QAOA 的性能，發(fā)現(xiàn)在D-Wave量子退火計(jì)算機(jī)上的性能優(yōu)于量子計(jì)算機(jī)模擬器。Bengtsson 等［7］使用超導(dǎo)量子處理器實(shí)現(xiàn)QAOA，可以提高找到精確覆蓋問(wèn)題最優(yōu)解的成功概率。QAOA 變分態(tài)的對(duì)稱(chēng)性會(huì)使算法本身有一定的局限性，但是基于伊辛模型的QAOA 優(yōu)于原始QAOA，且優(yōu)于Williamson 算法［8］。目前，QAOA 被用于解決許多組合優(yōu)化問(wèn)題，使用QAOA 找到問(wèn)題全局最優(yōu)解的概率比較依賴(lài)于量子線(xiàn)路的迭代次數(shù)（即步長(zhǎng)P）。然而，當(dāng)QAOA 的步長(zhǎng)P 很低時(shí)，找到近似最優(yōu)解的概率很小。Azad 等［9］在使用QAOA 解決車(chē)輛路徑規(guī)劃問(wèn)題時(shí)，迭代24次找到最優(yōu)解的概率約為30%，當(dāng)?shù)螖?shù)更高時(shí)，概率并沒(méi)有達(dá)到較高的水平。Zhang等［10］在使用QAOA 解決最小頂點(diǎn)覆蓋問(wèn)題時(shí)，迭代2 次時(shí)，概率低于20%；迭代10 次時(shí)，概率可以達(dá)到約80%。Vikstl 等［11］在使用QAOA 解決精確覆蓋問(wèn)題時(shí)，在迭代2 次時(shí)的單次測(cè)量下，找到最優(yōu)解的概率為8.97%，需要重復(fù)多次測(cè)量才能提高概率。此外，QAOA 還被應(yīng)用于哈密頓回路問(wèn)題［12］和最大權(quán)獨(dú)立集問(wèn)題［13］。盡管成功概率因不同問(wèn)題而異，但QAOA 無(wú)疑是解決組合優(yōu)化問(wèn)題的一種較好的方法。2020 年，Choi等［13］針對(duì)無(wú)線(xiàn)自組織網(wǎng)絡(luò)中簇頭選擇的問(wèn)題，采用量子經(jīng)典混合方法求解簇頭選擇策略。為了讓所選擇的簇頭具有較高的能效，將此問(wèn)題定義為最大加權(quán)獨(dú)立集問(wèn)題，運(yùn)用QAOA 求解最佳策略。2022 年，F(xiàn)an 等［14］使用QAOA 解決圖計(jì)算中最短路徑問(wèn)題，結(jié)果顯示，QAOA 在參數(shù)選擇和步長(zhǎng)選擇上優(yōu)于經(jīng)典算法和基于Grover 的最短路徑算法，且需要的量子比特?cái)?shù)更少。2023 年，Soloviev 等［15］為了解決許多傳統(tǒng)方法無(wú)法解決的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)問(wèn)題，采用基于3n（n-1）/2 個(gè)量子比特的QAOA 進(jìn)行求解（其中n 為貝葉斯網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)量）。結(jié)果顯示，在任何數(shù)據(jù)集上的性能都要優(yōu)于經(jīng)典和其他量子方法。在縮短整數(shù)線(xiàn)性規(guī)劃問(wèn)題的求解時(shí)間方面，QAOA 是一種有意義且可行的解決方法。

本文針對(duì)整數(shù)線(xiàn)性規(guī)劃問(wèn)題，提出一種基于改進(jìn)目標(biāo)哈密頓量的QAOA 的量子線(xiàn)路方法，提高在低迭代時(shí)找到最優(yōu)解的概率并縮短程序執(zhí)行時(shí)間。通過(guò)構(gòu)造與整數(shù)線(xiàn)性規(guī)劃問(wèn)題對(duì)應(yīng)的數(shù)學(xué)模型，將經(jīng)典伊辛模型量子化，得到本文所要解決問(wèn)題的目標(biāo)哈密頓量。推導(dǎo)哈密頓量對(duì)應(yīng)的量子門(mén)線(xiàn)路，并減少線(xiàn)路中使用的量子門(mén)數(shù)量。本文使用本源量子的py‐Qpanda框架進(jìn)行模擬，驗(yàn)證了改進(jìn)目標(biāo)哈密頓量對(duì)找到基態(tài)概率和執(zhí)行時(shí)間的影響。

1 資源分配問(wèn)題的整數(shù)線(xiàn)性規(guī)劃公式

為了便于理解這一類(lèi)場(chǎng)景下的整數(shù)線(xiàn)性規(guī)劃問(wèn)題，本文以車(chē)載自組織網(wǎng)絡(luò)為例進(jìn)行說(shuō)明。通過(guò)車(chē)載自組織網(wǎng)絡(luò)實(shí)現(xiàn)車(chē)輛之間通信可以有效地避免出現(xiàn)交通擁堵和事故，因?yàn)樗緳C(jī)可以獲得超出可視范圍內(nèi)的實(shí)時(shí)路況信息。但是遠(yuǎn)距離車(chē)輛無(wú)法直接通信，需要合作通信來(lái)獲取信息，合作通信需要使用中繼車(chē)輛節(jié)點(diǎn)的資源，但每輛車(chē)的剩余資源、移動(dòng)速度和位置都是不固定的。在這種情況下，需要考慮中繼節(jié)點(diǎn)如何選擇。如果中繼節(jié)點(diǎn)集中在一輛車(chē)上，那么會(huì)造成這輛車(chē)過(guò)載，從而導(dǎo)致通信失敗，所以中繼節(jié)點(diǎn)的負(fù)載平衡十分重要，需要合理分配中繼節(jié)點(diǎn)的資源。針對(duì)資源分配下的整數(shù)線(xiàn)性規(guī)劃問(wèn)題，本文以源節(jié)點(diǎn)代表需要請(qǐng)求計(jì)算資源的設(shè)備，以目標(biāo)節(jié)點(diǎn)代表提供計(jì)算資源的設(shè)備。

假設(shè)目標(biāo)節(jié)點(diǎn)具有相同的資源，源節(jié)點(diǎn)的資源需求量不同，那么影響延遲的主要因素即為通信距離。但是當(dāng)目標(biāo)節(jié)點(diǎn)的資源不足以處理所有請(qǐng)求時(shí)，會(huì)產(chǎn)生排隊(duì)延遲?，F(xiàn)在用G表示整個(gè)網(wǎng)絡(luò)，V 表示所有源節(jié)點(diǎn)的集合，R 表示所有目標(biāo)節(jié)點(diǎn)的集合，d 表示源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間的通信距離。資源分配的目的是實(shí)現(xiàn)負(fù)載均衡的同時(shí)盡量減少通信延遲。每個(gè)源節(jié)點(diǎn)的資源需求表示為vl，xvr為二元決策變量。如果源節(jié)點(diǎn)與目標(biāo)可以相連，則xvr為1，否則為0。此問(wèn)題可以表述為

可選取的目標(biāo)節(jié)點(diǎn)不確定是否每個(gè)都可以與全部源節(jié)點(diǎn)連接，但是需要確?？傆幸粋€(gè)目標(biāo)節(jié)點(diǎn)可以為其提供資源。通信條件相同的情況下，訪(fǎng)問(wèn)距離越短，訪(fǎng)問(wèn)延遲越小，且距離越短，可以連接的概率也越大，所以將源節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間的距離表示為dvr， xvr同樣為二元決策變量。如果源節(jié)點(diǎn)與目標(biāo)連接，xvr為1，否則為0，此問(wèn)題可以表述為

約束條件可以表述為

式中：n 為源節(jié)點(diǎn)的數(shù)目。式（1）和（2）為本文中的目標(biāo)，式（3）為約束條件，即一個(gè)源節(jié)點(diǎn)只能分配給一個(gè)目標(biāo)，不能分配給多個(gè)目標(biāo)，規(guī)劃范圍內(nèi)的所有源節(jié)點(diǎn)都要與相對(duì)應(yīng)的目標(biāo)連接，即所有源節(jié)點(diǎn)的請(qǐng)求都會(huì)受到相對(duì)應(yīng)的目標(biāo)的處理。與源節(jié)點(diǎn)相連的目標(biāo)應(yīng)該處理其所有的請(qǐng)求服務(wù)；一個(gè)目標(biāo)節(jié)點(diǎn)可管理多個(gè)源節(jié)點(diǎn)；不考慮源節(jié)點(diǎn)與源節(jié)點(diǎn)之間、目標(biāo)與目標(biāo)之間的鏈路。

2 基于伊辛模型的量子近似優(yōu)化算法

對(duì)于同一個(gè)問(wèn)題，當(dāng)設(shè)置的目標(biāo)哈密頓量不同時(shí)，結(jié)果是不同的。在解決整數(shù)線(xiàn)性規(guī)劃問(wèn)題時(shí)，設(shè)置了兩個(gè)不同的目標(biāo)哈密頓量。一種是僅為問(wèn)題函數(shù)（用Hp表示）求解目標(biāo)哈密頓量；另一種是將問(wèn)題函數(shù)和變形約束求和，并忽略公式中的常數(shù)，以獲得改進(jìn)的目標(biāo)哈密頓量（用Hc表示）。以上兩種方法用于設(shè)置不同的目標(biāo)哈密頓量，為比較實(shí)驗(yàn)做準(zhǔn)備。

QAOA 的核心是通過(guò)從初始哈密頓量的基態(tài)，經(jīng)過(guò)P 步迭代演化至目標(biāo)哈密頓量的基態(tài)，在這個(gè)過(guò)程中需要使用經(jīng)典計(jì)算來(lái)完成參數(shù)的更新。圖1 為QAOA 的算法結(jié)構(gòu)圖，它的線(xiàn)路是以初始量子態(tài)為生成元的酉變換和以目標(biāo)量子態(tài)為生成元的酉變換乘積的累積。Hb為初始哈密頓量，以Hb為生成元的酉變換等于e-iHbβi，Hp為目標(biāo)哈密頓量，以Hp為生成元的酉變換為e-iHpγi。其中βi和γi所代表的是不同的變分參數(shù)。

圖1 QAOA的算法結(jié)構(gòu)圖

對(duì)于目標(biāo)哈密頓量的設(shè)定，采用伊辛模型來(lái)實(shí)現(xiàn)，本文所描述問(wèn)題的目標(biāo)哈密頓量可以表示為HA+HB［16］，其中

使用二元決策變量xr∈{0，1}代替自旋變量sr∈{-1，1}，即

2.1 設(shè)置目標(biāo)哈密頓量HP

在資源分配整數(shù)線(xiàn)性規(guī)劃問(wèn)題中，主要考慮兩個(gè)方面，即通信延遲和工作負(fù)載。本文將通信延遲轉(zhuǎn)化為通信距離，以HA為目標(biāo)哈密頓量；將工作負(fù)載轉(zhuǎn)化為源節(jié)點(diǎn)的需求量，以HB為目標(biāo)哈密頓量。將公式展開(kāi)，得到問(wèn)題中

讓A、B、C、D、E為

式中：C 和E 是常數(shù)，將自旋變量變?yōu)樽孕堇仃噑i→σzi，即得到最終目標(biāo)哈密頓量

由于絕熱量子計(jì)算和量子門(mén)電路模型的計(jì)算能力相同［17］，本文將使用門(mén)電路構(gòu)造QAOA 的線(xiàn)路，經(jīng)過(guò)推導(dǎo)，最終得到基于伊辛模型的目標(biāo)哈密頓量是19 個(gè)CNOT 門(mén)、CZ 門(mén)和RZ門(mén)的組合，如式（9）所示

2.2 改進(jìn)目標(biāo)哈密頓量Hc

根據(jù)資源分配問(wèn)題的定義，本文將目標(biāo)哈密頓量改進(jìn)為原始目標(biāo)函數(shù)與約束條件函數(shù)之和，可以表述為

其中A'、B'、C'、D'、E'為

式中：C'和E'為常數(shù)，它只與哈密頓量的相位有關(guān)，對(duì)本征態(tài)沒(méi)有影響［10］，所以可以進(jìn)一步將其簡(jiǎn)化為

將自旋變量變?yōu)樽孕堇仃噑i→σzi，即得到最終目標(biāo)哈密頓量，如式（13）所示

經(jīng)過(guò)推導(dǎo)，目標(biāo)函數(shù)Hc可以表示為5 個(gè)CNOT門(mén)、RZ門(mén)組合，如式（14）所示

2.3 初始哈密頓量

設(shè)定初始哈密頓量為泡利X算符在每個(gè)量子位上的和，如式（15）所示

其基態(tài)是泡利算符對(duì)應(yīng)特征能量的張量積，如式（16）所示

經(jīng)過(guò)推導(dǎo)初始哈密頓量是H 門(mén)操作，原始QAOA和改進(jìn)QAOA的初始哈密頓量均為Hb。

3 仿真實(shí)驗(yàn)

本文使用基于python 的本源量子的pyQ‐panda 框架來(lái)執(zhí)行QAOA，并解決整數(shù)線(xiàn)性規(guī)劃問(wèn)題下的資源分配優(yōu)化問(wèn)題實(shí)例（4，2）。其中，4 表示源節(jié)點(diǎn)的數(shù)量，2 表示目標(biāo)節(jié)點(diǎn)的數(shù)量。實(shí)驗(yàn)所需的實(shí)際量子位N根據(jù)源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間的通信鏈路確定。當(dāng)源節(jié)點(diǎn)請(qǐng)求目標(biāo)節(jié)點(diǎn)的資源時(shí)，中間距離對(duì)通信延遲和連接的可能性都有影響。如果距離超過(guò)其覆蓋區(qū)域，則無(wú)法利用目標(biāo)節(jié)點(diǎn)的資源。

例如（4，2），使用式（17）來(lái)描述問(wèn)題（它是歸一化數(shù)據(jù)），相應(yīng)連接如圖2 所示，覆蓋區(qū)域分別表示E和F的可連接范圍。

圖2 問(wèn)題示例（4，2）的連接圖

如圖2 所示，A 和F 之間的距離太大，超出了F 的通信覆蓋范圍，從而阻止了鏈路連接。實(shí)際距離應(yīng)為∞，因此式（17）中使用1 表示無(wú)連接。為了編碼這個(gè)問(wèn)題，將每個(gè)量子位分配給圖2中的每個(gè)鏈路，即如果使用了鏈路，則意味著對(duì)應(yīng)的二進(jìn)制決策變量為1，否則為0。為了使用QAOA，必須采取以下步驟：

（1）初始化線(xiàn)路，并加入初始哈密頓量基態(tài)所對(duì)應(yīng)的量子門(mén)；

（2）通過(guò)初始化待優(yōu)化的參數(shù)β和γ來(lái)確定量子門(mén)的初始旋轉(zhuǎn)角度，根據(jù)參數(shù)生成更新的量子線(xiàn)路，然后測(cè)量期望值；

（3）將當(dāng)前的參數(shù)通過(guò)經(jīng)典計(jì)算機(jī)再次優(yōu)化會(huì)得到一組新的參數(shù)，通過(guò)新的參數(shù)計(jì)算新的損失值，直到滿(mǎn)足結(jié)束條件，即哈密頓量從初始基態(tài)演化到目標(biāo)基態(tài)。

3.1 QAOA中參數(shù)更新方法對(duì)比

如何進(jìn)行經(jīng)典計(jì)算來(lái)更新參數(shù)至關(guān)重要，雖然也有使用張量網(wǎng)絡(luò)技術(shù)［18］來(lái)尋找參數(shù)的策略，但是最常用的方法是使用優(yōu)化器計(jì)算。本文對(duì)比了AdaGrad 優(yōu)化器［19］、Adam［20］、Mo‐mentum［21］、RMSProp［22］和Vanilla Gradient De‐scent［23］5種優(yōu)化器分別在原始和改進(jìn)QAOA 中的性能。通過(guò)對(duì)比這5 種優(yōu)化器，可以看出哪一種更新參數(shù)的方法最適用于本文所提出的問(wèn)題。本文使用損失函數(shù)的收斂值來(lái)評(píng)價(jià)不同優(yōu)化器對(duì)算法的影響。

首先針對(duì)原始目標(biāo)哈密頓量Hp進(jìn)行實(shí)驗(yàn)，不同優(yōu)化器的性能如圖3 所示，在步長(zhǎng)P=2 且優(yōu)化器迭代次數(shù)為200時(shí)，5種優(yōu)化器所形成的損失函數(shù)值均不斷減小，其中Momentum 優(yōu)化器的整體損失函數(shù)值要低于其他優(yōu)化器，但其前期波動(dòng)較大，其余4 個(gè)優(yōu)化器的損失函數(shù)收斂值相近?？梢钥闯龀薃daGrad 優(yōu)化器之外，其余的損失函數(shù)收斂很快，在開(kāi)始迭代到50 次左右就可以穩(wěn)定收斂在固定數(shù)值，且保持在-0.900 3，但是前期同樣出現(xiàn)較小波動(dòng)。AdaGrad 優(yōu)化器雖然收斂不如其他優(yōu)化器快，但是并沒(méi)有任何波動(dòng)。綜合來(lái)說(shuō)Momentum優(yōu)化器雖然損失函數(shù)值更低，但是由于其波動(dòng)較為嚴(yán)重，所以不適用于目標(biāo)哈密頓量為Hp時(shí)的QAOA。

圖3 不同優(yōu)化器性能

改進(jìn)目標(biāo)哈密頓量Hc在不同優(yōu)化方法下?lián)p失函數(shù)的變化如圖4所示。在相同步長(zhǎng)和迭代次數(shù)時(shí)，Hc的損失函數(shù)值均低于Hp，可以看到Adam、Momentum、RMSProp 和Vanilla Gra‐dient Descent 4 種優(yōu)化器在迭代次數(shù)為50 時(shí)均可收斂，AdaGrad 優(yōu)化器在迭代200 次時(shí)還沒(méi)有明顯收斂趨勢(shì)，但當(dāng)?shù)螖?shù)為500 時(shí)可以收斂。Momentum 優(yōu)化器在收斂前一直存在明顯波動(dòng)，這是因?yàn)橐霘v史梯度信息動(dòng)量。Adam 優(yōu)化器是基于Momentum 優(yōu)化器和RM‐SProp 優(yōu)化器提出的，在迭代次數(shù)為20～30 也有小范圍波動(dòng)，之后達(dá)到收斂狀態(tài)。RMSProp優(yōu)化器和Vanilla Gradient Descent 優(yōu)化器沒(méi)有波動(dòng)，并且可以以較快的速度達(dá)到收斂值，其中Vanilla Gradient Descent 優(yōu)化器的初始值要低于RMSProp 優(yōu)化器。這與哈密頓量Hp存在一定差別，這是因?yàn)镠c與Hp本身存在差異，對(duì)于不同的目標(biāo)哈密頓量，最合適的優(yōu)化方法是不確定的。

圖4 Hc在不同優(yōu)化方法下?lián)p失函數(shù)的變化

3.2 QAOA的不同目標(biāo)哈密頓量性能對(duì)比

在實(shí)例（4，2）中，通信連接如圖2 所示，邊緣映射序列為｛A?E，B?E，A?F，C?E，C?F，D?E，D?F｝。一般來(lái)說(shuō)，基于門(mén)電路的QAOA 使用量子門(mén)形成絕熱演化過(guò)程，使得哈密頓量從初始基態(tài)演化到目標(biāo)基態(tài)。最后測(cè)量并得到哈密頓量的目標(biāo)基態(tài)，在這個(gè)問(wèn)題中，對(duì)應(yīng)的基態(tài)是|11100101〉，映射序列是｛A?E，B?E，C?F，D?F｝。當(dāng)P=2時(shí)，找到目標(biāo)基態(tài)的概率可以達(dá)到54.156 3%，對(duì)于低迭代級(jí)別來(lái)說(shuō)這是非常高的成功率。然而，隨著哈密頓量的改進(jìn)，概率進(jìn)一步增加到82.9%。概率分布如圖5 所示。

圖5 不同哈密頓量求得最優(yōu)解的概率

從圖5 可以看出，目標(biāo)哈密頓量為Hp時(shí)，所有解中概率較高的為“1011010”和“1100101”，雖然正確解“1100101”的概率高于“1011010”，但是極容易陷入局部最優(yōu)解。而當(dāng)目標(biāo)哈密頓量為Hc時(shí)，正確解“1100101”的概率遠(yuǎn)高于其他解，與目標(biāo)哈密頓量為Hp時(shí)相比，更加容易跳出局部最優(yōu)，以一個(gè)較高的概率得到問(wèn)題的正確解。

QAOA 的執(zhí)行時(shí)間與量子門(mén)的數(shù)量密切相關(guān)。與原始目標(biāo)哈密頓量Hp相比，改進(jìn)目標(biāo)哈密頓量Hc減少了量子門(mén)的數(shù)量，這影響了找到最優(yōu)解的時(shí)間。如圖6 所示，在同一設(shè)備上執(zhí)行QAOA，隨著步長(zhǎng)P 的增加，時(shí)間顯著增加，尤其是對(duì)于Hp?？梢钥闯?，盡管Hc的時(shí)間也隨著P 的增加而增加，但增加的幅度沒(méi)有Hp的大。在P=10 時(shí)，Hc的執(zhí)行時(shí)間為Hp的19.16%，P=2 時(shí)Hc的執(zhí)行時(shí)間為Hp的24.62%，Hc的平均執(zhí)行時(shí)間為Hp的20.8%。這意味著當(dāng)步長(zhǎng)P 較大時(shí)，改進(jìn)目標(biāo)哈密頓量Hc的優(yōu)勢(shì)更明顯。

圖6 不同哈密頓量的執(zhí)行時(shí)間

3.3 時(shí)間復(fù)雜度分析

QAOA 是經(jīng)典算法和量子算法的結(jié)合。經(jīng)典部分通過(guò)經(jīng)典優(yōu)化器優(yōu)化參數(shù)，其時(shí)間復(fù)雜度為O（poly（q）），其中q 是經(jīng)典優(yōu)化器迭代次數(shù)。本文中經(jīng)典部分主要對(duì)比AdaGrad、Adam、Momentum、RMSProp 和Vanilla Gradi‐ent Descent 5 種優(yōu)化器，其中Vanilla Gradient Descent每次更新需要計(jì)算整個(gè)數(shù)據(jù)集的梯度，且需要選擇合適的學(xué)習(xí)率，學(xué)習(xí)率太小會(huì)導(dǎo)致收斂緩慢，太大則會(huì)導(dǎo)致收斂效果波動(dòng)。Mo‐mentum 動(dòng)量法是在隨機(jī)梯度下降法（Stochas‐tic Gradient Descent， SGD）基礎(chǔ)上提出的，SGD 具有較快的下降速度，但因?yàn)榉讲铑l繁更新，容易出現(xiàn)劇烈波動(dòng)的情況，但也正是因?yàn)镾GD 的波動(dòng)性使其可能收斂到更好的局部最優(yōu)。Momentum 動(dòng)量法則可以抑制SGD 的搖擺情況，在減輕波動(dòng)情況的同時(shí)，更容易收斂到局部最優(yōu)。在本文實(shí)驗(yàn)中Momentum優(yōu)化器前期波動(dòng)，最終收斂值更低。AdaGrad 在訓(xùn)練過(guò)程中累計(jì)平方梯度越來(lái)越大，導(dǎo)致學(xué)習(xí)率過(guò)早減少，迭代時(shí)收斂緩慢。在本文實(shí)驗(yàn)中AdaGrad 優(yōu)化器在迭代200 次時(shí)沒(méi)有達(dá)到明顯收斂效果，速度緩慢。RMSProp 解決AdaGrad學(xué)習(xí)率急劇下降的問(wèn)題，加速效果更好，收斂速度快。在本文實(shí)驗(yàn)中，RMSProp 優(yōu)化器收斂速度最快。Adam 是Momentum 動(dòng)量法和RM‐SProp 的結(jié)合體，下降速度快，參數(shù)更新穩(wěn)定，但是可能存在小波動(dòng)。在本文實(shí)驗(yàn)中Adam 優(yōu)化器在迭代過(guò)程中出現(xiàn)小范圍波動(dòng)，下降速度最快。

量子部分需要完成從初始狀態(tài)到目標(biāo)狀態(tài)的演化，這部分的復(fù)雜度相當(dāng)于量子態(tài)演化的時(shí)間，即O（poly（P）），其中P 是迭代次數(shù)（即步長(zhǎng)）。QAOA 是從絕熱算法演變而來(lái)的，該系統(tǒng)可以通過(guò)使用絕熱算法來(lái)保證開(kāi)始狀態(tài)是基態(tài)，并且最終狀態(tài)也是基態(tài)，但是成本相對(duì)較高（例如時(shí)間成本）。相比之下，QAOA 運(yùn)行時(shí)間相對(duì)較短，但獲得基態(tài)的概率也受到限制。因此，如果增加迭代次數(shù)P，總體成功概率也會(huì)得到一定的提高。

根據(jù)上述分析，QAOA 的時(shí)間復(fù)雜度如式（18）所示

從式（18）可以看出，QAOA 在時(shí)間復(fù)雜度上的性能要優(yōu)于其他經(jīng)典算法，因?yàn)镼AOA 的復(fù)雜性與所需要求解問(wèn)題的大小無(wú)關(guān)，而經(jīng)典算法的復(fù)雜性隨著問(wèn)題規(guī)模的增加呈指數(shù)增長(zhǎng)。

4 結(jié)論

本文利用QAOA 解決了與資源分配相關(guān)的整數(shù)線(xiàn)性規(guī)劃問(wèn)題，將節(jié)點(diǎn)間的鏈路映射到量子位來(lái)編碼哈密頓量Hc、Hp和Hb。通過(guò)從原始的目標(biāo)哈密頓量Hp轉(zhuǎn)換到改進(jìn)的目標(biāo)哈密頓量Hc，量子電路的運(yùn)行時(shí)間和所需量子門(mén)的數(shù)量都顯著減少。此外，本文分析并比較了原始目標(biāo)哈密頓量Hp和改進(jìn)的目標(biāo)哈密頓量Hc對(duì)找到近似最優(yōu)解的影響。實(shí)驗(yàn)結(jié)果證明了QAOA 在解決這些問(wèn)題方面的有效性，即使有少量的迭代，該算法也有很高的成功率。例如，當(dāng)目標(biāo)哈密頓量是Hp時(shí)，成功率是54.156 3%，而當(dāng)它是Hc時(shí)，概率增加到82.9%。這種低迭代水平轉(zhuǎn)化為實(shí)現(xiàn)算法所需的低電路深度，證實(shí)了其在近期量子機(jī)器上的可行性。由于QAOA 的時(shí)間復(fù)雜性不受問(wèn)題大小的影響，因此它更適合大規(guī)模和多節(jié)點(diǎn)場(chǎng)景。此外，哈密頓量Hc的電路需要更少的量子門(mén)，這可以縮短執(zhí)行時(shí)間，平均執(zhí)行時(shí)間為Hp電路的20.8%。在未來(lái)，將會(huì)對(duì)QAOA 的內(nèi)部結(jié)構(gòu)進(jìn)行改進(jìn)，發(fā)現(xiàn)更有效的參數(shù)更新技術(shù)，并將不同的模型應(yīng)用于不同的組合優(yōu)化問(wèn)題。