量子计算优越性

**量子計算優越性**（英文：Quantum Advantage），或稱**量子霸權**（英語：quantum supremacy），是指用量子電腦解決古典電腦難以解決的問題，問題本身未必需要有實際應用。量子計算優越性則是指量子電腦在解決實務問題上能比古典電腦更快而帶來的優勢，從計算複雜性理論的角度來說，這通常代表量子電腦相對最佳古典演算法的加速是超多項式的。 這個術語最初是由約翰・普雷斯基爾所提出，但量子計算優勢的概念（特別是用於類比量子系統）可以追溯到尤里・馬寧（1980） 和理察・費曼（1981）提出的量子計算建議。 

秀爾演算法能在量子電腦上以多項式時間執行整數的因數分解，和已知的古典演算法相比具有超多項式加速。 一般認為使用古典資源分解整數很困難，然而嚴謹的證明尚未出現。缺乏古典計算困難度的證明，是難以明確展示量子優越性的主要原因。這影響了常見的量子優越性問題：Aaronson 和 Arkhipov 的玻色子抽樣問題（boson sampling）、 D-Wave 的 specialized frustrated cluster loop problems、 以及隨機量子電路抽樣問題。

像整數分解一樣，基於合理的複雜度假設，用古典電腦對隨機量子電路的輸出分布進行抽樣是困難的。Google 先前宣布，計劃在 2017 年底之前用含有 49 個超導量子位元的陣列解決這個問題，以展示量子優越性。 在那之後，Intel、IBM、Google 分別宣布了 49、53、72 個量子位元的系統。

2020 年 12 月 4 日，中國科學技術大學發布使用 76 個光子的量子電腦「九章」，並宣布實現量子優越性，使中國成為全球第二個實現「量子優越性」的國家。

## 計算複雜度

複雜度理論研究解決計算問題所需的資源如何隨問題的大小變化，量子複雜度理論延伸古典計算複雜度理論到通用量子電腦可以完成的工作上，對於建造量子電腦或處理退相干和雜訊的困難則忽略不計。 由於量子資訊比古典資訊更廣義 ，很顯然量子電腦可以有效地類比任何古典演算法 。

有限錯誤量子多項式時間（BQP）這個複雜度類別包括通用量子電腦在多項式時間能解決的決策問題，它和古典複雜度類別的關係是 $P\subseteq BPP\subseteq BQP\subseteq PSPACE$ ， 這些子集關係之中有沒有真子集仍是未決問題。

與答案為是或否的決策問題不同，抽樣問題要求從機率分布中抽取樣本。 如果有古典演算法可以有效地從任意量子電路的輸出中抽樣，則多項式譜系將崩潰到第三級，普遍認為這是極不可能的。 玻色子抽樣是較具體的提議，其古典困難度來自於計算具有複數元素的大矩陣其積和式的困難度，而那是 P#-complete 的問題。 用於得出此結論的論點也已擴展到 IQP 抽樣， 並只需假設問題的平均和最壞情況複雜度相同。

## 超多項式加速

下列演算法對已知的最好的古典演算法提供超多項式加速：

### 秀爾整數分解演算法

秀爾演算法用 ${\tilde {O}}(n^{3})$ 時間分解 n - 位元整數， 而已知的最好的古典演算法需要 $2^{O(n^{1/3})}$ 時間，複雜度的最佳上限是 $O(2^{n/3+o(1)})$ 。 它還能加速任何可化簡成整數分解的問題。 

這個演算法在歷史上和實務上都對量子計算很重要，它是第一個用多項式時間解決困難古典計算問題的量子演算法。 對其困難度的信念強烈到當今最常見的加密協定 RSA 就是根據整數分解。 能重複成功運行這種演算法的量子電腦有潛力破解這種加密系統。 需要避免迫在眉睫的這種風險被稱為 Y2Q，名稱來自 2000 年問題的別名 "Y2K"。

### 玻色子抽樣

這是基於一個古典計算問題：將全同光子穿過線性光學網路用來解決某些抽樣和檢索的問題，在一些猜測性的假設下，對古典計算是很棘手的。 然而，已經有研究顯示，如果系統具有足夠大的失真和雜訊，古典電腦能夠有效率地類比玻色子抽樣問題。 

迄今為止，最大的玻色子抽樣實驗能做到 6 個光學模式，一次最多可以處理 6 個光子。 對於包含 n 個光子 和 m 個輸出模式的系統，類比玻色子抽樣的古典演算法最好的執行時間是 。 BosonSampling 是一個用 R 寫的開放原始碼實作，估計需要 50 個光子才能達成玻色子抽樣的量子優越性。

### 對隨機量子電路的輸出分佈抽樣

在類比任意隨機量子電路的演算法當中，已知最佳的演算法需要的時間隨量子位元個數指數式地上升，因此一個研究小組估計 50 個量子位元可能就足以達成量子優越性。 Google 已經宣布打算在 2017 年底前用 49 量子位元的晶片展示量子優越性，方法是對其輸出分布抽樣，這個抽樣用古典電腦將無法在合理時間內類比。 然而 56 量子位元的量子電路類比已經在超級電腦上完成， 這可能讓達成量子優越性所需的量子位元數增加。

## 懷疑論

因為退相干和雜訊，量子電腦比古典電腦更容易受到資料錯誤的影響。 閾值定理指出，有雜訊的量子電腦只要每一步計算的錯誤率低於某個值，就可以用量子錯誤修正碼 類比無雜訊的量子電腦 ，數值類比的結果指出該閾值可以高達 3%。

然而，錯誤修正所需的資源會如何隨量子位元數上升並不清楚。 懷疑論者指出，大型量子系統中未知的雜訊行為是成功實作量子電腦和達成量子優越性的潛在障礙，要太多的量子位元用以糾錯最後會成為一堵高牆無法翻越。

## 實現面爭議

2017 年 10 月，IBM 在傳統的超級電腦上展示了 56 個量子位元的類比，增加了量子優越性所需的量子位元數量。 2018 年 11 月，Google 宣布與 NASA 建立合作夥伴關係，「將分析在 Google 量子處理器上運行的量子電路的結果，並... 與古典類比比較，以驗證 Google 硬體並為量子優越性建立基礎。」 2018 年發表的理論工作提出，如果能將錯誤率降到夠低，那麼「具有 7x7 量子位元的二維點陣執行大約 40 個時鐘週期」應該可以實現量子優越性。

2019 年 1 月 8 日，IBM 在消費電子展上展示了已開發的世界首款商業化量子電腦 IBM Q System One 但其基本只有實驗研究價值，沒有超越傳統電腦的實用性。而 6 月份開始一直有媒體傳言 Google 實現量子霸權的文章在流轉，《科學美國人》於 2019 年 6 月 21 日提出，根據聶文定律， 量子優越性可能在 2019 年發生。

2019 年 9 月 20 日，英國《金融時報》基於一篇在 NASA 網站上短暫出現的文章報導：「Google 聲稱已經用 54 個量子位元的陣列（其中 53 個功能正常）的量子電腦原型機懸鈴木達到了量子優越性，它們在 200 秒內執行一系列操作，相同運算將花費超級電腦大約 10,000 年才能完成」。

2019 年 10 月 21 日 IBM 於 arXiv 發佈一篇文章， 指出若能有效率使用 Summit 超級電腦的硬碟和平行計算資源，估計可以將 10,000 年時間降低至 2.5 天，計算 53 和 54 個量子位元分別需要 64PiB 和 128PiB 的硬碟空間。

2019 年 10 月 23 日自然期刊刊登了 Google 實現量子優越性的學術論文，各種學者和人士對此各種議論紛紛，莫衷一是：

* 美國總統川普女兒伊萬卡在社群媒體上稱美國正式實現量子霸權，Google 的專案是與川普政府、以及加州大學聖塔芭芭拉分校合作進行的。
* Google 首席執行長 Sundar Pichai 受訪時也對此事進行回應，用委婉的譬喻稱 Google 的實驗就是像是萊特兄弟首次飛行，雖第一架飛機只飛行了 12 秒鐘，並沒有真的實際應用性，但這仍然表明飛機的概念是可行的。
* 美國德州大學奧斯汀分校的理論電腦科學家斯科特 阿倫森（Scott Aaronson）則保守性中立認為，雖 Google 上述成果實際應用有限「但假設它是成立的，那麼科學象徵成就是巨大的。」因為代表量子電腦取代傳統電腦有其可能。
* 澳大利亞新南威爾斯大學量子物理學家米歇爾 西蒙斯（Michelle Simmons）說 Google 給了我們一種實驗證據，證明量子加速在真實世界的系統中是有可能的。
* 而值得關注是量子霸權此一名詞提出者約翰・普里斯基爾在同一時期雖沒對具體案例發言，但發表一種廣泛性觀察稱目前這霸權名詞被濫用「加劇了對量子技術現狀的過度炒作」，並且已經有跡象政治化「通過與白人至上（white supremacy）概念的聯絡，喚起了一種令人厭惡的政治立場。」

## 參考文獻

## 外部連結

* Originalartikel: Frank Arute, Kunal Arya, [...], John M. Martinis: Quantum supremacy using a programmable superconducting processor （頁面存檔備份，存於網際網路檔案館） auf nature.com
* YouTube 上的 Demonstrating Quantum Supremacy