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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

但這篇新論文也并非完美無瑕。“它不是要解決實(shí)際問題，也沒有人建議將其與實(shí)際問題聯(lián)系起來，即使要面向?qū)嶋H問題，也會因?yàn)閹淼倪\(yùn)算速度提升太小，導(dǎo)致人們不會在實(shí)際應(yīng)用中關(guān)注。如果量子計算機(jī)只比相同大小的經(jīng)典計算機(jī)快那么一點(diǎn)，那么由于量子計算機(jī)難以構(gòu)建，我們還是會選擇經(jīng)典算法。”Harrow說。