何鍵浩 李綠周
(中山大學(xué)計(jì)算機(jī)學(xué)院 廣州 510006)
優(yōu)化(optimization)是計(jì)算機(jī)科學(xué)與數(shù)學(xué)領(lǐng)域十分重要的基礎(chǔ)研究之一,同時(shí)也是機(jī)器學(xué)習(xí)的核心工具[1].相關(guān)理論與方法廣泛應(yīng)用于各類(lèi)工業(yè)生產(chǎn)[2]、工程設(shè)計(jì)與管理[3-5]、交通運(yùn)輸[6]、經(jīng)濟(jì)決策[7]、市場(chǎng)管理[8]等關(guān)乎國(guó)計(jì)民生的重要領(lǐng)域.一個(gè)具體的優(yōu)化問(wèn)題由3個(gè)基本要素組成:1)目標(biāo)函數(shù)(或損失函數(shù)),即決策者需要優(yōu)化的指標(biāo),如總消耗、總收益等,數(shù)學(xué)形式表現(xiàn)為由優(yōu)化變量到指標(biāo)的函數(shù)/映射.2)優(yōu)化變量,即決策者可以調(diào)整且會(huì)影響到目標(biāo)函數(shù)的變量,如產(chǎn)品工藝、資金分配等.3)約束條件,即在決策過(guò)程中必須遵守的限制,如安全標(biāo)準(zhǔn)、資源儲(chǔ)備總量等.優(yōu)化過(guò)程就是在約束條件的限制下,尋找能最小化或最大化目標(biāo)函數(shù)的優(yōu)化變量的賦值.優(yōu)化有時(shí)候也被稱(chēng)為數(shù)學(xué)規(guī)劃,下文中優(yōu)化與規(guī)劃意義等價(jià),具體使用的詞匯將根據(jù)該細(xì)分方向的用詞習(xí)慣決定.
根據(jù)優(yōu)化問(wèn)題的變量是否連續(xù),優(yōu)化技術(shù)可以分為離散變量?jī)?yōu)化(也稱(chēng)為組合優(yōu)化)和連續(xù)變量?jī)?yōu)化兩大類(lèi).其中,根據(jù)目標(biāo)函數(shù)是否是凸的,連續(xù)變量?jī)?yōu)化又可分為凸優(yōu)化和非凸優(yōu)化.凸優(yōu)化主要研究的是目標(biāo)函數(shù)為凸函數(shù)且優(yōu)化變量可行域?yàn)橥辜膬?yōu)化問(wèn)題,由于凸集凸函數(shù)有許多優(yōu)秀的性質(zhì)(例如極小值即最小值),使得凸優(yōu)化問(wèn)題有很多高效的解法,在應(yīng)用迭代方法求解時(shí)也能獲得良好的收斂速度.因此,凸優(yōu)化技術(shù)方面已有成體系的方法且有廣泛的應(yīng)用.相對(duì)而言,非凸優(yōu)化還有很大的發(fā)展空間.另外,許多非凸優(yōu)化問(wèn)題,目前有效的辦法仍然是轉(zhuǎn)化為凸優(yōu)化問(wèn)題求解.
與此同時(shí),自從Shor快速整數(shù)分解量子算法[9]、Grover量子搜索算法[10]以及HHL量子解線(xiàn)性方程算法[11]的提出,量子計(jì)算就因其與生俱來(lái)的并行性而受到廣泛關(guān)注,近年來(lái)量子計(jì)算理論方面的研究進(jìn)展可參考文獻(xiàn)[12-13].因此,如何利用量子計(jì)算技術(shù)來(lái)加速優(yōu)化問(wèn)題的求解、提高優(yōu)化效果成為受關(guān)注的問(wèn)題,逐漸形成了量子優(yōu)化這一研究方向.量子優(yōu)化算法的研究從時(shí)間上大致分為1996—2015年和2015—2021年這2個(gè)階段.
1)1996—2015年.此階段的量子優(yōu)化算法主要是針對(duì)離散變量?jī)?yōu)化問(wèn)題而設(shè)計(jì),且有較多的啟發(fā)式算法.此階段的量子算法主要得益于當(dāng)時(shí)3類(lèi)基礎(chǔ)離散量子技術(shù):
① Grover算法以及量子隨機(jī)游走.這2個(gè)基礎(chǔ)算法后續(xù)還有不少改進(jìn)與擴(kuò)展,多被用于加速搜索過(guò)程.
② 量子退火法.量子退火法無(wú)需使用糾纏態(tài),實(shí)現(xiàn)較簡(jiǎn)單,因此已經(jīng)有了D-Wave這樣的大型專(zhuān)用量子計(jì)算機(jī)可供實(shí)驗(yàn)研究.
③ 量子近似優(yōu)化技術(shù).量子近似優(yōu)化算法雖然還沒(méi)有關(guān)于理論優(yōu)勢(shì)的嚴(yán)格分析,但被認(rèn)為適合近期的含噪中等規(guī)模量子(noisy intermediate-scale quantum,NISQ)計(jì)算設(shè)備,因此得到不少關(guān)注.
2)2015—2021年.此階段的量子優(yōu)化算法主要針對(duì)連續(xù)變量?jī)?yōu)化問(wèn)題而設(shè)計(jì).連續(xù)變量?jī)?yōu)化問(wèn)題的解法以迭代算法為主,迭代開(kāi)銷(xiāo)以及收斂速度是影響算法效率的主要因素.此階段的量子算法主要得益于4類(lèi)量子技術(shù)的發(fā)展:
① 解線(xiàn)性方程量子算法的設(shè)計(jì)思想.此類(lèi)方法可用于加速與矩陣操作相關(guān)問(wèn)題的求解.
② 哈密頓模擬技術(shù).此類(lèi)方法的發(fā)展為量子態(tài)演化提供了高效的實(shí)現(xiàn)方案.
③ 量子隨機(jī)存儲(chǔ)器.借助量子隨機(jī)存儲(chǔ)技術(shù)對(duì)數(shù)據(jù)進(jìn)行預(yù)處理,可以使算法的效率得到提升,不過(guò)量子隨機(jī)存儲(chǔ)的搭建仍然需要進(jìn)一步的優(yōu)化來(lái)保證整體的優(yōu)勢(shì).
④ 量子梯度估計(jì)法.計(jì)算梯度是許多優(yōu)化問(wèn)題的核心步驟,量子梯度估計(jì)法的提出為此提供了便利.
連續(xù)變量量子優(yōu)化算法是近年的研究趨勢(shì),研究?jī)?nèi)容涵蓋了優(yōu)化領(lǐng)域中梯度下降、牛頓法、內(nèi)點(diǎn)法等常用的傳統(tǒng)迭代方法,也有針對(duì)具體優(yōu)化問(wèn)題的持續(xù)研究,因此本文將重點(diǎn)介紹連續(xù)變量量子優(yōu)化算法,該方向的研究目前主要集中在量子凸優(yōu)化方面.
本節(jié)介紹在量子優(yōu)化算法中使用頻率較高的基本量子算法/技術(shù).關(guān)于量子計(jì)算的基本知識(shí)以及更全面的介紹可參考文獻(xiàn)[14-16].本節(jié)主要介紹一些相對(duì)底層的核心算法/技術(shù),它們最初設(shè)計(jì)時(shí)并不是為了優(yōu)化算法,可廣泛應(yīng)用于不同的領(lǐng)域,其中當(dāng)然也包括優(yōu)化領(lǐng)域.
Grover算法與量子隨機(jī)游走已經(jīng)被應(yīng)用在許多領(lǐng)域,其中就有離散優(yōu)化領(lǐng)域.Grover算法于1996年被提出[10],用于無(wú)序數(shù)據(jù)庫(kù)搜索,其方法是通過(guò)迭代利用一個(gè)可識(shí)別搜索目標(biāo)的黑盒來(lái)提高搜索目標(biāo)在量子疊加態(tài)中的振幅,從而提高測(cè)量獲得搜索目標(biāo)的概率.后續(xù)有多個(gè)相關(guān)的改進(jìn)結(jié)果,如由清華大學(xué)的Long提出的Grover算法的精確版本[17].原始的Grover算法需要確切知道搜索空間中目標(biāo)的數(shù)量才能確定最優(yōu)的迭代次數(shù),過(guò)少的迭代次數(shù)達(dá)不到效果,過(guò)多的迭代也會(huì)降低搜索的成功率,迭代次數(shù)增多并不能保證一直趨向搜索目標(biāo).該問(wèn)題在文獻(xiàn)[18]中被稱(chēng)為“soufflé problem”.因此,對(duì)于搜索空間中目標(biāo)數(shù)量未知的情形,算法需要改進(jìn),Grover和Mizel先后對(duì)此作過(guò)討論,并給出了隨著迭代次數(shù)增加能一直增加搜索成功率的改進(jìn)版本[19-21],但這幾項(xiàng)工作都一定程度上犧牲了算法效率.最終Yoder等人給出了進(jìn)一步改進(jìn)[22],既保留了平方加速,也保證了迭代最終會(huì)一直趨向搜索目標(biāo).此系列改進(jìn)工作被稱(chēng)為固定點(diǎn)量子搜索(fixed-point quantum search).若搜索前對(duì)答案有一定的先驗(yàn)知識(shí),He等人給出了相應(yīng)最優(yōu)算法[23].
量子隨機(jī)游走于1993年由新墨西哥大學(xué)的Aharonov等3名學(xué)者提出[24].不同時(shí)期量子隨機(jī)游走的工作梳理可參見(jiàn)文獻(xiàn)[25-28].Grover算法可以看作是在一種特殊圖上的量子隨機(jī)游走,因此量子隨機(jī)游走是一種更一般化的量子搜索技術(shù),已經(jīng)成為一類(lèi)重要的量子算法設(shè)計(jì)模型.
作為量子算法里提供加速的最為核心的2個(gè)基本工具,量子傅里葉變換最早可追溯到1994年[29],而量子相位估計(jì)算法最早可追溯到1995年[30].利用量子解線(xiàn)性方程思想以及量子梯度估計(jì)法的量子優(yōu)化算法都直接或間接地使用了量子傅里葉變換或量子相位估計(jì)算法.讀者可以在任一量子計(jì)算教材中找到這2個(gè)基本工具的詳細(xì)介紹[14-16].
2002年,Brassard等4名學(xué)者提出了量子振幅放大以及量子振幅估計(jì)算法[31].前者通過(guò)一系列的反射操作,達(dá)到放大所需結(jié)果概率的目的;而后者則是在前者的基礎(chǔ)上結(jié)合量子相位估計(jì)算法,從而估計(jì)所需結(jié)果的概率.在量子優(yōu)化算法中,不完美的演化產(chǎn)生的垃圾信息,以及算法本身產(chǎn)生的無(wú)用信息一般都通過(guò)振幅放大過(guò)濾掉.該工作與Grover算法[10]以及量子計(jì)數(shù)[32]有密切聯(lián)系.Ambainis于2012年提出了量子振幅放大算法的時(shí)變版本[33],并用于求解線(xiàn)性代數(shù)問(wèn)題.量子振幅估計(jì)算法近期還有針對(duì)非布爾函數(shù)的推廣[34]以及無(wú)需使用量子相位估計(jì)算法的變種[35].
解線(xiàn)性方程量子算法最早在2009年由Harrow,Hassidim,Lloyd三名學(xué)者提出[11],所以也被稱(chēng)為HHL算法.解線(xiàn)性方程即給定矩陣A與向量b,求滿(mǎn)足Ax=b的x.此類(lèi)算法也可以用來(lái)處理矩陣與向量乘積、矩陣求逆等操作,因此也常見(jiàn)于量子優(yōu)化技術(shù)的迭代算法中.需要注意的是,解線(xiàn)性方程量子算法求解的是量子版本的問(wèn)題,即輸入輸出均為量子態(tài),無(wú)法直接得到解的每一個(gè)分量,因此在進(jìn)一步應(yīng)用時(shí)需要經(jīng)過(guò)巧妙設(shè)計(jì),一般在利用方程解的全局信息時(shí)才能體現(xiàn)量子算法的加速效果.Ambainis于次年提出了改進(jìn)版本,減少了算法復(fù)雜度對(duì)矩陣條件數(shù)的依賴(lài)[36].2017年,Childs等3名學(xué)者用其他思路給出了解線(xiàn)性方程量子算法[37],減少了計(jì)算復(fù)雜度中對(duì)精度的依賴(lài).2018年,Wossnig等3名學(xué)者利用量子奇異值估計(jì)算法,去除了計(jì)算復(fù)雜度中對(duì)矩陣稀疏度的依賴(lài)[38].關(guān)于此系列工作的梳理可以參見(jiàn)文獻(xiàn)[39].
要在經(jīng)典問(wèn)題上使用量子算法,經(jīng)典數(shù)據(jù)編碼成量子態(tài)是必不可少的重要步驟,量子隨機(jī)存取存儲(chǔ)(簡(jiǎn)稱(chēng)QRAM)則是這一過(guò)程的主要輔助技術(shù).同為實(shí)現(xiàn)數(shù)據(jù)的存儲(chǔ)和提取,QRAM與經(jīng)典的隨機(jī)存儲(chǔ)器最大的區(qū)別是:QRAM可以被量子疊加態(tài)地址訪(fǎng)問(wèn),返回與地址相糾纏的疊加態(tài)數(shù)據(jù),這為量子優(yōu)化算法以及量子機(jī)器學(xué)習(xí)的初態(tài)制備提供了有力工具.在量子優(yōu)化中使用得較多的為2008年Lloyd等3名學(xué)者提出的Bucket-Brigade結(jié)構(gòu)的QRAM[40-41],利用此結(jié)構(gòu)在對(duì)數(shù)時(shí)間復(fù)雜度內(nèi)可實(shí)現(xiàn)初態(tài)制備.值得注意的是搭建QRAM的時(shí)間復(fù)雜性仍然較高,整體上會(huì)抵消掉量子算法帶來(lái)的加速,QRAM搭建技術(shù)仍然需要進(jìn)一步優(yōu)化.2018年,Chakraborty等3名學(xué)者提出了塊編碼技術(shù),并證明與Bucket-Brigade結(jié)構(gòu)在矩陣編碼上等價(jià)[42].
哈密頓量是與量子系統(tǒng)總能量有關(guān)的運(yùn)算符,根據(jù)薛定諤方程可知,它可用于描述量子系統(tǒng)隨時(shí)間的演化,通過(guò)操作哈密頓量可以實(shí)現(xiàn)量子態(tài)的演化.在部分量子優(yōu)化算法中(特別是用到解線(xiàn)性方程量子算法思想的算法),矩陣被編碼成哈密頓量的形式,進(jìn)而作用到量子態(tài)上.哈密頓量模擬就是尋找能高效逼近目標(biāo)哈密頓演化的酉演化,從而在有效時(shí)間內(nèi)完成演化(亦即實(shí)現(xiàn)了量子算法的過(guò)程).關(guān)于哈密頓量模擬的正式結(jié)果最早可追溯到1996年Lloyd發(fā)表在《Science》上的文章[43],并隨后被推廣到稀疏哈密頓量的模擬上[44-45],且效率得到逐步提升[46-49].以上的工作針對(duì)的都是時(shí)間無(wú)關(guān)哈密頓量,而其后還有針對(duì)時(shí)間相關(guān)哈密頓量的推廣工作[50-51].除研究時(shí)間復(fù)雜度與查詢(xún)復(fù)雜度外,近年也出現(xiàn)了研究哈密頓量模擬采樣復(fù)雜度的工作[52].
本節(jié)簡(jiǎn)要介紹離散變量量子優(yōu)化技術(shù).主要離散變量量子優(yōu)化技術(shù)的提出時(shí)間距今較長(zhǎng),因此本節(jié)只簡(jiǎn)單介紹各技術(shù)的歷史以及給出重要工作的引文供讀者進(jìn)一步了解.
經(jīng)典離散優(yōu)化的算法往往離不開(kāi)搜索,而Grover算法與量子隨機(jī)游走則正是加速搜索的量子算法,因此十分適合用于加速離散優(yōu)化問(wèn)題的求解.用Grover算法解決的離散優(yōu)化問(wèn)題有:無(wú)序數(shù)據(jù)最小值尋找[53]、最小生成樹(shù)與最短路問(wèn)題[54]、最大整數(shù)網(wǎng)絡(luò)流查找[55]等.作為Grover算法推廣的振幅放大算法也有相應(yīng)的離散優(yōu)化應(yīng)用[56].量子隨機(jī)游走則被用于加速基于Markov鏈的技術(shù)[57]等.近年也有用連續(xù)時(shí)間量子隨機(jī)游走解決組合優(yōu)化問(wèn)題的工作[58].
量子退火法于1989年由比勒費(fèi)爾德大學(xué)的Carvalho等3位學(xué)者提出[59],也稱(chēng)為量子隨機(jī)優(yōu)化.如遺傳算法、蟻群算法與模擬退火等仿生算法都是非常實(shí)用的啟發(fā)式優(yōu)化技術(shù),其中模擬退火法是出現(xiàn)得較早的經(jīng)典技術(shù),研究較深入.1)量子退火法中使用隧道場(chǎng)強(qiáng)度作為經(jīng)典模擬退火法的溫度參數(shù).由于量子隧穿效應(yīng)的存在,使得量子退火法更容易跳出局部最優(yōu)解,獲得全局最優(yōu)解,從而體現(xiàn)出超越經(jīng)典模擬退火的優(yōu)勢(shì).2)量子退火不需要運(yùn)用量子糾纏,因此易于實(shí)現(xiàn),D-Wave公司生產(chǎn)的專(zhuān)用量子計(jì)算機(jī)即可運(yùn)行量子退火算法.關(guān)于量子退火的早期工作可參閱文獻(xiàn)[60-61],關(guān)于D-Wave計(jì)算機(jī)與量子退火的綜合介紹可參閱文獻(xiàn)[62].
一般我們說(shuō)的量子近似優(yōu)化算法,都習(xí)慣特指本節(jié)所述的求解組合優(yōu)化問(wèn)題的量子近似優(yōu)化算法,關(guān)于該算法的入門(mén)介紹可參照文獻(xiàn)[63-64].
量子近似優(yōu)化算法(簡(jiǎn)稱(chēng)QAOA)于2014年由麻省理工學(xué)院的Farhi等3位學(xué)者提出[65],最初的設(shè)計(jì)是用于求解組合優(yōu)化問(wèn)題.該工作的量子電路深度依賴(lài)于一個(gè)與精度有關(guān)的參數(shù),最壞情況下電路深度隨著該參數(shù)與約束條件數(shù)量的乘積呈線(xiàn)性增長(zhǎng).該工作給出了使用QAOA解決p-正則圖最大割(Max-Cut)問(wèn)題的例子(p≤3),而傳統(tǒng)做法是把最大割問(wèn)題轉(zhuǎn)化為圓錐線(xiàn)性?xún)?yōu)化問(wèn)題(conic linear optimization problem)解決.相較于經(jīng)典算法,初期的QAOA并沒(méi)有顯示出明顯的優(yōu)勢(shì),直到2016年麻省理工學(xué)院的Harrow等2名學(xué)者指出QAOA是實(shí)現(xiàn)量子霸權(quán)(quantum supremacy)的方法之一[66],熱度才有所上升,近年也有理論分析的嘗試[67].另一方面,QAOA算法實(shí)現(xiàn)時(shí)對(duì)相干時(shí)長(zhǎng)要求低,或許是現(xiàn)有的小規(guī)模量子計(jì)算機(jī)理想的實(shí)驗(yàn)內(nèi)容之一,因此受到了量子計(jì)算實(shí)驗(yàn)研究者的關(guān)注,陸續(xù)有實(shí)驗(yàn)文章出現(xiàn)[68].另外,近年也出現(xiàn)了用QAOA算法解決連續(xù)優(yōu)化問(wèn)題的研究,見(jiàn)3.5節(jié).
本節(jié)將詳細(xì)介紹連續(xù)變量量子優(yōu)化技術(shù).連續(xù)變量量子優(yōu)化技術(shù)是近5年的研究熱點(diǎn),因此本節(jié)將詳細(xì)給出各工作所針對(duì)的具體問(wèn)題、算法復(fù)雜度,以及所采用技術(shù)的直觀描述.對(duì)于與經(jīng)典模型有關(guān)的量子算法,本文還會(huì)給出該經(jīng)典模型的框架介紹以便讀者理解.問(wèn)題和模型都將列在方框內(nèi).
在許多優(yōu)化方法中,特別是迭代方法的梯度下降法與牛頓法,都需要目標(biāo)函數(shù)的梯度信息,因此梯度估計(jì)是這類(lèi)方法的核心技術(shù)之一.量子梯度估計(jì)法于2005年由麻省理工學(xué)院的Jordan提出[69].
梯度估計(jì)問(wèn)題(查詢(xún)模型):
給定:函數(shù)f:Rd→R的查詢(xún)黑盒Of(查詢(xún)返回詢(xún)問(wèn)點(diǎn)的函數(shù)值),點(diǎn)x=(x1,x2,…,xd)∈d.
該工作研究的是查詢(xún)模型,在給定目標(biāo)函數(shù)黑盒的情況下,量子梯度估計(jì)算法只需要調(diào)用O(1)次查詢(xún)黑盒,即可近似計(jì)算出目標(biāo)函數(shù)在某點(diǎn)的梯度,與優(yōu)化變量的維度無(wú)關(guān).當(dāng)目標(biāo)函數(shù)估值較困難、優(yōu)化變量維度較大時(shí),量子梯度估計(jì)法有一定的優(yōu)勢(shì).美中不足的是,該算法無(wú)法通過(guò)遞歸求解目標(biāo)函數(shù)的高階導(dǎo)數(shù),求n階導(dǎo)數(shù)需要額外的2n次查詢(xún)來(lái)計(jì)算所需要的相位信息,因而失去了量子優(yōu)勢(shì).此工作主要使用了量子相位估計(jì)技術(shù).2019年,來(lái)自荷蘭國(guó)家數(shù)學(xué)與計(jì)算機(jī)中心與微軟研究院的研究人員合作改進(jìn)了量子梯度估計(jì)法[70],并指出原有的量子梯度估計(jì)法采取的黑盒輸入模型過(guò)強(qiáng),實(shí)際上難以達(dá)到所需精度,因此改而研究相位黑盒輸入模型與概率輸入模型,并給出了這2種輸入模型的轉(zhuǎn)化關(guān)系.在該輸入模型下,改進(jìn)算法估計(jì)平滑函數(shù)的梯度時(shí)在查詢(xún)復(fù)雜度上有二次(quadratic)加速,并且證明了量子優(yōu)化產(chǎn)生的大多數(shù)目標(biāo)函數(shù)會(huì)滿(mǎn)足必要的平滑條件.
迭代方法在無(wú)閉式解的優(yōu)化問(wèn)題中有非常廣泛的應(yīng)用,梯度下降法就是其中一種迭代方法.梯度下降法從初始的、未經(jīng)優(yōu)化的解開(kāi)始,每輪根據(jù)與目標(biāo)函數(shù)的梯度有關(guān)的更新規(guī)則迭代更新解.由于梯度方向是函數(shù)增長(zhǎng)速度最快的方向,梯度的反方向是函數(shù)下降速度最快的方向,因此參照梯度信息進(jìn)行迭代,能更快地獲得滿(mǎn)足要求的近似最優(yōu)解.
由于量子計(jì)算的特性,運(yùn)用迭代方法時(shí)一旦其中一步失敗,輸入就損毀了,一切就要重頭再來(lái),這使得若要達(dá)到迭代τ次的效果,往往需要遠(yuǎn)多于τ次實(shí)現(xiàn)迭代操作的量子演化.
梯度下降法:
猜測(cè)初始解θ0;
針對(duì)單位范數(shù)(unit norm)約束多項(xiàng)式優(yōu)化(polynomial optimization)的量子梯度下降法于2019年由MIT的Lloyd等學(xué)者提出[71].該方法對(duì)數(shù)據(jù)維度較大的情況有優(yōu)勢(shì),且把量子計(jì)算技術(shù)推進(jìn)到了非二次優(yōu)化甚至非凸優(yōu)化問(wèn)題上.
多項(xiàng)式優(yōu)化(帶單位范數(shù)約束)問(wèn)題:
給定:N2p個(gè)系數(shù)Ai1…i2p∈,其中p為正整數(shù).
二次優(yōu)化問(wèn)題:
給定:A∈n×n,b∈n,c∈.
帶權(quán)最小二乘問(wèn)題:
給定:樣例矩陣X、對(duì)應(yīng)的標(biāo)簽向量y以及權(quán)重向量w.
此工作運(yùn)用的技術(shù)為量子奇異值估計(jì)算法(包含了量子振幅放大、量子振幅估計(jì)以及量子相位估計(jì)算法).該工作在原有QRAM的算法設(shè)計(jì)模型上作了一些改進(jìn),使得量子奇異值估計(jì)算法的時(shí)間復(fù)雜度由原來(lái)的與待分解矩陣的F范數(shù)有關(guān),改進(jìn)為與最大行范數(shù)與F范數(shù)兩者之間的較小者有關(guān).由于有不少現(xiàn)實(shí)問(wèn)題待分解的矩陣的行范數(shù)都是有界的(boundedl1norm),這一改進(jìn)是有應(yīng)用價(jià)值的,而且該改進(jìn)也可以運(yùn)用在量子解線(xiàn)性方程上.
在線(xiàn)凸優(yōu)化是在線(xiàn)學(xué)習(xí)中的一個(gè)重要的框架,是凸優(yōu)化與博弈論的交叉領(lǐng)域,在決策問(wèn)題中有非常廣泛的應(yīng)用,如在線(xiàn)路由問(wèn)題、投資組合問(wèn)題以及推薦系統(tǒng)等,都可以用在線(xiàn)凸優(yōu)化的框架建模,并用相關(guān)技術(shù)解決.
在線(xiàn)凸優(yōu)化模型:
給定凸集K?n,凸函數(shù)族F:n→.
決策者依序進(jìn)行T*輪決策,在第t∈{1,2,…,T*}輪時(shí):
1)在凸集K中做出決策xt;
2)遭受損失ft(xt),其中ft∈F由對(duì)手選取或者由環(huán)境生成;
牛頓法是一種處理無(wú)約束優(yōu)化問(wèn)題的迭代方法,相比每次迭代沿著梯度方向移動(dòng)的梯度下降法,牛頓法把曲率也考慮在內(nèi),因此往往能加快收斂速度.梯度下降法與牛頓法之間是迭代復(fù)雜度與迭代次數(shù)之間的相互轉(zhuǎn)化,每次迭代考慮更多信息的牛頓法自然單次迭代計(jì)算復(fù)雜度會(huì)更高,但由于收斂更快,因此迭代次數(shù)相應(yīng)下降.2種方法不能簡(jiǎn)單說(shuō)孰優(yōu)孰劣,各有不同的適應(yīng)場(chǎng)景.
牛頓法:
猜測(cè)解θ0;
針對(duì)連續(xù)優(yōu)化問(wèn)題的量子近似優(yōu)化算法于2019年由滑鐵盧大學(xué)的Killoran等學(xué)者提出[74].該工作參考了離散版本QAOA的思路,并用量子粒子勢(shì)能動(dòng)力學(xué)(quantum dynamics of particles in energy potentials)的技術(shù)編碼目標(biāo)函數(shù).該算法適用于有約束與無(wú)約束優(yōu)化,稍加修改也可以解決離散優(yōu)化問(wèn)題.文章作者給出了使用此算法最小化非凸Styblinski-Tang函數(shù)的數(shù)值模擬實(shí)驗(yàn).
同樣地,該工作相對(duì)現(xiàn)存經(jīng)典技術(shù)的優(yōu)勢(shì)仍待進(jìn)一步論證,且此版本的實(shí)現(xiàn)難度要比離散版本高,超出了目前量子計(jì)算機(jī)可實(shí)驗(yàn)的范圍.
內(nèi)點(diǎn)法是處理有約束優(yōu)化問(wèn)題的迭代方法之一,常用于線(xiàn)性規(guī)劃與二次規(guī)劃,實(shí)際應(yīng)用面與著名的單純形法分庭抗禮,而且相較于非多項(xiàng)式算法的單純形法,內(nèi)點(diǎn)法是多項(xiàng)式算法,因此在大規(guī)模的線(xiàn)性規(guī)劃問(wèn)題中有更大的用武之地.
內(nèi)點(diǎn)法:
松弛變量,把待優(yōu)化問(wèn)題的不等式約束條件轉(zhuǎn)化為線(xiàn)性不等式約束;
目標(biāo)函數(shù)中引入不等式約束條件的屏障函數(shù)(barrier function),構(gòu)造中央路徑(central path)函數(shù);
用牛頓法沿著中央路徑尋找最優(yōu)解.
在內(nèi)點(diǎn)法中,計(jì)算牛頓線(xiàn)性系統(tǒng)矩陣(Newton linear system matrix)是非常花時(shí)間的,而該文提出了構(gòu)造牛頓線(xiàn)性系統(tǒng)矩陣塊編碼的量子技術(shù),加速了這一過(guò)程,主要運(yùn)用的是量子態(tài)層析技術(shù).該文作者同時(shí)證明了算法的收斂速度與經(jīng)典方法一致,因此量子內(nèi)點(diǎn)法所需的迭代次數(shù)與經(jīng)典算法一致.綜合每次迭代的加速而言,量子內(nèi)點(diǎn)法是一個(gè)理論突破.
2019年,文獻(xiàn)[75]的2名學(xué)者與Szilágyi合作先后發(fā)表3篇文章,分別把量子內(nèi)點(diǎn)法擴(kuò)展到解決二階錐規(guī)劃[76],以及應(yīng)用到投資組合問(wèn)題[77]與支持向量機(jī)[78]上.
二階錐規(guī)劃問(wèn)題:給定: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]. 投資組合問(wèn)題:投資者需要對(duì)m只投資產(chǎn)品的資金分配做T輪決策,每輪結(jié)算后根據(jù)之前的投資決策進(jìn)行下一輪的分配計(jì)劃,最終目的是使得總收益最大化.
半正定規(guī)劃是凸優(yōu)化問(wèn)題的一個(gè)分支,針對(duì)的是目標(biāo)函數(shù)為線(xiàn)性函數(shù)、優(yōu)化變量約束在光譜面上(半正定矩陣構(gòu)成的錐體與仿射空間的交集)的優(yōu)化問(wèn)題,存在多項(xiàng)式時(shí)間的經(jīng)典算法.由于半正定規(guī)劃在現(xiàn)實(shí)中應(yīng)用面廣,輸入規(guī)模大,因此多項(xiàng)式時(shí)間仍然不能滿(mǎn)足發(fā)展需要.2017—2019年,量子半正定規(guī)劃法經(jīng)過(guò)了多次迭代,并得到了快速發(fā)展.
半正定規(guī)劃問(wèn)題(原始形式):給定:A1,A2,…,Am,C∈RRn×n,b1,b2,…,bm∈RR.求:max{tr(CX)|?j∈[m],tr(AjX)≤bj,X≥0}. 半正定規(guī)劃問(wèn)題(對(duì)偶形式):給定: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)于矩陣維度的平方級(jí)加速,且當(dāng)矩陣越稀疏,優(yōu)勢(shì)越明顯.量子吉布斯采樣(quantum Gibbs sampling)與乘權(quán)法(the multiplicative weight method)是實(shí)現(xiàn)該算法的關(guān)鍵技術(shù).
文獻(xiàn)[79]的作者還與馬里蘭大學(xué)的研究人員合作,針對(duì)設(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é)者提出了對(duì)文獻(xiàn)[79]的改進(jìn)[81],降低了精度對(duì)算法上界的影響,并給出了所有線(xiàn)性規(guī)劃算法的量子查詢(xún)下界(因此包括了所有的半正定規(guī)劃算法),該工作還把他們的改進(jìn)版本應(yīng)用在了實(shí)現(xiàn)給定哈密頓量平滑函數(shù)與函數(shù)廣義最小值查找算法上.
2018年,van Apeldoorn等2名學(xué)者綜合以上的幾項(xiàng)工作的優(yōu)點(diǎn)以及Gentle Quantum Search引理,提出了量子半正定規(guī)劃的改進(jìn)版本[82].該工作給出了更優(yōu)的上下界,分別論證了在量子態(tài)輸入、稀疏矩陣輸入以及量子算子輸入這3種不同輸入模型下的算法效率,并應(yīng)用到陰影層析問(wèn)題、量子態(tài)區(qū)分問(wèn)題以及E-最優(yōu)設(shè)計(jì)上.
這4項(xiàng)工作的復(fù)雜度上下界詳見(jiàn)表1.
Table 1 Main Results of Quantum Semi-Definite Programming表1 主要量子半正定規(guī)劃結(jié)果
需要注意的是,精度等參數(shù)對(duì)于量子半正定規(guī)劃計(jì)算復(fù)雜度的影響仍然較大,因此要在實(shí)際問(wèn)題上超越經(jīng)典算法依然需要進(jìn)一步的研究.
線(xiàn)性規(guī)劃是半正定規(guī)劃的一個(gè)特殊形式,從實(shí)用的角度比更一般的半正定規(guī)劃應(yīng)用更為廣泛.除了3.6節(jié)提到的可用于解線(xiàn)性規(guī)劃問(wèn)題的內(nèi)點(diǎn)法外,還有2項(xiàng)針對(duì)線(xiàn)性規(guī)劃問(wèn)題的量子工作.
線(xiàn)性規(guī)劃問(wèn)題(原始形式):給定:A∈RRn×m,b∈RRn,c∈RRm.求:minx∈RRm{cTx|Ax≥b,x≥0}. 線(xiàn)性規(guī)劃問(wèn)題(對(duì)偶形式):給定:A∈RRn×m,b∈RRn,c∈RRm.求:maxy∈RRn{bTy|ATy≤c,y≥0}.
針對(duì)一般的無(wú)約束凸優(yōu)化問(wèn)題,馬里蘭大學(xué)的Childs團(tuán)隊(duì)[85]與荷蘭國(guó)家數(shù)學(xué)與計(jì)算機(jī)中心de Wolf團(tuán)隊(duì)[86]于2020年分別獨(dú)立地提出了相應(yīng)的量子算法.
一般凸優(yōu)化問(wèn)題(查詢(xún)模型):
給定:凸集K?n的成員黑盒OK(查詢(xún)返回詢(xún)問(wèn)點(diǎn)是否在集合內(nèi)),凸函數(shù)f:K→的估值黑盒Of(查詢(xún)返回詢(xún)問(wèn)點(diǎn)的函數(shù)值).
文獻(xiàn)[85-86]的2項(xiàng)工作結(jié)論一致,研究的均為黑盒查詢(xún)模型,思路大致類(lèi)似.在給定成員黑盒(用于查詢(xún)優(yōu)化變量給定取值是否在可行域中)與估值黑盒(用于計(jì)算目標(biāo)函數(shù)在給定點(diǎn)的值)情況下,2項(xiàng)工作的結(jié)果由表2說(shuō)明.我們可以從表中看到,在時(shí)間復(fù)雜度相同的情況下,量子算法的查詢(xún)上界達(dá)到了經(jīng)典算法的下界,這意味著該量子算法在理論上達(dá)到了經(jīng)典算法潛在的最好情況.另外,量子算法上下界仍然未緊,這意味著量子算法仍然有提升空間.由于2項(xiàng)工作結(jié)論一致,以下主要介紹文獻(xiàn)[85]的技術(shù).
Table 2 Comparison of Quantum and Classical General Convex Optimization Algorithms表2 量子與經(jīng)典一般凸優(yōu)化算法的對(duì)比
針對(duì)一般凸優(yōu)化問(wèn)題的量子算法使用的主要是量子梯度估計(jì)技術(shù),從估值黑盒出發(fā)通過(guò)量子梯度估計(jì)求得分離超平面,經(jīng)由分離超平面再得出最小化線(xiàn)性函數(shù)的方法,最后得出一般凸優(yōu)化問(wèn)題的算法,這過(guò)程中綜合運(yùn)用工程中常見(jiàn)的誤差縮小技術(shù)與函數(shù)緩和技術(shù)處理邊界不光滑等會(huì)影響算法性能與誤差的問(wèn)題.
優(yōu)化問(wèn)題在生產(chǎn)生活中無(wú)處不在,經(jīng)典計(jì)算領(lǐng)域把優(yōu)化作為一個(gè)正式的學(xué)科分支進(jìn)行研究已經(jīng)有一百多年的歷史,而最優(yōu)化方法的起源甚至可以追溯到三四百年前費(fèi)馬、拉格朗日、牛頓以及高斯的微積分時(shí)代.隨后經(jīng)歷了高度依賴(lài)一階、高階導(dǎo)數(shù)的分析算法階段、用準(zhǔn)確度交換速度的啟發(fā)式算法階段,以及高度依賴(lài)數(shù)據(jù)的代理模型階段.如今在工程實(shí)踐中,各類(lèi)方法高度融合,產(chǎn)生著巨大的經(jīng)濟(jì)社會(huì)效益.
但縱使已經(jīng)研究了數(shù)百年,在優(yōu)化領(lǐng)域還一直有許多難題尚未得到有效的解決,有如大部分的非凸優(yōu)化問(wèn)題、組合優(yōu)化里的NP問(wèn)題,以及許多規(guī)模極大的P問(wèn)題,都還處于探索階段.而量子計(jì)算的興起為這些難題帶來(lái)了新的希望和探索方向.量子算法已經(jīng)在不少問(wèn)題上相對(duì)于經(jīng)典算法帶來(lái)了加速優(yōu)勢(shì),但由于中等規(guī)模量子計(jì)算機(jī)目前依然昂貴,大型的通用量子計(jì)算機(jī)難見(jiàn)蹤跡,因此量子優(yōu)化算法的設(shè)計(jì)目前依然處于理論分析難、實(shí)驗(yàn)成本高的階段,學(xué)術(shù)界與工業(yè)界都迫切盼望量子計(jì)算能在基礎(chǔ)理論與軟硬件技術(shù)上有進(jìn)一步的突破.
本文通過(guò)對(duì)量子優(yōu)化算法研究方面的梳理觀察得出4方面:
1)從時(shí)間上看,連續(xù)變量的量子優(yōu)化算法是近年的趨勢(shì),也將會(huì)是未來(lái)短期內(nèi)的研究熱點(diǎn).這并非說(shuō)組合優(yōu)化不重要,而是組合優(yōu)化問(wèn)題有很大一部分是NP問(wèn)題,要找到高效的量子算法具有挑戰(zhàn)性.已有的針對(duì)組合優(yōu)化問(wèn)題的量子算法要么是采用Grover算法,在某個(gè)子過(guò)程達(dá)到根號(hào)級(jí)別加速,要么就是采用無(wú)法在理論上分析復(fù)雜度的啟發(fā)式算法,而目前的量子計(jì)算機(jī)規(guī)模還不足以驗(yàn)證啟發(fā)式量子算法的應(yīng)用價(jià)值.連續(xù)變量?jī)?yōu)化問(wèn)題似乎更有希望獲得更多的量子加速,而且其應(yīng)用面也因人工智能的發(fā)展而日益廣泛.
2)量子優(yōu)化使用的基本量子技術(shù)的核心思想大多都是1995—2008年提出的,HHL算法以及Jordan量子梯度估計(jì)法均為1995年相位估計(jì)算法框架的延展,幅值放大技術(shù)為1996年Grover算法的延展,而哈密頓量模擬算法以及量子隨機(jī)存儲(chǔ)技術(shù)也已有10~20年的歷史.若需要尋找新的方向,還需要在最為底層的算法上有突破.
3)除啟發(fā)式算法外,主要的量子優(yōu)化算法相對(duì)于經(jīng)典算法都在理論上體現(xiàn)了一定的加速,既有體現(xiàn)在時(shí)間復(fù)雜度的加速,也有體現(xiàn)在查詢(xún)復(fù)雜度上的加速.一般來(lái)說(shuō),問(wèn)題的計(jì)算復(fù)雜度下界往往很難證明,但查詢(xún)復(fù)雜度的下界證明有如對(duì)手法[89]等較成體系的方法.縱觀現(xiàn)有工作,在一般凸優(yōu)化問(wèn)題的查詢(xún)模型上[85-86]尋找量子優(yōu)勢(shì)是很有希望的,因?yàn)槠淞孔由辖缫呀?jīng)達(dá)到經(jīng)典下界,且量子上下界還未緊,還有改進(jìn)空間.
4)目前獲得量子加速的優(yōu)化問(wèn)題十分有限,優(yōu)化領(lǐng)域依然存在許多值得量子計(jì)算科學(xué)家探索的問(wèn)題,如優(yōu)化領(lǐng)域的難題:非凸優(yōu)化.對(duì)凸優(yōu)化研究的深入是經(jīng)典優(yōu)化領(lǐng)域的一個(gè)分水嶺[90],因?yàn)橥购瘮?shù)具有極小值即最小值等良好特性,使得凸優(yōu)化問(wèn)題大多都有可行、高效的算法,因此凸優(yōu)化問(wèn)題與能轉(zhuǎn)化成凸優(yōu)化問(wèn)題的優(yōu)化問(wèn)題被認(rèn)為是較易解決的.相對(duì)地,解決非凸優(yōu)化則比較困難.現(xiàn)在的量子優(yōu)化算法中,針對(duì)的線(xiàn)性規(guī)劃、二次規(guī)劃、半正定規(guī)劃問(wèn)題都是常見(jiàn)的特殊凸優(yōu)化問(wèn)題,都屬于經(jīng)典優(yōu)化領(lǐng)域認(rèn)為較易解決的部分,針對(duì)非凸優(yōu)化的量子算法還很少.再者還有更多貼近實(shí)際應(yīng)用的優(yōu)化問(wèn)題,如引入更多約束條件的約束優(yōu)化、目標(biāo)函數(shù)不單一的多目標(biāo)規(guī)劃、帶有不確定性的不確定規(guī)劃、問(wèn)題隨時(shí)間而變的動(dòng)態(tài)規(guī)劃、部分變量要求為整數(shù)的混合整數(shù)規(guī)劃等.經(jīng)典優(yōu)化對(duì)于這些優(yōu)化問(wèn)題均有系統(tǒng)的研究,而量子計(jì)算目前依然缺席,均可進(jìn)行探索.