新智元報道
編輯：David
【新智元導讀】自誕生之日起，量子霸權成為了無數研究人員試圖打破的命題。如今，哈佛大學、加州大學伯克利分校和以色列希伯來大學的聯合團隊終于朝着這個方向邁出堅實一步。實驗證明，量子霸權并不存在！
量子霸權，這個詞已經誕生了近4年了。
2019年，谷歌的實體學家宣布成功用一台53量子比特的機器實作了量子霸權，這是一個具有重大象征的裡程碑。
在Nature上發表的論文中稱，該量子系統隻用了200秒完成一個計算，而同樣的計算用當時最強大的超級計算機Summit執行，需要約10000年。
什麼是量子霸權？
所謂「量子霸權」，或者叫「量子優勢」（以下稱「量子霸權」）是指，量子計算機能完成的任務超出了任何可行經典算法的範圍。
這些任務即使放在最先進的傳統超級計算機上，計算時間之長（往往是成千上萬年）也會讓算法失去實用意義。
有趣的是，在2019年谷歌的成果中，隻說了實作了量子霸權，沒有說明在哪些具體執行個體下，量子計算機超過了經典計算機。
這是一個很難回答的問題，因為目前量子計算機受到錯誤頻發的困擾，這些錯誤會累積，破壞量子計算的性能和穩定。
實際上，與量子霸權的實作領域相比，科學家更想知道的是另一個問題：随着量子計算機越來越大，經典算法是否能夠跟上腳步。
德克薩斯大學奧斯汀分校的計算機科學家Scott Aaronson說：「我們希望最終量子一方會完全拉開距離，徹底結束這場競争。」
大多數研究人員推測，答案是否定的。
即經典算法總有一天會徹底跟不上量子計算的腳步，但一直無法準确全面地證明這一點。要确定證明這個推論，一個途徑是找到量子計算能夠獲得相對于傳統計算「持久優勢」的條件。
現在，這個問題似乎有了初步答案：
省流：量子計算是會産生錯誤的，如果糾錯跟不上，這種錯誤就 會打破理想狀态下的「量子霸權」，讓經典算法能夠跟得上量子算法的腳步。
最近，在一篇Arxiv上發表的預印本論文中，由哈佛大學、加州大學伯克利分校、以色列希伯來大學的聯合團隊朝着證明這個結論邁出了一大步。
他們證明了，目标錯誤糾正是随機電路采樣中持久量子霸權的必要條件，為幾年前谷歌的研究結論提供了支撐。在目前的量子糾錯水準下，量子霸權實際上是并不存在的。
再無量子霸權「黃金地帶」
研究人員開發了一種經典算法，可以模拟存在錯誤時的随機電路取樣實驗來證明這個結論。
從一個量子比特陣列開始，用被稱為「量子門」的操作随機操縱這些量子比特。一些量子門會使成對的量子比特處于糾纏态，即意味着彼此共享一個量子态，不能被單獨描述。
在多層電路中重複設定這些量子門，可以讓量子比特進入更複雜的糾纏态。
左圖為理想狀态下的随機電路取樣，右圖為包含幹擾的随機電路取樣
為了了解這種量子态，研究人員測量了陣列中的所有量子比特。這個行為會導緻所有量子比特的集體量子态坍縮為一串随機的普通比特，即0和1。
可能的結果數量随着陣列中的量子比特數量的增加而迅速增長。在谷歌2019年的的實驗中，53個量子比特下包含近10萬億個結果。
而且，這種方法需要從随機電路中多次重複測量，建立一個關于結果的機率分布圖。
關于量子霸權的問題是，用一個不使用任何糾纏的經典算法，來模仿這種機率分布，是否很難甚至不可能？
2019年，谷歌研究人員就證明，對于無誤差、不會産生錯誤的量子電路來說，這個目标是困難的。在沒有錯誤的情況下，确實很難用經典算法模拟一個随機電路采樣實驗。
從計算複雜度的角度看，當量子比特數量增加時，傳統分類算法的計算複雜度是呈指數增加的，而量子算法是呈多項式增加的。
當n增加到足夠大時，一個在n中呈指數級的算法，要遠遠落後于任何在n中呈多項式的算法。
當我們談到一個對經典計算機來說很難，但對量子計算機來說很容易的問題時，指的就是這種差別。最好的經典算法需要指數時間，而量子計算機可以在多項式時間内解決問題。
不過，2019年的那篇論文沒有考慮不完善的量子門造成錯誤的影響，研究結論實際上留了個口子，也就是說，沒有糾錯的随機電路采樣，是否還能實作量子霸權？
實際上，如果考慮量子糾纏中産生的、可以累積的錯誤，那麼用經典算法模拟随機電路采樣實驗的難度就會大大降低。而如果經典算法模拟的計算複雜度，降低到與量子算法相同的多項式級别，量子霸權就将不複存在。
這篇新論文表明，假設保持電路深度不變，比如說很淺的3層，随着量子比特數量的增加，不會有太多的量子糾纏，輸出仍然可以進行經典模拟。
另一方面，如果增加電路深度，跟上不斷增加的量子比特數量，那麼由量子門錯誤累積的效應将沖淡糾纏産生的複雜程度，用經典算法模拟輸出仍然會變得更加容易。
在這兩者之間有一個「黃金地帶」，即量子霸權得以繼續存活的視窗，即傳統算法模拟跟不上量子糾纏的範圍。
在這篇論文發表之前，即使随着量子比特數的增加，當量子比特數量達到某個中間範圍時，量子霸權是仍然存在的。
在這種電路深度下，即使輸出會因量子算法錯誤而穩定地退化，但在每一步都難以進行經典算法模拟。
這篇新論文把這個「黃金地帶」幾乎消滅了。
論文中推導出一種模拟随機電路采樣的經典算法，并證明了其運作時間是運作相應量子實驗所需時間的多項式函數，而非指數函數。
這一結果在随機電路采樣的經典方法和量子方法的速度之間建立了緊密的理論聯系，即宣告了在理論上已經實作的量子霸權，在實際上幾乎并不存在。
之是以說「幾乎」，是因為新算法的基本假設對某些較淺的電路是無效的，留下了一個未知的「小缺口」。
不過，很少有研究人員還對在這個缺口中實作量子霸權抱有希望。連2019年谷歌那篇論文的作者之一、芝加哥大學的計算機科學家比爾·費弗曼（Bill Fefferman）也表示：「我看這個幾率相當小」。
可以這麼說，按照計算複雜性理論的嚴格标準，随機電路采樣已經不會産生量子霸權了。
另外，面對這個結論，所有研究人員都同意，量子糾錯對于量子計算的長期成功将是多麼關鍵。Fefferman說：「我們研究到最後都發現，量子糾錯才是解決方案。」
參考資料：
https://www.quantamagazine.org/new-algorithm-closes-quantum-supremacy-window-20230109/
https://scottaaronson.blog/?p=6957