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

我國(guó)科學(xué)家最早開(kāi)啟了「稱霸標(biāo)準(zhǔn)」問(wèn)題的研究,。最近,，《國(guó)家科學(xué)評(píng)論》（National Science Review）以「A Benchmark Test of Boson Sampling on Tianhe-2 Supercomputer」為題正式發(fā)表了國(guó)防科技大學(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)通過(guò)采樣輸出光子直接完成玻色采樣。

量子霸權(quán)

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

到目前為止,，科學(xué)家仍未成功打造出能夠展示量子霸權(quán)的實(shí)際量子裝置。2010 年，MIT 科學(xué)家 Scott Aaronson 提出了可用于展示霸權(quán)的玻色采樣問(wèn)題,。玻色采樣是一種針對(duì)光子（玻色子）系統(tǒng)的量子霸權(quán)測(cè)試案例,。理論上，經(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)起來(lái),。2013 年,，首批玻色采樣的原理實(shí)驗(yàn)裝置問(wèn)世，實(shí)現(xiàn)了 3-4 個(gè)光子的玻色采樣實(shí)驗(yàn),。當(dāng)時(shí),，金賢敏所在的牛津大學(xué)研究組，正是國(guó)際上最早實(shí)現(xiàn)玻色采樣實(shí)驗(yàn)的團(tuán)隊(duì)之一,。

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

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

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

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

值得關(guān)注的另一種量子霸權(quán)測(cè)試案例,，是隨機(jī)量子線路采樣問(wèn)題,，國(guó)內(nèi)外科學(xué)家同樣用超級(jí)計(jì)算機(jī)進(jìn)行這一問(wèn)題的稱霸標(biāo)準(zhǔn)測(cè)試。2016 年 7 月,，Google 科學(xué)家在 arXiv 上發(fā)文,，測(cè)試了 Edison 超級(jí)計(jì)算機(jī)（當(dāng)時(shí)排名世界第 39）求解這一問(wèn)題的性能；次年 3 月,，他們?cè)?Nature 上發(fā)表評(píng)論文章,，認(rèn)為 49 個(gè)量子比特、深度為 25 的隨機(jī)量子線路是這個(gè)案例的稱霸標(biāo)準(zhǔn),。這掀起了 Google,、IBM 等的「量子霸權(quán)爭(zhēng)奪戰(zhàn)」，爭(zhēng)相展示各自的隨機(jī)線路采樣量子屠龍刀雛形,。而與此同時(shí),，科學(xué)家們不斷改進(jìn)方法，隨機(jī)線路采樣問(wèn)題的稱霸門(mén)檻也被不斷提高：IBM 科學(xué)家在去年 10 月將稱霸標(biāo)準(zhǔn)提升至 56 個(gè)量子比特,；今年 2 月,，門(mén)檻再次被中科大提升至 72 個(gè)量子比特。中國(guó)科學(xué)院院士楊學(xué)軍：「高性能計(jì)算已經(jīng)成為現(xiàn)代科學(xué)技術(shù)研究中必不可少的重要手段,。未來(lái),，超級(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)在，吳俊杰所在的國(guó)防科大成立了首個(gè)計(jì)算機(jī)學(xué)科的量子信息研究所,，金賢敏也已回國(guó)在上海交大組建了光子集成與量子信息實(shí)驗(yàn)室,。我們相信，在所有科學(xué)家的共同努力下,，量子計(jì)算一定能給我們創(chuàng)造更美好的未來(lái),！

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

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

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

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

式中，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ī)模擬玻色采樣過(guò)程中最耗時(shí)的任務(wù),，因?yàn)樗遣Ｉ蓸釉谟?jì)算復(fù)雜性理論中所表現(xiàn)出困難性的根源,。因此，計(jì)算這個(gè) n x n 子矩陣 U_{S,T} 的積和式性能是從分布 Pr[S→T] 生成 n-光子采樣的性能的上界,。在本文中,，我們通過(guò)在天河二號(hào)上（如圖 1a 所示）測(cè)試兩種最高效的積和式計(jì)算算法來(lái)評(píng)估這個(gè)上界，結(jié)果表明天河二號(hào)需要大約 100 分鐘來(lái)生成一個(gè) 50 光子的樣本,。

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

圖 2：可擴(kuò)展性。（a）和（b）展示了用 P 個(gè)節(jié)點(diǎn)來(lái)計(jì)算一個(gè) n x n 矩陣的積和式的執(zhí)行時(shí)間,?！窣CPU」表示僅在 CPU 上運(yùn)行獲得的結(jié)果，「@Hybrid」表示在 CPU 和加速器異構(gòu)并行執(zhí)行獲得的結(jié)果,。擬合曲線的斜率表明 n 每增加 1,，執(zhí)行時(shí)間增長(zhǎng)約 1.95 倍，而計(jì)算節(jié)點(diǎn)每加倍,，執(zhí)行時(shí)間減少約 0.52-0.56 的比例,。（c）是 Ryser 算法用 P 個(gè)節(jié)點(diǎn)來(lái)計(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)來(lái)計(jì)算 50x50 矩陣的積和式的預(yù)測(cè)時(shí)間,。

由于精度問(wèn)題,，我們使用 BB/FG 而不是 Ryser 算法的擬合執(zhí)行時(shí)間數(shù)據(jù)，來(lái)分析天河二號(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é)語(yǔ)

在本文中，我們推斷了天河二號(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ì)變得越來(lái)越高,。此外,，對(duì)兩種算法的精度評(píng)估表明，使用經(jīng)典計(jì)算機(jī)進(jìn)行實(shí)驗(yàn)驗(yàn)證時(shí),，BB/FG 算法應(yīng)是首選,。