随着世界各地的多个研究小组竞相建立可扩展的量子计算机，关于如何验证量子至上的实现仍然存在疑问。量子至上是描述量子计算机解决计算任务的能力的术语，对于任何经典算法来说这都是非常困难的。它被认为是量子计算的一个重要里程碑，但由于量子活动的本质违背了传统的确证，因此一直在努力找到一种方法来证明量子至上已经实现。

加州大学伯克利分校的研究人员刚刚给出了一个领先的实用方案，称为随机电路采样(RCS)，是一种合格的批准印章，其背后是复杂性理论证据。随机电路采样是谷歌提出的一种技术，用于证明它是否已经通过今年早些时候推出的名为Bristlecone的72-qubit计算机芯片实现了量子至上。加州大学伯克利分校的计算机理论家在10月29日星期一发表在“自然物理学”杂志上的论文中发表了他们的RCS证明作为验证方法。

加州大学伯克利分校的电子工程和计算机科学教授Roger A. Strauch表示，“对量子至上的强有力证据的需求未得到充分重视，但重要的是要将其降低，”研究主要研究者Umesh Vazirani说道。量子至上是在有用的量子计算机的道路上的一个里程碑，它是一种新的物理实验，用于测试新制度中的量子力学。对于任何这样的实验，必须回答的基本问题是我们是多么自信观察到的行为确实是量子的，不可能通过经典手段复制。这就是我们的结果所解决的。“本文的其他研究者是博士后研究员Adam Bouland和Bill Feffer，以及博士研究生Chinmay Nirkhe。学生，都在Vazirani的理论计算研究小组。

对量子的投资正在升温

本文是在政府，学术界和工业界开展量子信息科学活动的过程中加入的。国会正在考虑国家量子倡议法案，上个月，美国能源部和国家科学基金会宣布将近2.5亿美元的拨款用于支持量子科学和技术研究。

与此同时，劳伦斯伯克利国家实验室和加州大学伯克利分校宣布成立伯克利量子公司，该公司旨在加速和扩大量子信息科学的创新。随着国际量子研究竞争的加剧以及对日益复杂的计算的需求的增长，风险很高。对于真正的量子计算，即使是迄今为止最快的超级计算机也不切实际的问题可能相对有效地解决。它将成为密码学，分子和化学相互作用模拟以及机器学习的改变者。

量子计算机不受传统计算机位的传统0和1的限制。相反，量子比特或量子比特可以编码0，1和两者的任何量子叠加，以同时创建多个状态。当Google公布了Bristlecone时，它表示其量子至上的经验证据将来自随机电路采样，这是一种技术，其中设备将使用随机设置来表现得像随机量子电路。为了说服力，还需要有力的证据表明，在经典计算机上运行的经典算法不能模拟随机量子电路，至少在合理的时间内。

检测量子重音

Vazirani的团队提到了随机量子电路的输出和英语中的一串随机音节之间的类比：即使音节不形成连贯的句子或单词，它们仍将具有英语“重音”并且将具有可识别的不同来自希腊语或梵语。他们表明，通过称为“最差 - 平均 - 减少案例”的技术复杂性理论结构，产生具有“量子重音”的随机输出对于经典计算机来说确实很难。

下一步是验证量子器件实际上是否具有量子重音。这依赖于Goldilocks原理 - 一台50-bit的机器足够大，功能强大，但足够小，可以用经典的超级计算机模拟。如果可以验证50-qubit机器是否具有量子重音，那么这将提供强有力的证据表明100夸脱的机器，这将非常难以经典模拟，也会这样做。但是，即使经典的超级计算机被编程为具有量子重音，它是否能够识别母语人士?伯克利研究人员说，验证说话人输出的唯一方法是通过统计检验。谷歌研究人员建议通过称为“交叉熵差异”的指标来衡量匹配程度。交叉熵得分为1将是理想的匹配。

所谓的量子器件可以被认为表现得像添加了随机噪声的理想量子电路。Fefferman和Bouland说，交叉熵分数将证明量子重音的真实性，前提是噪声总是会增加输出的熵。情况并非总是如此 - 例如，如果噪声过程优先消除0超过1秒，它实际上可以减少熵。“如果谷歌的随机电路是由允许这种擦除的过程产生的，那么交叉熵就不会成为衡量量子至上的有效方法，”布兰德说。“这就是为什么谷歌确定其设备如何偏离真正的随机量子电路非常重要的原因。”

这些结果是Vazirani在1993年与他的学生Ethan Bernstein所做的工作的回声，他们提出了量子计算机将指数地加速某些计算的第一个正式证据。这打开了量子算法的大门，表明量子计算机违反了扩展教会 - 图灵论文，这是计算机科学的基本原理。贝尔实验室的Peter Shor进一步展示了一个非常重要的实际问题 - 整数分解，可以通过量子计算机以指数方式加速。“这个序列为竞赛构建工作量子计算机提供了一个模板，”Vazirani说。“量子至上是对Extended Church-Turing论文的实验性违反。一旦实现，下一个挑战将是设计能够解决实际有用问题的量子计算机。”陆军研究办公室，国家科学基金会，Vannevar Bush教职员奖学金和国家标准与技术研究所帮助支持了这项研究。