量子计算优越性（英文：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]

复杂度理论研究解决计算问题所需的资源如何随问题的大小变化，量子复杂度理论延伸古典计算复杂度理论到通用量子电脑可以完成的工作上，对于建造量子电脑或处理退相干和噪声的困难则忽略不计。^[11] 由于量子资讯比古典资讯更广义 ，很显然量子电脑可以有效地模拟任何古典算法 。

有限错误量子多项式时间（BQP）这个复杂度类包括通用量子电脑在多项式时间能解决的决策问题，它和古典复杂度类的关系是${\displaystyle P\subseteq BPP\subseteq BQP\subseteq PSPACE}$ ， ^[12] 这些子集关系之中有没有真子集仍是未决问题。

与答案为是或否的决策问题不同，抽样问题要求从几率分布中抽取样本。^[13] 如果有古典算法可以有效地从任意量子电路的输出中抽样，则多项式谱系将崩溃到第三级，普遍认为这是极不可能的。 玻色子抽样是较具体的提议，其古典困难度来自于计算具有复数元素的大矩阵其积和式的困难度，而那是P#-complete的问题。^[14] 用于得出此结论的论点也已扩展到IQP抽样，^[15] 并只需假设问题的平均和最坏情况复杂度相同。

下列算法对已知的最好的古典算法提供超多项式加速：^[16]

秀尔算法用 ${\displaystyle {\tilde {O))(n^{3})}$时间分解n-位元整数，^[6] 而已知的最好的古典算法需要${\displaystyle 2^{O(n^{1/3})))$时间，复杂度的最佳上限是 ${\displaystyle O(2^{n/3+o(1)})}$ 。 它还能加速任何可化简成整数分解的问题。 ^[17]

这个算法在历史上和实务上都对量子计算很重要，它是第一个用多项式时间解决困难古典计算问题的量子算法。 ^[6] 对其困难度的信念强烈到当今最常见的加密协议RSA就是根据整数分解。 ^[18] 能重复成功运行这种算法的量子电脑有潜力破解这种加密系统。 ^[19] 需要避免迫在眉睫的这种风险被称为Y2Q，名称来自2000年问题的别名"Y2K"。

这是基于一个古典计算问题：将全同光子穿过线性光学网络用来解决某些抽样和检索的问题，在一些猜测性的假设下，对古典计算是很棘手的。 ^[7] 然而，已经有研究显示，如果系统具有足够大的失真和噪声，古典电脑能够有效率地模拟玻色子抽样问题。 ^[20]

迄今为止，最大的玻色子抽样实验能做到6个光学模式，一次最多可以处理6个光子。^[21] 对于包含 n 个光子 和 m 个输出模式的系统，模拟玻色子抽样的古典算法最好的执行时间是 。 ^[22] BosonSampling 是一个用 R 写的开放原始码实现，估计需要50个光子才能达成玻色子抽样的量子优越性。

在模拟任意随机量子电路的算法当中，已知最佳的算法需要的时间随量子位元个数指数式地上升，因此一个研究小组估计50个量子位元可能就足以达成量子优越性。^[23] Google已经宣布打算在2017年底前用49量子位元的晶片展示量子优越性，方法是对其输出分布抽样，这个抽样用古典电脑将无法在合理时间内模拟。^[8] 然而56量子位元的量子电路模拟已经在超级计算机上完成， 这可能让达成量子优越性所需的量子位元数增加。^[24]

因为退相干和噪声，量子电脑比古典电脑更容易受到资料错误的影响。 阈值定理指出，有噪声的量子电脑只要每一步计算的错误率低于某个值，就可以用量子错误修正码^[25][26] 模拟无噪声的量子电脑 ，数值模拟的结果指出该阈值可以高达3%。^[27]

然而，错误修正所需的资源会如何随量子位元数上升并不清楚。 怀疑论者指出，大型量子系统中未知的噪声行为是成功实现量子电脑和达成量子优越性的潜在障碍，要太多的量子位元用以纠错最后会成为一堵高墙无法翻越。^[28]

2017年10月，IBM在传统的超级计算机上展示了56个量子位元的模拟，增加了量子优越性所需的量子位元数量。^[24] 2018年11月，Google宣布与NASA建立合作伙伴关系，“将分析在Google量子处理器上运行的量子电路的结果，并...与古典模拟比较，以验证Google硬件并为量子优越性建立基础。”^[29] 2018年发表的理论工作提出，如果能将错误率降到够低，那么“具有7x7量子位元的二维点阵执行大约40个时钟周期”应该可以实现量子优越性。^[23]

2019年1月8日，IBM在消费电子展上展示了已开发的世界首款商业化量子电脑IBM Q System One^[30]但其基本只有实验研究价值，没有超越传统电脑的实用性。而6月份开始一直有媒体传言谷歌实现量子霸权的文章在流转，《科学美国人》于2019年6月21日提出，根据聂文定律（英语：Neven's law），^[31] 量子优越性可能在2019年发生。

2019年9月20日，英国《金融时报》基于一篇在NASA网站上短暂出现的文章报导：“Google声称已经用54个量子位元的数组（其中53个功能正常）的量子电脑原型机悬铃木^[32]达到了量子优越性，它们在200秒内执行一系列操作，相同运算将花费超级计算机大约10,000年才能完成”。^[33]

2019年10月21日IBM于arXiv发布一篇文章，^[34][35] 指出若能有效率使用Summit超级计算机的硬盘和并行计算资源，估计可以将10,000年时间降低至2.5天，计算53和54个量子位元分别需要64PiB和128PiB的硬盘空间。^[36]

2019年10月23日自然期刊刊登了Google实现量子优越性的学术论文^[37][38]，各种学者和人士对此各种议论纷纷，莫衷一是：

• 美国总统川普女儿伊万卡在社交媒体上称美国正式实现量子霸权，谷歌的项目是与特朗普政府、以及加州大学圣塔芭芭拉分校合作进行的。^[39]
• 谷歌首席行政总裁 Sundar Pichai 受访时也对此事进行回应，用委婉的譬喻称Google 的实验就是像是莱特兄弟首次飞行，虽第一架飞机只飞行了 12 秒钟，并没有真的实际应用性，但这仍然表明飞机的概念是可行的。^[40]
• 美国德州大学奥斯汀分校的理论电脑科学家斯科特 阿伦森（Scott Aaronson）则保守性中立认为，虽谷歌上述成果实际应用有限“但假设它是成立的，那么科学象征成就是巨大的。”因为代表量子电脑取代传统电脑有其可能。^[40]
• 澳大利亚新南威尔士大学量子物理学家米歇尔 西蒙斯（Michelle Simmons）说谷歌给了我们一种实验证据，证明量子加速在真实世界的系统中是有可能的。^[40]
• 而值得关注是量子霸权此一名词提出者约翰·普里斯基尔在同一时期虽没对具体案例发言^[36]，但发表一种广泛性观察称目前这霸权名词被滥用“加剧了对量子技术现状的过度炒作”，并且已经有迹象政治化“通过与白人至上（white supremacy）概念的联络，唤起了一种令人厌恶的政治立场。”

• 量子计算
• 量子资讯科学
• 量子技术

• Originalartikel: Frank Arute, Kunal Arya, [...], John M. Martinis: Quantum supremacy using a programmable superconducting processor （页面存档备份，存于互联网档案馆） auf nature.com
• YouTube上的Demonstrating Quantum Supremacy