Science今天發(fā)表一篇IBM和慕尼黑工業(yè)大學(xué)研究人員的論文，論文嚴(yán)格證明了在相同限制條件下，量子計算機能擊敗經(jīng)典計算機，這是量子計算領(lǐng)域一大突破，也指出一條更容易達(dá)到“量子霸權(quán)”的道路。

實現(xiàn)“量子霸權(quán)”又近了一步！

今天，來自IBM和德國慕尼黑工業(yè)大學(xué)的一組研究人員在Science上發(fā)表了一篇論文，嚴(yán)格證明了near-term量子計算機超過了經(jīng)典計算機。

不過，前提條件是對量子計算機和經(jīng)典計算機的能力都作了嚴(yán)格的限制，雖然還沒有證明被大家瘋狂追求的“量子霸權(quán)”（quantum supremacy）已經(jīng)實現(xiàn)，但這是表明量子處理器有一天可能達(dá)到量子霸權(quán)的重要里程碑事件！

相同限制條件下，量子計算機被證明能擊敗經(jīng)典計算機

量子計算機可能看起來更快，但要有嚴(yán)格的數(shù)學(xué)證明。目前，在理論上已經(jīng)證明了量子計算能夠超越經(jīng)典計算。

今天的經(jīng)典計算機可以將每個問題都轉(zhuǎn)換成二進(jìn)制代碼串，由可以是0或1的位元表示。

量子計算機的量子比特（qubits）以一種全新的方式進(jìn)行通信。量子比特可以在計算過程中取0和1之間的值，并以常規(guī)計算機位元無法做到的方式進(jìn)行交互。 量子處理器仍然總是返回表示0和1的二進(jìn)制字符串，但每個量子比特的最終值有一個固有的概率，這個概率基于在程序測量量子比特之前它的值與0或1的接近程度。量子比特也可以糾纏，在這種情況下，兩個或兩個以上的量子比特值的組合同時受到概率的影響。

目前，IBM和Rigetti等公司有一些基本形式的量子計算機，通常只有20或更少的量子比特。在構(gòu)建這些設(shè)備的過程中，物理學(xué)家和計算機科學(xué)家正在開發(fā)量子算法，希望能比傳統(tǒng)計算機更好地解決問題。

今天Science雜志刊登的論文，是IBM的科學(xué)家們?nèi)ツ暝O(shè)計的一個證明。這篇論文證明，在解決簡單的線性代數(shù)問題時，有限的量子計算機總能擊敗經(jīng)典計算機，但前提條件是經(jīng)典計算機具有與量子計算機相同的限制。

這些限制即具有“shallow circuits”。計算機科學(xué)中將單個位元交互稱為“邏輯門”（logic gates）。這些門基于一個或多個位元返回一個值。相反，量子門將量子比特的值移動到0或1之間的某個位置，或者改變一個糾纏的量子比特對的內(nèi)置數(shù)值（built-in statistics）?！癱ircuit”是一系列的門?！皊hallow quantum circuit（SQC）”是指每個量子比特只能在再次變?yōu)?或1之前只能執(zhí)行有限數(shù)量的門，并且這些門最多只能包含另一個量子比特。如果兩個門同時出現(xiàn)在處理器上不相關(guān)的量子比特對上，是沒問題的。

經(jīng)典與量子計算模型之間構(gòu)成可證明的分離

目前，大多數(shù)的量子算法都超出了當(dāng)前的實驗?zāi)芰Γ核鼈兊膶崿F(xiàn)需要一個包含錯誤修正的全功能量子計算機。雖然編碼和操作量子數(shù)據(jù)容錯的開銷是漸近小的，但它仍然不適用于當(dāng)前的技術(shù)。 因此，預(yù)計near-term量子計算機將缺乏糾錯能力。

沒有糾錯的量子計算在量子比特解碼（qubits decohere）和熵建立（entropy builds up）之前只能執(zhí)行恒定數(shù)量的運算。當(dāng)量子比特經(jīng)歷具有恒定退相干率（constant decoherence rate）的獨立噪聲時，無法實現(xiàn)無源量子存儲（passive quantum memories）。

在論文中，研究人員比較了SQC和它的經(jīng)典計算機對應(yīng)部分（即恒定深度經(jīng)典電路）的計算能力。

他們提出一個簡單的二元二次型相關(guān)的線性代數(shù)問題，它可以由一個由作用于2D網(wǎng)格的最近鄰門組成的SQC確定地求解。這種設(shè)置反映了near-term的實驗?zāi)芰Α?/p>

同時，研究人員證明了沒有恒定深度的經(jīng)典概率電路可以解決所考慮的問題，并且對于所有情況都具有足夠小的誤差概率。

經(jīng)典電路在任何意義上都不必是幾何局部的，并且可以訪問從僅依賴于輸入大小的任意概率分布中抽取的隨機位元。唯一的要求是經(jīng)典電路中的所有門必須具有有界扇入（bounded fan-in）（即每個門具有恒定數(shù)量的輸入導(dǎo)線）。該結(jié)果提供了恒定深度量子和經(jīng)典電路的功率之間的無條件分離。

量子計算領(lǐng)域一大突破，也指出一條更容易達(dá)到量子霸權(quán)的道路

盡管這項工作離實現(xiàn)“量子霸權(quán)”之路還有距離，但論文仍然是一個重要的里程碑。

華為量子計算軟件與算法首席科學(xué)家翁文康教授表示，要證明量子霸權(quán)需要找出具體電路大?。ò孔颖忍財?shù)目和電路深度）是經(jīng)典計算機在合理的時間內(nèi)不能有效模擬的。

“ 他們找到一類量子算法，在物理實現(xiàn)上不需要太大的量子電路，就可以在理論上超越經(jīng)典計算機的能力。但是如果要真正實現(xiàn)量子霸權(quán)的話，我們還要具體看經(jīng)典計算機對這個新的量子算法的模擬能力。”

翁文康認(rèn)為，這項研究結(jié)果雖然還不清楚能解決什么實際的問題，但是他們能嚴(yán)格證明量子計算機確實比經(jīng)典計算機要強大，是量子計算領(lǐng)域的一大突破，同時也指出一條更容易達(dá)到量子霸權(quán)的道路。

馬里蘭大學(xué)的計算機科學(xué)家Andrew Childs認(rèn)為，“能夠?qū)α孔佑嬎銠C和經(jīng)典計算機之間的關(guān)系進(jìn)行清晰陳述，這真是太好了。我們必須從某個地方開始探索，要在正確的方向上實現(xiàn)理論上的進(jìn)步?！?/p>

麻省理工學(xué)院理論物理學(xué)教授Aram Harrow也認(rèn)為，大多數(shù)之前描述的量子計算機在沒有淺電路限制的情況下?lián)魯〗?jīng)典計算機的例子中，仍然需要對經(jīng)典計算機的能力和實現(xiàn)內(nèi)容做一些整體假設(shè)。換句話說，你可能會假設(shè)一位馬拉松運動員不可能超越一只獵豹，但沒有真正證明這一點。本次發(fā)表的論文不需要這樣的假設(shè)。

量子霸權(quán)爭奪戰(zhàn)：IBM、谷歌都已開發(fā)出原型量子計算設(shè)備

“量子霸權(quán)”最早由加州理工學(xué)院量子理論學(xué)家John Preskill提出，之后受到了量子計算支持者的認(rèn)同，部分人甚至認(rèn)為量子霸權(quán)可能會2017年年底之前出現(xiàn)。

不過，也有部分人認(rèn)為“量子霸權(quán)”它不是一個突然的邊界，而是一個象征性的姿態(tài)：量子霸權(quán)是一個概念工具，可以在其上討論與經(jīng)典計算方法之間的差異。

盡管如此，對“量子霸權(quán)”的熱情激勵著學(xué)術(shù)和產(chǎn)業(yè)界。IBM和谷歌都已開發(fā)出原型量子計算設(shè)備。

IBM Q量子計算機內(nèi)部

IBM已經(jīng)將一個5比特的設(shè)備作為基于云的資源供公眾使用，并于去年11月宣布它已經(jīng)為商業(yè)用戶提供了一個20比特的設(shè)備。同時，IBM的計算機科學(xué)家也當(dāng)年報告說他們成功測試了50比特的電路。谷歌也正在開發(fā)具有49-50比特率的設(shè)備，并且，谷歌的研究人員還曾希望在2017年年底前展示量子霸權(quán)成果。

論文一作Sergey Bravyi表示，這項工作更重要的是，科學(xué)家們?nèi)匀灰褂萌δ艿慕?jīng)典計算機來驗證量子計算機是否能夠取得正確的結(jié)果。這與谷歌的“量子霸權(quán)”的實驗不同，后者是一個設(shè)計的問題，量子計算機在解決問題的速度上可能比模擬量子計算機的經(jīng)典計算機有著指數(shù)級的優(yōu)勢。

但這篇新論文也并非完美無瑕?！八皇且鉀Q實際問題，也沒有人建議將其與實際問題聯(lián)系起來，即使要面向?qū)嶋H問題，也會因為帶來的運算速度提升太小，導(dǎo)致人們不會在實際應(yīng)用中關(guān)注。如果量子計算機只比相同大小的經(jīng)典計算機快那么一點，那么由于量子計算機難以構(gòu)建，我們還是會選擇經(jīng)典算法?！盚arrow說。