林鍵 葉夢 朱家緯 李曉鵬

(復旦大學物理學系, 上海 200433)

量子計算在近十年取得了長足的進展. 隨著量子調(diào)控技術(shù)達到前所未有的高度, 包括超導量子比特、光量子器件、原子系綜等在內(nèi)的量子實驗平臺都進入到了嶄新的時代. 目前在特定計算任務上超越經(jīng)典的量子計算優(yōu)勢也已經(jīng)被報道. 其中一種可以有效運用可控量子器件的計算方案是采用絕熱量子計算. 絕熱量子計算中算法的選擇與研究至關(guān)重要, 其將直接決定量子計算優(yōu)勢是否能夠最大限度地被挖掘. 本綜述主要介紹近期機器學習在絕熱量子算法設計方面的應用, 并講述該計算架構(gòu)在3-SAT和Grover搜索等問題上的應用.通過與未經(jīng)機器學習優(yōu)化設計的絕熱量子算法對比, 研究表明機器學習方法的應用可以極大提高絕熱量子算法的計算效率.

1 引 言

量子計算概念最早可以追溯到20世紀80年代, 當時Benioff[1]提出了量子圖靈機概念, Feynman[2]有了量子模擬的想法. 而后Deutsch[3]提出量子線路模型來實現(xiàn)普適量子計算, Yao[4]證明了量子線路模型與量子圖靈機的等價性—兩者可以在多項式時間內(nèi)互相模擬. 在量子算法方面,1994年Shor[5]基于量子線路模型提出了可在多項式時間內(nèi)求解質(zhì)因數(shù)分解問題的量子算法. 由于質(zhì)因數(shù)分解問題的困難性是Rivest-Shamir-Adleman (RSA) 公鑰加密體系安全性的保障, 這一由Shor提出的多項式量子算法引起了密碼學和相關(guān)實驗領(lǐng)域的高度關(guān)注[6—12]. 量子計算有了從理論研究走向?qū)嶋H應用的趨勢, 量子計算機的研發(fā)開始引起多方投入[13]. 同時, 人們也從量子信息理論和量子計算復雜度的角度展開研究, 期待設計出更多具有顯著量子計算優(yōu)勢的量子算法[14—17].

目前已知的具有超越經(jīng)典計算優(yōu)勢的量子算法主要可以歸為三大類[16]. 第一類是利用量子傅里葉變換尋找周期的量子算法, 包括Shor算法[5]、Simon算法[18]、以及Hallgren算法[19]等. 第二類是以有量子加速的Grover搜索算法[20]為基礎(chǔ)的搜索及優(yōu)化算法—可以在時間內(nèi)完成對N個項目的搜索. 第三類是在量子計算機上對復雜的量子多體體系進行高效模擬. 這是基于Feynman“利用量子計算機來進行量子模擬”的想法[2].量子系統(tǒng)的希爾伯特空間會隨量子自由度(比如原子數(shù)等)的數(shù)目指數(shù)增長, 所以如果用經(jīng)典計算機來模擬量子多體系統(tǒng)需要大量的內(nèi)存資源和計算資源. 而量子計算機可以直接用量子比特進行計算, 具有對復雜量子多體系統(tǒng)模擬的天然優(yōu)勢.這一方面對量子化學計算、材料科學的復雜微觀物理機制(如高溫超導)的揭示等具有重要科學價值.

量子算法與經(jīng)典算法的很大一點不同是量子力學允許的量子操作、量子疊加和量子糾纏很難直接與直觀經(jīng)驗建立聯(lián)系, 甚至是反直覺的. 這極大地增加了量子算法設計的難度, 同時使得人們在經(jīng)典計算算法設計上積累的經(jīng)驗很難被直接借用[16].

在開發(fā)設計量子算法時, 我們期待設計出能夠相比于經(jīng)典計算更高效的量子算法. 對于可以在量子計算機上以多項式時間解決的問題, 人們把它們歸為BQP (bounded-error quantum polynomial time)復雜類. 目前人們還沒有一個普適的理論來確定這類問題的邊界, 在后文中我們將對此做更具體的介紹. 雖然通常人們不認為量子計算能夠指數(shù)加速NP-complete問題, 但在具體算法設計中, 任何能夠提升量子計算能力的設計方法和技巧都值得嘗試[21]. 在量子計算的發(fā)展進程中, 我們也可以適當借鑒經(jīng)典計算領(lǐng)域的發(fā)展. 設計出具有量子優(yōu)勢的量子算法還有待于量子研究領(lǐng)域與經(jīng)典計算研究領(lǐng)域的深度交融.

Farhi等[22,23]在2001年提出了與量子線路模型相應的絕熱量子計算模型—AQC(adiabatic quantum computation). 在絕熱量子計算中, 我們首先會構(gòu)造一個非平庸的問題哈密頓量, 其基態(tài)編碼了我們關(guān)心問題的答案. 然后我們讓系統(tǒng)從一個與問題哈密頓量非對易的平庸哈密頓量基態(tài)開始做演化, 一直演化到這個編碼的問題哈密頓量. 如果整個演化過程是完全絕熱的并且基態(tài)與激發(fā)態(tài)之間始終存在能級差[24], 我們最后也就能獲得問題哈密頓量的基態(tài), 即這個計算問題的正確解. 這也就將一個計算問題變成了一個哈密頓量求基態(tài)的問題. 絕熱量子計算模型可以看作連續(xù)時間的量子計算, 其與離散時間的量子線路模型的等價性也在理論上得到了證明[25,26]. “演化體系哈密頓量”這一想法與量子模擬非常接近. 而人們在量子模擬及量子控制方面也具備了很多理論知識和實驗經(jīng)驗[27—30]. 所以絕熱量子計算概念的提出不但給我們提供了一種全新的普適量子計算框架,而且有利于將我們對量子模擬的物理直覺與量子算法設計結(jié)合起來以打開新思路. 后文將詳細介紹絕熱量子計算的算法設計.

經(jīng)典計算領(lǐng)域的算法設計復雜程度也在愈趨加大, 如何實現(xiàn)經(jīng)典算法的自動化設計也變得越來越重要. 對于一個問題, 如果存在多種可以解決的算法, 那么如何高效地挑選一個最優(yōu)的算法就非常關(guān)鍵. 這就涉及算法選擇問題(algorithm selection)[31]; 而對于一個算法, 在不同的問題例子中如何去優(yōu)化算法構(gòu)型(algorithm configuration)[32]也相當重要. 我們將在后文中詳細介紹機器學習在經(jīng)典算法設計領(lǐng)域的應用. 另一方面, 近些年機器學習也在處理量子多體問題上, 特別是在物態(tài)的相分類[33—37]、多體波函數(shù)的表示及基態(tài)制備[38—41]、優(yōu)化量子操控[42—45]等方向上有了一系列的應用.

雖然經(jīng)典與量子算法的設計領(lǐng)域差別很大, 但兩者的復雜性使得它們都面臨著巨大挑戰(zhàn). 通過借鑒機器學習在經(jīng)典算法設計與量子多體物理中的成功應用, 我們也希望機器學習方法能輔助量子算法設計. 這不僅會幫助我們設計出具有量子優(yōu)越性的算法, 同時設計獲得的量子算法也有望實現(xiàn)機器學習的量子加速[46]. 我們期待這兩個領(lǐng)域的交融會碰撞出靈感的火花.

2 絕熱量子計算與哈密頓量編碼

本節(jié)將對絕熱量子計算的概念以及絕熱量子計算中問題哈密頓量的編碼方案與自旋玻璃物理的聯(lián)系進行介紹. 而后, 給出三個具體計算問題的哈密頓量構(gòu)造方案. 最后討論運用絕熱量子計算模型探索BQP復雜類的研究途徑.

2.1 絕熱量子計算

絕熱量子計算作為一種普適的量子計算框架[22,23,25,26,47], 其原理是將一個計算問題變成量子體系求基態(tài)的問題. 設想有兩個非對易的哈密頓量Hb和Hp, 其中初始哈密頓量Hb的基態(tài)非常容易制備, 而問題哈密頓量Hp的基態(tài)則編碼了我們所關(guān)心問題的解. 讓量子系統(tǒng)從初始哈密頓量Hb的基態(tài)開始演化, 直到系統(tǒng)到達問題哈密頓量Hp. 一般可以用以下含時哈密頓量來刻畫該過程:

其中s(t/T) 為哈密頓量的演化路徑(從 0 變化到 1 ),T為總的演化時間. 如果演化時間T足夠長并且系統(tǒng)的基態(tài)與激發(fā)態(tài)之間始終存在能級差[24], 那么由絕熱定理可以保證, 這個量子系統(tǒng)將時刻處于瞬時哈密頓量的基態(tài). 量化絕熱條件是絕熱定理成立的必要條件[48]. 由此, 可以估計出絕熱演化時間[22,49,47], 其中Δmin為基態(tài)與第一激發(fā)態(tài)之間的最小能隙. 通過測量演化T時間后的系統(tǒng)狀態(tài), 將得到問題哈密頓量的基態(tài), 即問題的解.

絕熱量子計算在被提出之時就將目標指向解決NP-complete和NP-hard問題[22,23]. 而后, 對其是否能夠超越經(jīng)典計算的質(zhì)疑也接踵而來—因為對于這類NP-complete和NP-hard問題, 其最小能隙呈指數(shù)減小, 所以絕熱量子計算需要的時間是指數(shù)增長的. 其并不能做到相比于經(jīng)典算法的指數(shù)加速, 但可能在系數(shù)因子上會比經(jīng)典的算法更優(yōu)[50—55].

2.2 哈密頓量編碼

本節(jié)將介紹絕熱量子計算哈密頓量編碼與自旋玻璃問題的關(guān)聯(lián). 也將介紹三個典型計算問題的哈密頓量構(gòu)造方法.

2.2.1 哈密頓量編碼與自旋玻璃問題

在理論和實驗中, 總可以將絕熱量子計算的哈密頓量編碼為伊辛自旋模型的量子形式[56,57]. 一個經(jīng)典的伊辛自旋模型可以寫作:

在絕熱量子計算中, 通過將自旋si寫成泡利算符形式來得到問題哈密頓量Hp:

其中為作用在第i個自旋上的泡利X算符.

這樣的問題哈密頓量構(gòu)造與物理中的自旋玻璃模型可以一一對應. 自旋玻璃問題是一個在凝聚態(tài)物理和統(tǒng)計及計算物理領(lǐng)域中悠久且豐富的物理問題[58—60]. 自旋玻璃問題和NP(nondeterministic polynomial) 問題的聯(lián)系也備受關(guān)注. 這種關(guān)聯(lián)給了我們從物理角度來理解計算中的困難的機會[61—63]. Karp[64]在1972年研究發(fā)現(xiàn)21個組合及圖論計算問題都可以在多項式時間歸約到一個NP-complete問題上, 也就證明了它們都是NP-complete問題. Lucas[65]研究了這些典型NPcomplete問題如何編碼為自旋玻璃形式的問題哈密頓量. 一般人們也會把這類編碼后的問題叫作QUBO (quadratic unconstrained binary optimization) 問題.

2.2.2 基于絕熱量子計算的Grover搜索算法

基于線路模型的Grover搜索算法被證明具有超越經(jīng)典搜索算法的平方加速[20]. 這個搜索問題是指在N=2n個項目中尋找到標記的項. 對于一個函數(shù)只有被標記的項f(m)=1, 對于任意的我們的目標是用最少的詢問神諭(oracle)次數(shù)來找到這個標記的項目m. 對應到絕熱量子計算, 可以將初始哈密頓量 寫 成Hb=1-|ψ0〉〈ψ0|, 以 及 問 題 哈 密 頓 量Hp=1-|m〉〈m| , 其中為某一個被標記的態(tài). 在這樣的哈密頓量構(gòu)造下,如果將演化路徑簡單地選擇為s=t/T, 其中的最小能隙出現(xiàn)在s=1/2 :

由絕熱定理條件可知,(2n))[47], 這與經(jīng)典搜索算法的復雜度一致. 所以在絕熱量子計算中簡單地選擇線性哈密頓量演化路徑不會使得Grover搜索問題具有量子加速. 而在如此編碼下,研究表明: 可以解析地優(yōu)化哈密頓量演化路徑以使得上述Grover搜索問題在絕熱量子計算中依舊具有平方的量子加速[66].

2.2.3 基于絕熱量子計算的3-SAT算法

布爾可滿足性問題(Boolean satisfiability problem)中含有n個布爾變量zi, 由其組成了一系列子句 (clause)Cα, 其中每一個子句Cα內(nèi)都含有k個變量并以“或”(∨)連接, 如:Cα=(b1∨b2∨···∨bk) , 其 中bi∈{z1,z2,···,zn,?z1,?z2,···?zn}. 最終我們希望找到一串布爾變量zi,使得所有用“與”(∧)連接的子句都得到滿足, 即:

如果每個子句中有相同變量個數(shù)k=2 , 這類問題稱作2-SAT. 這類問題可以在經(jīng)典計算中有效地被解決, 歸屬于復雜類P. 而對于k≥3 的情況, 這類問題都是NP-complete問題, 它們可以在多項式時間內(nèi)互相轉(zhuǎn)化. Farhi等[22]提出絕熱量子計算時就嘗試對3-SAT問題進行測試. 為了構(gòu)造3-SAT問題哈密頓量, 我們舉例一個涉及三個布爾變量ziC,zjC,zkC的子句C, 并且對此定義一個經(jīng)典的能量函數(shù):

于是, 這就將3-SAT問題的解編碼到了Hp的基態(tài)上.

2.2.4 基于絕熱量子計算的質(zhì)因數(shù)分解算法

質(zhì)因數(shù)分解問題是希望將一個大數(shù)N分解為兩個質(zhì)因數(shù)p和q, 也就是實現(xiàn)N→p×q的分解.RSA公鑰加密體系的安全性正是基于當前經(jīng)典算法無法在多項式時間內(nèi)求解質(zhì)因數(shù)分解問題. 在經(jīng)典計算領(lǐng)域, 大家嘗試了求解該問題的不同方法,如基于啟發(fā)式算法的設計[67], 機器學習方法[68,69],以及仿生算法[70,71]和隨機架構(gòu)算法[72]等. 而在量子計算領(lǐng)域, Shor算法可在多項式時間內(nèi)解決質(zhì)因數(shù)分解問題[5]. 但Shor算法對量子比特數(shù)量和門的保真度要求很高, 在目前的實驗條件下[73], 還只能在比較小的數(shù)字上做分解[9,74]. 另一方面, 近些年大家對在絕熱量子計算中實現(xiàn)質(zhì)因數(shù)分解也做了大量工作[75,76,47,77,78,55]. 在絕熱量子計算質(zhì)因數(shù)分解問題中, 構(gòu)造問題哈密頓量一般有兩種主要方式. 一種是直接將問題寫成損失函數(shù)fcost=(N-p×q)2[79], 為了避免其中耦合強度出現(xiàn)指數(shù)增長, 人們提出了另一種基于乘法表的損失函數(shù)構(gòu)造方法[77]. 其中, 通過將二進制數(shù)映射為泡利算符,繼而引入額外的量子比特將高階耦合項降到二階,人們可以將這一問題約化到前文提到的QUBO問題, 并得到相應的問題哈密頓量.

2.3 絕熱量子計算與BQP復雜類

自從Shor[5]提出質(zhì)因數(shù)分解的多項式算法以來, 量子計算領(lǐng)域獲得了更廣泛的關(guān)注, 也涌現(xiàn)出許多不同新的研究方向. 然而不同于量子計算復雜度理論、量子密碼學以及量子糾錯等領(lǐng)域的快速發(fā)展, 量子算法設計作為量子計算研究的核心問題之一, 特別是設計出相比經(jīng)典算法具有指數(shù)加速的量子算法, 并沒有如人們想象中那樣順利推進. 對于這一現(xiàn)象, Shor[16]指出, 一個可能的原因, 是由于人們沒有像設計經(jīng)典算法一樣好的直覺設計量子算法. 而找到能充分展現(xiàn)量子計算機超越經(jīng)典計算機能力的BQP問題具有十分重要的現(xiàn)實意義.

在計算復雜度理論中, BQP問題是指在量子計算機上存在多項式規(guī)模的量子線路并且出錯概率小于1/2求解的一類判定問題(decision problem)[80], 簡言之, 就是能在量子計算機上在多項式時間內(nèi)求解的問題. 與其類似的經(jīng)典計算問題是BPP(bounded-error probabilistic polynomial time)問題, 它被定義為能在多項式時間內(nèi)被概率圖靈機以有界的錯誤率求解的判定問題. 雖然在具體問題中, 如質(zhì)因數(shù)分解[5]、二次符號權(quán)重計數(shù)問題 (quadratically signed weight enumerator problem)[81]、瓊斯多項式估計(approximation of Jones polynomials)[82,83], local Hamiltonian本征值采樣問題(LHES)、相位估計采樣問題(PES)、酉矩陣平均本征值估計(LUAE)[84]等問題上量子計算可以做到指數(shù)加速, 但BQP計算復雜類的邊界仍然是未解決的理論問題. 在量子計算機上可以高效解決的問題仍有待進一步探索.

前文提到, 由于人們?nèi)鄙倭孔邮澜缬^以及量子線路模型難以提供好的算法設計直覺, 那么絕熱量子算法會是尋找BQP問題的一條途徑. 量子線路模型被證明能以多項式量級的步驟轉(zhuǎn)換為一個絕熱量子算法[25]. 因此利用量子線路模型定義的BQP問題, 也可以等價地在絕熱計算機上定義. 若對于要求解的問題有已知的量子線路算法, 那么可以根據(jù)已知的線路模型中的一系列門操作構(gòu)造出初始哈密頓量和問題哈密頓量, 使得問題哈密頓量的基態(tài)為歷史態(tài)其中|α(l)〉 表示原來的線路模型中每個時刻對應的邏輯態(tài),|1l0L-l〉 是標記演化時刻的時間態(tài). 于是原本線路模型中的求解過程轉(zhuǎn)換成為尋找問題哈密頓量的基態(tài). 這個轉(zhuǎn)換過程花費的步驟呈多項式增長. 在線路模型中, 質(zhì)因數(shù)分解問題[5]就是一個典型的BQP問題. 通過絕熱量子算法判定的BQP問題也有典型的例子, 如膠合樹問題[85]. 如果機器學習方法可以輔助設計絕熱算法, 就有望通過這種方式找到更多的BQP問題, 進而探索BQP復雜類的邊界.

3 機器學習與量子經(jīng)典組合算法

本節(jié)將首先對機器學習的幾個方向及其在經(jīng)典算法設計中的應用做簡要介紹. 而后介紹量子與經(jīng)典組合算法以及機器學習在量子控制中的應用.

3.1 機器學習分類

1956年的達特茅斯會議中, “用機器來模仿人類學習以及其他方面的智能”的觀點被首次提出[86]. 機器學習往往面對的是大量的數(shù)據(jù), 通過學習來擬合出其中的復雜關(guān)系. 我們期待機器能自行學會數(shù)據(jù)中的關(guān)聯(lián), 并能給出符合人類邏輯認知甚至超越人類能力的預判. 近些年來, 機器學習在圖像識別[87]、自然語言處理[88]以及策略游戲[89]等方面表現(xiàn)出令人稱嘆的能力, 其中非常值得一提的就是誤差逆?zhèn)鞑ニ惴?error back propagation)[90]在多層神經(jīng)網(wǎng)絡中的應用. 一個多層神經(jīng)網(wǎng)絡可被分為輸入層、隱藏層和輸出層, 其中每一個隱藏層和輸出層的神經(jīng)元中都含有激活函數(shù)(可被激活或抑制來模仿生物的神經(jīng)元機能). 在訓練時我們將信號逐層向前傳遞直到輸出層, 而后將誤差逆?zhèn)鬟f來更新權(quán)重. 我們期待訓練好的網(wǎng)絡會有很強的表示能力與泛化能力. 也即是, 對于一個完全陌生的輸入數(shù)據(jù), 網(wǎng)絡也能給出符合預期甚至超越人類認知的判斷. 機器學習的方法主要有三大類[91]: 監(jiān)督學習、無監(jiān)督學習和強化學習. 監(jiān)督學習中具有代表性的是處理“分類”和“回歸”問題. 需要給機器大量的帶標簽數(shù)據(jù). 機器通過學習數(shù)據(jù)特征和標簽的關(guān)聯(lián), 獲得對新數(shù)據(jù)進行預測的能力. 如果預測的結(jié)果是離散的, 就屬于“分類”; 如果預測的結(jié)果是連續(xù)的, 就屬于“回歸”. 對于無監(jiān)督學習, 給機器的是不帶標簽的數(shù)據(jù), 也就是希望機器能夠自己發(fā)現(xiàn)數(shù)據(jù)之間的共同特征, 將相關(guān)的部分歸為一類進行“聚類”. 強化學習[89]則是讓智能體與環(huán)境進行有探索地交互來訓練獲得最大獎勵. 智能體在某一個狀態(tài)st下根據(jù)策略做出動作a, 并且獲得環(huán)境的獎勵r, 到達下一個狀態(tài)st+1. 其中的會用到Q值來表示在某個狀態(tài)下做不同動作的未來獎勵的估計.對于像圍棋這樣的游戲, 狀態(tài)空間會隨著格點個數(shù)指數(shù)增長. 考慮到要存下這么多狀態(tài)空間需要大量內(nèi)存, 在近期的強化學習中都采用了神經(jīng)網(wǎng)絡的強大表示能力來表示Q值. 在人類專家知識輸入不斷減少的情況下, 強化學習智能體在策略游戲中依舊表現(xiàn)得非常出色[92—95].

3.2 機器學習在經(jīng)典算法設計中的應用

隨著經(jīng)典算法設計變得越來越復雜, 機器學習也被用在設計經(jīng)典算法上. 1976年Rice[31]就提出了“算法選擇問題”, 他將“算法選擇問題”與“沒有免費午餐定理”[96]相提并論—對于任何算法,想要其表現(xiàn)好于其他算法就必須付出代價. 換句話說, 即沒有一個普適的最好算法來解決一大類問題. 在面對擁有多種求解算法的一類問題(特別是NP-hard問題)中, 不同問題實例的求解效果不盡相同. 如何挑選出其中最好的算法就顯得非常關(guān)鍵[97]. 下面通過回顧在經(jīng)典領(lǐng)域的自動化算法設計, 期待能對量子算法的設計有一些啟發(fā).

在早期工作中, 人們通過將算法選擇問題映射為馬爾科夫決策過程, 利用強化學習選擇算法來使得算法運行時間最短[98]以及并行不同算法加速求解組合搜索問題[99]. 為了預測不同算法在具體問題求解中的所需時間, 需要根據(jù)人類專家知識預先選擇出可能影響問題計算時間的特征, 將一系列問題的特征和和真實算法所需運行時間作為數(shù)據(jù)集,通過學習利用回歸方式預測每個算法在具有某些特征的問題上求解所需時間[100,101]. 值得一提的是,連續(xù)多年蟬聯(lián)SAT比賽冠軍的SATzilla[102]在處理3-SAT問題時會利用預設的求解算法在短時間內(nèi)求解那些簡單的問題實例. 而對于那些沒有在短時間內(nèi)被求解的問題實例, 其將根據(jù)問題特征來挑選出預測的最好算法進行求解. 曾經(jīng)用于分類的元學習(meta-learning)也被運用到算法選擇中[103],不同的機器學習方法在算法選擇問題上的表現(xiàn)也得到了評估和對比[104]. 機器學習在推薦系統(tǒng)(特別是在購物網(wǎng)站)中的成功應用也推動了自動化算法推薦系統(tǒng)的出現(xiàn)[105].

與算法選擇問題相應的, 算法本身就具有許多可被調(diào)整的參數(shù). 手動對大量的參數(shù)進行“調(diào)參”不僅費時也非常依賴于專業(yè)知識. 算法構(gòu)型的設計[32]就是在高維參數(shù)空間中選擇出最佳的算法構(gòu)型參數(shù). 目前已開發(fā)的一系列算法構(gòu)型設計工具包[106—109]都可以給出優(yōu)化的固定參數(shù)算法構(gòu)型. 但人工智能算法在計算過程中需要不斷迭代, 最佳的算法參數(shù)一般會隨著整個程序運行的時間而發(fā)生變化.為此, 利用強化學習[110]以及基于啟發(fā)式算法[111]的動態(tài)算法構(gòu)型設計框架也被提出.

算法選擇問題是希望獲得一個選擇機制以在面對新的問題實例時挑選出最佳的算法, 而算法構(gòu)型設計是對算法本身的參數(shù)做優(yōu)化. 在經(jīng)典計算算法設計上人們也有將兩者進行融合[112]以獲得對困難問題的高效計算.

3.3 量子與經(jīng)典組合算法

量子算法的設計與研究并不是一蹴而就的. 在研究與設計量子算法的過程中, 人們也會將經(jīng)典算法中的一些思想與手段加以利用, 進而設計出量子與經(jīng)典的組合算法. 一般地, 這些組合算法按照形式可以分為以下兩類.

其一是利用量子系統(tǒng)具有的優(yōu)越性來實現(xiàn)一些經(jīng)典算法, 其中具有代表性的是量子機器學習(quantum machine learning, QML). 量子機器學習領(lǐng)域主要研究如何借助量子系統(tǒng)中的疊加與糾纏等性質(zhì)來實現(xiàn)經(jīng)典機器學習算法的加速[113]. 在機器學習算法中, 有很多算法本質(zhì)上都可以分解為基于矩陣的一些線性代數(shù)運算. 在這些線性代數(shù)運算中, 對于傅里葉變換[5]、尋找矩陣特征值與特征向量[15]以及求解線性方程組[114,115]等運算, 都有著相比經(jīng)典算法有指數(shù)或者多項式級別加速的量子算法. 這一系列具有量子加速的線性代數(shù)運算(quantum basic linear algebra subroutines,qBLAS)[113]可以加速許多機器學習領(lǐng)域中的算法,例如最小二乘法[116]、梯度下降法與牛頓法[117]、半正定規(guī)劃[118]、主成分分析[119]、拓撲分析[120]、支持向量機[121]等. 在這些機器學習算法的實現(xiàn)中, 為了避免經(jīng)典數(shù)據(jù)的輸入與讀取成為限制算法效率的瓶頸, 量子隨機讀取內(nèi)存(quantum random access memory, qRAM)[122]技術(shù)被提出, 并旨在極大地提升數(shù)據(jù)讀取的效率. 量子機器學習的另一大研究領(lǐng)域是利用量子模擬器或可編程量子線路以建立量子深度學習網(wǎng)絡(deep quantum learning network)[123,124]. 基于玻爾茲曼分布的量子玻爾茲曼機(quantum Boltzmann machine)將神經(jīng)網(wǎng)絡表示成為伊辛模型下量子自旋及其間的相互作用,通過訓練和優(yōu)化過程使得量子系統(tǒng)可以學習到數(shù)據(jù)的概率分布[125]. 相較于經(jīng)典版本, 量子玻爾茲曼機可以更有效地加速訓練過程[126], 同時在自旋相互作用模型的選取上也更具靈活性[125]. 除此之外,量子機器學習不僅可以和經(jīng)典機器學習一樣接收經(jīng)典信息并進行處理, 還可以直接處理量子系統(tǒng)與量子過程產(chǎn)生的量子信息[113].

其二則是將量子態(tài)的制備、演化與測量過程與經(jīng)典的優(yōu)化算法相結(jié)合, 利用經(jīng)典計算機調(diào)節(jié)并優(yōu)化量子計算過程中的相應參數(shù). 其中具有代表性的算法有量子近似優(yōu)化算法(quantum approximate optimization algorithm, QAOA)與變分量子本征求解(variational quantum eigensolver, VQE)算法. 量子近似優(yōu)化算法, 最初由Farhi與Goldstone[127]在2014年提出, 主要被用于解決一些NP-hard的組合優(yōu)化問題. 一般地, 量子計算機的演化過程可以用 2p個幺正算符來描述, 其中p為預先設定的正整數(shù)決定量子線路的深度[127]. 量子近似優(yōu)化算法利用經(jīng)典的優(yōu)化算法調(diào)節(jié)這些算符, 進而影響對應的量子計算過程, 并通過迭代最終使演化結(jié)果能夠很好地近似對應組合優(yōu)化問題的最優(yōu)解. 量子近似優(yōu)化算法不僅被證明具有通用計算的能力[128],同時還在例如連續(xù)優(yōu)化[129]、線性代數(shù)[130]等領(lǐng)域中的一些問題中有著良好的表現(xiàn). 除此之外, 它也被認為具有實現(xiàn)量子優(yōu)越性的潛力[131], 并且在谷歌“懸鈴木”[132]、D-Wave 2000 Q[133]等量子計算硬件上表現(xiàn)出了良好的適配性, 但是該算法的量子計算優(yōu)勢還需要更準確地刻畫[134].

Peruzzo等[135]在2014年提出的變分量子本征求解算法, 則是為了解決量子化學領(lǐng)域的相關(guān)問題. 變分量子本征求解算法借助變分原理, 通過預先擬設(ansatz)來選擇量子初態(tài)與量子線路, 并在量子演化后利用哈密頓量平均(Hamiltonian averaging)的手段估計能量期望值, 最終利用經(jīng)典的非線性優(yōu)化過程優(yōu)化參數(shù)直至尋找到符合要求的近似解[136]. 盡管理論上傳統(tǒng)求解特征值的量子相位估計算法有著很好的性能, 但它對于量子系統(tǒng)的相干性有著很高的要求. 相對地, 變分量子本征求解算法對于相干性的要求大大降低[135]. 目前, 在不同的量子計算硬件上, 變分量子本征求解算法可以很好地求解 H2[137]、 H eH+[135,138]、 L iH[139,140]、 B eH2[139]等分子系統(tǒng)的基態(tài)能量問題以及 H2[141]等分子系統(tǒng)的激發(fā)態(tài)能量問題.

3.4 機器學習在量子控制中的應用

經(jīng)典最優(yōu)控制理論通常需要對物理系統(tǒng)建立一個數(shù)學模型, 其基本目的是控制系統(tǒng)來根據(jù)參考軌跡運動或者根據(jù)目標函數(shù)優(yōu)化系統(tǒng)的動力學[142].但如果這個數(shù)學模型過于復雜以至于無法解析得到參考路徑之時, 那么機器學習就是一個可供選擇的方式[143,144]. 與經(jīng)典控制類似的量子控制在量子計算與量子信息的應用中起到至關(guān)重要的作用, 其核心是控制量子動力學過程向既定的方向(比如特殊的量子態(tài))去演化, 簡單來說就是對量子系統(tǒng)的控制[27].

對于傳統(tǒng)的貝葉斯優(yōu)化, 需要知道系統(tǒng)動力學的知識[145]. 而在機器學習方法下, 可以將量子系統(tǒng)視為一個黑箱—此時量子控制的策略會根據(jù)系統(tǒng)結(jié)果的輸出, 來近似知道對應的動力學過程[146,147]. 人們可以利用機器學習在量子計算及量子測量中進行量子調(diào)控[148—153], 實現(xiàn)在高維量子多體系統(tǒng)中的非凸優(yōu)化[154,42], 以及利用神經(jīng)網(wǎng)絡對控制脈沖進行設計[155]等.

近些年, 強化學習在量子系統(tǒng)優(yōu)化控制中的應用也備受關(guān)注. 如在量子線路模型中, 通過在強化學習的環(huán)境中加入不同的控制誤差來訓練優(yōu)化智能體以實現(xiàn)普適的量子控制[43]. 另外, 強化學習在實現(xiàn)高保真度目標態(tài)的快速制備[45,156,157]、量子線路優(yōu)化[158]、控制非平衡量子熱力學過程[159]以及在量子開放系統(tǒng)中進行最優(yōu)化控制并與傳統(tǒng)優(yōu)化方法進行對比[160—162], 結(jié)合強化學習與量子絕熱捷徑技術(shù)實現(xiàn)對單個量子比特進行更快更魯棒地控制[163,164]等領(lǐng)域得到廣泛應用.

機器學習(特別是強化學習)在有噪聲的中等規(guī)模量子(NISQ)[73]控制中與傳統(tǒng)量子優(yōu)化方法,如GRAPE[165]、CRAB[166]一并成為了新的一種量子最優(yōu)化控制方法, 并且能夠幫助人們對自旋玻璃物理以及對量子相變物理進行控制, 輔助建立更直觀的物理圖像[42,45,167].

4 強化學習在絕熱量子算法設計中的應用

本文第2節(jié)談到絕熱量子計算的定義, 了解到為了避免出現(xiàn)從基態(tài)向激發(fā)態(tài)的躍遷 (Landau—Zener transition)[168,169], 原則上需要給系統(tǒng)很長的演化時間. 在絕熱量子計算中, 人們通過解析局部優(yōu)化哈密頓量演化路徑, 使系統(tǒng)在最小能隙處降低演化速率來保證不發(fā)生躍遷, 并實現(xiàn)了Grover搜索問題的平方加速[66].

必須要指出的是, 想要在復雜的量子多體系統(tǒng)中做到對整個能譜的全局認知本身就非常困難. 所以對于復雜量子多體體系, 很難解析地知道這些最小能隙的位置來局域地優(yōu)化哈密頓量演化路徑[170—172]. 而在經(jīng)典及量子最優(yōu)化控制部分的介紹中, 我們已經(jīng)談到可以嘗試將復雜的物理系統(tǒng)看作黑箱, 利用機器學習來獲取最優(yōu)化的控制.

本節(jié)將具體介紹我們利用強化學習輔助設計絕熱量子算法的一個工作[173]. 從前文的介紹中了解到絕熱量子計算的表現(xiàn)與演化路徑密切相關(guān). 在接下來的內(nèi)容中, 所說的絕熱量子算法的設計就對應于絕熱演化的路徑設計. 我們在第2節(jié)中介紹了幾個計算問題的哈密頓量編碼方式. 而對于給定一個計算問題, 總有不同的問題實例. 如在Grover搜索問題中對不同的目標態(tài)的搜索以及在3-SAT問題中不同子句的選擇, 這都會使不同問題實例具有不同的答案. 絕熱算法設計或者說哈密頓量演化路徑設計不能依賴于具體的某一個問題實例. 這也就有別于對具體目標量子態(tài)制備[45]以及實現(xiàn)快速的量子門操作[174,155,43], 如何學習并自動化設計絕熱量子計算中哈密頓量演化路徑以使得計算過程體現(xiàn)出量子優(yōu)勢就是一個量子算法設計問題[173,175,176]. 對此, 我們構(gòu)造了自動化絕熱量子算法設計框架, 如圖1. 這一框架特別適合對那些很難被求解但容易被驗證的問題進行絕熱算法設計, 如Grover搜索問題、質(zhì)因數(shù)分解問題、3-SAT問題等等. 在該框架中, 我們參數(shù)化哈密頓量演化路徑為:

圖1 強化學習輔助絕熱量子算法設計的示意圖[173]. 其中強化學習中的智能體(agent)根據(jù)絕熱量子計算(AQC)輸出的結(jié)果來獲取獎勵, 并根據(jù)深度神經(jīng)網(wǎng)絡近似表示的Q值表格來選擇動作更新絕熱量子算法Fig. 1. Schematic diagram of the reinforcement learning approach for quantum adiabatic algorithm design[173]. The learning agent collects the reward according to the result obtained from adiabatic quantum computing (AQC) and produces an action to update the quantum adiabatic algorithm based on its Q table represented by a deep neural network.

其中C為截斷階數(shù). 當C趨于無窮時, 這樣的參數(shù)化形式就是完備的. 強化學習中智能體(agent)的狀態(tài)s為需要設計的哈密頓量演化路徑中的全部參數(shù)bm, 稱作“路徑態(tài)”(path state). 智能體的動作a是對路徑態(tài)中參數(shù)bm的操作, 其根據(jù)絕熱量子計算機的輸出結(jié)果對錯來獲得不同獎勵r, 即答案正確獎勵為1, 答案錯誤獎勵為0. 強化學習的目標是最大化獎勵, 所以通過讓智能體從線性路徑開始對路徑參數(shù)進行調(diào)整, 也就能優(yōu)化設計出好的絕熱量子算法. 這樣的框架就非常適合在D-wave機器[177]中應用. 值得一提的是, 在訓練智能體的時候, 將同一系統(tǒng)規(guī)模的大量問題實例一起輸入并對最后的表現(xiàn)進行平均, 這樣的處理能夠讓算法設計更為魯棒.

智能體中深度神經(jīng)網(wǎng)絡近似地表示Q值表格,并用其來估計當前狀態(tài)下選擇不同動作的未來累積獎勵. 在例如圍棋游戲中, 智能體的動作是離散的. 而這里通過類似模擬退火的方式連續(xù)化了強化學習智能體的動作, 實現(xiàn)了自動化設計具有量子加速的絕熱量子Grover搜索算法. 其中固定系統(tǒng)總的演化時間T與系統(tǒng)規(guī)模n的關(guān)系為人們解析地得到了基于第2節(jié)中介紹的Grover搜索算法哈密頓量編碼方式下的具有量子加速的絕熱算法[66]. 在這一演化時間內(nèi), 線性的演化路徑會大概率以失敗告終. 而利用強化學習自動化絕熱量子算法設計框架獲得的算法, 其可以在這一演化時間內(nèi)到達與解析獲得的算法[66]相當?shù)慕Y(jié)果(成功概率99.9% 以上), 在過程中甚至有超越解析算法[66]的表現(xiàn), 如圖2. 通過對系統(tǒng)的能譜以及強化學習得到的路徑進行觀察, 發(fā)現(xiàn)演化路徑在能隙最小處變化得最緩慢, 出現(xiàn)了平臺[173]. 這個重要特征與解析結(jié)果[66]是一致的.

圖2 強化學習輔助設計的絕熱量子算法在Grover搜索問題上的表現(xiàn)[173]. 其中成功概率(success probability)是演化終態(tài)與目標態(tài)交疊的平方, 總的演化時間T與系統(tǒng)規(guī)模n的關(guān)系為 . 圖中藍色虛線表示的線性演化路徑成功概率會隨著系統(tǒng)尺寸增大不斷降低. 紅色實線和黑色虛線分別表示強化學習設計得到的演化路徑和解析獲得的非線性路徑[66]的表現(xiàn). 在選擇的演化時間下, 兩者的成功概率都能接近于1, 說明兩者都具有平方的量子加速Fig. 2. Performance of reinforcement learning designed quantum adiabatic algorithm in success probability for Grover search problem[173]. The success probability is obtained by taking the square of wave-function overlap of the final evolved quantum state with the target state. The total adiabatic evolution time is chosen as where n is the system size. The blue dashed line denotes the success probability of linear path which decreases as increasing the system size. The red solid line and black dashed line denote the performance of the reinforcement learning designed path and the nonlinear path[66], respectively. Given the choice of total evolution time, the success probability close to 1 by both implies that they both exhibit quadratic quantum speed up.

我們測試了強化學習在量子比特數(shù)量拓展過程中的表現(xiàn), 如圖3. 其中線性演化路徑的結(jié)果非保真度(infidelity)增長得很快, 說明其計算表現(xiàn)能力不佳(前文中提到其被證明沒有量子加速). 我們測試了將在10 qubits系統(tǒng)強化學習得到的路徑直接用到11—16 qubits上, 發(fā)現(xiàn)雖然保真度會有下降但這也會比直接用線性路徑更好. 而如果將在iqubits系統(tǒng)中強化學習得到的路徑用到i+1 qubits系統(tǒng)并計算其非保真度. 這樣拓展具有遠超線性路徑的表現(xiàn)能力, 其結(jié)果的非保真度都接近于1%. 對于另一種實驗友好的編碼方式, 即如果將初始哈密頓量寫成解析的方法[66]無法得到最優(yōu)的演化路徑, 而基于強化學習的方式依舊可以獲得這一具有平方加速的量子算法[173].

圖3 強化學習在Grover搜索問題的絕熱量子算法設計中的拓展性[173]. 其中綠線是線性路徑的表現(xiàn), 藍線是將10 qubits系統(tǒng)中強化學習學到的路徑推廣到更大系統(tǒng), 橘線是將在n qubits系統(tǒng)強化學習獲得的路徑推廣到n+1 qubits系統(tǒng)Fig. 3. Transferability of reinforcement learning based quantum adiabatic algorithm design for Grover search problem[173]. The green line denotes the infidelity of linear path.The blue line denotes the infidelity of the path obtained by training the 10 qubits system. The orange line denotes the performance of applying the path learned from the n qubits system to the n +1 qubits system.

在對3-SAT這個NP-complete問題研究中,我們對10 qubits系統(tǒng)且僅對包含3個子句的問題進行強化學習來獲得絕熱量子算法. 將這樣設計得到的算法直接推廣到其他不同子句數(shù)量的問題上,其表現(xiàn)能力與一般的線性演化路徑相比具有明顯的提升. 這樣獲得的絕熱算法具備一定的可遷移性[173].

在這個工作中[173], 我們利用強化學習優(yōu)化設計了參數(shù)s(t). 也可以將其推廣, 將初始哈密頓量和問題哈密頓量前的參數(shù)在保證邊界條件下分別優(yōu)化. 有研究表明, 這樣的分別優(yōu)化會有更好的表現(xiàn)[178,179]. 人們也考慮在演化過程中設計加入額外的哈密頓量, 并且讓這些額外的哈密頓量在初始和結(jié)束演化時關(guān)閉來提升絕熱量子計算的能力[180,172,47]. 此外, 強化學習在自動化設計優(yōu)化量子線路[181—183]、完成在量子模擬中的哈密頓量構(gòu)造[184]、優(yōu)化量子糾錯碼[185]、優(yōu)化數(shù)字量子模擬[186]以及容錯量子計算[187]等量子計算方面也有廣泛應用.

5 結(jié)束語

量子計算因其具有超越經(jīng)典計算的優(yōu)勢而受到高度關(guān)注. 其中量子計算算法的設計開發(fā)與量子計算的硬件實現(xiàn)都至關(guān)重要. 本文對絕熱量子計算、機器學習及其在經(jīng)典算法設計中的應用做了回顧, 介紹了機器學習, 特別是強化學習在量子最優(yōu)化控制中以及絕熱量子計算算法設計中的具體應用. 我們看到了機器學習在設計經(jīng)典算法和求解量子多體物理上的成功應用, 也期待機器學習能夠?qū)碗s且違反經(jīng)典直覺的量子算法設計提供更多幫助. 這不僅能夠更好地將量子計算優(yōu)勢挖掘出來,量子計算的計算優(yōu)勢也能更有力地加速機器學習對大量數(shù)據(jù)的處理. 我們預期量子計算與機器學習的交融會給這兩個領(lǐng)域帶來新的契機和突破.