量子计算机仅仅是比经典计算机强了那么一点点、快了那么一点点、效率高了一点点吗？我们都知道，答案是“不”。
然而，为了证明量子计算机的真正实力，科学家颇费了一番功夫。在量子计算机研究的早期，计算机科学家提出了一个问题。他们知道，这个问题的答案会深刻揭示这些未来机器的威力。然而，25年后的今天，这个问题差点还是没能解决。
现在，他们终于找到了一个只有量子计算机才能解决的问题。
今年5月底在网上发表的一篇论文中，计算机科学家冉·拉兹(Ran Raz，普林斯顿大学和魏茨曼科学学院的教授)和阿维沙伊·塔尔(Avishay Tal，斯坦福大学博士后研究员)提出了有力的证据，证明量子计算机拥有任何传统计算机都不可能达到的计算能力。
拉兹和塔尔定义了一个具体的计算问题，然后证明，量子计算机可以有效地解决这个问题，而传统计算机永远都解决不了。从1993年开始，计算机科学家就一直在寻找这样一个问题。在那一年，计算机科学家首次定义了一类涵盖量子计算机能解决的所有问题集，统称为“BQP”。
从那时起，计算机科学家希望将BQP与被称为“PH”的一类问题进行比较。PH涵盖经典计算机可以解决的所有问题，哪怕是未来文明建造的、先进到不可思议的经典计算机。想要进行那种比较，就必须找到一个问题，证明这个问题属于BQP，但不属于PH。现在，拉兹和塔尔做到了。
他们的研究结果并没有使量子计算机在实际应用中超越经典计算机。理论计算机科学家已经知道，量子计算机可以解决经典计算机能解决的任何问题。工程师们还在努力研制切实可用的量子计算机。但拉兹和塔尔的论文证明，量子计算机和经典计算机是两码事——即使经典计算机的表现超出了所有的现实期望，量子计算机仍然会高高在上。
量子级计算
理论计算机科学的一个基本任务是把问题进行复杂性归类。一个复杂性类包含在某一特定的资源预算内可以解决的所有问题。这里的资源可以是像时间或者内存这样的东西。 两个最著名的复杂性类是“P”和“NP”。P是经典计算机能迅速解决的所有问题(“这个数字是质数吗”属于P)，NP是经典计算机未必能迅速解决的所有问题，但在给出答案的情况下，经典计算机能迅速证明答案是否正确(“其质因数是什么”属于NP)。计算机科学家认为，P和NP是截然不同的类，但真正证明这一点是该领域里最困难、最重要的问题。
