科学家为了寻找一类只能用量子计算机解决而不能用经典计算机解决的问题花了很多年。现在，他们找到了这样的问题。

在量子计算机研究的早期，计算机科学家提出一个问题，它的答案将揭示这种来自未来的机器的威力。25年后，这个问题已经几乎被解决了。五月初在线发表的一篇论文中，科学家Ran Raz 和 Avishav Tal 拿出了量子计算机具有经典计算机不具备的计算能力的证据。

Raz是普林斯顿大学和威茨曼科学研究学院的教授，Tal 是斯坦福大学的博士后，他们设计了一类特殊的计算问题。他们证明，量子计算机可以有效地解决这类问题但传统计算机却无能为力。1993年，计算机科学家第一次定义了一系列被称为“BQP”的问题，BQP包含所有量子计算机可以解决的问题，从那时起计算机科学家就在寻找这个问题。

从那以后，计算机科学家希望将一类被称为“PH”的问题与BQP进行对比，PH是理论上可以用经典计算机解决的问题，即使可能需要大大推进我们现有的技术才能做到。要做这种对比就要找到一种属于BQP但是不属于PH的问题。现在，Raz和Tal已经找到了它。

这个结果并不能在任何应用的意义上把量子计算机的地位提升的比经典计算机还高。举例来说，理论计算机科学家已经知道量子计算机可以解决任何经典计算机可以解决的问题。并且工程师都竞相组建有用的量子机器。但是Raz和Tal的文章提到量子和经典计算机是不同的类别——即使在经典计算机可以完成所有工作的领域，量子计算机仍然不可取代。

复杂度分类

理论计算机科学家的基本任务就是将不同的问题进行复杂度分类。一个复杂度分类包含所有可以用给定资源预算解决的问题，资源包含时间和储存空间等。

计算机科学家已经找到一个有效的算法，例如，检验一个数是不是素数。但是他们没有找到将一个巨大的数分解成质因数的有效算法。因此，计算机学家相信两种问题分属不同的复杂度分类。

两个最著名的复杂度分类是“P”和“NP”，P代表可以被经典计算机快速解决的问题。（如“判断一个数是不是质数属于P”）NP代表不可能被经典计算机快速解决的问题，但是如果可以给出答案，经典计算机可以快速的验证答案。（寻如“寻找一个数的所有质因数”）。计算机学家相信，P和NP不是同一种类型的问题，但是证明它们之间的不同是这个领域中最困难最重要的开放性问题。

图中画出了各种类型问题之间的关系。

1993年，计算机学家Ethan Bernstein 和 Umesh Vazirani 定义了一个新的叫做“BQP(bounded-error quantum polynomial time)”的复杂度分类。他们定义这个分类包含量子计算机可以有效解决的决策性问题，也就是答案是“是”或“否”的问题。在大约相同的时间，他们证明了量子计算机可以解决经典计算机可以解决的所有问题。也就是说，BQP包含P中的所有问题。

但他们不能确定BQP是否包含不存在于PH中的问题，PH是“polynomial hierarchy.”。PH是NP的推广，它包含所有对NP中的所有问题所做的某些推广，这些推广包括增加“存在”和“对所有情况”等陈述。比较BQP和PH是为了确定量子计算机相比经典计算机是否更具优势（即便是在经典计算机的计算能力比现在大大增强之后）。

“PH是最基础的经典复杂度分类之一，”Scott Aaronson说，它是奥斯汀德克萨斯大学的计算机学家。“因此我们想知道的是，在经典复杂度理论中量子计算处于什么位置。”

区分两个复杂度分类的最好的办法就是找到一个处于其中一个但不在另外一个中的问题。但是由于基础理论和技术上的障碍，寻找这样的问题是一个巨大挑战。

如果你想找到一个属于BQP但不属于PH的问题，你必须找到“一个经典计算机无法解决，甚至无法验证的问题”Aaronson说。“这排除了很多计算机领域我们思考过的问题。”

寻找不属于PH的BQP

想象你有两个随机数生成器，每一个生成器产生一列数据。对于计算机来说问题是：这两列数据是相互独立的吗，或者它们是否以隐藏的方式相互联系（其中一列数是另一列的傅里叶变换）？Aaronson在2009年提出这种“forrelation”问题并证明它属于BQP。这留下了更加困难的第二步，也就是证明它不属于PH。

Ran Raz

在某种意义上讲，这就是Raz和Tal所做的。他们实现了被称为“预言（oracle）”（或“黑盒子（black box）”）的BQP和PH之间的分辨。

实际上最好的区分BQP和PH这种复杂度分类的方法是测量在每一类中解决一个问题需要的时间。但是计算机学家“对于真实的计算时间没有成熟的理解，也没有能力测量精确地时间。”Henry Yuen说。

因此，代替方案是，计算机学家测量那些可以帮助他们加深对计算时间理解的量：他们利用计算机运行“Oracl”得到答案的时间。Orale像一个提示者。你不知道它如何给出提示，但是你知道它们是可信的。

如果你的问题是指出两个随机数生成器是否有隐藏关联，你可以问这样的问题：“从每个生成器中产生的第六个数是什么？”然后可以通过每种计算机解决问题需要的提示多少来判断谁的计算能力强。需要提示多的计算机更慢一些。

“某种意义上说，我们对这种模型的理解要好得多。它和信息而非计算更加相关。”Tal说。

Avishay Ta

在Raz和Tal新的论文中，他们证明量子计算机相比经典计算机需要少得多的提示来解决forrelation问题。实际上，量子计算机仅需要一个提示，而PH无论有多少个提示都无法解决这类问题。“这意味着存在解决这个问题的非常高效的量子算法，”Raz说。“但是如果你只是考虑经典算法，即便是非常高端的经典算法，也解决不了这个问题。”这证明了forrelation问题属于BQP而不是PH。

Raz和Tal四年前差点就得到这个结果，但他们没能完成最后一步证明。仅仅一个月之后，Tal听到一篇关于伪随机数生成器的文章的讨论并意识到文章中的技术正是他们所需要的。“这正是缺失的一环”Tal说。

区分BQP和PH的新闻传播的非常快。“量子复杂性世界被震动了。”Lance Fortnow写到。

这个工作证明了量子计算机存在于和经典计算机不同的范畴内。尽管是P和NP相等的领域，Raz和Tal的证明说明了仍然存在只有量子计算机可以解决的问题。

本文来源：中科院物理所