量子计算优越性

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

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

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

計算複雜度

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

Bounded-error quantum polynomial time（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月份開始一直有媒體傳言谷歌實現量子霸權的文章在流轉，《科學美國人》於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實現量子優越性的學術論文，各種學者和人士對此各種議論紛紛，莫衷一是：

• 美國總統川普女兒伊萬卡在社交媒体上称美国正式实现量子霸权，谷歌的项目是与特朗普政府、以及加州大学圣塔芭芭拉分校合作进行的。
• 谷歌首席執行長 Sundar Pichai 受訪時也對此事進行回應，用委婉的譬喻稱Google 的實驗就是像是萊特兄弟首次飛行，雖第一架飛機只飛行了 12 秒鐘，並沒有真的實際應用性，但這仍然表明飛機的概念是可行的。
• 美国德州大学奥斯汀分校的理论计算机科学家斯科特 阿伦森（Scott Aaronson）則保守性中立认为，虽谷歌上述成果实际应用有限“但假设它是成立的，那么科学象徵成就是巨大的。”因為代表量子電腦取代傳統電腦有其可能。
• 澳大利亚新南威尔士大学量子物理学家米歇尔 西蒙斯（Michelle Simmons）说谷歌给了我们一種实验证据，证明量子加速在真实世界的系统中是有可能的。
• 而值得關注是量子霸权此一名詞提出者約翰·普里斯基爾在同一時期雖沒對具體案例發言，但發表一種廣泛性觀察稱目前这霸權名词被濫用“加剧了对量子技术现状的过度炒作”，并且已經有跡象政治化“通过与白人至上（white supremacy）概念的联系，唤起了一种令人厌恶的政治立场。”