已经证明：量子计算机能比传统计算机更快解决特定问题

来自 IBM T.J.Watson 研究中心，加拿大滑铁卢大学（University of Waterloo）和德国慕尼黑工业大学（Technical University of Munich）的研究员们已经在理论上证实了量子计算机能够比传统计算机更快地解决特定问题。他们设计的算法已经达到当前量子计算机处理器的计算能力极限，实验证明可能即将推出。

严格来说，Sergey Bravyi、David Gosset 和 Robert König 等三位研究员证明了：

在恒定的时间周期内运行的并行量子算法一定比经典算法更加强大；在解决与二元二次型相关的特定线性代数问题上它们很可能更优。

他们提供的证据基于一种算法，以解决可以在量子常数深度中实现的二次“隐式线性函数”问题。隐式线性函数是一个不完全已知的线性函数，但它“隐藏”在你可以计算的另一个函数中。例如，一个线性函数可以隐藏在一个可以查询的 oracle 中。挑战是基于应用已知函数的结果来充分表征隐式线性函数。如果这听起来有点类似于将公钥反转以找到其私钥的问题，那么这并不意外，因为这正是它所要解决的问题。

在Oracle 的例子中，这个问题通过经典的 Bernstein-Vazirani 算法解决，该算法最小化对 oracle 的查询次数。根据三位研究员的观点，Bernstein-Vazirani 算法被应用于 oracle 的事实限制了它的实际适用性，所以他们建议在二维网格图中“隐藏”一个线性函数。在证明这种做法确实可行之后，他们建立了一个量子常量深度算法来找出隐藏的函数。

研究员们提供的另一半证据表明，与量子电路相反，任何传统电路都需要随输入数量的增加而提高其深度。例如，量子算法可以用一个最大深度为10 的量子电路解决该问题，而无论你有多少输入，但反过来看传统呢，对于16 个输入的问题，需要一个深度为10 的传统电路；对于32 个输入的问题，需要一个深度14 的电路；对于64 个输入的问题，需要一个深度20 的电路等等。

证明的第二部分在哲学上是非常有趣的，因为它详述了量子非局域性的概念，而量子非局域性又与量子纠缠有关，量子纠缠与叠加是量子处理器最独特的特性之一。所以，量子优势似乎来自量子物理学最本质的特性。

在理论层面上，这一成就的价值也不可低估。IBM IBM Q 副总裁 Bob Sutor 写道：

这个证明是量子算法和经典算法之间无条件分离的首次证明，尽管是在恒定深度计算的特殊情况下。

以前，量子计算机比经典计算机更强大的想法是基于因式分解问题。 Shor 指出，量子计算机可以在多项式时间内对整数进行因子分解，也就是说比任何已知的经典计算机算法更高效。尽管这是一个有趣的结果，但它并不排除确实可以找到更高效的经典因式分解算法的可能性。因此，除非人们猜想根本不存在高效的因式分解问题解决方案，这等价于证明” P ≠ NP “，否则人们不能真正地说量子优势被证明。

如上所述，Bravyi、Gosset 和 König 的算法依赖于恒定数量的操作（量子电路的深度），这似乎正好适合当前量子计算机处理器的局限。这些基本与量子位的错误率和相干时间有关，它们限制了操作序列的最大持续时间及其总数。因此，使用短深度电路是当前量子电路任何可行应用的关键。Sutor 说，由于所提出的算法的这种特性，IBM 的研究人员已经开始使用 IBM 量子计算机来证明量子优势。

如果你有兴趣了解证明的全部细节，请不要错过 David Gosset 在普里美特理论物理研究所（Perimeter Institute for Theoretical Physics）的演讲以及演示幻灯片。

查看英文原文： https://www.infoq.com/news/2018/10/quantum-advantage-proved-ibm

感谢冬雨对本文的审校。