
_START_ARTICLE_
量子優越性
_START_PARAGRAPH_
量子优越性（Quantum Supremacy）是指用量子电脑解决古典电脑实际上解决不了的问题，问题本身未必需要有实际应用。量子优势（Quantum Advantage）则是指量子电脑在解决实务问题上能比古典电脑更快而带来的优势，从计算复杂性理论的角度来说，这通常代表量子电脑相对最佳古典算法的加速是超多项式的。 这个术语最初是由约翰·普里斯基尔（John Preskill）所提出，但量子计算优势的概念（特别是用于模拟量子系统）可以追溯到尤里·马宁（1980） 和理察·费曼（1981）提出的量子计算建议。   _NEWLINE_秀尔算法能在量子电脑上以多项式时间执行整数的因数分解，和已知的古典算法相比具有超多项式加速。 一般认为使用古典资源分解整数很困难，然而严谨的证明尚未出现。缺乏古典计算困难度的证明，是难以明确展示量子优越性的主要原因。这影响了常见的量子优越性问题：Aaronson和Arkhipov的玻色子抽样问题（boson sampling）、 D-Wave的specialized frustrated cluster loop problems、 以及随机量子电路抽样问题。_NEWLINE_像整数分解一样，基于合理的复杂度假设，用古典电脑对随机量子电路的输出分布进行抽样是困难的。Google先前宣布，计划在2017年底之前用含有49个超导量子位元的阵列解决这个问题，以展示量子优越性。 在那之后，Intel、IBM、Google分别宣布了49、53、72个量子位元的系统。 2017年10月，IBM在传统的超级电脑上展示了56个量子位元的模拟，增加了量子优越性所需的量子位元数量。 2018年11月，Google宣布与NASA建立合作伙伴关系，“将分析在Google量子处理器上运行的量子电路的结果，并...与古典模拟比较，以验证Google硬件并为量子优越性建立基础。” 2018年发表的理论工作提出，如果能将错误率降到够低，那么“具有7x7量子位元的二维点阵执行大约40个时钟周期”应该可以实现量子优越性。 《 科学美国人》于2019年6月21日提出，根据聂文定律（Neven's law），  量子优越性可能在2019年发生。 2019年9月20日，英国《金融时报》报导：“ Google声称已经用54个量子位元的阵列（其中53个功能正常）达到了量子优越性，它们在200秒内执行一系列操作，相同运算将花费超级电脑大约10,000年才能完成”。
_START_SECTION_
计算复杂度
_START_PARAGRAPH_
复杂度理论研究解决计算问题所需的资源如何随问题的大小变化，量子复杂度理论延伸古典计算复杂度理论到通用量子电脑可以完成的工作上，对于建造量子电脑或处理退相干和噪声的困难则忽略不计。 由于量子资讯比古典资讯更广义，很显然量子电脑可以有效地模拟任何古典算法 。_NEWLINE_Bounded-error quantum polynomial time（BQP）这个复杂度类别包括通用量子电脑在多项式时间能解决的决策问题，它和古典复杂度类别的关系是 ，  这些子集关系之中有没有真子集仍是未决问题。  _NEWLINE_与答案为是或否的决策问题不同，抽样问题要求从几率分布中抽取样本。 如果有古典算法可以有效地从任意量子电路的输出中抽样，则多项式谱系将崩溃到第三级，普遍认为这是极不可能的。 玻色子抽样是较具体的提议，其古典困难度来自于计算具有复数元素的大矩阵其积和式的困难度，而那是P#-complete的问题。 用于得出此结论的论点也已扩展到IQP抽样，  并只需假设问题的平均和最坏情况复杂度相同。
_START_SECTION_
超多项式加速
_START_PARAGRAPH_
下列算法对已知的最好的古典算法提供超多项式加速：
_START_SECTION_
秀尔整数分解算法
_START_PARAGRAPH_
秀尔算法用时间分解n-位元整数， 而已知的最好的古典算法需要时间，复杂度的最佳上限是 。  它还能加速任何可化简成整数分解的问题。 _NEWLINE_这个算法在历史上和实务上都对量子计算很重要，它是第一个用多项式时间解决困难古典计算问题的量子算法。  对其困难度的信念强烈到当今最常见的加密协议RSA就是根据整数分解。  能重复成功运行这种算法的量子电脑有潜力破解这种加密系统。  需要避免迫在眉睫的这种风险被称为Y2Q，名称来自2000年问题的别名"Y2K"。
_START_SECTION_
玻色子抽样
_START_PARAGRAPH_
这是基于一个古典计算问题：将全同光子穿过线性光学网络用来解决某些抽样和检索的问题，在一些猜测性的假设下，对古典计算是很棘手的。  然而，已经有研究显示，如果系统具有足够大的失真和噪声，古典电脑能够有效率地模拟玻色子抽样问题。  _NEWLINE_迄今为止，最大的玻色子抽样实验能做到6个光学模式，一次最多可以处理6个光子。 对于包含n 个光子 和m 个输出模式的系统，模拟玻色子抽样的古典算法最好的执行时间是。   BosonSampling 是一个用R 写的开放源码实作，估计需要50个光子才能达成玻色子抽样的量子优越性。
_START_SECTION_
对随机量子电路的输出分布抽样
_START_PARAGRAPH_
在模拟任意随机量子电路的算法当中，已知最佳的算法需要的时间随量子位元个数指数式地上升，因此一个研究小组估计50个量子位元可能就足以达成量子优越性。 Google已经宣布打算在2017年底前用49量子位元的芯片展示量子优越性，方法是对其输出分布抽样，这个抽样用古典电脑将无法在合理时间内模拟。 然而56量子位元的量子电路模拟已经在超级电脑上完成， 这可能让达成量子优越性所需的量子位元数增加。
_START_SECTION_
怀疑论
_START_PARAGRAPH_
因为退相干和噪声，量子电脑比古典电脑更容易受到资料错误的影响。 阈值定理指出，有噪声的量子电脑只要每一步计算的错误率低于某个值，就可以用量子错误修正码 模拟无噪声的量子电脑，数值模拟的结果指出该阈值可以高达3%。_NEWLINE_然而，错误修正所需的资源会如何随量子位元数上升并不清楚。  怀疑论者指出，大型量子系统中未知的噪声行为是成功实作量子电脑和达成量子优越性的潜在障碍。