量子霸權(quán)，這個(gè)詞已經(jīng)誕生了近4年了。

2019年，谷歌的物理學(xué)家宣布成功用一臺(tái)53量子比特的機(jī)器實(shí)現(xiàn)了量子霸權(quán)，這是一個(gè)具有重大象征的里程碑。

在Nature上發(fā)表的論文中稱，該量子系統(tǒng)只用了200秒完成一個(gè)計(jì)算，而同樣的計(jì)算用當(dāng)時(shí)最強(qiáng)大的超級(jí)計(jì)算機(jī)Summit執(zhí)行，需要約10000年。

什么是量子霸權(quán)？

所謂「量子霸權(quán)」，或者叫「量子優(yōu)勢(shì)」（以下稱「量子霸權(quán)」）是指，量子計(jì)算機(jī)能完成的任務(wù)超出了任何可行經(jīng)典算法的范圍。

這些任務(wù)即使放在最先進(jìn)的傳統(tǒng)超級(jí)計(jì)算機(jī)上，計(jì)算時(shí)間之長(zhǎng)（往往是成千上萬年）也會(huì)讓算法失去實(shí)用意義。

有趣的是，在2019年谷歌的成果中，只說了實(shí)現(xiàn)了量子霸權(quán)，沒有說明在哪些具體實(shí)例下，量子計(jì)算機(jī)超過了經(jīng)典計(jì)算機(jī)。

這是一個(gè)很難回答的問題，因?yàn)槟壳傲孔佑?jì)算機(jī)受到錯(cuò)誤頻發(fā)的困擾，這些錯(cuò)誤會(huì)累積，破壞量子計(jì)算的性能和穩(wěn)定。

實(shí)際上，與量子霸權(quán)的實(shí)現(xiàn)領(lǐng)域相比，科學(xué)家更想知道的是另一個(gè)問題：隨著量子計(jì)算機(jī)越來越大，經(jīng)典算法是否能夠跟上腳步。

德克薩斯大學(xué)奧斯汀分校的計(jì)算機(jī)科學(xué)家Scott Aaronson說：「我們希望最終量子一方會(huì)完全拉開距離，徹底結(jié)束這場(chǎng)競(jìng)爭(zhēng)。」

大多數(shù)研究人員推測(cè)，答案是否定的。

即經(jīng)典算法總有一天會(huì)徹底跟不上量子計(jì)算的腳步，但一直無法準(zhǔn)確全面地證明這一點(diǎn)。要確定證明這個(gè)推論，一個(gè)途徑是找到量子計(jì)算能夠獲得相對(duì)于傳統(tǒng)計(jì)算「持久優(yōu)勢(shì)」的條件。

現(xiàn)在，這個(gè)問題似乎有了初步答案：

省流：量子計(jì)算是會(huì)產(chǎn)生錯(cuò)誤的，如果糾錯(cuò)跟不上，這種錯(cuò)誤就 會(huì)打破理想狀態(tài)下的「量子霸權(quán)」，讓經(jīng)典算法能夠跟得上量子算法的腳步。?

最近，在一篇Arxiv上發(fā)表的預(yù)印本論文中，由哈佛大學(xué)、加州大學(xué)伯克利分校、以色列希伯來大學(xué)的聯(lián)合團(tuán)隊(duì)朝著證實(shí)這個(gè)結(jié)論邁出了一大步。

他們證明了，目標(biāo)錯(cuò)誤糾正是隨機(jī)電路采樣中持久量子霸權(quán)的必要條件，為幾年前谷歌的研究結(jié)論提供了支撐。在目前的量子糾錯(cuò)水平下，量子霸權(quán)實(shí)際上是并不存在的。?

再無量子霸權(quán)「黃金地帶」

研究人員開發(fā)了一種經(jīng)典算法，可以模擬存在錯(cuò)誤時(shí)的隨機(jī)電路取樣實(shí)驗(yàn)來證明這個(gè)結(jié)論。

從一個(gè)量子比特陣列開始，用被稱為「量子門」的操作隨機(jī)操縱這些量子比特。一些量子門會(huì)使成對(duì)的量子比特處于糾纏態(tài)，即意味著彼此共享一個(gè)量子態(tài)，不能被單獨(dú)描述。

在多層電路中重復(fù)設(shè)置這些量子門，可以讓量子比特進(jìn)入更復(fù)雜的糾纏態(tài)。

左圖為理想狀態(tài)下的隨機(jī)電路取樣，右圖為包含干擾的隨機(jī)電路取樣

為了了解這種量子態(tài)，研究人員測(cè)量了陣列中的所有量子比特。這個(gè)行為會(huì)導(dǎo)致所有量子比特的集體量子態(tài)坍縮為一串隨機(jī)的普通比特，即0和1。

可能的結(jié)果數(shù)量隨著陣列中的量子比特?cái)?shù)量的增加而迅速增長(zhǎng)。在谷歌2019年的的實(shí)驗(yàn)中，53個(gè)量子比特下包含近10萬億個(gè)結(jié)果。

而且，這種方法需要從隨機(jī)電路中多次重復(fù)測(cè)量，建立一個(gè)關(guān)于結(jié)果的概率分布圖。

關(guān)于量子霸權(quán)的問題是，用一個(gè)不使用任何糾纏的經(jīng)典算法，來模仿這種概率分布，是否很難甚至不可能？

2019年，谷歌研究人員就證明，對(duì)于無誤差、不會(huì)產(chǎn)生錯(cuò)誤的量子電路來說，這個(gè)目標(biāo)是困難的。在沒有錯(cuò)誤的情況下，確實(shí)很難用經(jīng)典算法模擬一個(gè)隨機(jī)電路采樣實(shí)驗(yàn)。

從計(jì)算復(fù)雜度的角度看，當(dāng)量子比特?cái)?shù)量增加時(shí)，傳統(tǒng)分類算法的計(jì)算復(fù)雜度是呈指數(shù)增加的，而量子算法是呈多項(xiàng)式增加的。

當(dāng)n增加到足夠大時(shí)，一個(gè)在n中呈指數(shù)級(jí)的算法，要遠(yuǎn)遠(yuǎn)落后于任何在n中呈多項(xiàng)式的算法。

當(dāng)我們談到一個(gè)對(duì)經(jīng)典計(jì)算機(jī)來說很難，但對(duì)量子計(jì)算機(jī)來說很容易的問題時(shí)，指的就是這種區(qū)別。最好的經(jīng)典算法需要指數(shù)時(shí)間，而量子計(jì)算機(jī)可以在多項(xiàng)式時(shí)間內(nèi)解決問題。

不過，2019年的那篇論文沒有考慮不完善的量子門造成錯(cuò)誤的影響，研究結(jié)論實(shí)際上留了個(gè)口子，也就是說，沒有糾錯(cuò)的隨機(jī)電路采樣，是否還能實(shí)現(xiàn)量子霸權(quán)？

實(shí)際上，如果考慮量子糾纏中產(chǎn)生的、可以累積的錯(cuò)誤，那么用經(jīng)典算法模擬隨機(jī)電路采樣實(shí)驗(yàn)的難度就會(huì)大大降低。而如果經(jīng)典算法模擬的計(jì)算復(fù)雜度，降低到與量子算法相同的多項(xiàng)式級(jí)別，量子霸權(quán)就將不復(fù)存在。

這篇新論文表明，假設(shè)保持電路深度不變，比如說很淺的3層，隨著量子比特?cái)?shù)量的增加，不會(huì)有太多的量子糾纏，輸出仍然可以進(jìn)行經(jīng)典模擬。

另一方面，如果增加電路深度，跟上不斷增加的量子比特?cái)?shù)量，那么由量子門錯(cuò)誤累積的效應(yīng)將沖淡糾纏產(chǎn)生的復(fù)雜程度，用經(jīng)典算法模擬輸出仍然會(huì)變得更加容易。

在這兩者之間有一個(gè)「黃金地帶」，即量子霸權(quán)得以繼續(xù)存活的窗口，即傳統(tǒng)算法模擬跟不上量子糾纏的范圍。

在這篇論文發(fā)表之前，即使隨著量子比特?cái)?shù)的增加，當(dāng)量子比特?cái)?shù)量達(dá)到某個(gè)中間范圍時(shí)，量子霸權(quán)是仍然存在的。

在這種電路深度下，即使輸出會(huì)因量子算法錯(cuò)誤而穩(wěn)定地退化，但在每一步都難以進(jìn)行經(jīng)典算法模擬。

這篇新論文把這個(gè)「黃金地帶」幾乎消滅了。?

論文中推導(dǎo)出一種模擬隨機(jī)電路采樣的經(jīng)典算法，并證明了其運(yùn)行時(shí)間是運(yùn)行相應(yīng)量子實(shí)驗(yàn)所需時(shí)間的多項(xiàng)式函數(shù)，而非指數(shù)函數(shù)。

這一結(jié)果在隨機(jī)電路采樣的經(jīng)典方法和量子方法的速度之間建立了緊密的理論聯(lián)系，即宣告了在理論上已經(jīng)實(shí)現(xiàn)的量子霸權(quán)，在實(shí)際上幾乎并不存在。

之所以說「幾乎」，是因?yàn)樾滤惴ǖ幕炯僭O(shè)對(duì)某些較淺的電路是無效的，留下了一個(gè)未知的「小缺口」。

不過，很少有研究人員還對(duì)在這個(gè)缺口中實(shí)現(xiàn)量子霸權(quán)抱有希望。連2019年谷歌那篇論文的作者之一、芝加哥大學(xué)的計(jì)算機(jī)科學(xué)家比爾·費(fèi)弗曼（Bill Fefferman）也表示：「我看這個(gè)幾率相當(dāng)小」。

可以這么說，按照計(jì)算復(fù)雜性理論的嚴(yán)格標(biāo)準(zhǔn)，隨機(jī)電路采樣已經(jīng)不會(huì)產(chǎn)生量子霸權(quán)了。

另外，面對(duì)這個(gè)結(jié)論，所有研究人員都同意，量子糾錯(cuò)對(duì)于量子計(jì)算的長(zhǎng)期成功將是多么關(guān)鍵。Fefferman說：「我們研究到最后都發(fā)現(xiàn)，量子糾錯(cuò)才是解決方案。」