量子計算優越性
量子计算机解决经典计算机解决不了的问题 / 維基百科,自由的 encyclopedia
量子計算優越性(英文:Quantum Advantage)[1],或稱量子霸權(英語:quantum supremacy),是指用量子電腦解決古典電腦難以解決的問題,問題本身未必需要有實際應用。量子計算優越性則是指量子電腦在解決實務問題上能比古典電腦更快而帶來的優勢,從計算複雜性理論的角度來說,這通常代表量子電腦相對最佳古典演算法的加速是超多項式的。[2] 這個術語最初是由約翰·普雷斯基爾所提出,[3]但量子計算優勢的概念(特別是用於模擬量子系統)可以追溯到尤里·馬寧(1980)[4] 和理察·費曼(1981)提出的量子計算建議。 [5]
秀爾演算法能在量子電腦上以多項式時間執行整數的因數分解,和已知的古典演算法相比具有超多項式加速。[6] 一般認為使用古典資源分解整數很困難,然而嚴謹的證明尚未出現。缺乏古典計算困難度的證明,是難以明確展示量子優越性的主要原因。這影響了常見的量子優越性問題:Aaronson和Arkhipov的玻色子抽樣問題(boson sampling)、[7] D-Wave的specialized frustrated cluster loop problems、 以及隨機量子電路抽樣問題。
像整數分解一樣,基於合理的複雜度假設,用古典電腦對隨機量子電路的輸出分佈進行抽樣是困難的。Google先前宣佈,計劃在2017年底之前用含有49個超導量子位元的陣列解決這個問題,以展示量子優越性。[8] 在那之後,Intel、IBM、Google分別宣佈了49、53、72個量子位元的系統。[9]
2020年12月4日,中國科學技術大學發佈使用76個光子的量子電腦「九章」,並宣佈實現量子優越性,使中國成為全球第二個實現「量子優越性」的國家。[10]