近日，来自 TUM、滑铁卢大学和 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 的量子算法，该算法有效解决了大数素因子分解问题。然而，这仅仅是一个复杂的理论猜想，没有量子计算机，这个问题就无法有效解决。也可以理解为高效的方法是存在的，只是经典计算机还没找到。
但是这篇论文不是量子计算超越经典计算的首次理论证明。若只从查询复杂度评估，Grover算法、DJ算法等很多算法很早就被理论证明具有相对对应经典算法的理论优势。
该工作的主要意义在于，证明存在一个计算问题（一种特殊形式的二次型）可以用常数深度的量子电路计算，但是该问题不可以用常数深度的经典电路计算（事实上证明了任何计算该问题的经典电路都需要log n量级的深度）。该证明工作中的计算问题是关于电路深度复杂度的separation，是第一个分离开了SQC和NC^0的工作；且不需要基于其他复杂性类别上的猜想或假设。
同时本文所提出的常数深度电路只需要使用1-2个在2D网络上定域性地运作的量子比特门，其理论上可实现的量子优势也将更有望在近期小规模、没有纠错机制的量子计算机上被实验验证。该类量子电路统称Shallow Quantum Circuits（SQC）。
参考内容：https://phys.org/news/2018-10-proof-quantum-advantage.html
