首次理论证明：Science论文提出超越经典计算的量子算法

机器之心报道，参与：晓坤、王淑婷、张倩。

近日，来自 TMU、滑铁卢大学和 IBM 的研究者在 Science 上发表论文，首次证明了量子算法可以在特定代数问题上拥有相对于经典算法的理论优势，而在此之前，这还只是个猜想。

Science 评论道：

人们预期量子计算机在求解特定计算问题的时候其性能比经典计算机更高。这种预期基于计算复杂度理论中一个有充分根据的猜想，但严谨地把量子算法和经典算法进行对比是很难实现的。Bravyi 等人在理论上证明了，并行量子电路求解特定线性代数问题时需要的计算步骤和问题规模无关，而类似的经典电路需要的计算步数随着问题规模的增长而指数级增加。这就是所谓的量子优势，源于量子电路中存在的量子关联，这在经典电路中是无法被重现的。

论文：Quantum advantage with shallow circuits

论文地址：http://science.sciencemag.org/content/362/6412/308

arXiv 地址：https://arxiv.org/pdf/1704.00690.pdf

多年来，量子计算机不仅仅是一个想法，人们还在为此付诸行动。如今，企业、政府和情报机构都在投资发展量子技术。现在，TUM 复杂量子系统理论研究院教授 Robert König，与滑铁卢大学量子计算研究所的 David Gosset 以及来自 IBM 的 Sergey Bravyi 合作，已经为这个充满希望的领域奠定了基石。

传统计算机遵循经典物理定律。它们依赖二进制数 0 和 1。这些数字被储存并用于数学运算。在传统的储存单元中，每个比特（信息的最小单位）都由一个电位来表示，该电位决定该比特设置为 1 还是 0。

但在量子计算机中，一个比特（量子比特）可以同时为 0 和 1。因为量子物理定律允许电子一次占据多个状态。因此，量子比特（qubit）以多个重叠状态存在。这种所谓的叠加允许量子计算机一次对多个值执行操作，而单个传统计算机必须顺序执行这些操作。量子计算的前景在于能够更快速地解决某些问题。

从猜想到证明

König 和他的同事决定性地证明了量子计算机的优势。为此，他们开发了一种可以求解一类特别困难的代数问题的量子电路。新的电路有很简单的结构：它仅在每个量子比特上执行固定数量的运算。这样的电路被称作拥有固定的深度。在他们的研究中，研究者证明了这个问题不能用固定深度的经典电路求解。他们还进一步回答了量子算法超越所有经典电路的原因：量子算法利用了量子物理的非局域性。

在本研究之前，量子计算机的优势既没有得到证明，也没办法用实验方法进行展示，尽管有证据指向这个可能。一个实例是 Shor 的量子算法，该算法有效解决了大数素因子分解问题。然而，这仅仅是一个复杂的理论猜想，没有量子计算机，这个问题就无法有效解决。也可以理解为高效的方法是存在的，只是经典计算机还没找到。

Robert König 认为，新的结果主要是对复杂理论的贡献。他表示，「我们的结果表明，量子信息处理的确有很多优点——不必依赖于未证明的复杂理论猜想。」除此之外，该研究为量子计算机研究树立了新的里程碑。由于结构简单，这一新的量子电路可以作为量子算法近期实验实现的备选对象。

参考内容：https://phys.org/news/2018-10-proof-quantum-advantage.html