何鍵浩 李綠周

(中山大學(xué)計算機學(xué)院 廣州 510006)

優(yōu)化(optimization)是計算機科學(xué)與數(shù)學(xué)領(lǐng)域十分重要的基礎(chǔ)研究之一，同時也是機器學(xué)習(xí)的核心工具[1].相關(guān)理論與方法廣泛應(yīng)用于各類工業(yè)生產(chǎn)[2]、工程設(shè)計與管理[3-5]、交通運輸[6]、經(jīng)濟(jì)決策[7]、市場管理[8]等關(guān)乎國計民生的重要領(lǐng)域.一個具體的優(yōu)化問題由3個基本要素組成：1)目標(biāo)函數(shù)(或損失函數(shù))，即決策者需要優(yōu)化的指標(biāo)，如總消耗、總收益等，數(shù)學(xué)形式表現(xiàn)為由優(yōu)化變量到指標(biāo)的函數(shù)/映射.2)優(yōu)化變量，即決策者可以調(diào)整且會影響到目標(biāo)函數(shù)的變量，如產(chǎn)品工藝、資金分配等.3)約束條件，即在決策過程中必須遵守的限制，如安全標(biāo)準(zhǔn)、資源儲備總量等.優(yōu)化過程就是在約束條件的限制下，尋找能最小化或最大化目標(biāo)函數(shù)的優(yōu)化變量的賦值.優(yōu)化有時候也被稱為數(shù)學(xué)規(guī)劃，下文中優(yōu)化與規(guī)劃意義等價，具體使用的詞匯將根據(jù)該細(xì)分方向的用詞習(xí)慣決定.

根據(jù)優(yōu)化問題的變量是否連續(xù)，優(yōu)化技術(shù)可以分為離散變量優(yōu)化(也稱為組合優(yōu)化)和連續(xù)變量優(yōu)化兩大類.其中，根據(jù)目標(biāo)函數(shù)是否是凸的，連續(xù)變量優(yōu)化又可分為凸優(yōu)化和非凸優(yōu)化.凸優(yōu)化主要研究的是目標(biāo)函數(shù)為凸函數(shù)且優(yōu)化變量可行域為凸集的優(yōu)化問題，由于凸集凸函數(shù)有許多優(yōu)秀的性質(zhì)(例如極小值即最小值)，使得凸優(yōu)化問題有很多高效的解法，在應(yīng)用迭代方法求解時也能獲得良好的收斂速度.因此，凸優(yōu)化技術(shù)方面已有成體系的方法且有廣泛的應(yīng)用.相對而言，非凸優(yōu)化還有很大的發(fā)展空間.另外，許多非凸優(yōu)化問題，目前有效的辦法仍然是轉(zhuǎn)化為凸優(yōu)化問題求解.

與此同時，自從Shor快速整數(shù)分解量子算法[9]、Grover量子搜索算法[10]以及HHL量子解線性方程算法[11]的提出，量子計算就因其與生俱來的并行性而受到廣泛關(guān)注，近年來量子計算理論方面的研究進(jìn)展可參考文獻(xiàn)[12-13].因此，如何利用量子計算技術(shù)來加速優(yōu)化問題的求解、提高優(yōu)化效果成為受關(guān)注的問題，逐漸形成了量子優(yōu)化這一研究方向.量子優(yōu)化算法的研究從時間上大致分為1996—2015年和2015—2021年這2個階段.

1)1996—2015年.此階段的量子優(yōu)化算法主要是針對離散變量優(yōu)化問題而設(shè)計，且有較多的啟發(fā)式算法.此階段的量子算法主要得益于當(dāng)時3類基礎(chǔ)離散量子技術(shù)：

① Grover算法以及量子隨機游走.這2個基礎(chǔ)算法后續(xù)還有不少改進(jìn)與擴(kuò)展，多被用于加速搜索過程.

② 量子退火法.量子退火法無需使用糾纏態(tài)，實現(xiàn)較簡單，因此已經(jīng)有了D-Wave這樣的大型專用量子計算機可供實驗研究.

③ 量子近似優(yōu)化技術(shù).量子近似優(yōu)化算法雖然還沒有關(guān)于理論優(yōu)勢的嚴(yán)格分析，但被認(rèn)為適合近期的含噪中等規(guī)模量子(noisy intermediate-scale quantum,NISQ)計算設(shè)備，因此得到不少關(guān)注.

2)2015—2021年.此階段的量子優(yōu)化算法主要針對連續(xù)變量優(yōu)化問題而設(shè)計.連續(xù)變量優(yōu)化問題的解法以迭代算法為主，迭代開銷以及收斂速度是影響算法效率的主要因素.此階段的量子算法主要得益于4類量子技術(shù)的發(fā)展：

① 解線性方程量子算法的設(shè)計思想.此類方法可用于加速與矩陣操作相關(guān)問題的求解.

② 哈密頓模擬技術(shù).此類方法的發(fā)展為量子態(tài)演化提供了高效的實現(xiàn)方案.

③ 量子隨機存儲器.借助量子隨機存儲技術(shù)對數(shù)據(jù)進(jìn)行預(yù)處理，可以使算法的效率得到提升，不過量子隨機存儲的搭建仍然需要進(jìn)一步的優(yōu)化來保證整體的優(yōu)勢.

④ 量子梯度估計法.計算梯度是許多優(yōu)化問題的核心步驟，量子梯度估計法的提出為此提供了便利.

連續(xù)變量量子優(yōu)化算法是近年的研究趨勢，研究內(nèi)容涵蓋了優(yōu)化領(lǐng)域中梯度下降、牛頓法、內(nèi)點法等常用的傳統(tǒng)迭代方法，也有針對具體優(yōu)化問題的持續(xù)研究，因此本文將重點介紹連續(xù)變量量子優(yōu)化算法，該方向的研究目前主要集中在量子凸優(yōu)化方面.

1 基本量子算法簡介

本節(jié)介紹在量子優(yōu)化算法中使用頻率較高的基本量子算法/技術(shù).關(guān)于量子計算的基本知識以及更全面的介紹可參考文獻(xiàn)[14-16].本節(jié)主要介紹一些相對底層的核心算法/技術(shù)，它們最初設(shè)計時并不是為了優(yōu)化算法，可廣泛應(yīng)用于不同的領(lǐng)域，其中當(dāng)然也包括優(yōu)化領(lǐng)域.

1.1 Grover算法與量子隨機游走(Grover algorithm &quantum random walk)

Grover算法與量子隨機游走已經(jīng)被應(yīng)用在許多領(lǐng)域，其中就有離散優(yōu)化領(lǐng)域.Grover算法于1996年被提出[10]，用于無序數(shù)據(jù)庫搜索，其方法是通過迭代利用一個可識別搜索目標(biāo)的黑盒來提高搜索目標(biāo)在量子疊加態(tài)中的振幅，從而提高測量獲得搜索目標(biāo)的概率.后續(xù)有多個相關(guān)的改進(jìn)結(jié)果，如由清華大學(xué)的Long提出的Grover算法的精確版本[17].原始的Grover算法需要確切知道搜索空間中目標(biāo)的數(shù)量才能確定最優(yōu)的迭代次數(shù)，過少的迭代次數(shù)達(dá)不到效果，過多的迭代也會降低搜索的成功率，迭代次數(shù)增多并不能保證一直趨向搜索目標(biāo).該問題在文獻(xiàn)[18]中被稱為“soufflé problem”.因此，對于搜索空間中目標(biāo)數(shù)量未知的情形，算法需要改進(jìn)，Grover和Mizel先后對此作過討論，并給出了隨著迭代次數(shù)增加能一直增加搜索成功率的改進(jìn)版本[19-21]，但這幾項工作都一定程度上犧牲了算法效率.最終Yoder等人給出了進(jìn)一步改進(jìn)[22]，既保留了平方加速，也保證了迭代最終會一直趨向搜索目標(biāo).此系列改進(jìn)工作被稱為固定點量子搜索(fixed-point quantum search).若搜索前對答案有一定的先驗知識，He等人給出了相應(yīng)最優(yōu)算法[23].

量子隨機游走于1993年由新墨西哥大學(xué)的Aharonov等3名學(xué)者提出[24].不同時期量子隨機游走的工作梳理可參見文獻(xiàn)[25-28].Grover算法可以看作是在一種特殊圖上的量子隨機游走，因此量子隨機游走是一種更一般化的量子搜索技術(shù)，已經(jīng)成為一類重要的量子算法設(shè)計模型.

1.2 量子傅里葉變換與量子相位估計算法(quantum Fourier transform &quantum phase estimation algorithm)

作為量子算法里提供加速的最為核心的2個基本工具，量子傅里葉變換最早可追溯到1994年[29]，而量子相位估計算法最早可追溯到1995年[30].利用量子解線性方程思想以及量子梯度估計法的量子優(yōu)化算法都直接或間接地使用了量子傅里葉變換或量子相位估計算法.讀者可以在任一量子計算教材中找到這2個基本工具的詳細(xì)介紹[14-16].

1.3 量子幅值放大/幅值估計(quantum amplitude amp-lification and amplitude estimation)

2002年，Brassard等4名學(xué)者提出了量子振幅放大以及量子振幅估計算法[31].前者通過一系列的反射操作，達(dá)到放大所需結(jié)果概率的目的;而后者則是在前者的基礎(chǔ)上結(jié)合量子相位估計算法，從而估計所需結(jié)果的概率.在量子優(yōu)化算法中，不完美的演化產(chǎn)生的垃圾信息，以及算法本身產(chǎn)生的無用信息一般都通過振幅放大過濾掉.該工作與Grover算法[10]以及量子計數(shù)[32]有密切聯(lián)系.Ambainis于2012年提出了量子振幅放大算法的時變版本[33]，并用于求解線性代數(shù)問題.量子振幅估計算法近期還有針對非布爾函數(shù)的推廣[34]以及無需使用量子相位估計算法的變種[35].

1.4 解線性方程量子算法(quantum linear system algorithm)

解線性方程量子算法最早在2009年由Harrow，Hassidim，Lloyd三名學(xué)者提出[11]，所以也被稱為HHL算法.解線性方程即給定矩陣A與向量b，求滿足Ax=b的x.此類算法也可以用來處理矩陣與向量乘積、矩陣求逆等操作，因此也常見于量子優(yōu)化技術(shù)的迭代算法中.需要注意的是，解線性方程量子算法求解的是量子版本的問題，即輸入輸出均為量子態(tài)，無法直接得到解的每一個分量，因此在進(jìn)一步應(yīng)用時需要經(jīng)過巧妙設(shè)計，一般在利用方程解的全局信息時才能體現(xiàn)量子算法的加速效果.Ambainis于次年提出了改進(jìn)版本，減少了算法復(fù)雜度對矩陣條件數(shù)的依賴[36].2017年，Childs等3名學(xué)者用其他思路給出了解線性方程量子算法[37]，減少了計算復(fù)雜度中對精度的依賴.2018年，Wossnig等3名學(xué)者利用量子奇異值估計算法，去除了計算復(fù)雜度中對矩陣稀疏度的依賴[38].關(guān)于此系列工作的梳理可以參見文獻(xiàn)[39].

1.5 量子隨機存取存儲(quantum random access memory)

要在經(jīng)典問題上使用量子算法，經(jīng)典數(shù)據(jù)編碼成量子態(tài)是必不可少的重要步驟，量子隨機存取存儲(簡稱QRAM)則是這一過程的主要輔助技術(shù).同為實現(xiàn)數(shù)據(jù)的存儲和提取，QRAM與經(jīng)典的隨機存儲器最大的區(qū)別是：QRAM可以被量子疊加態(tài)地址訪問，返回與地址相糾纏的疊加態(tài)數(shù)據(jù)，這為量子優(yōu)化算法以及量子機器學(xué)習(xí)的初態(tài)制備提供了有力工具.在量子優(yōu)化中使用得較多的為2008年Lloyd等3名學(xué)者提出的Bucket-Brigade結(jié)構(gòu)的QRAM[40-41]，利用此結(jié)構(gòu)在對數(shù)時間復(fù)雜度內(nèi)可實現(xiàn)初態(tài)制備.值得注意的是搭建QRAM的時間復(fù)雜性仍然較高，整體上會抵消掉量子算法帶來的加速，QRAM搭建技術(shù)仍然需要進(jìn)一步優(yōu)化.2018年，Chakraborty等3名學(xué)者提出了塊編碼技術(shù)，并證明與Bucket-Brigade結(jié)構(gòu)在矩陣編碼上等價[42].

1.6 哈密頓量模擬(Hamiltonian simulation)

哈密頓量是與量子系統(tǒng)總能量有關(guān)的運算符，根據(jù)薛定諤方程可知，它可用于描述量子系統(tǒng)隨時間的演化，通過操作哈密頓量可以實現(xiàn)量子態(tài)的演化.在部分量子優(yōu)化算法中(特別是用到解線性方程量子算法思想的算法)，矩陣被編碼成哈密頓量的形式，進(jìn)而作用到量子態(tài)上.哈密頓量模擬就是尋找能高效逼近目標(biāo)哈密頓演化的酉演化，從而在有效時間內(nèi)完成演化(亦即實現(xiàn)了量子算法的過程).關(guān)于哈密頓量模擬的正式結(jié)果最早可追溯到1996年Lloyd發(fā)表在《Science》上的文章[43]，并隨后被推廣到稀疏哈密頓量的模擬上[44-45]，且效率得到逐步提升[46-49].以上的工作針對的都是時間無關(guān)哈密頓量，而其后還有針對時間相關(guān)哈密頓量的推廣工作[50-51].除研究時間復(fù)雜度與查詢復(fù)雜度外，近年也出現(xiàn)了研究哈密頓量模擬采樣復(fù)雜度的工作[52].

2 離散變量量子優(yōu)化技術(shù)

本節(jié)簡要介紹離散變量量子優(yōu)化技術(shù).主要離散變量量子優(yōu)化技術(shù)的提出時間距今較長，因此本節(jié)只簡單介紹各技術(shù)的歷史以及給出重要工作的引文供讀者進(jìn)一步了解.

2.1 基于Grover算法與量子隨機游走的優(yōu)化算法(optimization based on Grover algorithm &quantum random walk)

經(jīng)典離散優(yōu)化的算法往往離不開搜索，而Grover算法與量子隨機游走則正是加速搜索的量子算法，因此十分適合用于加速離散優(yōu)化問題的求解.用Grover算法解決的離散優(yōu)化問題有：無序數(shù)據(jù)最小值尋找[53]、最小生成樹與最短路問題[54]、最大整數(shù)網(wǎng)絡(luò)流查找[55]等.作為Grover算法推廣的振幅放大算法也有相應(yīng)的離散優(yōu)化應(yīng)用[56].量子隨機游走則被用于加速基于Markov鏈的技術(shù)[57]等.近年也有用連續(xù)時間量子隨機游走解決組合優(yōu)化問題的工作[58].

2.2 量子退火/量子隨機優(yōu)化(quantum annealing/quantum stochastic optimization)

量子退火法于1989年由比勒費爾德大學(xué)的Carvalho等3位學(xué)者提出[59]，也稱為量子隨機優(yōu)化.如遺傳算法、蟻群算法與模擬退火等仿生算法都是非常實用的啟發(fā)式優(yōu)化技術(shù)，其中模擬退火法是出現(xiàn)得較早的經(jīng)典技術(shù)，研究較深入.1)量子退火法中使用隧道場強度作為經(jīng)典模擬退火法的溫度參數(shù).由于量子隧穿效應(yīng)的存在，使得量子退火法更容易跳出局部最優(yōu)解，獲得全局最優(yōu)解，從而體現(xiàn)出超越經(jīng)典模擬退火的優(yōu)勢.2)量子退火不需要運用量子糾纏，因此易于實現(xiàn)，D-Wave公司生產(chǎn)的專用量子計算機即可運行量子退火算法.關(guān)于量子退火的早期工作可參閱文獻(xiàn)[60-61]，關(guān)于D-Wave計算機與量子退火的綜合介紹可參閱文獻(xiàn)[62].

2.3 量子近似優(yōu)化算法(quantum approximate optimization algorithm)

一般我們說的量子近似優(yōu)化算法，都習(xí)慣特指本節(jié)所述的求解組合優(yōu)化問題的量子近似優(yōu)化算法，關(guān)于該算法的入門介紹可參照文獻(xiàn)[63-64].

量子近似優(yōu)化算法(簡稱QAOA)于2014年由麻省理工學(xué)院的Farhi等3位學(xué)者提出[65]，最初的設(shè)計是用于求解組合優(yōu)化問題.該工作的量子電路深度依賴于一個與精度有關(guān)的參數(shù)，最壞情況下電路深度隨著該參數(shù)與約束條件數(shù)量的乘積呈線性增長.該工作給出了使用QAOA解決p-正則圖最大割(Max-Cut)問題的例子(p≤3)，而傳統(tǒng)做法是把最大割問題轉(zhuǎn)化為圓錐線性優(yōu)化問題(conic linear optimization problem)解決.相較于經(jīng)典算法，初期的QAOA并沒有顯示出明顯的優(yōu)勢，直到2016年麻省理工學(xué)院的Harrow等2名學(xué)者指出QAOA是實現(xiàn)量子霸權(quán)(quantum supremacy)的方法之一[66]，熱度才有所上升，近年也有理論分析的嘗試[67].另一方面，QAOA算法實現(xiàn)時對相干時長要求低，或許是現(xiàn)有的小規(guī)模量子計算機理想的實驗內(nèi)容之一，因此受到了量子計算實驗研究者的關(guān)注，陸續(xù)有實驗文章出現(xiàn)[68].另外，近年也出現(xiàn)了用QAOA算法解決連續(xù)優(yōu)化問題的研究，見3.5節(jié).

3 連續(xù)變量量子優(yōu)化技術(shù)

本節(jié)將詳細(xì)介紹連續(xù)變量量子優(yōu)化技術(shù).連續(xù)變量量子優(yōu)化技術(shù)是近5年的研究熱點，因此本節(jié)將詳細(xì)給出各工作所針對的具體問題、算法復(fù)雜度，以及所采用技術(shù)的直觀描述.對于與經(jīng)典模型有關(guān)的量子算法，本文還會給出該經(jīng)典模型的框架介紹以便讀者理解.問題和模型都將列在方框內(nèi).

3.1 量子梯度估計法(quantum gradient estimation)

在許多優(yōu)化方法中，特別是迭代方法的梯度下降法與牛頓法，都需要目標(biāo)函數(shù)的梯度信息，因此梯度估計是這類方法的核心技術(shù)之一.量子梯度估計法于2005年由麻省理工學(xué)院的Jordan提出[69].

梯度估計問題(查詢模型)：

給定：函數(shù)f:Rd→R的查詢黑盒Of(查詢返回詢問點的函數(shù)值)，點x=(x1,x2,…,xd)∈d.

該工作研究的是查詢模型，在給定目標(biāo)函數(shù)黑盒的情況下，量子梯度估計算法只需要調(diào)用O(1)次查詢黑盒，即可近似計算出目標(biāo)函數(shù)在某點的梯度，與優(yōu)化變量的維度無關(guān).當(dāng)目標(biāo)函數(shù)估值較困難、優(yōu)化變量維度較大時，量子梯度估計法有一定的優(yōu)勢.美中不足的是，該算法無法通過遞歸求解目標(biāo)函數(shù)的高階導(dǎo)數(shù)，求n階導(dǎo)數(shù)需要額外的2n次查詢來計算所需要的相位信息，因而失去了量子優(yōu)勢.此工作主要使用了量子相位估計技術(shù).2019年，來自荷蘭國家數(shù)學(xué)與計算機中心與微軟研究院的研究人員合作改進(jìn)了量子梯度估計法[70]，并指出原有的量子梯度估計法采取的黑盒輸入模型過強，實際上難以達(dá)到所需精度，因此改而研究相位黑盒輸入模型與概率輸入模型，并給出了這2種輸入模型的轉(zhuǎn)化關(guān)系.在該輸入模型下，改進(jìn)算法估計平滑函數(shù)的梯度時在查詢復(fù)雜度上有二次(quadratic)加速，并且證明了量子優(yōu)化產(chǎn)生的大多數(shù)目標(biāo)函數(shù)會滿足必要的平滑條件.

3.2 量子梯度下降法(quantum gradient descent)

迭代方法在無閉式解的優(yōu)化問題中有非常廣泛的應(yīng)用，梯度下降法就是其中一種迭代方法.梯度下降法從初始的、未經(jīng)優(yōu)化的解開始，每輪根據(jù)與目標(biāo)函數(shù)的梯度有關(guān)的更新規(guī)則迭代更新解.由于梯度方向是函數(shù)增長速度最快的方向，梯度的反方向是函數(shù)下降速度最快的方向，因此參照梯度信息進(jìn)行迭代，能更快地獲得滿足要求的近似最優(yōu)解.

由于量子計算的特性，運用迭代方法時一旦其中一步失敗，輸入就損毀了，一切就要重頭再來，這使得若要達(dá)到迭代τ次的效果，往往需要遠(yuǎn)多于τ次實現(xiàn)迭代操作的量子演化.

梯度下降法：

猜測初始解θ0；

針對單位范數(shù)(unit norm)約束多項式優(yōu)化(polynomial optimization)的量子梯度下降法于2019年由MIT的Lloyd等學(xué)者提出[71].該方法對數(shù)據(jù)維度較大的情況有優(yōu)勢，且把量子計算技術(shù)推進(jìn)到了非二次優(yōu)化甚至非凸優(yōu)化問題上.

多項式優(yōu)化(帶單位范數(shù)約束)問題：

給定：N2p個系數(shù)Ai1…i2p∈，其中p為正整數(shù).

二次優(yōu)化問題：

給定：A∈n×n,b∈n,c∈.

帶權(quán)最小二乘問題：

給定：樣例矩陣X、對應(yīng)的標(biāo)簽向量y以及權(quán)重向量w.

此工作運用的技術(shù)為量子奇異值估計算法(包含了量子振幅放大、量子振幅估計以及量子相位估計算法).該工作在原有QRAM的算法設(shè)計模型上作了一些改進(jìn)，使得量子奇異值估計算法的時間復(fù)雜度由原來的與待分解矩陣的F范數(shù)有關(guān)，改進(jìn)為與最大行范數(shù)與F范數(shù)兩者之間的較小者有關(guān).由于有不少現(xiàn)實問題待分解的矩陣的行范數(shù)都是有界的(boundedl1norm)，這一改進(jìn)是有應(yīng)用價值的，而且該改進(jìn)也可以運用在量子解線性方程上.

3.3 量子在線梯度下降(quantum online gradient descent)

在線凸優(yōu)化是在線學(xué)習(xí)中的一個重要的框架，是凸優(yōu)化與博弈論的交叉領(lǐng)域，在決策問題中有非常廣泛的應(yīng)用，如在線路由問題、投資組合問題以及推薦系統(tǒng)等，都可以用在線凸優(yōu)化的框架建模，并用相關(guān)技術(shù)解決.

在線凸優(yōu)化模型：

給定凸集K?n，凸函數(shù)族F:n→.

決策者依序進(jìn)行T*輪決策，在第t∈{1,2,…,T*}輪時：

1)在凸集K中做出決策xt;

2)遭受損失ft(xt)，其中ft∈F由對手選取或者由環(huán)境生成;

3.4 量子牛頓法(quantum Newton’s method)

牛頓法是一種處理無約束優(yōu)化問題的迭代方法，相比每次迭代沿著梯度方向移動的梯度下降法，牛頓法把曲率也考慮在內(nèi)，因此往往能加快收斂速度.梯度下降法與牛頓法之間是迭代復(fù)雜度與迭代次數(shù)之間的相互轉(zhuǎn)化，每次迭代考慮更多信息的牛頓法自然單次迭代計算復(fù)雜度會更高，但由于收斂更快，因此迭代次數(shù)相應(yīng)下降.2種方法不能簡單說孰優(yōu)孰劣，各有不同的適應(yīng)場景.

牛頓法：

猜測解θ0；

3.5 連續(xù)變量量子近似優(yōu)化算法(quantum app-roximate optimization algorithm for continuous variable)

針對連續(xù)優(yōu)化問題的量子近似優(yōu)化算法于2019年由滑鐵盧大學(xué)的Killoran等學(xué)者提出[74].該工作參考了離散版本QAOA的思路，并用量子粒子勢能動力學(xué)(quantum dynamics of particles in energy potentials)的技術(shù)編碼目標(biāo)函數(shù).該算法適用于有約束與無約束優(yōu)化，稍加修改也可以解決離散優(yōu)化問題.文章作者給出了使用此算法最小化非凸Styblinski-Tang函數(shù)的數(shù)值模擬實驗.

同樣地，該工作相對現(xiàn)存經(jīng)典技術(shù)的優(yōu)勢仍待進(jìn)一步論證，且此版本的實現(xiàn)難度要比離散版本高，超出了目前量子計算機可實驗的范圍.

3.6 量子內(nèi)點法(quantum interior point method)

內(nèi)點法是處理有約束優(yōu)化問題的迭代方法之一，常用于線性規(guī)劃與二次規(guī)劃，實際應(yīng)用面與著名的單純形法分庭抗禮，而且相較于非多項式算法的單純形法，內(nèi)點法是多項式算法，因此在大規(guī)模的線性規(guī)劃問題中有更大的用武之地.

內(nèi)點法：

松弛變量，把待優(yōu)化問題的不等式約束條件轉(zhuǎn)化為線性不等式約束；

目標(biāo)函數(shù)中引入不等式約束條件的屏障函數(shù)(barrier function)，構(gòu)造中央路徑(central path)函數(shù)；

用牛頓法沿著中央路徑尋找最優(yōu)解.

在內(nèi)點法中，計算牛頓線性系統(tǒng)矩陣(Newton linear system matrix)是非?；〞r間的，而該文提出了構(gòu)造牛頓線性系統(tǒng)矩陣塊編碼的量子技術(shù)，加速了這一過程，主要運用的是量子態(tài)層析技術(shù).該文作者同時證明了算法的收斂速度與經(jīng)典方法一致，因此量子內(nèi)點法所需的迭代次數(shù)與經(jīng)典算法一致.綜合每次迭代的加速而言，量子內(nèi)點法是一個理論突破.

2019年，文獻(xiàn)[75]的2名學(xué)者與Szilágyi合作先后發(fā)表3篇文章，分別把量子內(nèi)點法擴(kuò)展到解決二階錐規(guī)劃[76]，以及應(yīng)用到投資組合問題[77]與支持向量機[78]上.

二階錐規(guī)劃問題:給定:A(i)∈RRm×ni,ci∈RRni,i∈[r],b∈RRm.求:minx1,…,xr{∑ri=1cTixi∑ri=1A(i)xi=b,xi∈Lni},其中Lni=x=x0;x～ ∈RRni x～≤x0}為洛倫茲錐(Lorentz cones),?i=[r]. 投資組合問題:投資者需要對m只投資產(chǎn)品的資金分配做T輪決策,每輪結(jié)算后根據(jù)之前的投資決策進(jìn)行下一輪的分配計劃,最終目的是使得總收益最大化.

3.7 量子半正定規(guī)劃(quantum semi-definite pro-gramming)

半正定規(guī)劃是凸優(yōu)化問題的一個分支，針對的是目標(biāo)函數(shù)為線性函數(shù)、優(yōu)化變量約束在光譜面上(半正定矩陣構(gòu)成的錐體與仿射空間的交集)的優(yōu)化問題，存在多項式時間的經(jīng)典算法.由于半正定規(guī)劃在現(xiàn)實中應(yīng)用面廣，輸入規(guī)模大，因此多項式時間仍然不能滿足發(fā)展需要.2017—2019年，量子半正定規(guī)劃法經(jīng)過了多次迭代，并得到了快速發(fā)展.

半正定規(guī)劃問題(原始形式):給定:A1,A2,…,Am,C∈RRn×n,b1,b2,…,bm∈RR.求:max{tr(CX)|?j∈[m],tr(AjX)≤bj,X≥0}. 半正定規(guī)劃問題(對偶形式):給定:A1,A2,…,Am,C∈RRn×n,b∈RRm.求:miny∈RRm{bTx|∑k∈[m]ykAk≥C}.

量子半正定規(guī)劃方法于2017年由加州理工學(xué)院的Brand?o與微軟研究院的Svore提出[79]，該算法比經(jīng)典算法有著關(guān)于矩陣維度的平方級加速，且當(dāng)矩陣越稀疏，優(yōu)勢越明顯.量子吉布斯采樣(quantum Gibbs sampling)與乘權(quán)法(the multiplicative weight method)是實現(xiàn)該算法的關(guān)鍵技術(shù).

文獻(xiàn)[79]的作者還與馬里蘭大學(xué)的研究人員合作，針對設(shè)備帶誤差的情況進(jìn)一步優(yōu)化了量子半正定規(guī)劃算法[80]，使得上界進(jìn)一步逼近下界.與文獻(xiàn)[79]不同的是，該算法使用的是量子態(tài)輸入模型直接獲得純化的混合態(tài)，且采取的是零和游戲框架.該文核心技術(shù)是用快速放大算法(fast amplification algorithm)改進(jìn)了量子OR引理，提高了算法速度.

van Apeldoorn等4名學(xué)者提出了對文獻(xiàn)[79]的改進(jìn)[81]，降低了精度對算法上界的影響，并給出了所有線性規(guī)劃算法的量子查詢下界(因此包括了所有的半正定規(guī)劃算法)，該工作還把他們的改進(jìn)版本應(yīng)用在了實現(xiàn)給定哈密頓量平滑函數(shù)與函數(shù)廣義最小值查找算法上.

2018年，van Apeldoorn等2名學(xué)者綜合以上的幾項工作的優(yōu)點以及Gentle Quantum Search引理，提出了量子半正定規(guī)劃的改進(jìn)版本[82].該工作給出了更優(yōu)的上下界，分別論證了在量子態(tài)輸入、稀疏矩陣輸入以及量子算子輸入這3種不同輸入模型下的算法效率，并應(yīng)用到陰影層析問題、量子態(tài)區(qū)分問題以及E-最優(yōu)設(shè)計上.

這4項工作的復(fù)雜度上下界詳見表1.

Table 1 Main Results of Quantum Semi-Definite Programming表1 主要量子半正定規(guī)劃結(jié)果

需要注意的是，精度等參數(shù)對于量子半正定規(guī)劃計算復(fù)雜度的影響仍然較大，因此要在實際問題上超越經(jīng)典算法依然需要進(jìn)一步的研究.

3.8 量子線性規(guī)劃(quantum linear programming)

線性規(guī)劃是半正定規(guī)劃的一個特殊形式，從實用的角度比更一般的半正定規(guī)劃應(yīng)用更為廣泛.除了3.6節(jié)提到的可用于解線性規(guī)劃問題的內(nèi)點法外，還有2項針對線性規(guī)劃問題的量子工作.

線性規(guī)劃問題(原始形式):給定:A∈RRn×m,b∈RRn,c∈RRm.求:minx∈RRm{cTx|Ax≥b,x≥0}. 線性規(guī)劃問題(對偶形式):給定:A∈RRn×m,b∈RRn,c∈RRm.求:maxy∈RRn{bTy|ATy≤c,y≥0}.

3.9 一般凸優(yōu)化的量子算法(quantum algorithm for general convex optimization)

針對一般的無約束凸優(yōu)化問題，馬里蘭大學(xué)的Childs團(tuán)隊[85]與荷蘭國家數(shù)學(xué)與計算機中心de Wolf團(tuán)隊[86]于2020年分別獨立地提出了相應(yīng)的量子算法.

一般凸優(yōu)化問題(查詢模型)：

給定：凸集K?n的成員黑盒OK(查詢返回詢問點是否在集合內(nèi))，凸函數(shù)f:K→的估值黑盒Of(查詢返回詢問點的函數(shù)值).

文獻(xiàn)[85-86]的2項工作結(jié)論一致，研究的均為黑盒查詢模型，思路大致類似.在給定成員黑盒(用于查詢優(yōu)化變量給定取值是否在可行域中)與估值黑盒(用于計算目標(biāo)函數(shù)在給定點的值)情況下，2項工作的結(jié)果由表2說明.我們可以從表中看到，在時間復(fù)雜度相同的情況下，量子算法的查詢上界達(dá)到了經(jīng)典算法的下界，這意味著該量子算法在理論上達(dá)到了經(jīng)典算法潛在的最好情況.另外，量子算法上下界仍然未緊，這意味著量子算法仍然有提升空間.由于2項工作結(jié)論一致，以下主要介紹文獻(xiàn)[85]的技術(shù).

Table 2 Comparison of Quantum and Classical General Convex Optimization Algorithms表2 量子與經(jīng)典一般凸優(yōu)化算法的對比

針對一般凸優(yōu)化問題的量子算法使用的主要是量子梯度估計技術(shù)，從估值黑盒出發(fā)通過量子梯度估計求得分離超平面，經(jīng)由分離超平面再得出最小化線性函數(shù)的方法，最后得出一般凸優(yōu)化問題的算法，這過程中綜合運用工程中常見的誤差縮小技術(shù)與函數(shù)緩和技術(shù)處理邊界不光滑等會影響算法性能與誤差的問題.

4 總 結(jié)

優(yōu)化問題在生產(chǎn)生活中無處不在，經(jīng)典計算領(lǐng)域把優(yōu)化作為一個正式的學(xué)科分支進(jìn)行研究已經(jīng)有一百多年的歷史，而最優(yōu)化方法的起源甚至可以追溯到三四百年前費馬、拉格朗日、牛頓以及高斯的微積分時代.隨后經(jīng)歷了高度依賴一階、高階導(dǎo)數(shù)的分析算法階段、用準(zhǔn)確度交換速度的啟發(fā)式算法階段，以及高度依賴數(shù)據(jù)的代理模型階段.如今在工程實踐中，各類方法高度融合，產(chǎn)生著巨大的經(jīng)濟(jì)社會效益.

但縱使已經(jīng)研究了數(shù)百年，在優(yōu)化領(lǐng)域還一直有許多難題尚未得到有效的解決，有如大部分的非凸優(yōu)化問題、組合優(yōu)化里的NP問題，以及許多規(guī)模極大的P問題，都還處于探索階段.而量子計算的興起為這些難題帶來了新的希望和探索方向.量子算法已經(jīng)在不少問題上相對于經(jīng)典算法帶來了加速優(yōu)勢，但由于中等規(guī)模量子計算機目前依然昂貴，大型的通用量子計算機難見蹤跡，因此量子優(yōu)化算法的設(shè)計目前依然處于理論分析難、實驗成本高的階段，學(xué)術(shù)界與工業(yè)界都迫切盼望量子計算能在基礎(chǔ)理論與軟硬件技術(shù)上有進(jìn)一步的突破.

本文通過對量子優(yōu)化算法研究方面的梳理觀察得出4方面：

1)從時間上看，連續(xù)變量的量子優(yōu)化算法是近年的趨勢，也將會是未來短期內(nèi)的研究熱點.這并非說組合優(yōu)化不重要，而是組合優(yōu)化問題有很大一部分是NP問題，要找到高效的量子算法具有挑戰(zhàn)性.已有的針對組合優(yōu)化問題的量子算法要么是采用Grover算法，在某個子過程達(dá)到根號級別加速，要么就是采用無法在理論上分析復(fù)雜度的啟發(fā)式算法，而目前的量子計算機規(guī)模還不足以驗證啟發(fā)式量子算法的應(yīng)用價值.連續(xù)變量優(yōu)化問題似乎更有希望獲得更多的量子加速，而且其應(yīng)用面也因人工智能的發(fā)展而日益廣泛.

2)量子優(yōu)化使用的基本量子技術(shù)的核心思想大多都是1995—2008年提出的，HHL算法以及Jordan量子梯度估計法均為1995年相位估計算法框架的延展，幅值放大技術(shù)為1996年Grover算法的延展，而哈密頓量模擬算法以及量子隨機存儲技術(shù)也已有10～20年的歷史.若需要尋找新的方向，還需要在最為底層的算法上有突破.

3)除啟發(fā)式算法外，主要的量子優(yōu)化算法相對于經(jīng)典算法都在理論上體現(xiàn)了一定的加速，既有體現(xiàn)在時間復(fù)雜度的加速，也有體現(xiàn)在查詢復(fù)雜度上的加速.一般來說，問題的計算復(fù)雜度下界往往很難證明，但查詢復(fù)雜度的下界證明有如對手法[89]等較成體系的方法.縱觀現(xiàn)有工作，在一般凸優(yōu)化問題的查詢模型上[85-86]尋找量子優(yōu)勢是很有希望的，因為其量子上界已經(jīng)達(dá)到經(jīng)典下界，且量子上下界還未緊，還有改進(jìn)空間.

4)目前獲得量子加速的優(yōu)化問題十分有限，優(yōu)化領(lǐng)域依然存在許多值得量子計算科學(xué)家探索的問題，如優(yōu)化領(lǐng)域的難題：非凸優(yōu)化.對凸優(yōu)化研究的深入是經(jīng)典優(yōu)化領(lǐng)域的一個分水嶺[90]，因為凸函數(shù)具有極小值即最小值等良好特性，使得凸優(yōu)化問題大多都有可行、高效的算法，因此凸優(yōu)化問題與能轉(zhuǎn)化成凸優(yōu)化問題的優(yōu)化問題被認(rèn)為是較易解決的.相對地，解決非凸優(yōu)化則比較困難.現(xiàn)在的量子優(yōu)化算法中，針對的線性規(guī)劃、二次規(guī)劃、半正定規(guī)劃問題都是常見的特殊凸優(yōu)化問題，都屬于經(jīng)典優(yōu)化領(lǐng)域認(rèn)為較易解決的部分，針對非凸優(yōu)化的量子算法還很少.再者還有更多貼近實際應(yīng)用的優(yōu)化問題，如引入更多約束條件的約束優(yōu)化、目標(biāo)函數(shù)不單一的多目標(biāo)規(guī)劃、帶有不確定性的不確定規(guī)劃、問題隨時間而變的動態(tài)規(guī)劃、部分變量要求為整數(shù)的混合整數(shù)規(guī)劃等.經(jīng)典優(yōu)化對于這些優(yōu)化問題均有系統(tǒng)的研究，而量子計算目前依然缺席，均可進(jìn)行探索.