里程碑！量子計算機超越經典計算機最新證據，量子霸權再進一步！_風聞

來源：微信公眾號“新智元”

**【新智元導讀】**Science今天發表一篇IBM和慕尼黑工業大學研究人員的論文，論文嚴格證明了在相同限制條件下，量子計算機能擊敗經典計算機，這是量子計算領域一大突破，也指出一條更容易達到“量子霸權”的道路。

震撼！AI WORLD 2018世界人工智能峯會開場視頻

實現“量子霸權”又近了一步！

今天，來自IBM和德國慕尼黑工業大學的一組研究人員在Science上發表了一篇論文，嚴格證明了near-term量子計算機超過了經典計算機。

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

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

量子計算機可能看起來更快，但要有嚴格的數學證明。目前，在理論上已經證明了量子計算能夠超越經典計算。

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

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

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

今天Science雜誌刊登的論文，是IBM的科學家們去年設計的一個證明。這篇論文證明，在解決簡單的線性代數問題時，有限的量子計算機總能擊敗經典計算機，但前提條件是經典計算機具有與量子計算機相同的限制。

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

經典與量子計算模型之間構成可證明的分離

目前，大多數的量子算法都超出了當前的實驗能力：它們的實現需要一個包含錯誤修正的全功能量子計算機。雖然編碼和操作量子數據容錯的開銷是漸近小的，但它仍然不適用於當前的技術。 因此，預計near-term量子計算機將缺乏糾錯能力。

沒有糾錯的量子計算在量子比特解碼（qubits decohere）和熵建立（entropy builds up）之前只能執行恆定數量的運算。當量子比特經歷具有恆定退相干率（constant decoherence rate）的獨立噪聲時，無法實現無源量子存儲（passive quantum memories）。 

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

他們提出一個簡單的二元二次型相關的線性代數問題，它可以由一個由作用於2D網格的最近鄰門組成的SQC確定地求解。這種設置反映了near-term的實驗能力。

同時，研究人員證明了沒有恆定深度的經典概率電路可以解決所考慮的問題，並且對於所有情況都具有足夠小的誤差概率。

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

量子計算領域一大突破，也指出一條更容易達到量子霸權的道路

儘管這項工作離實現“量子霸權”之路還有距離，但論文仍然是一個重要的里程碑。

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

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

翁文康認為，這項研究結果雖然還不清楚能解決什麼實際的問題，但是他們能嚴格證明量子計算機確實比經典計算機要強大，是量子計算領域的一大突破，同時也指出一條更容易達到量子霸權的道路。

馬里蘭大學的計算機科學家Andrew Childs認為，“能夠對量子計算機和經典計算機之間的關係進行清晰陳述，這真是太好了。我們必須從某個地方開始探索，要在正確的方向上實現理論上的進步。”

麻省理工學院理論物理學教授Aram Harrow也認為，大多數之前描述的量子計算機在沒有淺電路限制的情況下擊敗經典計算機的例子中，仍然需要對經典計算機的能力和實現內容做一些整體假設。換句話説，你可能會假設一位馬拉松運動員不可能超越一隻獵豹，但沒有真正證明這一點。本次發表的論文不需要這樣的假設。

量子霸權爭奪戰：IBM、谷歌都已開發出原型量子計算設備

“量子霸權”最早由加州理工學院量子理論學家John Preskill提出，之後受到了量子計算支持者的認同，部分人甚至認為量子霸權可能會2017年年底之前出現。

不過，也有部分人認為“量子霸權”它不是一個突然的邊界，而是一個象徵性的姿態：量子霸權是一個概念工具，可以在其上討論與經典計算方法之間的差異。

儘管如此，對“量子霸權”的熱情激勵着學術和產業界。IBM和谷歌都已開發出原型量子計算設備。

IBM Q量子計算機內部

IBM已經將一個5比特的設備作為基於雲的資源供公眾使用，並於去年11月宣佈它已經為商業用户提供了一個20比特的設備。同時，IBM的計算機科學家也當年報告説他們成功測試了50比特的電路。谷歌也正在開發具有49-50比特率的設備，並且，谷歌的研究人員還曾希望在2017年年底前展示量子霸權成果。

論文一作Sergey Bravyi表示，這項工作更重要的是，科學家們仍然要使用全功能的經典計算機來驗證量子計算機是否能夠取得正確的結果。這與谷歌的“量子霸權”的實驗不同，後者是一個設計的問題，量子計算機在解決問題的速度上可能比模擬量子計算機的經典計算機有着指數級的優勢。 

但這篇新論文也並非完美無瑕。“它不是要解決實際問題，也沒有人建議將其與實際問題聯繫起來，即使要面向實際問題，也會因為帶來的運算速度提升太小，導致人們不會在實際應用中關注。如果量子計算機只比相同大小的經典計算機快那麼一點，那麼由於量子計算機難以構建，我們還是會選擇經典算法。”Harrow説。

論文地址：

http://science.sciencemag.org/content/362/6412/308

參考資料：

https://gizmodo.com/theres-now-a-proven-way-for-quantum-computers-to-beat-c-1829844452

https://www.nature.com/news/race-for-quantum-supremacy-hits-theoretical-quagmire-1.22993