多年以来，计算机科学家一直在寻找某种类型的任务，即使是子孙后代，量子计算机也只能解决这一问题，而经典计算机则无法解决。 因此，他们找到了其中之一。
在量子计算机研究的早期阶段，计算机科学家提出了一个问题，他们认为应该回答这个问题才能揭示出有关这些未来机器的功能的深刻事实。 25年后，找到了答案。 在2018年5月发表的
一篇论文中，计算机科学家
Ren Rez和
Avishai Tal提供了令人信服的证据，证明了量子计算机的计算能力超越了传统计算机可以实现的任何功能。
普林斯顿大学和怀斯曼科学研究所的教授雷兹以及斯坦福大学的博士后塔尔（Tal）发现了一种特殊的计算问题。 他们一口气警告了量子计算机可以有效地解决该问题，而传统计算机将永远陷入困境，并试图做到这一点。 自1993年计算机科学家首次确定
BQP任务类以来，一直在寻找这样的问题，
该类包括量子计算机可以解决的所有任务。
从那时起，他们希望对比称为PH的BQP类任务，其中包括可以在任何经典计算机上执行的所有任务，甚至包括未来某些文明所开发的令人难以置信的高级任务。 这种对比的可能性取决于找到属于BQP类而不属于PH类的问题。 现在Rez和Tal已经做到了。
从实际的角度来看，这一结果并不能使量子计算机比经典计算机更好。 首先，理论计算机科学家已经知道，量子计算机能够解决经典计算机能够完成的任何任务。 工程师正在努力解决创建有用的量子机的问题。 但是Reza和Tal的工作证明了量子计算机和经典计算机所处类别之间的差异-即使在经典计算机已经超越任何梦想的世界中，量子计算机仍然可以超越它们。
量子类
理论信息学的基本任务是将任务分为复杂性类别。 复杂度类包含可以使用特定资源（例如时间或内存）解决的所有任务。
例如，科学家发现了一种有效的算法，可以检查数字是否为质数。 但是，他们找不到有效的算法来查找大量素数。 因此，他们认为（尽管无法证明）这两个问题属于不同类别的复杂性。
P和NP是两个著名的难度类别。 P是经典计算机可以快速解决的所有任务。 （问题“数字是素数吗？”属于P）。 NP包括经典计算机不一定能快速解决的所有任务，而是现有解决方案的正确性，它可以快速检查所有任务。 （“数字的主要因素是什么？”属于NP）。 科学家认为，P和NP类是不同的，但是证明这种差异的任务是该领域中最困难，也是最重要的开放问题。
PH包含一个包含P的NP。BQP是与PH分开的类吗？1993年，计算机科学家Ethan Bernstein和
Umesh Wazirani定义了一个新的复杂度类，他们将其称为BQP，即“具有错误概率限制的量子多项式时间”。 他们将类定义为包含量子计算机能够有效解决的所有决策任务，即答案为“是”或“否”的任务。 大约在同一时间，他们证明了量子计算机能够解决传统计算机能够完成的所有任务。 也就是说，BQP包含P中包含的所有任务。
单个任务类的另一个示例。 推销员问题询问通过某些城市的路径是否短于给定距离。 NP中就是这样的任务。 一个更困难的任务是询问此距离是否是穿过这些城市的最短路径。 这样的任务在PH中。
但是，他们无法确定BQP是否包含不在另一类重要任务（称为PH或“多项式层次结构”）中的任务。 PH是NP的概括。 它包含所有可能的任务，这些任务可以从NP中的任务开始并使其复杂化，并添加诸如“是否”和“针对所有人”之类的明确陈述。 经典计算机仍然不能解决PH中的大多数问题，但是如果事实证明P等于NP，则可以将此类视为经典计算机可以解决的一类问题。 换句话说，为了比较BQP和PH，有必要确定量子计算机是否比经典计算机具有优势，即使经典计算机突然学会解决比今天更多的问题，这种优势仍然存在。
“ PH是现有的最简单的复杂性类别之一，”德克萨斯大学奥斯汀分校的IT专家
Scott Aaronson说。 “因此，我们有点想知道量子计算在古典复杂世界中的地位。”
分离这两个难度类别的最佳方法是找到一个问题，证明其中一个问题被证明包含在另一个问题中，而不包含在另一个问题中。 然而，由于基本和技术障碍的结合，很难找到这样的任务。
为了找到属于BQP但不属于PH的任务，您需要定义一些东西，“从定义上讲，经典计算机甚至无法有效地检查答案，更不用说找到答案了，” Aaronson说。 “这消除了我们在计算机科学领域从事的许多工作。”
问甲骨文
挑战。 假设我们有两个随机数生成器，每个生成器生成一个数字序列。 给计算机的问题是：这两个序列是彼此完全独立的，还是以某种方式难以觉察地连接在一起（例如，一个序列是通过另一个序列
的傅立叶变换获得的 ）？ 亚伦森（Aaronson）在2009年引入了这项“分叉”任务，并证明它属于BQP。 第二个更困难的步骤仍然是-证明PH中不包括糠醛。
兰·雷兹从某种意义上说，这正是Resu和Talu所做的。 他们的工作借助所谓的BQP和PH “
oracle ”或“ black box”。 这是计算机科学的普遍结果，当研究人员没有以任何方式证明自己想要证明的东西时，就会诉诸于此。
分离BQP和PH复杂度类别的最佳方法是衡量解决每个类别的问题所需的计算时间。 多伦多大学计算机科学家亨利·扬（Henry Youn）说，但是计算机科学对“实时计算时间或测量时间没有深刻的理解”。
取而代之的是，计算机科学中正在测量其他事物，这被认为可以提供无法直接测量的计算时间的理解。 科学家计算出对“甲骨文”进行回答的计算机调用次数。 甲骨文似乎提供了线索。 我们不知道他如何收到它们，但我们知道它们是可靠的。
如果您的任务是找出两个随机数生成器之间是否存在秘密连接，则可以询问oracle问题，例如“每个生成器的第六个数字是多少？” 然后，您需要根据每台计算机解决问题所需的提示数量来比较计算能力。 需要更多提示的计算机运行速度较慢。
“从某种意义上说，我们对这种模型了解得更好。 她谈论的更多的是信息而不是计算。
Avishai TalReza和Tal的新著作证明，与经典计算机相比，量子计算机需要更少的线索来解决分叉问题。 此外，尽管PH即使具有无限数量的提示，也没有解决该问题的算法，但量子计算机仅需要一个提示。 Rez说：“这意味着有一种非常有效的量子算法可以解决此类问题。” “但是，如果我们仅考虑经典算法，那么即使我们到达经典算法的顶级类别，他们也将无法应对。” 这证明在预言机中，分叉指的是属于BQP的任务，而不是PH的任务。
雷兹（Rez）和塔尔（Tal）大约在四年前就达到了这一结果，但在未来的证明中却无法迈出一步。 然后，在该出版物出版的前一个月，塔尔听说了有关伪随机数生成器的一项新
工作 ，并意识到该文章中的技术恰好满足了他和雷兹完成自己的研究所需。 “这是一块丢失的东西，”塔尔说。
BQP和PH类别分离的消息迅速传播。 这项工作发表后的第二天，佐治亚理工大学的IT专家Lance Fortnau
写道： “量子复杂性世界嗡嗡作响。”
这项工作使人们对量子计算机与经典计算机存在于一个独立的计算世界中（至少是根据预言的定义）充满了信心。 即使在P等于NP的世界中，解决旅行推销员问题就像在电子表格中找到最合适的行一样简单，但Reza和Tal的证明表明，只有量子计算机才能解决问题。
Fortnau说：“即使在如此强大的假设下，即使P等于NP，量子计算机也仍将赶不上。”