蒋多多| 经典计算的天花板：科学家找到只有量子计算才能解决的问题 前沿-机器之心
蒋多多选自QuantaMagazine
作者：Kevin Hartnett
机器之心编译
参与：Huiyuan Zhuo、刘晓坤
在量子计算机研究的早期，计算机科学家提出了一个问题，他们知道这个问题的答案将会揭晓这些未来机器的强大力量背后的秘密。25 年过去了，问题仍然没有解决。在 5 月底在线发布的一篇论文中《Oracle Separation of BQP and PH》，计算机科学家 Ran Raz 和 Avishay Tal 提供了强有力的证据，证明量子计算机具有超越任何传统计算机能够达到的计算能力。Raz 是普林斯顿大学和魏茨曼科学研究员的教授，Tal 是斯坦福大学博士后，他们定义了一类特定的计算问题。他们在一定程度上证明了量子计算机能够有效解决这个问题，而传统计算机却永远无法解决。自 1993 年以来，计算机科学家一直在找寻这样一个问题，在当时他们首次定义了一类被称为「BQP」的问题，它涵盖了量子计算机可以解决的所有问题。
Oracle Separation of BQP and PH：
计算机科学家希望将 BQP 与一类被称为「PH」的问题进行对比，PH 涵盖了任何可能的传统计算机（甚至是一些未来文明所设计的不可思议的先进计算机）所能解决的问题。能否进行对比取决于能否找到一个被证明是 BQP 却不是 PH 的问题。现在，Raz 和 Tal 做到了。
这一成果并没有使量子计算机在任何实际意义上超越传统计算机。比如，理论计算机科学家已经知道量子计算机可以解决传统计算机所能解决的任何问题。同时，工程师仍在努力构建有用的量子计算机。但是 Raz 和 Tal 的论文证明了量子计算机和传统计算机其实是不同的类别——即使在传统计算机超越所有现实的世界中，量子计算机仍然会超越它们。
量子类别
理论计算机科学的基本任务是将问题按复杂度等级分类。一个复杂类包含在给定资源预算内所能解决的所有问题，其中资源可能是指时间或内存。
计算机科学家已经找到了一种有效的算法，例如用于测试一个数字是否是素数。然而，他们仍没有找到一个有效的算法来计算大数的素数因子。因此，计算机科学家认为（但无法证明）这两个问题属于不同的复杂度等级。
两个最著名的复杂度等级是「P」和「NP」。P 是传统计算机可以快速解决的所有问题。（「这个数字是否是素数？」属于 P。）NP 是传统计算机不能迅速解决的所有问题，但可以快速验证一个答案。（「哪些数是这个数的素数因子？」属于 NP。）计算机科学家认为 P 和 NP 是不同的类别，但事实上证明它们的不同是该领域最难和最重要的开放性问题。
P∈NP∈PH，BQP 覆盖所有的 P 问题和部分的 NP、PH 问题（未证明）；现在人们终于找到了属于 BQP 而不属于 PH 的问题。图源：Lucy Reading-Ikkanda / Quanta Magazine
1993 年计算机科学家 Ethan Bernstein 和 Umesh Vazirani 为「有界误差量子多项式时间」定义了一个新的复杂度等级，他们称之为 BQP。他们定义的类包含量子计算机可以有效解决的所有决策问题——问题的答案为是或否。同时他们也证明了量子计算机可以解决传统计算机可以解决的所有问题。也就是说，BQP 包含 P 中的所有问题。
但是他们无法确定 BQP 是否包含另一个重要的类「PH」（即「多项式分层」）中找不到的问题。PH 是 NP 的一个推广。这意味着如果你从 NP 中的一个问题出发，并通过「存在」和「任意」这样的限定语句进行分层以使其更为复杂，PH 也包含了所有你遇到的问题。现今传统计算机无法解决 PH 中的大多数问题，但如果 P 被证明等价于 NP，则可以将 PH 看作是传统计算机可以解决的所有问题的类。换言之，比较 BQP 和 PH 是为了确定是否量子计算机优于传统计算机，那么即使传统计算机能（出乎意料地）解决比现在的量子计算机更多的问题，量子计算机仍能存在。德克萨斯大学奥斯汀分校的计算机科学家 Scott Aaronson 说：「PH 是最基本的传统复杂度等级之一。所以我们想知道量子计算机如何适应传统复杂度理论？」
当谈到复杂度等级时，举个例子会很有帮助。「旅行推销员问题」询问是否存在一条途经一些城市且短于给定距离的路径。这是个 NP 问题。一个更复杂的问题是，通过这些城市的最短路径是否等于给定距离。这个问题是 PH。
区分两个复杂度等级的最好方法是找到一个问题，其能够被证明属于一个类而不属于另一个类。然而由于基础和技术上的障碍，找到这样一个问题很有挑战性。
如果你想要找到一个在 BQP 但不在 PH 中的问题，你必须确定一些东西，也就是 Aaronson 说的：「根据定义，一个传统计算机甚至无法有效验证答案，更别说找到答案了。这就排除了我们在计算机科学中考虑的许多问题。」
询问 oracle
问题是这样的。设想你有两个随机数字生成器，每个生成器产生一个数字序列。你的计算机得到的问题是这样的：这两个序列是否完全独立，还是以某种隐秘的方式相关（例如，一个序列是另一个序列的「傅立叶变换」）？Aaronson 在 2009 年介绍了这种「forrelation」问题并证明其属于 BQP。更难的第二步是证明 forrelation 不在 PH 中。
普林斯顿大学的理论计算机科学家 Ran Raz 找到一种分离两个计算类的方法。
从特定的意义上来说，这正是 Raz 和 Tal 所做的。他们的论文实现了 BQP 和 PH 之间的分离，被称为「oracle」（或「黑箱」）分离。这是计算机科学中常见的一种结果，当研究人员真正想证明的事情超出他们的理解范围时，他们会采取这种方法。
区分像 BQP 和 PH 这样的复杂度等级的最佳方法实际上是测量解决每个问题所需的计算时间。但如多伦多大学的计算机科学家 Henry Yuen 所说：「计算机科学家对实际的计算时间没有充足的理解或测量能力。」因此，计算机科学家测量了其它一些他们希望可以侧面反映无法测量的计算时间的东西：他们计算出计算机需要咨询 oracle 以便得出答案所需的次数。oracle 就像一位提示者。你不知道它的提示如何产生的，但你知道它们是可靠的。
如果你的问题是要弄清楚两个随机数字生成器是否潜在相关，那么你可以向 oracle 提问，比如说：「每个生成器的第六个数字是什么？」然后你根据每种计算机解决问题所需的提示数量比较它们的计算能力。需要更多提示的计算机速度更慢。
Tal 说：「从某种意义上来说，我们能更好地理解模型。它传递更多的是信息而不是计算。」
斯坦福大学的理论计算机科学家 Avishay 使用 oracle 分离来区分 BQP 和 PH。
Raz 和 Tal 的新论文证明了，量子计算机需要比传统计算机少得多的提示来解决 forrelation 问题。事实上，量子计算机仅需要一个提示。而即使有无穷多的提示，PH 中也没有可以解决问题的算法。Raz 说：「这意味着存在一个非常有效的量子算法可以解决这个问题。但如果你仅考虑传统算法，即使你拥有很高等级的传统算法，它们也无法解决。」这表明，对于 oracle 而言，forrelation 问题在 BQP 而不是 PH 中。
差不多 4 年以前，Raz 和 Tal 几乎达成了这一结果，但他们无法在证明中完成一个步骤。然后就在一个月前，Tal 听到一篇关于伪随机数生成器的新论文《Pseudorandom Generators from Polarizing Random Walks》，并意识到这篇论文中的技术正是他和 Raz 需要完成的。Tal 说：「这正是我们缺失的一块拼图。」
Pseudorandom Generators from Polarizing Random Walks：
BQP 和 PH 分离的消息迅速传了开来。Raz 和 Tal 发表证明的第二天，乔治亚理工大学的计算机科学家，Lance Fortnow 写道：「量子复杂度的世界摇摆不定。」
这项工作提供了一个铁证，那就是相比于传统计算机（至少相对于 oracle 而言），量子计算机存在于一个不同的计算领域。甚至在 P 等价于 NP 的世界里（其中「旅行推销员问题」就像在电子表格上找到最合适的线一样简单），Raz 和 Tal 的证明仍然表明存在着只有量子计算机才能解决的问题。
Fortnow 说：「即使 P 等价于 NP，甚至做出了强有力的假设，仍然不足以掌握量子计算。」
原文链接：
本文为机器之心编译，转载请联系本公众号获得授权。
?------------------------------------------------
加入机器之心（全职记者 / 实习生）：hr@jiqizhixin.com
投稿或寻求报道：content@jiqizhixin.com
广告 & 商务合作：bd@jiqizhixin.com