量子優(yōu)化算法綜述

何鍵浩 李綠周

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

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

根據(jù)優(yōu)化問題的變量是否連續(xù)，優(yōu)化技術(shù)可以分為離散變量優(yōu)化(也稱為組合優(yōu)化)和連續(xù)變量優(yōu)化兩大類.其中，根據(jù)目標函數(shù)是否是凸的，連續(xù)變量優(yōu)化又可分為凸優(yōu)化和非凸優(yōu)化.凸優(yōu)化主要研究的是目標函數(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)注，近年來量子計算理論方面的研究進展可參考文獻[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ā)式算法.此階段的量子算法主要得益于當時3類基礎(chǔ)離散量子技術(shù)：

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

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

③ 量子近似優(yōu)化技術(shù).量子近似優(yōu)化算法雖然還沒有關(guān)于理論優(yōu)勢的嚴格分析，但被認為適合近期的含噪中等規(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ù)進行預(yù)處理，可以使算法的效率得到提升，不過量子隨機存儲的搭建仍然需要進一步的優(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)于量子計算的基本知識以及更全面的介紹可參考文獻[14-16].本節(jié)主要介紹一些相對底層的核心算法/技術(shù)，它們最初設(shè)計時并不是為了優(yōu)化算法，可廣泛應(yīng)用于不同的領(lǐ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ù)庫搜索，其方法是通過迭代利用一個可識別搜索目標的黑盒來提高搜索目標在量子疊加態(tài)中的振幅，從而提高測量獲得搜索目標的概率.后續(xù)有多個相關(guān)的改進結(jié)果，如由清華大學的Long提出的Grover算法的精確版本[17].原始的Grover算法需要確切知道搜索空間中目標的數(shù)量才能確定最優(yōu)的迭代次數(shù)，過少的迭代次數(shù)達不到效果，過多的迭代也會降低搜索的成功率，迭代次數(shù)增多并不能保證一直趨向搜索目標.該問題在文獻[18]中被稱為“soufflé problem”.因此，對于搜索空間中目標數(shù)量未知的情形，算法需要改進，Grover和Mizel先后對此作過討論，并給出了隨著迭代次數(shù)增加能一直增加搜索成功率的改進版本[19-21]，但這幾項工作都一定程度上犧牲了算法效率.最終Yoder等人給出了進一步改進[22]，既保留了平方加速，也保證了迭代最終會一直趨向搜索目標.此系列改進工作被稱為固定點量子搜索(fixed-point quantum search).若搜索前對答案有一定的先驗知識，He等人給出了相應(yīng)最優(yōu)算法[23].

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

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

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

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

2002年，Brassard等4名學者提出了量子振幅放大以及量子振幅估計算法[31].前者通過一系列的反射操作，達到放大所需結(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三名學者提出[11]，所以也被稱為HHL算法.解線性方程即給定矩陣A與向量b，求滿足Ax=b的x.此類算法也可以用來處理矩陣與向量乘積、矩陣求逆等操作，因此也常見于量子優(yōu)化技術(shù)的迭代算法中.需要注意的是，解線性方程量子算法求解的是量子版本的問題，即輸入輸出均為量子態(tài)，無法直接得到解的每一個分量，因此在進一步應(yīng)用時需要經(jīng)過巧妙設(shè)計，一般在利用方程解的全局信息時才能體現(xiàn)量子算法的加速效果.Ambainis于次年提出了改進版本，減少了算法復(fù)雜度對矩陣條件數(shù)的依賴[36].2017年，Childs等3名學者用其他思路給出了解線性方程量子算法[37]，減少了計算復(fù)雜度中對精度的依賴.2018年，Wossnig等3名學者利用量子奇異值估計算法，去除了計算復(fù)雜度中對矩陣稀疏度的依賴[38].關(guā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)化算法以及量子機器學習的初態(tài)制備提供了有力工具.在量子優(yōu)化中使用得較多的為2008年Lloyd等3名學者提出的Bucket-Brigade結(jié)構(gòu)的QRAM[40-41]，利用此結(jié)構(gòu)在對數(shù)時間復(fù)雜度內(nèi)可實現(xiàn)初態(tài)制備.值得注意的是搭建QRAM的時間復(fù)雜性仍然較高，整體上會抵消掉量子算法帶來的加速，QRAM搭建技術(shù)仍然需要進一步優(yōu)化.2018年，Chakraborty等3名學者提出了塊編碼技術(shù)，并證明與Bucket-Brigade結(jié)構(gòu)在矩陣編碼上等價[42].

1.6 哈密頓量模擬(Hamiltonian simulation)

哈密頓量是與量子系統(tǒng)總能量有關(guān)的運算符，根據(jù)薛定諤方程可知，它可用于描述量子系統(tǒng)隨時間的演化，通過操作哈密頓量可以實現(xiàn)量子態(tài)的演化.在部分量子優(yōu)化算法中(特別是用到解線性方程量子算法思想的算法)，矩陣被編碼成哈密頓量的形式，進而作用到量子態(tài)上.哈密頓量模擬就是尋找能高效逼近目標哈密頓演化的酉演化，從而在有效時間內(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ù)的歷史以及給出重要工作的引文供讀者進一步了解.

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年由比勒費爾德大學的Carvalho等3位學者提出[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)于量子退火的早期工作可參閱文獻[60-61]，關(guān)于D-Wave計算機與量子退火的綜合介紹可參閱文獻[62].

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

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

量子近似優(yōu)化算法(簡稱QAOA)于2014年由麻省理工學院的Farhi等3位學者提出[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年麻省理工學院的Harrow等2名學者指出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ù)變量量子優(yōu)化技術(shù).連續(xù)變量量子優(yōu)化技術(shù)是近5年的研究熱點，因此本節(jié)將詳細給出各工作所針對的具體問題、算法復(fù)雜度，以及所采用技術(shù)的直觀描述.對于與經(jīng)典模型有關(guān)的量子算法，本文還會給出該經(jīng)典模型的框架介紹以便讀者理解.問題和模型都將列在方框內(nèi).

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

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

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

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

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

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

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

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

梯度下降法：

猜測初始解θ0；

針對單位范數(shù)(unit norm)約束多項式優(yōu)化(polynomial optimization)的量子梯度下降法于2019年由MIT的Lloyd等學者提出[71].該方法對數(shù)據(jù)維度較大的情況有優(yōu)勢，且把量子計算技術(shù)推進到了非二次優(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)的標簽向量y以及權(quán)重向量w.

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

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

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

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

給定凸集K?n，凸函數(shù)族F: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年由滑鐵盧大學的Killoran等學者提出[74].該工作參考了離散版本QAOA的思路，并用量子粒子勢能動力學(quantum dynamics of particles in energy potentials)的技術(shù)編碼目標函數(shù).該算法適用于有約束與無約束優(yōu)化，稍加修改也可以解決離散優(yōu)化問題.文章作者給出了使用此算法最小化非凸Styblinski-Tang函數(shù)的數(shù)值模擬實驗.

同樣地，該工作相對現(xiàn)存經(jīng)典技術(shù)的優(yōu)勢仍待進一步論證，且此版本的實現(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)化為線性不等式約束；

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

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

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

2019年，文獻[75]的2名學者與Szilágyi合作先后發(fā)表3篇文章，分別把量子內(nèi)點法擴展到解決二階錐規(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ù)之前的投資決策進行下一輪的分配計劃,最終目的是使得總收益最大化.

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

半正定規(guī)劃是凸優(yōu)化問題的一個分支，針對的是目標函數(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年由加州理工學院的Brand?o與微軟研究院的Svore提出[79]，該算法比經(jīng)典算法有著關(guān)于矩陣維度的平方級加速，且當矩陣越稀疏，優(yōu)勢越明顯.量子吉布斯采樣(quantum Gibbs sampling)與乘權(quán)法(the multiplicative weight method)是實現(xiàn)該算法的關(guān)鍵技術(shù).

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

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

2018年，van Apeldoorn等2名學者綜合以上的幾項工作的優(yōu)點以及Gentle Quantum Search引理，提出了量子半正定規(guī)劃的改進版本[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)典算法依然需要進一步的研究.

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)化問題，馬里蘭大學的Childs團隊[85]與荷蘭國家數(shù)學與計算機中心de Wolf團隊[86]于2020年分別獨立地提出了相應(yīng)的量子算法.

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

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

文獻[85-86]的2項工作結(jié)論一致，研究的均為黑盒查詢模型，思路大致類似.在給定成員黑盒(用于查詢優(yōu)化變量給定取值是否在可行域中)與估值黑盒(用于計算目標函數(shù)在給定點的值)情況下，2項工作的結(jié)果由表2說明.我們可以從表中看到，在時間復(fù)雜度相同的情況下，量子算法的查詢上界達到了經(jīng)典算法的下界，這意味著該量子算法在理論上達到了經(jīng)典算法潛在的最好情況.另外，量子算法上下界仍然未緊，這意味著量子算法仍然有提升空間.由于2項工作結(jié)論一致，以下主要介紹文獻[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)化作為一個正式的學科分支進行研究已經(jīng)有一百多年的歷史，而最優(yōu)化方法的起源甚至可以追溯到三四百年前費馬、拉格朗日、牛頓以及高斯的微積分時代.隨后經(jīng)歷了高度依賴一階、高階導數(shù)的分析算法階段、用準確度交換速度的啟發(fā)式算法階段，以及高度依賴數(shù)據(jù)的代理模型階段.如今在工程實踐中，各類方法高度融合，產(chǎn)生著巨大的經(jīng)濟社會效益.

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

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

1)從時間上看，連續(xù)變量的量子優(yōu)化算法是近年的趨勢，也將會是未來短期內(nèi)的研究熱點.這并非說組合優(yōu)化不重要，而是組合優(yōu)化問題有很大一部分是NP問題，要找到高效的量子算法具有挑戰(zhàn)性.已有的針對組合優(yōu)化問題的量子算法要么是采用Grover算法，在某個子過程達到根號級別加速，要么就是采用無法在理論上分析復(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)達到經(jīng)典下界，且量子上下界還未緊，還有改進空間.

4)目前獲得量子加速的優(yōu)化問題十分有限，優(yōu)化領(lǐng)域依然存在許多值得量子計算科學家探索的問題，如優(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)化問題被認為是較易解決的.相對地，解決非凸優(yōu)化則比較困難.現(xiàn)在的量子優(yōu)化算法中，針對的線性規(guī)劃、二次規(guī)劃、半正定規(guī)劃問題都是常見的特殊凸優(yōu)化問題，都屬于經(jīng)典優(yōu)化領(lǐng)域認為較易解決的部分，針對非凸優(yōu)化的量子算法還很少.再者還有更多貼近實際應(yīng)用的優(yōu)化問題，如引入更多約束條件的約束優(yōu)化、目標函數(shù)不單一的多目標規(guī)劃、帶有不確定性的不確定規(guī)劃、問題隨時間而變的動態(tài)規(guī)劃、部分變量要求為整數(shù)的混合整數(shù)規(guī)劃等.經(jīng)典優(yōu)化對于這些優(yōu)化問題均有系統(tǒng)的研究，而量子計算目前依然缺席，均可進行探索.