在哪些具體情況下量子計算機超越了經典計算機? 這是一個很難回答的問題,部分原因是當今的量子計算機是挑剔的東西,充滿了可能堆積並破壞計算的錯誤。

從某種意義上說,當然,他們已經做到了。 2019 年,谷歌的物理學家 宣布 他們使用 53 量子比特的機器來實現 量子至上,一個像徵性的里程碑,標誌著量子計算機可以做一些超出任何實用經典算法範圍的事情。 類似 示威 中國科學技術大學的物理學家緊隨其後。

 

但是,計算機科學家不是專注於一台特定機器的實驗結果,而是想知道經典算法是否能夠隨著量子計算機變得越來越大而跟上。 “希望最終量子方面完全退出,直到不再有競爭,”說 斯科特·阿倫森,德克薩斯大學奧斯汀分校的計算機科學家。

 

這個一般性問題仍然很難回答,部分原因還是因為那些討厭的錯誤。 (未來的量子機器將使用一種稱為 量子誤差校正,但這種能力還有很長的路要走。)即使有未糾正的錯誤,是否有可能獲得希望的失控量子優勢?

 

大多數研究人員懷疑答案是否定的,但他們無法在所有情況下證明這一點。 現在,在一個  發佈到預印本服務器 arxiv.org,一組計算機科學家已邁出重要一步,全面證明糾錯對於隨機電路採樣中持久的量子優勢是必要的 - 這是谷歌用來展示量子霸權的定制問題。 他們通過開發一種經典算法來做到這一點,該算法可以在存在錯誤時模擬隨機電路採樣實驗。

“這是一個漂亮的理論結果,”Aaronson 說,同時強調新算法對於模擬像谷歌這樣的真實實驗實際上沒有用。

 

在隨機電路採樣實驗中,研究人員從一組量子位或量子位開始。 然後,他們通過稱為量子門的操作隨機操縱這些量子位。 一些門導致成對的量子位糾纏在一起,這意味著它們共享一個量子態並且不能單獨描述。 重複的門控層使量子比特進入更複雜的糾纏狀態。

 

為了了解該量子態,研究人員隨後測量了陣列中的所有量子位。 這導致它們的集體量子態坍縮為隨機的普通位串——0 和 1。 可能結果的數量隨著陣列中量子位的數量而快速增長:在 53 個量子位中,與穀歌的實驗一樣,它接近 10 千萬億。 並非所有字符串的可能性都相同。 從隨機電路中採樣意味著多次重複此類測量,以構建結果背後的概率分佈圖。

 

量子優勢的問題很簡單:很難模仿概率分佈嗎 用經典算法 那不使用任何糾纏?

 

在2019,研究人員 證明 對於無錯誤的量子電路,答案是肯定的:當沒有錯誤時,確實很難經典地模擬隨機電路採樣實驗。 研究人員在計算複雜性理論的框架內工作,該理論對不同問題的相對難度進行了分類。 在這個領域,研究人員並不把量子比特的數量當作一個固定的數字,比如 53。“把它想像成 n,這是一些會增加的數字,”說 阿蘭哈羅,麻省理工學院物理學家。 “然後你想問:我們是否正在做一些努力成倍增長的事情? n 或多項式 n? 這是對算法的運行時間進行分類的首選方法——當 n 增長到足夠大,一個指數增長的算法 n 遠遠落後於多項式的任何算法 n. 當理論家談到一個對經典計算機來說很難但對量子計算機來說很容易的問題時,他們指的是這種區別:最好的經典算法需要指數時間,而量子計算機可以在多項式時間內解決問題。

然而,那篇 2019 年的論文忽略了由不完美的門引起的錯誤的影響。 這為沒有糾錯的隨機電路採樣的量子優勢留下了懸而未決的情況。

 

如果你想像像複雜性理論家那樣不斷增加量子比特的數量,並且你還想考慮錯誤,你需要決定是否還要繼續添加更多的門層——如研究人員所說,增加電路深度。 假設隨著量子比特數的增加,您將電路深度保持在相對較淺的三層。 你不會有太多的糾纏,輸出仍然適用於經典模擬。 另一方面,如果增加電路深度以跟上不斷增長的量子比特數,門錯誤的累積效應將消除糾纏,輸出將再次變得易於經典模擬。

 

但介於兩者之間的是金發姑娘區。 在新論文發表之前,即使量子位的數量增加,量子優勢仍然有可能在這裡生存。 在這種中等深度的情況下,隨著量子比特數量的增加,電路深度的增加非常緩慢:即使輸出會因錯誤而穩步下降,但可能仍然很難在每一步進行經典模擬。

新論文填補了這個漏洞。 作者推導出了一種模擬隨機電路採樣的經典算法,並證明其運行時間是運行相應量子實驗所需時間的多項式函數。 結果在經典和量子隨機電路採樣方法的速度之間建立了緊密的理論聯繫。

 

新算法適用於主要類別的中等深度電路,但它的基本假設對於某些較淺的電路來說是錯誤的,留下了一個小的差距,其中有效的經典模擬方法是未知的。 但很少有研究人員抱有希望,即隨機電路採樣將難以在剩下的狹小窗口中進行經典模擬。 “我給它的賠率很小,”說 比爾·費弗曼,芝加哥大學計算機科學家,2019年理論論文作者之一。

 

結果表明,根據計算複雜性理論的嚴格標準,隨機電路採樣不會產生量子優勢。 同時,它說明了一個事實,複雜性理論家不加區別地稱之為高效的多項式算法在實踐中不一定很快。 隨著錯誤率的降低,新的經典算法變得越來越慢,並且在量子霸權實驗中達到的低錯誤率下,它太慢而不實用。 如果沒有錯誤,它就會完全崩潰,所以這個結果與研究人員所知道的在理想、無錯誤的情況下經典地模擬隨機電路採樣有多麼困難並不矛盾。 塞爾吉奧·博伊索領導谷歌量子霸權研究的物理學家表示,他認為這篇論文“比其他任何東西都更能證明隨機電路採樣”。

 

有一點,所有研究人員都同意:新算法強調了量子糾錯對量子計算的長期成功至關重要。 “歸根結底,這就是解決方案,”費弗曼說。

翻譯»