（圖片來(lái)源：網(wǎng)絡(luò)）

?

摘要：量子近似優(yōu)化算法（QAOA）是一種變分量子算法，旨在為組合優(yōu)化問(wèn)題提供次優(yōu)解決方案。人們普遍認(rèn)為，QAOA 有潛力在淺層電路的中等噪聲規(guī)模量子 (NISQ) 處理器中展示應(yīng)用級(jí)量子優(yōu)勢(shì)。由于 QAOA 的核心問(wèn)題是計(jì)算目標(biāo)哈密頓量期望值，在一般的淺層量子電路上，能否找到一種求解量子期望值的有效經(jīng)典算法以便快速獲取最佳變分參數(shù)對(duì)于在NISQ硬件上展示潛在的量子優(yōu)勢(shì)至關(guān)重要。

?

北京量子信息科學(xué)研究院（以下簡(jiǎn)稱(chēng)“北京量子院”）的科研團(tuán)隊(duì)提出了一種基于圖分解的新型經(jīng)典算法，該算法可以在除完全圖情況外的大多數(shù)優(yōu)化問(wèn)題中，對(duì)淺層QAOA電路實(shí)行量子均值的高效經(jīng)典計(jì)算。北京量子院科研團(tuán)隊(duì)在論文中論述，“與最先進(jìn)的方法相比，該算法對(duì)Max-cut、圖著色和SK（Sherrington-Kirkpatrick ）模型問(wèn)題的數(shù)值測(cè)試實(shí)現(xiàn)了數(shù)量級(jí)的性能改進(jìn)。我們的研究結(jié)果不僅對(duì)探索 QAOA 的量子優(yōu)勢(shì)很重要，而且對(duì) NISQ 處理器的性能基準(zhǔn)測(cè)試也將非常有幫助。”

?

量子計(jì)算技術(shù)在過(guò)去幾十年里的快速發(fā)展吸引了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注。

?

2021年，IBM在美國(guó)量子峰會(huì)上宣布其127 量子比特計(jì)算芯片“Eagle（老鷹）”。問(wèn)世之后，在其蘇黎世研究中心舉行的量子計(jì)算活動(dòng)上，又公布了要實(shí)現(xiàn)萬(wàn)分之一錯(cuò)誤率的高保真量子系統(tǒng)研發(fā)計(jì)劃。

?

同年，祖沖之2.1宣布采樣任務(wù)的經(jīng)典模擬復(fù)雜度比谷歌“懸鈴木”高6個(gè)數(shù)量級(jí)，比祖沖之2.0高3個(gè)數(shù)量級(jí)。而且祖沖之2.1在4.2小時(shí)內(nèi)完成的60量子比特、24層循環(huán)的隨機(jī)電路采樣任務(wù)，將花費(fèi)Summit超級(jí)計(jì)算機(jī)4.8萬(wàn)年的時(shí)間來(lái)模擬?！?-2】

?

這些工作無(wú)疑表明，我們已經(jīng)進(jìn)入了中等噪聲規(guī)模量子 (NISQ) 時(shí)代【3】。在這個(gè)時(shí)代，量子處理器包含大約50至數(shù)百個(gè)噪聲量子比特，但是受噪聲影響量子邏輯門(mén)操作的錯(cuò)誤率較大，這導(dǎo)致可以有效執(zhí)行的線(xiàn)路深度極其受限，因而如何有效的使用 NISQ 芯片并在某些應(yīng)用中展示量子優(yōu)勢(shì)成為目前最為緊迫和重要的問(wèn)題。

?

變分量子算法（VQA）

?

變分量子算法（VQA），包括用于量子化學(xué)求解的變分量子本征求解算法VQE、用于機(jī)器學(xué)習(xí)的量子神經(jīng)網(wǎng)絡(luò)算法QNN，以及求解組合優(yōu)化問(wèn)題的量子近似優(yōu)化算法（QAOA）。VQA被廣泛認(rèn)為是目前少有的適用于NISQ應(yīng)用的一種有效算法，可應(yīng)用于如量子化學(xué)、機(jī)器學(xué)習(xí)和組合優(yōu)化等實(shí)際問(wèn)題中【4-12】。VQA的基本思想是通過(guò)對(duì)參數(shù)化量子電路的采樣估計(jì)代價(jià)函數(shù)，并調(diào)用經(jīng)典優(yōu)化器尋找迭代參數(shù)，直至達(dá)到收斂條件【13】。最后，利用優(yōu)化后的參數(shù)對(duì)量子電路進(jìn)行采樣，得到比特串輸出作為問(wèn)題的解。

?

其中，代價(jià)函數(shù)一般可描述為某種哈密頓量的期望值，它可以被寫(xiě)成多（n）泡利算子的線(xiàn)性組合，例如QAOA中的伊辛哈密頓量。隨著量子比特?cái)?shù)的增加，量子電路的采樣在經(jīng)典場(chǎng)景下難以處理【14-16】，因此經(jīng)典計(jì)算機(jī)能否有效地計(jì)算出淺層電路的量子期望值是一個(gè)很重要的問(wèn)題。如果答案是肯定的，則只需在VQA算法的量子采樣部分需要用到NISQ處理器。這將極大的縮短在NISQ硬件上執(zhí)行VQA算法的時(shí)間。

?

Bravyi，Gosset和Movassagh在最近的一篇論文中指出，對(duì)于幾何局部二維量子電路【17】的特殊情況，經(jīng)典算法的運(yùn)行時(shí)間與量子比特的數(shù)量成線(xiàn)性關(guān)系。然而，在一般的淺層電路上，量子期望值計(jì)算問(wèn)題能否在經(jīng)典計(jì)算機(jī)上有效地解決，仍然是一個(gè)核心的未決問(wèn)題。北京量子院的科研團(tuán)隊(duì)證明了在一般的淺層QAOA電路中，確實(shí)存在一個(gè)經(jīng)典算法能夠有效地計(jì)算量子期望值。

?

由于小實(shí)例可以獨(dú)立處理，所以這種算法是一種自然并行算法，即利用圖分解和電路圖映射的方法。分析數(shù)值試驗(yàn)表明，對(duì)于大多數(shù)優(yōu)化問(wèn)題，該算法的運(yùn)行時(shí)間與量子比特?cái)?shù)成線(xiàn)性關(guān)系。對(duì)于特殊的QAOA實(shí)例，如Sherrington-Kirkpatrick (S-K)模型，盡管其運(yùn)行時(shí)間呈指數(shù)級(jí)增長(zhǎng)，但其性能仍?xún)?yōu)于目前最先進(jìn)的張量網(wǎng)絡(luò)算法。數(shù)值效果圖如下：

?

量子近似優(yōu)化算法(QAOA)

?

QAOA的核心思想是通過(guò)變分方法尋找含參數(shù)的淺層量子線(xiàn)路的最優(yōu)參數(shù)，以使得和問(wèn)題對(duì)應(yīng)的哈密頓量期望值最小，含有最優(yōu)參數(shù)的量子線(xiàn)路的輸出態(tài)可以被認(rèn)為是問(wèn)題哈密頓量的近似基態(tài)解。

?

例如，在Farhi, Goldstone和Gut-mann發(fā)布的一篇論文中，提出將QAOA作為一種變分量子算法來(lái)產(chǎn)生組合優(yōu)化（CO）問(wèn)題【10】的近似解。此后，大量關(guān)于QAOA的研究工作在理論和實(shí)驗(yàn)上【12,18-32】得到了證實(shí)。類(lèi)似于量子退火（QA），其中CO問(wèn)題被建模為伊辛哈密頓量的形式，QAOA也從成本函數(shù)的伊辛形式開(kāi)始，代價(jià)函數(shù)為二次函數(shù)，其一般算式為：

?

而QAOA則通過(guò)在量子電路中生成盡可能接近最優(yōu)基向量的量子態(tài)來(lái)逼近最優(yōu)解，是通過(guò)引入其他算式來(lái)實(shí)現(xiàn)：

?

基于計(jì)算基向量一致疊加的期望值，然后通過(guò)外環(huán)經(jīng)典優(yōu)化器進(jìn)行優(yōu)化，找到最優(yōu)參數(shù)，一旦得到最優(yōu)態(tài)，我們就可以對(duì)優(yōu)化后的量子電路進(jìn)行采樣，并輸出使運(yùn)營(yíng)商成本最小的位串作為近似解。

?

因此，量子近似優(yōu)化算法(QAOA)可以求解組合優(yōu)化問(wèn)題的近似解，被廣泛認(rèn)為有潛力在中等嘈雜型量子(NISQ)計(jì)算芯片上展現(xiàn)量子優(yōu)勢(shì)。目前，在 NISQ 芯片實(shí)施 QAOA 算法的常用流程是：

?

(1)?首先在量子芯片上執(zhí)行含初始參數(shù)的 QAOA 量子線(xiàn)路的采樣任務(wù)；

?

(2)?其次使用經(jīng)典計(jì)算機(jī)根據(jù)采樣結(jié)果獲得問(wèn)題哈密頓量的含參數(shù)期望值，并調(diào)用優(yōu)化器諸如 COBYA 計(jì)算得到新的迭代參數(shù);

?

(3)?隨后將量子芯片上的 QAOA 量子線(xiàn)路參數(shù)更新為迭代參數(shù)繼續(xù)重復(fù)上述 1-2 過(guò)程直至達(dá)到收斂條件并輸出最優(yōu)參數(shù);

?

(4)?最后在量子芯片上對(duì)含最優(yōu)參數(shù)的 QAOA 量子線(xiàn)路采樣，輸出使得問(wèn)題哈密頓量最小的比特串做為問(wèn)題的近似解。

?

在上述流程中，量子芯片需要被多次調(diào)用求解問(wèn)題哈密頓量期望值，其缺點(diǎn)主要有兩個(gè)：

?

(1)?量子芯片一般是很寶貴的計(jì)算資源，多次調(diào)用一方面占用了執(zhí)行其他算法的時(shí)間，另一方面也不利于芯片的使用壽命；

?

(2)?量子線(xiàn)路中參數(shù)迭代在實(shí)際中需要快速改變儀器的操作參數(shù)，當(dāng)需要迭代的參數(shù)間相差不大時(shí)，在實(shí)際中并不容易實(shí)現(xiàn)。

?

針對(duì)上述缺點(diǎn)，目前的主要解決思路是先通過(guò)經(jīng)典模擬方法找到最優(yōu)參數(shù)，最后再使用量子芯片采樣輸出近似解。因此設(shè)計(jì)有效的經(jīng)典模擬方法快速尋找 QAOA 淺層量子線(xiàn)路的最優(yōu)參數(shù)至關(guān)重要，而其中最為核心的是實(shí)現(xiàn)問(wèn)題哈密頓量期望值的有效經(jīng)典模擬計(jì)算。

?

北京量子院科研團(tuán)隊(duì)提出，目前對(duì)于量子線(xiàn)路的哈密頓量期望值計(jì)算主要有兩種算法：

?

(1)基于態(tài)矢量模擬器直接計(jì)算，缺點(diǎn)是運(yùn)算規(guī)模極其有限且速度較慢；

?

(2)將量子線(xiàn)路轉(zhuǎn)化為張量圖，通過(guò)張量縮并計(jì)算，運(yùn)算規(guī)模和速度相比(1)可以大大提高，但依然需要進(jìn)一步提高以滿(mǎn)足實(shí)際應(yīng)用。?

?

基于圖分解的經(jīng)典算法

?

這里，北京量子院科研團(tuán)隊(duì)將展示一種全新的 QAOA 期望值計(jì)算算法，用來(lái)尋找 QAOA 淺層量子線(xiàn)路的最優(yōu)參數(shù)，其核心想法是將優(yōu)化問(wèn)題的哈密頓量與權(quán)重圖對(duì)應(yīng)，通過(guò)圖分解算法獲取一系列的子圖，這些子圖與特定的 QAOA 量子線(xiàn)路期望值計(jì)算一一對(duì)應(yīng)，加和所有子圖對(duì)應(yīng)的期望值即可得到問(wèn)題哈密頓量期望值。最后，通過(guò)調(diào)用經(jīng)典優(yōu)化器進(jìn)行迭代至收斂條件即可找到 QAOA 淺層量子線(xiàn)路的最優(yōu)參數(shù)。

?

北京量子院科研團(tuán)隊(duì)指出，在計(jì)算優(yōu)勢(shì)上，該算法相比現(xiàn)有算法主要有三個(gè)優(yōu)勢(shì)：

?

(1)?由于每個(gè)子圖對(duì)應(yīng)的期望值計(jì)算可以獨(dú)立進(jìn)行，因而我們的算法支持根據(jù)經(jīng)典硬件資源進(jìn)行大規(guī)模并行運(yùn)算從而相比現(xiàn)有算法可以極大的提高計(jì)算速度，計(jì)算速度的提高僅僅取決于如何高效的利用經(jīng)典硬件資源;

?

(2)?問(wèn)題哈密頓量對(duì)應(yīng)的權(quán)重圖分解可以在多項(xiàng)式時(shí)間內(nèi)完成，算法的計(jì)算復(fù)雜度僅取決于分解的子圖對(duì)應(yīng)的期望值量子線(xiàn)路大小，與待求解問(wèn)題規(guī)模無(wú)關(guān)，因而我們的算法相比現(xiàn)有算法課處理更大規(guī)模的優(yōu)化問(wèn)題；

?

(3)?對(duì)于分解后的子圖對(duì)應(yīng)的期望值求解可以調(diào)用已有的算法計(jì)算，這使得我們的算法具有極好的包容性和擴(kuò)展性。

?

基于上述提出的核心算法，科研團(tuán)隊(duì)初步完成了計(jì)算軟件包 QCover，即基于QAOA 的組合優(yōu)化問(wèn)題加速求解器，目前已開(kāi)源到github【11】。

?

其中，QCover 軟件包主要包括五個(gè)模塊，即核心算法模塊，優(yōu)化問(wèn)題庫(kù)模塊，量子線(xiàn)路模擬器后端模塊，經(jīng)典優(yōu)化器模塊以及編譯優(yōu)化模塊。在 Max-cut，圖著色等常用 benchmark 案例的測(cè)試結(jié)果表明，QCover 相比于現(xiàn)有軟件包如 IBM 的 qiskit,谷歌的 cirq 等不論是在運(yùn)算速度還是規(guī)模都有量級(jí)的性能提高。QCover 軟件包與將來(lái)的NISQ 硬件結(jié)合使用將有助于加速在應(yīng)用層面上展示量子優(yōu)勢(shì)。

?

結(jié)論

?

雖然我們已經(jīng)證明了經(jīng)典計(jì)算機(jī)可以有效求解淺層QAOA電路的量子均值，但對(duì)其他VQA（如VQE和QML）來(lái)說(shuō)，量子均值仍然是一個(gè)懸而未決的問(wèn)題。此外，QAOA的最后一階段的采樣仍然需要NISQ處理器，這在傳統(tǒng)意義上難以處理。

?

然而，我們的算法和軟件可以作為一個(gè)強(qiáng)大的經(jīng)典輔助工具，幫助發(fā)現(xiàn)和實(shí)現(xiàn)可能的優(yōu)化問(wèn)題，適合在NISQ處理器中展示應(yīng)用級(jí)量子優(yōu)勢(shì)，這也有助于我們的算法驗(yàn)證和基準(zhǔn)測(cè)試NISQ計(jì)算機(jī)。由于QAOA處理的是伊辛哈密頓量，我們的算法有潛力幫助實(shí)現(xiàn)任意長(zhǎng)程伊辛哈密頓量【30】的快速近似基態(tài)制備。

?

參考文獻(xiàn)詳情鏈接：

https://mp.weixin.qq.com/s/fGErr7IZYw7jFof4QlNIpQ

編輯：慕一/王衍

?