人们预期量子计算机在求解特定估算问题的时侯其性能比精典计算机更高。这些预期基于估算复杂度理论中一个有充分依据的猜测，但严谨地把量子算法和精典算法进行对比是很难实现的。等人在理论上证明了，并行量子电路求解特定线性代数问题时须要的估算步骤和问题规模无关，而类似的精典电路须要的估算步数随着问题规模的下降而对数式降低。这就是所谓的量子优势，缘于量子电路中存在的量子关联，这在精典电路中是难以被再现的。
论文：with
论文地址：
arXiv地址：
多年来，量子计算机不仅仅是一个看法，人们还在因此付诸行动。现在，企业、政府和情报机构都在投资发展量子技术。如今，TUM复杂量子系统理论研究院院长König，与滑铁卢学院量子估算研究所的David以及来自IBM的合作，早已为这个饱含希望的领域奠定了基石。
传统计算机遵守精典化学定理。它们依赖二补码数0和1。这种数字被存储并用于物理运算。在传统的存储单元中，每位比特（信息的最小单位）都由一个电位来表示，该电位决定该比特设置为1还是0。
但在量子计算机中，一个比特（量子比特）可以同时为0和1。由于量子化学定理容许电子一次抢占多个状态。为此，量子比特（qubit）以多个重叠状态存在。这些所谓的叠加容许量子计算机一次对多个值执行操作，而单个传统计算机必须次序执行这种操作。量子估算的前景在于能否更快速地解决个别问题。
从推测到证明
König和他的朋友决定性地证明了量子计算机的优势。因此，她们开发了一种可以求解一类非常困难的代数问题的量子电路。新的电路有很简单的结构：它仅在每位量子比特上执行固定数目的运算。这样的电路被叫做拥有固定的深度。在她们的研究中，研究者证明了这个问题不能用固定深度的经典电路求解。她们还进一步回答了量子算法赶超所有精典电路的缘由：量子算法借助了量子化学的非局域性。
在本研究之前，量子计算机的优势既没有得到证明，也没办法用实验方式进行展示，虽然有证据指向这个可能。一个实例是Shor的量子算法关于量子物理的论文，该算法有效解决了大数素因子分解问题。但是，这仅仅是一个复杂的理论推测，没有量子计算机，这个问题就难以有效解决。也可以理解为高效的方式是存在的，只是精典计算机还没找到。
König觉得，新的结果主要是对复杂理论的贡献。他表示，「我们的结果表明，量子信息处理的确有好多优点——不必依赖于未证明的复杂理论猜测。」除此之外关于量子物理的论文，该研究为量子计算机研究树立了新的里程碑。因为结构简单，这一新的量子电路可以作为量子算法近日实验实现的备选对象。
参考内容：