“哈加物理学家开发出‘量子便裤’”，讽刺周刊《洋葱报》的头条新闻写道。文章解释说，通过利用一种奇异的“薛定谔的裤子”二元性，这些非牛顿裤子可以同时表现得像正装和休闲装。《洋葱报》的作者显然是在恶搞那些充斥着大众科学媒体十年的关于量子计算的令人兴奋的文章。
一个常见的错误——例如 2007 年 2 月 15 日的《经济学人》杂志——是声称原则上量子计算机可以快速解决一组特别困难的数学难题，称为 NP 完全问题，即使是最好的现有计算机也无法快速解决（就目前所知）。量子计算机本应通过拥有能够同时处理每个可能答案的硬件来实现这一壮举，而不是同时具有正装和休闲装的特性。
如果我们真的可以制造出一台能够轻松解决 NP 完全问题的神奇计算机，世界将会变得非常不同：我们可以要求我们的神奇计算机寻找可能存在于股票市场数据、天气记录或大脑活动记录中的任何模式。与今天的计算机不同，找到这些模式将完全是例行公事，并且不需要对问题的主题有详细的了解。这台神奇的计算机还可以自动化数学创造力。对于任何数学圣杯——例如哥德巴赫猜想或黎曼猜想，这两个猜想都已经一百多年没有得到解决——我们可以简单地要求我们的计算机搜索所有可能的证明和反证，最多包含比如十亿个符号。（如果证明比这长得多，我们甚至不清楚我们是否想阅读它。）
支持科学新闻报道
如果您喜欢这篇文章，请考虑通过以下方式支持我们屡获殊荣的新闻报道 订阅。通过购买订阅，您正在帮助确保有关塑造我们当今世界的发现和想法的具有影响力的故事的未来。
如果量子计算机承诺如此强大的数学能力，也许我们应该期望它们与曲速引擎发生器和反重力盾牌大约在同一时间出现在商店货架上。但是，尽管我们不应该接受通常的炒作，但在我看来，将量子计算视为科幻小说同样是误导。相反，我们应该找出量子计算机的局限性，以及如果我们拥有它们，它们真正能做什么。
自从物理学家理查德·费曼首次提出量子计算的概念以来的 26 年里，计算机科学家在弄清楚量子计算机擅长解决哪些问题方面取得了巨大进展。根据我们目前的理解，它们将为少数特定问题提供显着的加速，例如破解广泛用于互联网货币交易的密码。然而，对于其他问题，例如下棋、安排航班和证明定理，现在的证据强烈表明，量子计算机将遭受与当今经典计算机相同的许多算法限制。这些限制完全独立于构建量子计算机的实际困难，例如退相干（量子计算机与其环境之间不希望有的相互作用，这会引入错误）。特别是，即使物理学家设法构建了一台完全没有退相干的量子计算机，对计算机可以编程执行的数学可能性的限制仍然适用。
难、更难、最难
量子计算机为何可以在某些问题（例如破解代码）上提供加速，但在其他问题上却不能？难道更快的计算机不就是更快的计算机吗？答案是否定的，要解释原因，需要直接深入计算机科学的智力核心。对于计算机科学家来说，问题的关键在于解决问题所需的时间随着问题规模的增加而增长的速度有多快。时间以算法达到解决方案所需的基步骤数来衡量。例如，使用小学方法，我们可以在时间量级与数字平方成正比的时间内，即 n 2 （时间量级被称为“n 的多项式”）内，将两个 n 位数字相乘。但是对于将一个数字分解为素数，即使是最先进的已知方法也需要时间量级与数字位数呈指数增长的时间（特别是，像 2 的 n 的立方根次方）。因此，因式分解似乎本质上比乘法更难——当我们达到数千位数字时，这种差异比 Commodore 64 和超级计算机之间的差异重要得多。
计算机可以在合理的时间内解决的问题类型，即使对于较大的 n 值，也是那些我们有算法可以使用步数与 n 的固定幂（例如 n、n 2 或 n 2.5 ）成正比增长的问题。计算机科学家称这种算法为高效算法，而可以通过高效算法解决的问题被称为属于复杂度类 P，其中 P 代表“多项式时间”。
P 类问题的一个简单示例是：给定一张公路地图，是否每个城镇都可以从其他每个城镇到达？P 类也包含一些高效解决方案不太明显的问题，例如：给定一个整数，它是素数（如 13）还是合数（如 12）？给定一份男人和女人彼此愿意结婚的名单，是否有可能将每个人与一位愿意的伴侣配对？
但是，假设现在给你各种尺寸的盒子，你想要一种将它们装进后备箱的方法。或者假设给你一张地图，你想用红色、蓝色或绿色为每个国家着色，以便没有两个相邻的国家颜色相同。或者给你一份由桥梁连接的岛屿列表，你想要一次访问每个岛屿的游览。尽管已知对于这些问题存在比尝试每种可能的解决方案稍好的算法，但尚不知有从根本上更好的算法。每个已知的算法都需要时间量级随着问题规模呈指数增长的时间。
事实证明，我刚刚列出的这三个问题具有一个非常有趣的特性：它们都是“相同”的问题，因为其中任何一个问题的有效算法都将意味着所有其他 NP 问题的有效算法。多伦多大学的斯蒂芬·A·库克、加州大学伯克利分校的理查德·卡普和现任波士顿大学的列昂尼德·列文在 20 世纪 70 年代得出了这个非凡的结论，当时他们发展了 NP 完全性理论。
NP 代表“nondeterministic polynomial time”（非确定性多项式时间）。不要担心那是什么意思。基本上，NP 是这样一类问题，对于这类问题，一旦找到解决方案，就可以在多项式时间内（类似于 n 2 等）识别为正确——即使解决方案本身可能很难找到。例如，如果您获得一张包含数千个岛屿和桥梁的地图，可能需要数年时间才能找到一次访问每个岛屿的游览。然而，如果有人向您展示一次游览，则很容易检查此人是否成功解决了问题。当一个问题具有此属性时，我们说它属于 NP 类。NP 类捕获了大量具有实际意义的问题。请注意，所有 P 类问题也是 NP 类问题，或者换句话说，P 类包含在 NP 类中。如果您可以快速解决一个问题，您也可以快速验证解决方案。
NP 完全问题本质上是最难的 NP 问题。它们是库克、卡普和列文发现的具有以下特性的问题：如果找到其中任何一个问题的有效算法，就可以将其调整为解决所有其他 NP 问题。
NP 完全问题的有效算法将意味着计算机科学家目前对 P 类、NP 类和 NP 完全类的看法完全错误，因为它将意味着每个 NP 问题（包括所有 NP 完全问题）实际上都是 P 类问题。换句话说，P 类将等于 NP 类，这写为 P = NP。
这样的算法存在吗？P 等于 NP 吗？这确实是一个价值百万美元的问题——它获得了马萨诸塞州剑桥市克莱数学研究所 1,000,000 美元的奖励——并且它至少在三个电视节目（《辛普森一家》、《飞出个未来》和《数字追凶》）中扮演了客串角色。
自从这个问题被认识到以来的半个世纪里，没有人为 NP 完全问题找到有效的算法。因此，即使我们还不够聪明，无法理解为什么会这样或将其证明为定理，但如今的计算机科学家几乎普遍认为 P 不等于 NP，或者 P ≠ NP。
量子能做什么
如果我们承认 P ≠ NP，那么解决 NP 完全问题的多项式时间的唯一希望仍然存在：即扩大我们对“计算机”的理解。乍一看，量子力学似乎提供了所需的资源。量子力学使得在相对少量粒子的状态中存储和操纵大量信息成为可能。为了了解这是如何发生的，假设我们有 1,000 个粒子，并且每个粒子在测量时都可以被发现是向上或向下旋转。就我们的目的而言，粒子向上或向下旋转意味着什么并不重要；重要的是粒子具有某种特性，在测量时具有两个值之一。
为了描述这组粒子的量子态，必须为测量粒子的每个可能结果指定一个数字。这些数字被称为可能结果的幅度，并且与每个结果的概率有关，但与概率不同，量子幅度可以是正数或负数（实际上，它们是复数）。例如，需要一个幅度来表示所有 1,000 个粒子将被发现向上旋转的可能性，另一个幅度表示发现前 500 个粒子向上旋转，而后 500 个粒子向下旋转的可能性，依此类推。有 2 1,000 种可能的结果，或大约 10 300 种，这就是需要的数字数量——比可见宇宙中的原子还多！这种情况的技术术语是，这 1,000 个粒子处于这 10 300 个状态的叠加态。
换句话说，我们可以同时在我们的 1,000 个粒子上存储 10 300 个数字。然后，通过对粒子和一些辅助粒子执行各种操作——也许用一系列激光脉冲或无线电波击打它们——我们可以执行一种算法，该算法同时转换所有 10 300 个数字（每个数字都是一个潜在的解决方案）。如果在执行完此操作后，我们可以准确地读出粒子的最终量子态，那么我们真的会拥有一台神奇的计算机：它将能够检查 10 300 个问题的可能解决方案，并且在最后我们可以快速识别出正确的解决方案。
不幸的是，这里有一个陷阱。当测量粒子时（这是读取其最终状态所必需的），量子力学的规则规定，测量将随机挑选出 10 300 种可能性中的一种，而所有其他可能性都将消失。（回到哈加开发的量子便裤，如果你尝试穿上它们，你会发现自己要么穿着正装，要么穿着休闲装，而不是两者都穿。）我们似乎并没有比使用经典计算机并尝试一个随机选择的可能解决方案更好——在任何一种情况下，我们最终只了解一个这样的可能解决方案。
令人高兴的是，我们仍然可以玩一些技巧，从量子粒子中榨取一些优势。当正幅度与负幅度结合时，幅度可以相互抵消，这种现象称为相消干涉。因此，一个好的量子计算机算法将确保导致错误答案的计算路径将以这种方式抵消。它还将确保导致正确答案的路径都具有相同符号的幅度——这会产生相长干涉，从而提高了在最后测量粒子时找到它们的概率。
对于哪些计算问题，我们可以编排这种干涉，使用比经典方法解决问题所需的步骤更少的步骤？
1994 年，现任麻省理工学院的彼得·肖尔发现了第一个量子算法示例，该算法可以显着加速解决实际问题的速度。特别是，肖尔展示了量子计算机如何使用步数仅以约 n 2 的速度增长的方式分解 n 位数字——换句话说，在多项式时间内。如前所述，已知的经典计算机的最佳算法使用的步数呈指数增长。
黑盒
因此，至少对于因式分解，使用量子方法确实可以比已知的经典算法获得指数级的加速。但是，尽管人们普遍误解，但因式分解问题既不是已知的也不是被认为是 NP 完全问题。为了创建他的算法，肖尔利用了合数及其因子的某些数学特性，这些特性特别适合产生量子计算机可以蓬勃发展的相长干涉和相消干涉类型。NP 完全问题似乎不具有这些特殊属性。直到今天，研究人员只发现了少数其他量子算法，这些算法似乎可以为问题提供从指数时间到多项式时间的加速。
因此，问题仍然没有答案：是否存在解决 NP 完全问题的有效量子算法？尽管进行了很多尝试，但尚未找到这样的算法——尽管毫不奇怪，计算机科学家无法证明它不存在。毕竟，我们甚至无法证明不存在解决 NP 完全问题的多项式时间经典算法。
我们可以说的是，能够有效解决 NP 完全问题的量子算法，就像肖尔的算法一样，必须利用问题的结构，但方式远远超出当今的技术。不能通过将问题视为无结构的“黑盒”来获得指数级的加速，该黑盒由要并行测试的指数数量的解决方案组成。然而，仍然可以从这种黑盒方法中挤出一些加速，计算机科学家已经确定了这种加速有多好——以及有多有限。产生加速的算法是第二大量子算法。
黑盒方法可以通过假装您正在寻找一个难题的解决方案来说明，而您唯一知道如何执行的操作是猜测一个解决方案并查看它是否有效。假设有 S 个可能的解决方案，其中 S 随着问题规模 n 的增加而呈指数增长。您可能会很幸运，第一次尝试就猜对了解决方案，但在最坏的情况下，您将需要 S 次尝试，平均而言，您将需要 S/2 次尝试。
现在假设您可以询问量子叠加中的所有可能解决方案。1996 年，贝尔实验室的洛夫·格罗弗开发了一种算法，在这种情况下，仅使用约 √—S 步即可找到正确的解决方案。从 S/2 到 √—S 的加速对于某些问题来说是一个有用的进步——如果有一百万个可能的解决方案，您将需要大约 1,000 步而不是 500,000 步。但是平方根不会将指数时间转换为多项式时间；它只是产生一个较小的指数。而格罗弗的算法对于这种黑盒搜索来说已经是最好了：1994 年，研究人员已经表明，任何黑盒量子算法至少需要 √—S 步。
在过去的十年中，研究人员已经表明，类似的适度加速是除搜索列表之外的许多其他问题的极限，例如计算选举中的选票、在地图上查找最短路线以及玩国际象棋或围棋等策略游戏。一个特别困难的问题是所谓的碰撞问题，即在一个长列表中查找两个相同或“碰撞”的项目的问题。如果有一种快速的量子算法来解决这个问题，那么许多安全的电子商务基本构建模块在量子计算机世界中将变得毫无用处。
在一个列表中搜索一个项目就像大海捞针，而搜索碰撞就像寻找两块相同的干草，这为问题提供了一种量子计算机可以潜在利用的结构。尽管如此，我在 2002 年表明，在黑盒模型中，任何量子算法都需要指数时间才能解决碰撞问题。
诚然，这些黑盒限制并没有排除发现解决 NP 完全问题甚至更难问题的有效量子算法的可能性。然而，如果存在这样的算法，它们将不得不以与我们所见过的任何算法不同的方式利用问题的结构，这与解决相同问题的有效经典算法必须做到的方式非常相似。量子魔法本身不会奏效。基于这种洞察力，许多计算机科学家现在不仅推测 P ≠ NP，而且量子计算机无法在多项式时间内解决 NP 完全问题。
神奇的理论
我们所知道的一切都与量子计算机是终点线的可能性一致——也就是说，它们是与物理定律兼容的最通用的计算机类型。但是物理学家还没有最终的物理理论，因此不能排除未来理论有一天可能会揭示一种物理手段来有效解决 NP 完全问题。正如您所预料的那样，人们推测了更强大的计算机类型，其中一些计算机将使量子计算机看起来像自动售货机一样平庸。然而，它们都将依赖于对物理定律的推测性改变。
量子力学的核心特征之一是称为线性的数学性质。1998 年，当时都在麻省理工学院的丹尼尔·S·艾布拉姆斯和塞思·劳埃德表明，如果在量子力学方程中添加一个小的非线性项，量子计算机将能够有效地解决 NP 完全问题。在您过于兴奋之前，您应该意识到，如果存在这样的非线性项，那么人们也可以违反海森堡不确定性原理并发送速度超过光速的信号。正如艾布拉姆斯和劳埃德指出的那样，也许对这些结果的最佳解释是它们有助于解释为什么量子力学是线性的。
另一种推测类型的机器将通过在有限的时间内塞入无限数量的步骤来实现奢华的计算能力。不幸的是，根据物理学家目前的理解，时间似乎会退化为量子涨落的海洋——有点像泡沫而不是均匀的光滑线——在 10 –43 秒（普朗克时间）的尺度上，这似乎使这种机器成为不可能。
如果时间不能被任意薄地切割，那么也许另一种有效解决 NP 完全问题的方法是利用时间旅行。研究这个问题的物理学家谈论的不是时间机器，而是闭合类时曲线 (CTC)。本质上，CTC 是物质或能量可以沿着它行进以在过去与自身相遇的空间和时间路线，形成一个闭环。目前的物理理论对于 CTC 是否可以存在尚无定论，但这不妨碍我们询问，如果 CTC 确实存在，那么对于计算机科学来说会产生什么后果。
似乎很明显，人们可以如何使用 CTC 来加速计算：对您的计算机进行编程，使其花费解决问题所需的任何时间，然后将答案及时发送回您自己，时间点在计算机启动之前。唉，这个简单的想法行不通，因为它忽略了著名的祖父悖论，即你回到过去杀死你自己的祖父（但那样你就永远不会出生，所以你永远不会回到过去，因此你的祖父仍然活着生儿育女，然后你出生了，但是然后……）。在我们的环境中，如果您在收到来自未来的答案后关闭计算机，会发生什么？
1991 年，牛津大学的物理学家大卫·多伊奇定义了一个使用 CTC 的计算模型，该模型避免了这种困难。在多伊奇的模型中，自然将确保当事件沿着构成 CTC 的圆形时间线展开时，永远不会出现悖论，这一事实可以用来对在 CTC 内部循环以解决难题的计算机进行编程。
事实上，通过使用 CTC，我们可以有效地解决不仅是 NP 问题，甚至是表面上更大的类 PSPACE 中的问题。PSPACE 是可以在传统计算机上使用多项式数量的内存解决但可能需要指数级时间的问题类。实际上，CTC 将使时间和空间成为可互换的计算资源。（直到现在我才不得不提及多项式内存约束，因为对于 P 类和 NP 类问题，计算机是否可以访问超过多项式内存的内存无关紧要。）最近，安大略省滑铁卢大学的约翰·沃特罗斯和我表明，在 CTC 中使用量子计算机而不是传统计算机并不能有效地解决 PSPACE 之外的任何问题。换句话说，如果 CTC 存在，那么量子计算机并不比经典计算机强大。
计算氪石
物理学家不知道未来的理论是否会允许任何这些非凡的机器出现。然而，在不否认我们无知的情况下，我们可以从不同的角度看待这种无知。与其从物理理论开始，然后询问它们的计算含义，不如从假设 NP 完全问题很难开始，然后研究该假设对物理学的影响。例如，如果 CTC 可以让我们有效地解决 NP 完全问题，那么从 NP 完全问题难以解决的假设开始，我们可以得出结论，CTC 不可能存在。
在某些人看来，这种方法似乎过于教条。对我来说，这与假设热力学第二定律或不可能进行超光速通信没有什么不同——这是对技术的两个早期限制，随着时间的推移，它们赢得了物理原理的地位。是的，第二定律可能会在明天被实验证伪——但在那之前，物理学家发现假设它是正确的，然后使用这个假设来研究从汽车发动机到黑洞的一切都更有用。我预测，NP 完全问题的难度有一天会被视为相同的：作为描述我们宇宙本质一部分的基本原理。无法预知未来应用这种基本原理会带来什么样的理论启示或实际后果。
与此同时，我们知道不要对量子计算机抱有幻想。对于某些人来说，量子计算机的明显局限性可能会令人失望。然而，人们可以给这些相同的局限性一个更乐观的解读。它们意味着，尽管某些密码在拥有量子计算机的世界中可能会被破解，但其他密码可能仍将保持安全。它们增加了我们对量子计算完全有可能实现的信心——因为一种拟议的技术听起来越像科幻漫画，我们就应该越怀疑。（您更倾向于相信谁：是提供一种从量子真空中产生无限自由能源的设备的销售人员，还是提供一种比去年的型号更高效的冰箱的销售人员？）最后，这些限制确保了计算机科学家将继续努力设计新的量子算法。就像没有脚后跟的阿喀琉斯或没有氪石的超人一样，一台没有任何限制的计算机很快就会变得乏味。