量子計算理論專家解讀“谷歌實現量子霸權”，你看懂了嗎？_風聞

最近，谷歌聲稱實現 “量子霸權”，打造出第一台能夠超越當今最強大的超級計算機能力的量子計算機！

該計算機能夠在3 分 20 秒內執行一個計算，而同樣的計算用當今最強大的超級計算機 Summit 進行，需要約 10000 年。這被認為是量子計算里程碑式的進展！

谷歌的論文一開始在NASA網站上發佈，但不久被悄悄刪除，但論文仍通過各種渠道流傳，關於谷歌的“量子霸權”研究，我們也得以一窺究竟。

論文地址：

https://drive.google.com/file/d/19lv8p1fB47z1pEZVlfDXhop082Lc-kdD/view

今天，著名理論計算機科學家、量子計算專家Scott Aaronson在個人網站就谷歌的“量子霸權”研究進行了FAQ解答，他認為谷歌的正式論文可能會在一個月內在某知名期刊（哪本期刊？選項可以縮小到2個）發表。Scott Aaronson分析了谷歌的量子霸權實驗、量子霸權本身是否有任何應用、谷歌下一步是什麼等問題。

Scott Aaronson 何許人也？

**Scott Aaronson，美國理論計算機科學家，德州大學奧斯汀分校計算機科學教授，量子信息中心主任。**此前曾與麻省理工學院電子工程與計算機科學系任教多年，研究領域包括量子計算機的性能與侷限，更廣義的計算複雜度理論等。在MIT期間，Scott曾是姚班學霸陳立傑的導師。

 

Scott Aaronson

Aaronson 在康奈爾大學獲計算機科學專業學士學位，在加州大學伯克利分校獲博士學位，在加拿大滑鐵盧大學量子計算研究所做博士後研究員。2007-2016 年在麻省理工學院任教，2007 年秋任助理教授，2013 年春晉升為副教授。2016 年至今在德州大學奧斯汀分校任教，任全職教授。著有《德謨克利特以來的量子計算》。

他的個人博客 “Shtetl-Optimized” 經常從科普向角度解答一些關於量子計算的問題，一直廣受歡迎。他撰寫的《誰可以命名更大的數字？》一文在計算機科學學術界中得到了廣泛傳播，文中使用了 Tibor Radó 所描述的 Busy Beaver Numbers 的概念來説明在教學環境中可計算性的侷限性。

他講授的面向研究生的調查課程《自德謨克利特以來的量子計算》的講義已由劍橋大學出版社出版。書中將關於量子計算的不同主題編成一個整體，其中涵蓋量子力學、複雜度、自由意志、時間旅行、人類準則等內容。

知名科普期刊《科學美國人》曾發表了他的《量子計算機的侷限性》一文，他的觀點和言論也經常被大眾主流媒體所引用。

“量子霸權”15問：沒有破解不了的密碼了嗎？非也

**Q1：**什麼是量子計算霸權?

通常縮寫為“量子霸權”(quantum supremacy)，這個術語指的是利用量子計算機來解決一些定義明確的問題，而這些問題如果使用現有的經典計算機和已知算法來解決，需要的時間是數量級更長的。這不是偶然的原因，而是由於漸進量子複雜性。

這裏的重點是，要儘可能確定這個問題確實已經被量子計算機解決了，並且確實對於經典計算機而言是棘手的，並且在理想情況下能夠很快實現加速。如果這個問題對某件事也有用，那就更好了，但這完全沒有必要。萊特飛行器和費米堆本身並沒有什麼用處。

**Q2：**如果谷歌真的實現了量子霸權，是否意味着正如民主黨總統候選人安德魯・楊（Andrew Yang）最近在推特上所説的那樣，現在“沒有什麼密碼是不可破解的”？

不是這樣。(但我仍然喜歡楊。)

這裏有兩個問題。首先，目前由谷歌、IBM和其他公司製造的設備具有50-100個量子比特，而且沒有糾錯功能。運行 Shor算法來破解RSA密碼系統將需要數千個邏輯量子比特。使用已知的糾錯方法，可以很容易地轉換成數百萬個物理量子比特，而且這些量子比特的質量比目前存在的任何一種都要高。我認為現在沒有人能做到這一點，我們也不知道需要花多長時間。

但第二個問題是，根據我們目前的理解，即使未來擁有可擴展的、有糾錯功能的量子計算機，它們也只能破解某些密碼，而不是全部。不幸的是，他們能夠破解的公鑰密碼包括了我們目前用來保護互聯網安全的大部分內容：RSA、Diffie-Hellman、橢圓曲線加密等等。但是私鑰密碼受到的影響應該很小。甚至還有一些候選的公鑰密碼系統(例如，基於lattices的)，經過20多年的嘗試，仍然沒有人知道如何進行量子破解。現在正在進行的一些工作，已經開始遷移到這些系統了。

**Q3.：**谷歌計劃進行或已經完成了哪些通常認為經典計算機很難做到的計算？

它計算的是：一個“challenger”生成一個隨機量子電路C(即一個由1個量子比特和最近鄰的2個量子比特組成的隨機序列，深度為20，作用於n=50至60 qubits的二維網格上)。然後，challenger將C發送到量子計算機，並要求它將C應用於全部為0的初始狀態，以{0,1}為基礎來測量結果，並返回所觀察到的所有n-bit字符串，並重複數千次甚至數百萬次。最後，challenger利用統計檢驗來來檢查輸出是否與量子計算機所做的一致。

所以，這不是一個因式分解問題。電路C在n-bit字符串上產生了一些概率分佈，稱為DC，問題是從這個分佈中輸出樣本。事實上，通常會有2^n個字符串支持DC，如此之多，以至於如果量子計算機按預期工作，將永遠不會觀察到相同的輸出兩次。然而，關鍵的一點是，DC的分佈並不均勻。雖然我們只會觀察到與2^n相比很小的樣本，但我們可以檢查樣本是否優先地聚集在預測更有可能的字符串中，從而建立起我們對完成傳統上棘手的事情的信心。

一句話總結：量子計算機只是被要求應用一個隨機(但已知的)量子操作序列——不是因為我們關心結果，而是因為我們試圖證明它能在一些定義明確的任務上擊敗經典計算機。

**Q4：**但是，如果量子計算機只是執行一些隨機的電路，其唯一的目的就是經典計算機難以模擬，那麼有什麼意義呢？這不是過度宣傳嗎?

當然有意義。

要對我們在這裏所談論的巨大規模，以及使它成為現實所需要的可怕的工程，有一點尊重。達到量子霸權之前，量子計算機懷疑論者可以嘲笑，因為花了數十億美元、20多年，仍然沒有一台量子計算機能比筆記本電腦更快地解決一個問題。在後量子霸權的世界，情況將不再是這樣。

我再次提到萊特飛行器，因為我們正在談論的內容與我在互聯網上見到的人們的不屑一顧之間的鴻溝，對我來説非常令人驚訝。就好像，如果你堅信空中旅行從根本上就是不可能，那麼看到一架木製螺旋槳飛機保持在高空飛行不會改變你的信念，但也不會讓你感到放心。

**Q5：**幾年前，你批評大眾對D-Wave過於興奮，而它聲稱通過量子退火可以極大地加速優化問題。但現在，你又批評大眾對量子霸權不夠興奮。這是為什麼？

因為我的目標不是朝着大眾偏愛的方向發展“興奮水平”，而是朝着正確的方向！事後看來，你會承認我對D-Wave的看法基本上是正確的，即使那讓我在一些圈子裏非常不受歡迎。我也在努力證明我對量子霸權的觀點是正確的。

**Q6：**如果量子霸權的計算只涉及從概率分佈中採樣，你如何驗證它們是否正確?

好問題！這是我和其他人在過去十年中發展起來的大量理論的主題。我已經在我對Q3的回答中給出了一個簡短的版本：通過對QC返回的樣本進行統計來驗證，檢驗它們優先聚集在混沌概率分佈DC的“峯值”。有一個簡便的方法，谷歌稱為“線性交叉熵檢驗”，就是將量子計算機返回的所有樣本s1,…, sk的Pr[C outputs si]相加，然後求和。當且僅當總和超過某個閾值（例如 bk/2^n, 常數b介於1和2之間）時，才聲明測試 “成功” 。

誠然，為了應用這個測試，你需要在經典計算機上計算Pr[C output si]的概率，而唯一已知的計算它們的方法需要蠻力，並且需要大約2^n的時間。如果n是50，並且你是谷歌，那麼是有能力處理2^50這樣的數字的。通過運行一個巨大的經典內核集羣(比方説)一個月，你最終可以驗證量子計算機幾秒鐘內生成的輸出——同時還可以計算量子計算機快了多少個數量級。然而，這確實意味着基於採樣的量子霸權實驗幾乎是專為目前正在建造的50量子比特設備而設計的。如果有100個量子比特，我們可能就不知道如何使用地球上所有可用的經典計算能力來驗證結果了。

**Q7：**等等，如果經典計算機只能檢驗量子霸權實驗的結果，在一個經典計算機仍能模擬實驗(儘管速度極慢)的體制下，那麼你怎麼能宣稱“量子霸權”呢?

對於一個53量子比特的芯片，在一個仍然可以直接驗證輸出結果的系統中，你完全有可能看到速度增加了數百萬倍，同時你也可以看到速度隨着量子比特的數量呈指數增長，這與漸近分析所預測的完全一致。

**Q8：**是否有數學證據證明沒有任何快速的經典算法能夠欺騙基於採樣的量子霸權實驗的結果?

不，目前沒有。但這並不是量子霸權研究人員的錯！只要理論計算機科學家不能證明P≠NP或P≠PSPACE這樣的基本猜想，就不可能無條件地排除快速經典模擬的可能性。我們所能期望的最好結果是 conditional hardness。

我們確實成功地證明了一些這樣的結果——例如玻色子採樣那篇論文，或者Bouland等人關於隨機電路中振幅計算的平均情況#P-hardness的論文，或者我與陳立傑合著的論文(“Complexity-Theoretic Foundations of Quantum Supremacy Experiments”)。在我看來，這方面最大的理論開放問題是證明更好的 conditional hardness結果。

**Q9：**基於採樣的量子霸權本身有什麼應用嗎?

人們第一次想到這個問題時，答案顯然是“毫無用處”！不過，最近情況發生了變化，例如，由於認證隨機性協議，顯示了一個基於採樣的量子霸權實驗幾乎可以立即被重新利用，從而生成可以被懷疑是隨機的比特(在計算假設下)。反過來，這可能適用於持有量證明加密貨幣(proof-of-stake cryptocurrencies)和其他加密協議。我希望在不久的將來能發現更多這樣的應用。

**Q10：**如果量子霸權實驗只是產生隨機比特，那不是很無趣嗎？僅僅通過測量就能把量子比特轉換成隨機比特，這不是很簡單嗎?

量子霸權實驗不會產生均勻的隨機比特。相反，它從一些複雜的、相關的、超過50或60位字符串的概率分佈中採樣。

**Q11：**數十年的量子力學實驗——例如，那些違反貝爾不等式的實驗——難道還沒有證明量子霸權嗎?

這純粹是文字上的混淆。其他的實驗證明了“量子霸權”的其他形式：例如，在違反貝爾不等式的情況下，你可以稱之為“quantum correlational supremacy”。他們沒有展示量子計算的優勢，這意味着是不可能用經典計算機模擬的事情(在經典計算機模擬中沒有空間局域性或其他類似的限制)。今天，當人們使用“量子霸權”這個短語時，它通常是量子計算霸權(quantum computational supremacy)的縮寫。

**Q12：即便如此，目前仍然有無數材料和化學反應無法用經典方法實現模擬，而且現在也出現大量特定用途的量子模擬器。**為什麼這些都不算是實現了 “量子霸權”？

如果按照一些人對 “量子霸權” 的定義，確實已經實現了！這次谷歌實現的與他們的主要區別在於，有了完全可編程的設備，可以通過傳統計算機發送適當的信號，使用任意序列的最近鄰的 2 - 量子比特門進行編程。

換句話説，這下量子計算的懷疑論者肯定會不高興了，可以肯定的是，有些量子系統很難用經典方法模擬，但這僅僅是因為大自然確實很難模擬，而且你不能把發現的什麼化學物質隨意重新定義為 “可以自我模擬的計算機。” 現在，在任何正常的定義下，谷歌、IBM 和其他公司正在建造的超導設備都的確是 “計算機”。

Q13：“量子霸權” 的概念是你發明的嗎？

不是，但我在開發上發揮了一些作用，這導致薩賓・霍森費爾德（Sabine Hossenfelder）等人誤以為整個概念都是我提出的。 “量子霸權” 一詞是約翰・普雷斯基爾（John Preskill）在 2012 年提出的，儘管從某種意義上説，其核心概念可以追溯到 1980 年代初的量子計算本身。1994 年，使用 Shor 算法來分解大量數據成為 “量子霸權” 實驗的手段，不過即使在現在，這個實驗仍然很難執行。

使用採樣問題來證明 “量子霸權” 的關鍵思想是由 Barbara Terhal 和 David DiVincenzo 在 2002 年發表的一篇有遠見的論文中首次提出的。當時出現了一批論文，不僅表明 “簡單的” 非通用量子系統可以解決看似困難的採樣問題，而且面向相同採樣問題的有效經典算法將意味着多項式層次結構的崩潰。即使是近似量子採樣問題，用經典方法解決也是非常困難的。

據我所知，“隨機電路採樣” 的思路源於我在 2015 年 12 月發起的一次電子郵件對話，參與成員還包括 John Martinis，Hartmut Neven，Sergio Boixo，Ashley Montanaro，Michael Bremner，Richard Jozsa，Aram Harrow，Greg Kuperberg 等人。該對話的標題為 “40 量子比特的硬採樣問題”。

當時我們討論了三種基於採樣方法的 “量子霸權” 方法的優缺點：（1）隨機電路，（2）對易的哈密頓量（commuting Hamiltonians），以及（3）玻色子取樣（Boson Sampling）。在 Greg Kuperberg 提出支持方案（1）的意見後，我們迅速達成共識，即從工程學的角度來看方案（1）確實是最好的選擇，即使理論分析仍不能令人滿意，也可以補救。。

之後，Google 團隊對理論和數值上的隨機電路採樣進行了大量分析，而 Lijie Chen、Bouland 和我則對此進行了分析，從理論上證明了用經典方法解決這類問題的難度。

Q14：如果量子霸權真的實現了，對於量子計算的懷疑論者而言意味着什麼？

我現在可不想成為他們的一員！他們當然可以退一步説，量子霸權是可能實現的（誰敢説絕對不可能？），其實真正的問題一直是 “量子糾錯”。確實，這些人中有些人始終保持這個立場。但是其他人，包括我的好朋友吉爾・凱萊（Gil Kalai）在內都曾經預測過，説出於根本原因，量子霸權不可能實現。現在把話收回去好像有點晚了。

Q15：下一步呢？

如果實現了量子霸權，那麼我認為 Google 團隊已經有了必要的硬件來執行我提出的協議，生成認證的隨機比特了。他們下一步確實計劃這麼做。

除此之外，顯而易見的下一個里程碑將是可編程量子計算機的應用（如 50-100 量子比特），可以比任何已知的經典方法更快執行一些有用的量子模擬任務（如凝聚態系統）。此外，“量子糾錯” 將走向應用，可以使編碼的量子比特存活時間長於基礎物理量子比特的存活時間。

毫無疑問，谷歌，IBM 等領跑者將朝着這兩個重要里程碑邁進。

谷歌“量子霸權”的論文究竟講了什麼？MIT 量子物理博士生專業解讀

儘管NASA在上線谷歌“量子霸權”的論文不久後悄悄撤下，這篇論文仍通過各種渠道流傳出來。MIT 量子物理專業博士生（知乎 ID：少司命）從專業角度，以通俗的語言解釋了谷歌這篇論文的主要內容。新智元經授權轉載如下：

毫無疑問的是，這會是量子計算領域一個里程碑一樣的大新聞.

9 月 20 號剛剛看到這個消息，據説是 NASA 發佈到官網上而後又迅速刪掉，但是內容已經在網上大規模流傳開了。文章寫的非常簡單易懂，我儘量用簡單的語言陳述一下這個新聞的主要內容吧 (蹭熱度)，如果沒有任何背景可以只看加粗字體部分。如果哪裏不準確歡迎指正補充。

首先一個概念，所謂的 quantum supremacy，有人翻譯為量子優勢也有人翻譯為量子霸權，一般指的是量子計算在某一個問題上，可以解決經典計算機不能解決的問題或者是比經典計算機有顯著的加速 (一般是指數加速)。

**回到文章，在硬件方面，谷歌家一直用的是超導電路系統，這裏是 54 個物理比特 (transmon) 排成陣列，**每個比特可以與臨近的四個比特耦合在一起，耦合強度可調 (從 0 到大概 40MHz)，實物圖和示意圖分別如下。

圖中一個灰色的叉號就代表一個量子比特，藍色的則是可調的耦合裝置

**有了硬件就要衡量其性能的好壞，所以首先要知道對這些量子比特進行操作時發生錯誤的概率 (error rates)。**這裏他們用 cross-entropy benchmarking (XEB) 的方法測量這些 error。XEB 早就有了我記得 google 在今年 3 月會議時候就講過，跟 randomized bechmarking 很像都是加一系列隨機的門操作，然後從保真度衰減信號中提取出 error rates。

下圖是他們最終得到的結果，在沒有並行時候單比特 0.15% 的錯誤率其實不算高，而雙比特 0.36% 的錯誤率 e2 有 0.36% 則還不錯，像 google 另一個 18 比特的 Gmon18 我記得兩比特的有 0.8%。

上面列了各個 error rate, 下面是 error 分佈的 heat map.

下面是文章最重要的部分，google 在多項式時間內實現了對一個隨機量子電路的採樣，而在已知的經典計算機上需要的時間則非常非常之久，像文中實現的最極端的例子是，對一個 53 比特 20 個 cycle 的電路採樣一百萬次，在量子計算機上需要 200 秒，而用目前人類最強的經典的超級計算機同樣情況下則需要一萬年。亦即在這個問題上，量子實現了對經典的超越。

這裏的 cycle 指的是對這些比特做操作的數目，一個 cycle 包含一系列單比特操作和雙比特操作，可以近似理解為電路的深度 (circuit depth)。對於最大的電路，即 53 個比特 20 個 cycle 的情況，在量子處理器上做一百萬次採樣後得到 XEB 保真度大於 0.1% (5 倍置信度)，用時大概 200 秒。而要在經典計算機上模擬的話，因為比特數目很多整個的希爾伯特空間有

而且還有那麼多電路操作，這已經超出了我們現在超級計算機的能力 (within considerable time)，就像文中舉的另一個例子，用 SFA 算法大概需要 50 萬億 core-hour (大概是一個 16 核處理器運行幾億年吧), 加 Wh 的能量 (也就是一萬億度電…)，可以想見是多麼難的事情了。而量子這個問題上為啥會比經典好也非常容易理解，用到的就是量子運算的並行性，即量子態可以是疊加態可以在多項式時間內遍歷整個希爾伯特空間，而經典計算機模擬的話需要的資源則是隨着比特數目指數增加的。

左邊圖 a 是經典計算機可以模擬的區域，右邊圖 b 則是量子有優勢的區域。紅色數據點為最複雜的電路，綠藍代表兩種稍作簡化後的電路。

​

當然有沒有可能是有些更好的經典採樣算法和量子的差不多，只是我們沒有找到呢？文中沒有給出很直接的回答，他們認為從複雜度分析來講經典算法總是會隨着比特數和 cycle 指數增加的，而且即使未來有一些更好的經典算法，到時候量子的處理器也發展了所以還是會比經典的好。

最後個人的一點 comment, **振奮的同時也要保持清醒，我們離着實現量子計算的完全功力還有很遠的距離。**硬件上有集成化的問題，比如這裏的超導比特系統要加微波 control 要諧振腔 readout，比特數目增加後有空間不足和 cross-talk 等各種問題，遠遠不止我們圖中看到的一個小芯片那麼簡單；再一個比特數多了電路深度大了怎麼繼續提高保真度也是很大問題，像這篇文章裏 53 個比特到第十幾個 circuit cycle 時候保真度只有 10 的負二次方量級了，怎麼 decorrelate error 實現量子糾錯，最終實現容錯量子計算等等，這些都是硬件上的挑戰；

算法上，除了這裏的採樣問題（由此延伸的可以解決的問題其實是非常有限的），又有哪些問題是可以證明量子比經典有顯著優勢的，可不可以設計一些算法使得量子計算機能解決經典不能解決的問題，或者量子比經典有顯著的加速，就像文章最後所説的：

…As a result of these developments, quantum computing is transitioning from a research topic to a technology that unlocks new computational capabilities. We are only one creative algorithm away from valuable near-term applications.

在 NISQ (noisy-intermediate scale quantum computer) 的時代 (如下圖)，雖然我們離綠色真正的容錯通用量子計算機還很遠，但是現在已經開始進入到藍色區域相信在未來幾年會有一些有趣的 near-term 的應用出現。

橫座標比特數目越大越好，縱座標錯誤率越小越好

回答一下大家關心的問題吧，以下是個人觀點：

一個是中國在這方面有什麼進展，我們國家在近些年在量子方面投入很大，很多組也做出了許許多多非常突出的貢獻，但必須承認的是，至少在我們在文中提到的用超導比特去做通用量子計算機這方面確實還有着比較明顯的差距，但是道路是曲折的前途是光明的，我相信國內一定會迎頭趕上並在很多領域做出超越的。現在無論學校科研院所還是大企業都有投入和發力，只不過具體方向會不一樣很多優秀的成果也沒有得到媒體的關注。

再一個問題就是很多同學表示還是看不太懂，確實沒有相關背景瞭解起來會比較吃力，既準確又通俗的科普是件很難的事…anyway, 還是我在文中強調的，文章的內容是量子計算重要的一步但是其應用是非常非常有限的，以後的路仍道阻且長，我們離着可以破解 RSA 密碼離着量子計算機的大規模普及還很遠，而且量子計算機也是不可能取代現在用的經典計算機的，這些應該是現在的業內共識。