短深度量子电路的量子优势已被正式证明

来自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

感谢冬雨对本文的审校。