自从费曼提出用量子计算机模拟量子系统的想法，量子计算的巨大潜力日益受到关注。一个很自然的问题是：量子计算相对经典计算是不是真的有优势？一个常见的看法是：因为量子比特有叠加性，允许有指数多个量子态的叠加，而经典比特做不到这一点，所以量子计算比经典计算更强大。然而，量子叠加并不能告诉我们在什么计算问题上量子比经典强大。要严格地证明量子优越性，我们需要从复杂度的角度出发。具体地说，我们希望知道量子计算在经典的复杂度类中处于什么位置。如果我们把量子计算机和经典计算机能在多项式时间内解决的问题分别记作BQP和P，那么问题就变成了探索BQP和P的关系。通常认为另一个复杂度类，NP（即那些能在多项式时间内验证的问题的集合）包含了P。整数分解就是一个NP问题，而Shor算法（一种量子算法）能在多项式时间内解决这个问题。然而，我们并不能确定整数分解是不是一定没有经典有效的算法去解决。

《国家科学评论》最近发表了南方科技大学物理系翁文康教授撰写的题为“Quantum supremacy: some fundamental concepts”的观点文章（Natl Sci Rev 2018; doi: 10.1093/nsr/nwy072. https://doi.org/10.1093/nsr/nwy072）。该文章讨论了量子霸权相关的一些基础概念以及常用模型。量子霸权指的是量子计算机能执行某个计算任务，而目前所有的经典计算机都无法在给定的时间内执行这个任务。尽管量子霸权相关的任务都有严谨的复杂度证明，但在这个语境下我们更关心准确的数字，比如需要多少个比特和量子门才能超越经典计算。该文章还讨论了经典模拟的准确概念，包括强模拟和弱模拟。强模拟指的是用经典计算机去计算量子线路的输出概率，而弱模拟指的是从量子线路对应的概率分布中采样。强模拟的模拟难度大于弱模拟。此外，模拟精度对模拟难度也是有影响的。

文章最后讨论了三个常见的量子霸权模型：玻色采样、IQP线路采样以及混沌量子线路采样。玻色采样指的是从一个线性光学网络中采样，而经典模拟的任务是模拟输出光子的概率分布。玻色采样的一个性质是输出概率跟复矩阵的积和式相关，而计算复矩阵的积和式对经典计算机来说是很难的。IQP线路是这样一种线路：从出发，对每个比特作用Hadamard门，再作用很多对角的门，最后又对每个比特作用Hadamard门。而混沌量子线路是按照特定的规则作用两比特门，然后随机地从某个量子门的集合中抽取单比特门来作用在空余的位置。这类线路的输出概率会趋近于量子混沌的特征分布——Porter-Thomas分布。尽管这三个模型都有严格的复杂度证明，但在现在的技术条件下实现量子霸权仍然是个挑战。（来源：科学网）