研究快讯 | 量子绝热算法和量子线路算法一样强大

原文已发表在CPL Express Letters栏目

Received 10 October 2018; online 23 October 2018

Express Letter                                                    

量子计算机为什么比经典计算机强大？是不是对于任何问题，量子计算机都比经典计算机强大？这些基本问题依然没有明确的答案。回答这些问题的一个途径是尝试为某个给定的问题设计最快的量子算法，然后和最快的经典算法比较。迄今为止，对于绝大多数问题，人们还没有设计出比经典算法更快的量子算法。经过多年的发展，人们发现量子算法有两类非常不同的设计思路。第一是大家熟知的量子线路算法：选择数量合适的量子比特，然后设计一系列量子门来完成某个给定的任务。第二是2000年提出的量子绝热算法：人们将一个简单哈密顿量缓慢转变成一个更复杂的哈密顿量，保证系统总是处于基态，而演化结束时的复杂哈密顿量的基态就是给定问题的解。

由于这两类算法非常不同，一个很自然的问题是，这两种算法在时间复杂度上等价吗？对于一个量子线路算法，一定存在一个等价的量子绝热算法吗？反之同问。早期的研究表明，量子绝热算法和量子线路算法在时间复杂度上是多项式等价的。也就是说，如果一个量子线路算法有L个量子门，那么一定存在一个量子绝热算法，它的运行时间正比于Lⁿ(n>1)。反之亦然。

本文中，北京大学吴飙课题组严格证明了每一个量子线路算法都可以转化为一个时间复杂度完全相同的量子绝热算法。换句话说，对于一个需要L个量子门的量子线路算法，我们可以找到一个量子绝热算法，它的运行时间正比于L。由于量子绝热算法的核心是设计物理上合理的哈密顿量，这一严格证明意味着对于任何一个问题（即使是纯数学问题），我们都可以通过物理的手段来寻找它的最快算法。在这个意义上，我们可以说量子算法是物理的（Quantum algorithm is physical）。

量子绝热算法的关键是设计起始哈密顿量和末点哈密顿量。一个相关的问题是，量子绝热算法的时间复杂度是不是完全由这两个哈密顿量决定？本文其实也回答了这个问题，答案是不。作者的证明方法里含有一个量子绝热算法，它和另外一个为人熟知的量子绝热算法拥有同样的起始哈密顿量和末点哈密顿量。但是，本文的算法由于选择了一个不同的绝热演化路径，有个明显的指数加快。