最后，一个只有量子计算机才能解决的问题(2018)

在量子计算机研究的早期，计算机科学家提出了一个问题，他们知道，这个问题的答案将深刻揭示这些未来机器的力量。25年后，这个问题几乎解决了。在5月底发布在网上的一篇论文中，计算机科学家朗·拉兹(Run Raz)和阿维沙伊·塔尔(Avishay Tal)提供了强有力的证据，证明量子计算机拥有传统计算机无法实现的计算能力。

普林斯顿大学(Princeton University)和魏茨曼科学研究所(Weizmann Institute Of Science)教授拉兹(Raz)和斯坦福大学(Stanford University)博士后研究员塔尔(Tal)定义了一种特定的计算问题。他们证明，有一定的警告，量子计算机可以有效地处理这个问题，而传统计算机将永远陷入困境，试图解决这个问题。自1993年以来，计算机科学家一直在寻找这样的问题，当时他们首次定义了一类被称为BQP的问题，这类问题涵盖了量子计算机可以解决的所有问题。

从那时起，计算机科学家们就希望将BQP与一类被称为“PH”的问题进行对比，“PH”涵盖了任何可能的经典计算机所能解决的所有问题--甚至包括由某些未来文明设计的深不可测的高级问题。进行这种对比取决于找到一个可以被证明存在于BQP而不是PH中的问题。现在，拉兹和塔尔做到了。

这一结果在任何实际意义上都不会使量子计算机超越经典计算机。首先，理论计算机科学家已经知道量子计算机可以解决经典计算机所能解决的任何问题。工程师们仍在努力建造一台有用的量子机。但拉兹和塔尔的论文证明，量子计算机和经典计算机实际上是一个截然不同的类别-即使在一个经典计算机取得了超越所有现实梦想的成功的世界里，量子计算机仍然会超越它们。

理论计算机科学的一项基本任务是将问题归类为复杂类。复杂性类包含在给定资源预算内可以解决的所有问题，其中资源是时间或内存之类的东西。

例如，计算机科学家已经找到了一种有效的算法来测试一个数字是否为质数。然而，他们还没有找到一种有效的算法来识别大数的素因数。因此，计算机科学家认为(但还无法证明)这两个问题属于不同的复杂性类别。

最著名的两个复杂类是“P”和“NP”。P是经典计算机可以快速解决的所有问题。(“这个数字是质数吗？”属于P.)。NP是经典计算机不一定能快速解决的所有问题，但如果有答案，它们可以快速验证答案。(“它的主要因素是什么？”属于NP。)。计算机科学家认为P和NP是两个截然不同的类别，但实际上证明其区分性是该领域最困难和最重要的公开问题。

1993年，计算机科学家伊桑·伯恩斯坦(Ethan Bernstein)和乌梅什·瓦兹拉尼(Uesh Vazirani)定义了一个新的复杂性类别，他们称之为BQP，意为“有界误差量子多项式时间”。他们将这一类定义为包含量子计算机可以有效解决的所有决策问题--答案为是或否的问题。大约在同一时间，他们还证明了量子计算机可以解决经典计算机能够解决的所有问题。也就是说，BQP包含了P中的所有问题。

但他们无法确定BQP是否包含另一类重要问题“PH”中没有的问题，PH代表“多项式层次”。PH是NP的推广。这意味着它包含了你从NP问题开始的所有问题，并通过层次化限定语句，如“存在”和“为了所有人”，使问题变得更加复杂。1今天的经典计算机不能解决PH中的大多数问题，但你可以把PH看作是如果P被证明等于NP，那么经典计算机可以解决的所有问题的类别。换句话说，比较BQP和PH就是确定量子计算机是否比经典计算机更有优势，即使经典计算机(出人意料地)能够解决比现在多得多的问题，经典计算机也能存活下来。

德克萨斯大学奥斯汀分校(University Of Texas At Austin)的计算机科学家斯科特·亚伦森(Scott Aaronson)说：“PH是最基本的经典复杂性课程之一。”“所以我们有点想知道，量子计算在经典复杂性理论的世界中处于什么位置？”

区分两个复杂性类别的最好方法是找到一个可以证明存在于其中一个而不是另一个中的问题。然而，由于基本面和技术上的障碍，找到这样一个问题一直是一个挑战。

Aaronson说，如果你想要一个存在于BQP而非PH中的问题，你必须找出一些“根据定义，经典计算机甚至无法有效地验证答案，更不用说找到它了”。“这排除了我们在计算机科学中思考的很多问题。”

这就是问题所在。假设您有两个随机数生成器，每个生成器都产生一个数字序列。你的计算机面临的问题是：这两个序列是完全相互独立的，还是以一种隐藏的方式联系在一起的(其中一个序列是另一个序列的“傅立叶变换”)？Aaronson在2009年提出了这个“关联”问题，并证明它属于BQP。这就留下了更难的第二步--证明For Relationship不在PH中。

这就是拉兹和塔尔在某种意义上所做的事情。他们的论文实现了BQP和PH之间所谓的“先知”(或“黑箱”)分离。这在计算机科学中是一种常见的结果，当他们真正想要证明的东西超出了他们的能力范围时，研究人员就会求助于这种结果。

区分BQP和PH等复杂类的实际最佳方法是测量解决每类复杂类中的问题所需的计算时间。但多伦多大学(University Of Toronto)的计算机科学家亨利·袁说，计算机科学家“对实际计算时间的理解或测量能力不是很高”。

取而代之的是，计算机科学家们测量了一些其他的东西，他们希望这些东西能为他们无法测量的计算时间提供洞察力：他们计算出一台计算机为了得到答案而需要咨询一位“先知”的次数。先知就像一个提示者。你不知道它的提示是怎么来的，但你知道它们是可靠的。

如果您的问题是要弄清楚两个随机数生成器是否秘密相关，您可以问一些先知问题，比如“每个生成器的第六个数字是什么？”然后，根据每种类型的计算机需要解决问题的提示数来比较计算能力。需要更多提示的计算机速度较慢。

“从某种意义上说，我们对这种模式的理解要好得多。它更多地谈论信息，而不是计算。“塔尔说。

Raz和Tal的新论文证明，量子计算机比经典计算机需要更少的提示来解决关联问题。事实上，量子计算机只需要一个提示，而即使有无限的提示，PH中也没有算法可以解决这个问题。拉兹说：“这意味着有一种非常有效的量子算法可以解决这个问题。”“但如果你只考虑经典算法，即使你上的是非常高级的经典算法，他们也做不到。”这表明，对于先知，关系是BQP中的问题，而不是PH中的问题。

拉兹和塔尔几乎在四年前就实现了这一结果，但他们在未来的证据中一步也没能完成。就在一个月前，塔尔听了一篇关于伪随机数生成器的新论文的演讲，意识到论文中的技术正是他和拉兹完成自己的论文所需要的。“这就是缺失的部分，”塔尔说。

BQP和PH分离的消息很快就传开了。佐治亚理工学院的计算机科学家兰斯·福特诺(Lance Fortnow)在拉兹(Raz)和塔尔(Tal)发表了他们的证明的第二天写道：“量子复杂性的世界正在震撼。”

这项工作提供了一个确凿的保证，即量子计算机存在于与经典计算机不同的计算领域(至少相对于先知而言)。即使在P等于NP的世界里--旅行推销员问题就像在电子表格上找到一条最合适的线一样简单--Raz和Tal的证明表明，仍然存在只有量子计算机才能解决的问题。

Fortnow说：“即使P等于NP，即使做出这样强有力的假设，也不足以捕获量子计算。”

更正2018年6月21日：这篇文章的早期版本指出，询问某条路径是否恰好是最短距离的旅行商问题的版本很可能是PH。事实上，它已经被证明处于PH状态。