量子霸權(quán)的實(shí)現(xiàn)，將是量子計(jì)算發(fā)展的一座重要里程碑，代表「量子計(jì)算的超強(qiáng)計(jì)算能力」自 37 年前提出以來首次從理論走進(jìn)實(shí)驗(yàn)，標(biāo)志一個(gè)新的計(jì)算能力飛躍時(shí)代的開始。近年來，隨著「實(shí)現(xiàn)量子霸權(quán)」的日益臨近，「稱霸標(biāo)準(zhǔn)」成為量子計(jì)算領(lǐng)域最重要的科學(xué)問題之一。

我國科學(xué)家最早開啟了「稱霸標(biāo)準(zhǔn)」問題的研究。最近，《國家科學(xué)評(píng)論》（National Science Review）以「A Benchmark Test of Boson Sampling on Tianhe-2 Supercomputer」為題正式發(fā)表了國防科技大學(xué)吳俊杰團(tuán)隊(duì)與上海交通大學(xué)金賢敏教授的合作研究成果，報(bào)道了玻色采樣案例的「稱霸標(biāo)準(zhǔn)」。

圖 1：實(shí)現(xiàn)玻色采樣的計(jì)算任務(wù)：（a）天河二號(hào)超級(jí)計(jì)算機(jī)計(jì)算積和式；（b）光量子系統(tǒng)通過采樣輸出光子直接完成玻色采樣。

量子霸權(quán)

上世紀(jì)八十年代，費(fèi)曼提出量子計(jì)算的概念。九十年代，科學(xué)家們發(fā)明了一批重要的量子算法，在理論上發(fā)現(xiàn)量子計(jì)算擁有經(jīng)典計(jì)算無法比擬的超強(qiáng)計(jì)算能力。人們開始意識(shí)到，量子計(jì)算機(jī)將是 IT 領(lǐng)域的「屠龍刀」，一旦實(shí)現(xiàn)將超越經(jīng)典計(jì)算的極限。美國加州理工學(xué)院物理學(xué)家 John Preskill，將這種超越所有經(jīng)典計(jì)算機(jī)的計(jì)算能力起名「量子霸權(quán)（quantum supremacy）」。

到目前為止，科學(xué)家仍未成功打造出能夠展示量子霸權(quán)的實(shí)際量子裝置。2010 年，MIT 科學(xué)家 Scott Aaronson 提出了可用于展示霸權(quán)的玻色采樣問題。玻色采樣是一種針對(duì)光子（玻色子）系統(tǒng)的量子霸權(quán)測試案例。理論上，經(jīng)典計(jì)算機(jī)求解玻色采樣需要指數(shù)量級(jí)計(jì)算時(shí)間，而量子計(jì)算只需要多項(xiàng)式量級(jí)計(jì)算時(shí)間。與此同時(shí)，相比通用量子計(jì)算，玻色采樣更容易實(shí)現(xiàn)。

天河二號(hào)

玻色采樣的理論方案一經(jīng)提出，全球科學(xué)家紛紛行動(dòng)起來。2013 年，首批玻色采樣的原理實(shí)驗(yàn)裝置問世，實(shí)現(xiàn)了 3-4 個(gè)光子的玻色采樣實(shí)驗(yàn)。當(dāng)時(shí)，金賢敏所在的牛津大學(xué)研究組，正是國際上最早實(shí)現(xiàn)玻色采樣實(shí)驗(yàn)的團(tuán)隊(duì)之一。

2013 年 9 月，國防科技大學(xué)的吳俊杰赴牛津訪問，與金賢敏交流起玻色采樣實(shí)現(xiàn)量子霸權(quán)所需的功力，發(fā)現(xiàn)科學(xué)家還未了解經(jīng)典計(jì)算機(jī)的真正實(shí)力。當(dāng)時(shí)，國防科大研制的天河二號(hào)超級(jí)計(jì)算機(jī)是經(jīng)典計(jì)算領(lǐng)域的「倚天劍」，剛在超級(jí)計(jì)算機(jī)中奪得頭籌，計(jì)算能力排名全球第一。于是，兩人商定要驗(yàn)驗(yàn)天河倚天劍到底能劈開多大規(guī)模的玻色采樣問題，為玻色采樣量子屠龍刀立下稱霸標(biāo)準(zhǔn)。

經(jīng)過嚴(yán)謹(jǐn)?shù)臏y試與分析，他們的成果于 2016 年 6 月發(fā)表在預(yù)印版網(wǎng)站 arXiv 上。當(dāng)時(shí)，天河二號(hào)正六次蟬聯(lián)超級(jí)計(jì)算機(jī)排行榜第一位。論文實(shí)際測試的問題規(guī)模達(dá)到 48 個(gè)光子，并推斷出天河二號(hào)完成 50 個(gè)光子玻色采樣的最高生成率約為每組樣本 100 分鐘。也就是說，一旦打造出「每組樣本 100 分鐘以內(nèi)的 50 個(gè)光子玻色采樣」的量子屠龍刀，就在求解玻色采樣問題上超過了天河倚天劍的功力，實(shí)現(xiàn)了量子霸權(quán)。

量子霸權(quán)爭奪戰(zhàn)

值得指出的是，因?yàn)椴⒉灰笥糜谡故玖孔影詸?quán)的問題具有任何實(shí)際用途，「實(shí)現(xiàn)量子霸權(quán)」相較「實(shí)現(xiàn)實(shí)際的量子計(jì)算機(jī)」要簡單許多。而與此同時(shí)，「稱霸標(biāo)準(zhǔn)」的研究成果表明，當(dāng)前實(shí)現(xiàn)量子霸權(quán)也絕非易事。英國布里斯托大學(xué)、倫敦帝國理工學(xué)院、意大利羅馬大學(xué)等科學(xué)家相繼發(fā)文，引用吳俊杰和金賢敏的成果，論證當(dāng)前的技術(shù)水平離實(shí)現(xiàn)量子霸權(quán)也依然存在不小差距。當(dāng)前，國際最高水平的玻色采樣量子裝置，是中科大實(shí)現(xiàn)的 5 光子實(shí)驗(yàn)。

值得關(guān)注的另一種量子霸權(quán)測試案例，是隨機(jī)量子線路采樣問題，國內(nèi)外科學(xué)家同樣用超級(jí)計(jì)算機(jī)進(jìn)行這一問題的稱霸標(biāo)準(zhǔn)測試。2016 年 7 月，Google 科學(xué)家在 arXiv 上發(fā)文，測試了 Edison 超級(jí)計(jì)算機(jī)（當(dāng)時(shí)排名世界第 39）求解這一問題的性能；次年 3 月，他們?cè)?Nature 上發(fā)表評(píng)論文章，認(rèn)為 49 個(gè)量子比特、深度為 25 的隨機(jī)量子線路是這個(gè)案例的稱霸標(biāo)準(zhǔn)。這掀起了 Google、IBM 等的「量子霸權(quán)爭奪戰(zhàn)」，爭相展示各自的隨機(jī)線路采樣量子屠龍刀雛形。而與此同時(shí)，科學(xué)家們不斷改進(jìn)方法，隨機(jī)線路采樣問題的稱霸門檻也被不斷提高：IBM 科學(xué)家在去年 10 月將稱霸標(biāo)準(zhǔn)提升至 56 個(gè)量子比特；今年 2 月，門檻再次被中科大提升至 72 個(gè)量子比特。中國科學(xué)院院士楊學(xué)軍：「高性能計(jì)算已經(jīng)成為現(xiàn)代科學(xué)技術(shù)研究中必不可少的重要手段。未來，超級(jí)計(jì)算機(jī)將會(huì)在量子計(jì)算科學(xué)與技術(shù)的發(fā)展進(jìn)步中發(fā)揮更大作用！」

量子計(jì)算是物理學(xué)、計(jì)算機(jī)科學(xué)、數(shù)學(xué)、材料學(xué)、光學(xué)等眾多學(xué)科的前沿交叉方向，研究前路依然充滿艱難險(xiǎn)阻！現(xiàn)在，吳俊杰所在的國防科大成立了首個(gè)計(jì)算機(jī)學(xué)科的量子信息研究所，金賢敏也已回國在上海交大組建了光子集成與量子信息實(shí)驗(yàn)室。我們相信，在所有科學(xué)家的共同努力下，量子計(jì)算一定能給我們創(chuàng)造更美好的未來！

論文：A benchmark test of boson sampling on Tianhe-2 supercomputer

論文地址：https://doi.org/10.1093/nsr/nwy079

摘要：一種被認(rèn)為用經(jīng)典計(jì)算難以有效處理的問題——玻色采樣，可以通過量子計(jì)算來有效解決。玻色采樣量子計(jì)算，僅需要擁有光子生成、線性演化和探測技術(shù)就可以實(shí)現(xiàn)。這種解決特定問題的模擬式量子計(jì)算機(jī)提供了一條捷徑，用來實(shí)際展示量子計(jì)算機(jī)擊敗經(jīng)典計(jì)算機(jī)的計(jì)算能力。然而，經(jīng)典計(jì)算機(jī)求解玻色采樣的能力上界尚未確定。因此，我們?cè)谔旌佣?hào)超級(jí)計(jì)算機(jī)上模擬了玻色采樣問題，該計(jì)算機(jī)在 2013-2016 年間六次位居世界第一。我們最大使用了天河二號(hào) 312,000 個(gè) CPU 內(nèi)核來計(jì)算矩陣的積和式，通過當(dāng)前最優(yōu)的積和式計(jì)算算法，我們推斷出天河二號(hào)的性能上界是約每 100 分鐘生成一個(gè) 50 光子樣本。此外，我們還發(fā)現(xiàn)了其中一種積和式計(jì)算算法的精度問題。

給定一個(gè) m x m 大小的幺正矩陣以及 n 個(gè)不可區(qū)分的玻色子（如圖 1b 所示），在經(jīng)典計(jì)算機(jī)上模擬玻色采樣的過程是從方程 (1) 描述的分布中進(jìn)行采樣來生成樣本：

式中，S=|s_1,...,s_m>是給定的輸入態(tài)，代表 s_i 個(gè)玻色子位于第 i 個(gè)輸入端，T=|t_1,...,t_m>是輸出態(tài)，代表 t_j 個(gè)玻色子位于第 j 個(gè)輸出端，U_{S,T} 是從 U 導(dǎo)出的 n x n 子矩陣。積和式計(jì)算是經(jīng)典計(jì)算機(jī)模擬玻色采樣過程中最耗時(shí)的任務(wù)，因?yàn)樗遣Ｉ蓸釉谟?jì)算復(fù)雜性理論中所表現(xiàn)出困難性的根源。因此，計(jì)算這個(gè) n x n 子矩陣 U_{S,T} 的積和式性能是從分布 Pr[S→T] 生成 n-光子采樣的性能的上界。在本文中，我們通過在天河二號(hào)上（如圖 1a 所示）測試兩種最高效的積和式計(jì)算算法來評(píng)估這個(gè)上界，結(jié)果表明天河二號(hào)需要大約 100 分鐘來生成一個(gè) 50 光子的樣本。

這兩種算法分別是 Ryser 算法和 BB/FG 算法，其計(jì)算時(shí)間復(fù)雜度都是 O(n^2·2^n)。

圖 2：可擴(kuò)展性。（a）和（b）展示了用 P 個(gè)節(jié)點(diǎn)來計(jì)算一個(gè) n x n 矩陣的積和式的執(zhí)行時(shí)間?！窣CPU」表示僅在 CPU 上運(yùn)行獲得的結(jié)果，「@Hybrid」表示在 CPU 和加速器異構(gòu)并行執(zhí)行獲得的結(jié)果。擬合曲線的斜率表明 n 每增加 1，執(zhí)行時(shí)間增長約 1.95 倍，而計(jì)算節(jié)點(diǎn)每加倍，執(zhí)行時(shí)間減少約 0.52-0.56 的比例。（c）是 Ryser 算法用 P 個(gè)節(jié)點(diǎn)來計(jì)算 n x n 矩陣的積和式的執(zhí)行時(shí)間。校正 R 平方統(tǒng)計(jì)系數(shù)是 0.9996，表明擬合結(jié)果良好。（d）是 BB/FG 算法的擬合執(zhí)行時(shí)間。黑點(diǎn)是使用天河二號(hào)全系統(tǒng)來計(jì)算 50x50 矩陣的積和式的預(yù)測時(shí)間。

由于精度問題，我們使用 BB/FG 而不是 Ryser 算法的擬合執(zhí)行時(shí)間數(shù)據(jù)，來分析天河二號(hào)的性能極限。擬合方程如下：

擬合結(jié)果如圖 2（d）所示，表明使用所有 CPU 和加速器的天河二號(hào)全系統(tǒng)計(jì)算 50x50 矩陣的積和式執(zhí)行時(shí)間大約是 93.8 分鐘，其 95% 置信區(qū)間是 [77.41, 112.44] 分鐘，這意味著天河二號(hào)的執(zhí)行時(shí)間上界是約每 100 分鐘生成一個(gè) 50 光子樣本。

結(jié)語

在本文中，我們推斷了天河二號(hào)超級(jí)計(jì)算機(jī)模擬玻色采樣性能的上界。因?yàn)樘旌佣?hào)是 2013 年至 2016 年間最快的經(jīng)典計(jì)算機(jī)，所以這個(gè)界限只是針對(duì)當(dāng)時(shí)的經(jīng)典計(jì)算機(jī)。由于硬件進(jìn)步和軟件優(yōu)化，經(jīng)典計(jì)算機(jī)的性能也在不斷提高，因此，這一性能上界也會(huì)變得越來越高。此外，對(duì)兩種算法的精度評(píng)估表明，使用經(jīng)典計(jì)算機(jī)進(jìn)行實(shí)驗(yàn)驗(yàn)證時(shí)，BB/FG 算法應(yīng)是首選。