量子计算机仅仅是比经典计算机强了那么一点点、快了那么一点点、效率高了一点点吗？我们都知道，答案是“不”。

然而，为了证明量子计算机的真正实力，科学家颇费了一番功夫。在量子计算机研究的早期，计算机科学家提出了一个问题。他们知道，这个问题的答案会深刻揭示这些未来机器的威力。然而，25年后的今天，这个问题差点还是没能解决。

现在，他们终于找到了一个只有量子计算机才能解决的问题。

今年5月底在网上发表的一篇论文中，计算机科学家冉·拉兹（Ran Raz，普林斯顿大学和魏茨曼科学学院的教授）和阿维沙伊·塔尔（Avishay Tal，斯坦福大学博士后研究员）提出了有力的证据，证明量子计算机拥有任何传统计算机都不可能达到的计算能力。

拉兹和塔尔定义了一个具体的计算问题，然后证明，量子计算机可以有效地解决这个问题，而传统计算机永远都解决不了。从1993年开始，计算机科学家就一直在寻找这样一个问题。在那一年，计算机科学家首次定义了一类涵盖量子计算机能解决的所有问题集，统称为“BQP”。

从那时起，计算机科学家希望将BQP与被称为“PH”的一类问题进行比较。PH涵盖经典计算机可以解决的所有问题，哪怕是未来文明建造的、先进到不可思议的经典计算机。想要进行那种比较，就必须找到一个问题，证明这个问题属于BQP，但不属于PH。现在，拉兹和塔尔做到了。

他们的研究结果并没有使量子计算机在实际应用中超越经典计算机。理论计算机科学家已经知道，量子计算机可以解决经典计算机能解决的任何问题。工程师们还在努力研制切实可用的量子计算机。但拉兹和塔尔的论文证明，量子计算机和经典计算机是两码事——即使经典计算机的表现超出了所有的现实期望，量子计算机仍然会高高在上。

量子级计算

理论计算机科学的一个基本任务是把问题进行复杂性归类。一个复杂性类包含在某一特定的资源预算内可以解决的所有问题。这里的资源可以是像时间或者内存这样的东西。 两个最著名的复杂性类是“P”和“NP”。P是经典计算机能迅速解决的所有问题（“这个数字是质数吗”属于P），NP是经典计算机未必能迅速解决的所有问题，但在给出答案的情况下，经典计算机能迅速证明答案是否正确（“其质因数是什么”属于NP）。计算机科学家认为，P和NP是截然不同的类，但真正证明这一点是该领域里最困难、最重要的问题。

1993年，计算机科学家伊森·伯恩斯坦（Ethan Bernstein）和乌梅什·瓦兹拉尼（Umesh Vazirani）定义了一个新的复杂性类，他们称之为BQP，即“有界误差量子多项式时间”。这个类包含量子计算机可以有效解决的所有判定性问题（答案为“是”或者“否”）。同时，他们也证明了量子计算机可以解决经典计算机能解决的所有问题，即BQP包含P中的所有问题。

但他们无法确定BQP是否包含PH中没有的问题。PH代表“多项式层次结构”，是NP的泛化，这意味着PH包含通过分层限定语句（比如“那里有”和“所有人”）使NP问题更加复杂的所有问题。当前的经典计算机无法解决大多数的PH问题，但如果P等于NP，PH就是经典计算机可以解决的那一类问题。换句话说，比较BQP和PH是为了确定量子计算机是否比经典计算机更具优势，即使经典计算机以后可以（出人意料地）解决比现在更多得多的问题。

“PH是最基本的经典复杂性类之一。”得克萨斯大学奥斯汀分校计算机科学家斯科特·阿伦森（Scott Aaronson）说，“因此，我们想知道，量子计算在经典复杂性理论的世界里处于什么位置？”

区分两个复杂性类的最好方法，是找到一个可证明属于其中一类但不属于另一类的问题。但由于基础性和技术性障碍，很难找到这样一个问题。

如果想找到一个属于BQP但不属于PH的问题，必须先找到一个“经典计算机无法有效验证答案，更别说得出答案”的问题。阿伦森说：“这排除了计算机科学家想到的很多问题。”

BQP还是PH？

假设你有两个随机数生成器，每个会生成一串数字。你向计算机提出的问题是：这两串数字是彼此完全独立，还是存在隐藏关联（一串数字是另一串数字的“傅里叶变换”）？阿伦森在2009年提出了这个“傅换关联”（forrelation）问题，并证明它属于BQP。然后是更加困难的第二步——证明傅换关联问题不属于PH。

普林斯顿大学理论计算机科学家冉·拉兹找到了区分两个计算类的方法

从某种意义上来说，这就是拉兹和塔尔所做的事。他们的论文实现了BQP和PH的“Oracle”（或者说“黑匣子”）分离。这是计算机科学领域里的一种常见结果。如果研究人员想要证明的东西超出了他们力所能及的范围之外，他们便求助于“Oracle”。

区分BQP和PH等复杂性类的最好方法，是衡量解决问题所需的计算时间。但多伦多大学计算机科学家亨利·袁（Henry Yuen）说，计算机科学家“对真正的计算时间缺乏深刻的了解，也没有能力去衡量。”

因此，计算机科学家衡量其他指标，希望借此洞悉他们无法衡量的计算时间。他们算出计算机询问“Oracle”以得到答案所需的时间。Oracle就像暗示者，你不知道祂是如何得出暗示的，但你知道暗示是可信的。

如果你的问题是弄清楚两个随机数生成器是否存在隐藏关联，你可以问Oracle“每个生成器的第六个数字是什么？”然后，你根据每一类计算机解决这个问题所需的暗示数量，来比较它们的计算能力。计算机需要的暗示越多，速度就越慢。

“从某种意义上讲，我们更了解这种模式。它更多地是关于信息而非计算。”塔尔说。

斯坦福大学理论计算机科学家阿维沙伊·塔尔利用“Oracle”分离来区分BQP和PH

拉兹和塔尔的新论文证明，量子计算机解决傅换关联问题所需的暗示数量远远少于经典计算机。事实上，量子计算机只需要一个暗示，而PH算法哪怕获得无数的暗示，也解决不了这个问题。“这意味着量子算法可以非常有效地解决那个问题，”拉兹说，“但如果只考虑经典算法，哪怕是非常高级的经典算法也不行。”因此，傅换关联问题属于BQP，但不属于PH。

拉兹和塔尔在差不多四年前就快要得出这一结果，但他们那时无法完成其证明过程的最后一步。不久前，塔尔看到了一篇关于伪随机数列生成器的论文。他意识到，那篇论文中谈到的方法正好可以帮助他和拉兹完成他们自己的论文。“这是缺失的一环，”塔尔说。

BQP和PH被分离的消息迅速传播。在拉兹和塔尔发表其论文的第二天，佐治亚理工学院计算机科学家兰斯·福特诺（Lance Fortnow）写道：“量子复杂性世界轰动了。”

这篇论文有力地证明，量子计算机存在于一个跟经典计算机不同的计算领域（至少在涉及神谕的问题上）。拉兹和塔尔的论文证明，即便是在P等于NP的情况下，有些问题仍然只有量子计算机才能解决。

福特诺说：“即使P等于NP，哪怕有了这个强假设，也不足以把握量子计算。”

翻译：于波

校对：李莉

造就：剧院式的线下演讲平台，发现最有创造力的思想

点击蓝字“了解更多”

閱讀更多 造就 的文章

關鍵字: 量子计算 量子 计算机