伯克利计算机理论家展示了验证量子节拍经典的途径

导读随着世界各地的多个研究小组竞相建立可扩展的量子计算机，关于如何验证量子至上的实现仍然存在疑问。量子至上性是描述量子计算机解决计算任

随着世界各地的多个研究小组竞相建立可扩展的量子计算机，关于如何验证量子至上的实现仍然存在疑问。

量子至上性是描述量子计算机解决计算任务的能力的术语，对于任何经典算法来说这都是非常困难的。它被认为是量子计算的一个重要里程碑，但由于量子活动的本质违背了传统的确证，因此一直在努力找到一种方法来证明量子至上已经实现。

加州大学伯克利分校的研究人员刚刚给出了一个领先的实用方案，称为随机电路采样(RCS)，这是一种合格的批准印章，其背后是复杂性理论证据。随机电路采样是谷歌提出的技术，用于证明它是否已经通过今年早些时候推出的72比特的计算机芯片 - Bristlecone实现了量子至上。

加州大学伯克利分校的计算机理论家在10月29日星期一发表在“ 自然物理学 ”杂志上的论文中发表了他们的RCS证据作为验证方法。

研究主要研究者Umesh Vazirani，加州大学伯克利分校电子工程和计算机科学教授Rome A. Strauch表示，“对量子至上的强有力证据的需求未被充分认识，但重要的是要将其降低。” “除了成为有用量子计算机之路上的里程碑之外，量子至上性是一种新的物理实验，用于在新制度中测试量子力学。对于任何这样的实验，必须回答的基本问题是我们有多自信观察到的行为确实是量子的，不可能通过经典手段复制。这就是我们的结果所解决的。“

本文的其他研究者是博士后研究员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论文的实验性违反。一旦实现，下一个挑战将是设计能够解决实际有用问题的量子计算机。”