天河二號制定「量子霸權」標準，國防科大與上海交大聯合發表NSR論文
量子霸權的實現，將是量子計算髮展的一座重要里程碑，代表「量子計算的超強計算能力」自 37 年前提出以來首次從理論走進實驗，標誌一個新的計算能力飛躍時代的開始。近年來，隨著「實現量子霸權」的日益臨近，「稱霸標準」成為量子計算領域最重要的科學問題之一。
我國科學家最早開啟了「稱霸標準」問題的研究。最近，《國家科學評論》（National Science Review）以「A Benchmark Test of Boson Sampling on Tianhe-2 Supercomputer」為題正式發表了國防科技大學吳俊傑團隊與上海交通大學金賢敏教授的合作研究成果，報道了玻色取樣案例的「稱霸標準」。
圖 1：實現玻色取樣的計算任務：（a）天河二號超級計算機計算積和式；（b）光量子系統通過取樣輸出光子直接完成玻色取樣。
量子霸權
上世紀八十年代，費曼提出量子計算的概念。九十年代，科學家們發明了一批重要的量子演算法，在理論上發現量子計算擁有經典計算無法比擬的超強計算能力。人們開始意識到，量子計算機將是 IT 領域的「屠龍刀」，一旦實現將超越經典計算的極限。美國加州理工學院物理學家 John Preskill，將這種超越所有經典計算機的計算能力起名「量子霸權（quantum supremacy）」。
到目前為止，科學家仍未成功打造出能夠展示量子霸權的實際量子裝置。2010 年，MIT 科學家 Scott Aaronson 提出了可用於展示霸權的玻色取樣問題。玻色取樣是一種針對光子（玻色子）系統的量子霸權測試案例。理論上，經典計算機求解玻色取樣需要指數量級計算時間，而量子計算只需要多項式量級計算時間。與此同時，相比通用量子計算，玻色取樣更容易實現。
天河二號
玻色取樣的理論方案一經提出，全球科學家紛紛行動起來。2013 年，首批玻色取樣的原理實驗裝置問世，實現了 3-4 個光子的玻色取樣實驗。當時，金賢敏所在的牛津大學研究組，正是國際上最早實現玻色取樣實驗的團隊之一。
2013 年 9 月，國防科技大學的吳俊傑赴牛津訪問，與金賢敏交流起玻色取樣實現量子霸權所需的功力，發現科學家還未了解經典計算機的真正實力。當時，國防科大研製的天河二號超級計算機是經典計算領域的「倚天劍」，剛在超級計算機中奪得頭籌，計算能力排名全球第一。於是，兩人商定要驗驗天河倚天劍到底能劈開多大規模的玻色取樣問題，為玻色取樣量子屠龍刀立下稱霸標準。
經過嚴謹的測試與分析，他們的成果於 2016 年 6 月發表在預印版網站 arXiv 上。當時，天河二號正六次蟬聯超級計算機排行榜第一位。論文實際測試的問題規模達到 48 個光子，並推斷出天河二號完成 50 個光子玻色取樣的最高生成率約為每組樣本 100 分鐘。也就是說，一旦打造出「每組樣本 100 分鐘以內的 50 個光子玻色取樣」的量子屠龍刀，就在求解玻色取樣問題上超過了天河倚天劍的功力，實現了量子霸權。
量子霸權爭奪戰
值得指出的是，因為並不要求用於展示量子霸權的問題具有任何實際用途，「實現量子霸權」相較「實現實際的量子計算機」要簡單許多。而與此同時，「稱霸標準」的研究成果表明，當前實現量子霸權也絕非易事。英國布里斯托大學、倫敦帝國理工學院、義大利羅馬大學等科學家相繼發文，引用吳俊傑和金賢敏的成果，論證當前的技術水平離實現量子霸權也依然存在不小差距。當前，國際最高水平的玻色取樣量子裝置，是中科大實現的 5 光子實驗。
值得關注的另一種量子霸權測試案例，是隨機量子線路取樣問題，國內外科學家同樣用超級計算機進行這一問題的稱霸標準測試。2016 年 7 月，Google 科學家在 arXiv 上發文，測試了 Edison 超級計算機（當時排名世界第 39）求解這一問題的效能；次年 3 月，他們在 Nature 上發表評論文章，認為 49 個量子位元、深度為 25 的隨機量子線路是這個案例的稱霸標準。這掀起了 Google、IBM 等的「量子霸權爭奪戰」，爭相展示各自的隨機線路取樣量子屠龍刀雛形。而與此同時，科學家們不斷改進方法，隨機線路取樣問題的稱霸門檻也被不斷提高：IBM 科學家在去年 10 月將稱霸標準提升至 56 個量子位元；今年 2 月，門檻再次被中科大提升至 72 個量子位元。中國科學院院士楊學軍：「高效能運算已經成為現代科學技術研究中必不可少的重要手段。未來，超級計算機將會在量子計算科學與技術的發展進步中發揮更大作用！」
量子計算是物理學、電腦科學、數學、材料學、光學等眾多學科的前沿交叉方向，研究前路依然充滿艱難險阻！現在，吳俊傑所在的國防科大成立了首個計算機學科的量子資訊研究所，金賢敏也已回國在上海交大組建了光子整合與量子資訊實驗室。我們相信，在所有科學家的共同努力下，量子計算一定能給我們創造更美好的未來！
論文：A benchmark test of boson sampling on Tianhe-2 supercomputer
論文地址：https://doi.org/10.1093/nsr/nwy079
摘要：一種被認為用經典計算難以有效處理的問題——玻色取樣，可以通過量子計算來有效解決。玻色取樣量子計算，僅需要擁有光子生成、線性演化和探測技術就可以實現。這種解決特定問題的模擬式量子計算機提供了一條捷徑，用來實際展示量子計算機擊敗經典計算機的計算能力。然而，經典計算機求解玻色取樣的能力上界尚未確定。因此，我們在天河二號超級計算機上模擬了玻色取樣問題，該計算機在 2013-2016 年間六次位居世界第一。我們最大使用了天河二號 312,000 個 CPU 核心來計算矩陣的積和式，通過當前最優的積和式計算演算法，我們推斷出天河二號的效能上界是約每 100 分鐘生成一個 50 光子樣本。此外，我們還發現了其中一種積和式計算演算法的精度問題。
給定一個 m x m 大小的么正矩陣以及 n 個不可區分的玻色子（如圖 1b 所示），在經典計算機上模擬玻色取樣的過程是從方程 (1) 描述的分佈中進行取樣來生成樣本：
式中，S=|s_1,...,s_m>是給定的輸入態，代表 s_i 個玻色子位於第 i 個輸入端，T=|t_1,...,t_m>是輸出態，代表 t_j 個玻色子位於第 j 個輸出端，U_{S,T} 是從 U 匯出的 n x n 子矩陣。積和式計算是經典計算機模擬玻色取樣過程中最耗時的任務，因為它正是玻色取樣在計算複雜性理論中所表現出困難性的根源。因此，計算這個 n x n 子矩陣 U_{S,T} 的積和式效能是從分佈 Pr[S→T] 生成 n-光子取樣的效能的上界。在本文中，我們通過在天河二號上（如圖 1a 所示）測試兩種最高效的積和式計算演算法來評估這個上界，結果表明天河二號需要大約 100 分鐘來生成一個 50 光子的樣本。
這兩種演算法分別是 Ryser 演算法和 BB/FG 演算法，其計算時間複雜度都是 O(n^2·2^n)。
圖 2：可擴充套件性。（a）和（b）展示了用 P 個節點來計算一個 n x n 矩陣的積和式的執行時間。「@CPU」表示僅在 CPU 上執行獲得的結果，「@Hybrid」表示在 CPU 和加速器異構並行執行獲得的結果。擬合曲線的斜率表明 n 每增加 1，執行時間增長約 1.95 倍，而計算節點每加倍，執行時間減少約 0.52-0.56 的比例。（c）是 Ryser 演算法用 P 個節點來計算 n x n 矩陣的積和式的執行時間。校正 R 平方統計係數是 0.9996，表明擬合結果良好。（d）是 BB/FG 演算法的擬合執行時間。黑點是使用天河二號全系統來計算 50x50 矩陣的積和式的預測時間。
由於精度問題，我們使用 BB/FG 而不是 Ryser 演算法的擬合執行時間資料，來分析天河二號的效能極限。擬合方程如下：
擬合結果如圖 2（d）所示，表明使用所有 CPU 和加速器的天河二號全系統計算 50x50 矩陣的積和式執行時間大約是 93.8 分鐘，其 95%置信區間是 [77.41, 112.44] 分鐘，這意味著天河二號的執行時間上界是約每 100 分鐘生成一個 50 光子樣本。
結語
在本文中，我們推斷了天河二號超級計算機模擬玻色取樣效能的上界。因為天河二號是 2013 年至 2016 年間最快的經典計算機，所以這個界限只是針對當時的經典計算機。由於硬體進步和軟體優化，經典計算機的效能也在不斷提高，因此，這一效能上界也會變得越來越高。此外，對兩種演算法的精度評估表明，使用經典計算機進行實驗驗證時，BB/FG 演算法應是首選。