史丹佛、柏克萊新研究推翻Google「量子霸權」！理論上很美，其實沒戲

量子霸權，這個字已經誕生了近4年了。

2019年，Google的物理學家宣布成功用一台53量子位元的機器實現了量子霸權，這是一個具有重大象徵的里程碑。

在Nature上發表的論文中稱，該量子系統只用了200秒完成一個計算，而同樣的計算用當時最強大的超級計算機Summit執行，需要約10000年。

什麼是量子霸權？

所謂「量子霸權」，或稱為「量子優勢」（以下稱為「量子霸權」）是指，量子電腦能完成的任務超出了任何可行經典演算法的範圍。

這些任務即使放在最先進的傳統超級電腦上，運算時間之長（往往是成千上萬年）也會讓演算法失去實用意義。

有趣的是，在2019年Google的成果中，只說了實現了量子霸權，沒有說明在哪些具體實例下，量子電腦超過了經典電腦。

這是一個很難回答的問題，因為目前量子電腦受到錯誤頻率的困擾，這些錯誤會累積，破壞量子運算的效能和穩定性。

實際上，與量子霸權的實現領域相比，科學家更想知道的是另一個問題：隨著量子電腦越來越大，經典演算法是否能夠跟上腳步。

德州大學奧斯汀分校的電腦科學家Scott Aaronson說：「我們希望最終量子一方會完全拉開距離，徹底結束這場競爭。」

大多數研究人員推測，答案是否定的。

即經典演算法總有一天會徹底跟不上量子運算的腳步，但一直無法準確全面地證明這一點。要確定證明這個推論，一個途徑是找到量子計算能夠獲得相對於傳統計算「持久優勢」的條件。

現在，這個問題似乎有了初步答案：

#省流：量子運算是會產生錯誤的，如果糾錯跟不上，這種錯誤就會打破理想狀態下的「量子霸權」，讓經典演算法跟上量子演算法的腳步。

最近，在一篇Arxiv上發表的預印本論文中，由哈佛大學、加州大學柏克萊分校、以色列希伯來大學的聯合團隊朝著證實這個結論邁出了一大步。

他們證明了，目標錯誤修正是隨機電路取樣中持久量子霸權的必要條件，為幾年前Google的研究結論提供了支撐。在目前的量子糾錯水準下，量子霸權其實是並不存在的。

再無量子霸權「黃金地帶」

研究人員開發了一種經典演算法，可以模擬有錯誤時的隨機電路取樣實驗來證明這個結論。

從一個量子位元陣列開始，用被稱為「量子閘」的操作隨機操縱這些量子位元。有些量子閘會使成對的量子位元處於糾纏態，即意味著彼此共享一個量子態，不能被單獨描述。

在多層電路中重複設定這些量子閘門，可以讓量子位元進入更複雜的糾纏態。

左圖為理想狀態下的隨機電路取樣，右圖為包含幹擾的隨機電路取樣

為了了解這種量子態，研究人員測量了陣列中的所有量子位元。這個行為會導致所有量子位元的集體量子態坍縮為一串隨機的普通位元，即0和1。

可能的結果數量隨著陣列中的量子位元數量的增加而迅速增長。在Google2019年的實驗中，53個量子位元下包含近10兆個的結果。

而且，這種方法需要從隨機電路中多次重複測量，建立一個關於結果的機率分佈圖。

關於量子霸權的問題是，用一個不使用任何糾纏的經典演算法，來模仿這種機率分佈，是否很難甚至不可能？

2019年，Google研究人員證明，對於無誤差、不會產生錯誤的量子電路來說，這個目標是困難的。在沒有錯誤的情況下，確實很難用經典演算法模擬一個隨機電路取樣實驗。

從計算複雜度的角度看，當量子位元數量增加時，傳統分類演算法的計算複雜度是呈指數增加的，而量子演算法是呈現多項式增加的。

當n增加到夠大時，一個在n中呈指數級的演算法，要遠遠落後於任何在n中呈多項式的演算法。

當我們談到一個對經典電腦來說很難，但對量子電腦來說很容易的問題時，指的就是這種區別。最好的經典演算法需要指數時間，而量子電腦可以在多項式時間內解決問題。

不過，2019年的那篇論文沒有考慮不完善的量子閘門造成錯誤的影響，研究結論其實留了個口子，也就是說，沒有糾錯的隨機電路取樣，是否還能實現量子霸權？

實際上，如果考慮量子糾纏中產生的、可以累積的錯誤，那麼用經典演算法模擬隨機電路取樣實驗的難度就會大大降低。而如果經典演算法模擬的計算複雜度，降低到與量子演算法相同的多項式級別，量子霸權就將不復存在。

這篇新論文表明，假設保持電路深度不變，比如說很淺的3層，隨著量子位元數量的增加，不會有太多的量子糾纏，輸出仍然可以進行經典模擬。

另一方面，如果增加電路深度，跟上不斷增加的量子位元數量，那麼由量子閘門錯誤累積的效應將沖淡糾纏產生的複雜程度，用經典演算法模擬輸出仍然會變得更加容易。

在這兩者之間有一個「黃金地帶」，即量子霸權得以繼續存活的窗口，即傳統演算法模擬跟不上量子糾纏的範圍。

在這篇論文發表之前，即使隨著量子位元數的增加，當量子位元數量達到某個中間範圍時，量子霸權是仍然存在的。

在這種電路深度下，即使輸出會因量子演算法錯誤而穩定地退化，但在每一步都難以進行經典演算法模擬。

這篇新論文把這個「黃金地帶」幾乎消滅了。

論文中推導出一種模擬隨機電路取樣的經典演算法，並證明了其運行時間是運行相應量子實驗所需時間的多項式函數，而非指數函數。

這一結果在隨機電路取樣的經典方法和量子方法的速度之間建立了緊密的理論聯繫，即宣告了在理論上已經實現的量子霸權，在實際上幾乎並不存在。

之所以說“幾乎”，是因為新演算法的基本假設對某些較淺的電路是無效的，留下了一個未知的「小缺口」。

不過，很少有研究人員也對在這個缺口中實現量子霸權抱持希望。連2019年Google那篇論文的作者之一、芝加哥大學的電腦科學家比爾‧費弗曼（Bill Fefferman）也表示：「我看這個幾率相當小」。

可以這麼說，依照計算複雜度理論的嚴格標準，隨機電路取樣已經不會產生量子霸權了。

另外，面對這個結論，所有研究人員都同意，量子糾錯對於量子運算的長期成功將是多麼關鍵。 Fefferman說：「我們研究到最後都發現，量子糾錯才是解決方案。」

以上是史丹佛、柏克萊新研究推翻Google「量子霸權」！理論上很美，其實沒戲的詳細內容。更多資訊請關注PHP中文網其他相關文章！