量子计算优越性
量子计算机解决经典计算机解决不了的问题 / 维基百科,自由的 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]