Transcription
CHINMAY NIRKHE: 感谢大家参加我们 2026 年的首次保罗·G·艾伦杰出讲座。今天，我很荣幸向德克萨斯大学奥斯汀分校的斯科特·艾伦森教授介绍，他是该校的施伦贝格计算机科学主席，也是其量子信息中心的创始主任。斯科特在康奈尔大学获得学士学位，在加州大学伯克利分校获得博士学位，他是一位理论计算机科学家，其研究重点是量子计算的能力和局限性。此外，他是一位多产的作家，以其著作《自德谟克利特以来的量子计算》和广为人知的博客“Shtetl Optimized”而闻名。他曾获得美国国家科学基金会的艾伦·T·沃特曼奖、美国总统早期职业科学家和工程师奖（PECASE）、托马索尼-基耶西物理学奖、2020 年 ACM 计算奖，并且是 ACM 和 AAS 的会士。在我看来，斯科特在所有理论计算机科学家中，有着一种独特的视角，能够通过清晰的计算视角看待物理学，并使看似令人生畏的物理学变得更容易处理。所以，请大家和我一起欢迎今天的斯科特·艾伦森。
[掌声]
SCOTT AARONSON: 好的。非常感谢，钦迈。很高兴能回到华盛顿大学，这里有我认识了很长时间的许多好朋友和同事，现在也包括钦迈。但昨晚我在西塔克机场时还在想，这里的优步停车点又是怎么运作的呢？然后我才想起，我上次来这里的时候，优步还没有出现。所以，确实有段时间没来了，但很高兴能回来。
所以，这将会是一个有点“滔滔不绝”的讲座。这个讲座最初是为哲学系设计的。我在哥伦比亚大学讲过。但后来钦迈说他对我在华盛顿大学讲这个讲座感兴趣。所以，希望如果你喜欢计算机科学，或者喜欢物理学、哲学，或者任何非空子集，那么这个讲座都会有所收获。
所以，是的，它叫做“计算复杂性与物理学中的解释”。那么，什么是计算复杂性呢？我的意思是，这是计算机科学系，所以你们可能至少见过它。但我会称之为研究解决计算问题所需的固有资源，如时间和内存，还有其他东西，如随机性、量子性，特别是这些资源如何随着我们试图解决的问题的大小而扩展。它们是多项式扩展吗？它们是指数扩展吗？我们可以问更细粒度的问题。如果我们真的关心，我们可以尝试削减对数因子。但我们主要对广泛的扩展行为感兴趣，即一个问题的难度或容易程度的特征，这些特征在很大程度上不取决于我们使用的编程语言或芯片架构的细节，而是广泛地取决于我们拥有什么样的计算机，或者它遵循什么样的物理定律。
现在，问题可能难以解决或不可能解决的原因有很多。这些包括，我们信息有限，“垃圾进，垃圾出”的问题。我们就是没有所有相关数据。或者与此相关的是混沌，许多物理系统可能难以预测，因为我们无法以必要的精度测量初始状态，任何微小的误差都会随着时间的推移呈指数级增长。即使我们拥有无限快的计算机，这种情况仍然存在。然后还有所有的非理性，正如我们现在每天读新闻时都会提醒我们的那样，即使我们拥有所有信息和所有计算能力，也可能阻止我们做出正确的决定。
但在这里，我们特别关注计算上的不可行性，即一个问题之所以难以解决，仅仅是因为缺乏正确的计算资源，而我们拥有所需的所有数据。如果我们拥有一台无限快的计算机，那么我们就可以处理这些数据并了解我们想要的东西，但我们没有。我们没有那台计算机。所以人们很早就意识到了这一点。我的意思是，即使是公元前 300 年的欧几里得也在谈论如何加速计算，例如，计算两个整数之间的最大公约数，尽管我们直到 1930 年代才系统化了什么是可计算的理论，然后我们才在 1960 年代左右开始系统化什么是有效可计算的理论。
所以，有一句我非常喜欢的引言。
[有人提问]
AUDIENCE: 你想 [听不清] 吗？
SCOTT AARONSON: 当然，当然。随便。
AUDIENCE: 关于最后一个关于混沌的，那真的不是一个复杂性问题吗？
SCOTT AARONSON: 我认为我会争辩说它不是，因为这里的重点是，即使你拥有一台无限快的计算机，也可能有一个限制，比如你能在多远的未来预测天气。而这个限制不是来自计算上的不可行性。它来自于你无法以必要的精度测量大气中所有原子的状态。
AUDIENCE: 我明白了。
SCOTT AARONSON: 是的。好的，很好。
所以，这是艾伦·T·（图灵）的一句引言，这是他著名的《模仿游戏》论文中的话。他说：“我认为，机器不会产生惊喜的观点，是由于一个我称之为数学家和哲学家特别容易犯的谬误。那就是，一旦一个事实被呈现给一个心灵，这个事实的所有后果就与它同时出现在心灵中。在许多情况下，这是一个非常有用的假设，但当它太容易被遗忘时，它就是错误的。”
所以，基本问题——这是我一直思考的问题。我实际上在 2011 年写了一篇完整的调查文章，题为“为什么哲学家应该关心计算复杂性”。事实上，有趣的是，如果你在谷歌上输入“为什么哲学家应该”，它会自动补全为“关心计算复杂性”。但他们应该关心吗？或者如果你只是关心——很容易采取这样的立场，当然，即使你关心某事是否可计算，一旦它可计算，它需要多少步来计算它，这是一个非常细致的量化问题。这真的不是更广泛的哲学兴趣，或者说，让我们说——似乎，当然，这是一个在技术上很重要的问题。
在这次讲座中，我想问一个具体的问题，它对物理学中的解释重要吗？我指的是什么？所以，很明显，问题的计算难度或容易程度对我们认识物理定律的能力有很大影响。这里有一张照片，展示了他们用于分析日内瓦大型强子对撞机数据的计算集群之一。我实际上参观了那里的 CMS 探测器，这是世界奇迹之一。但是，在你看到探测器之前，你只看到一排排用于分析所有粒子碰撞事件的计算机，决定哪些要保存以供以后处理。所以，这显然涉及巨大的计算能力。甚至可以想知道，是否因为缺乏足够的计算能力来分析所有产生的数据，而错过了有趣的新的物理事件？所以，显然，如果你关心这些事情，你就会关心你有多少计算能力？而现在，世界经济的一半正被用于建造更大、更多的数据中心，其中大部分用于运行人工智能。所以，当然，很自然地会意识到，好吧，当然，如果人工智能将在为我们做科学或做物理学方面发挥越来越大的作用，那么我们拥有多少计算能力将是一个关键问题。
但在这次讲座中，我想关注一个不同的问题，那就是，计算复杂性本身能否在我们对物理定律的解释中发挥直接作用？所以，当我们解释为什么物理定律是这样的而不是那样的，计算难度与此相关吗？你可能会担心，这太以人类为中心了。这是人类关心的事情，因为人类想计算东西，但这似乎不是物理定律应该关心的事情。你可以采取这种立场。
与其在抽象中争论，不如在这个讲座中，我基本上想谈论三个不同的案例研究，其中一些人认为计算复杂性直接关系到解释一些关于基本物理学的东西，我们将尝试探讨它们。第一个是关于量子计算和量子力学的多世界解释，这是一个我可以说已经存在了几十年的古老争论。但我会将其与最近在量子计算领域发生的一些事情联系起来。第二个是我称之为“带有计算复杂性理论余味的奥卡姆剃刀”。所以，在寻找物理学中的解释时，例如，我们是否应该不仅重视最简单的解释，而且重视计算上有效的最简单的解释，或者其预测可以在合理的时间内计算出来的解释？这是我们应该重视的事情吗？我们应该如何看待它？
然后第三件事是一个更近期的方向，它真正源于丹尼尔·哈洛和帕特里克·海登在 2012 年关于黑洞信息悖论的工作。但这是计算复杂性作为我所说的“有效理论的盔甲”。也就是说，当我们看物理学中的有效理论时，比如量子场论、广义相对论，这些我们不认为是自然界最终真理的东西，它们最终会被其他东西取代，但它们有其有效性范围。计算复杂性与界定其有效性范围相关吗？他们给出了一个非常、非常引人注目的例子，至少在黑洞的背景下，似乎我们需要计算上的困难才能说，我们已知物理定律的有效性范围是什么。
我将举一个不同的推测性例子，它源于我最近与热力学第二定律有关的一些工作，或者基本上如果 P 等于 NP，我们是否能够违反第二定律，制造出麦克斯韦妖，制造出永动机？我认为这是一个你可以自然提出的问题。人们已经讨论了这个想法几十年了，所以我会至少给你一些关于这方面的见解，希望如此。
所以，让我们从量子计算和多世界解释开始，这里的问题是解释量子计算机为何能获得如此巨大的加速，或者我们是否被迫假定多个宇宙的现实，无论我们对此意味着什么。所以，在我谈论如此深刻的问题之前，我应该做的第一件事是稍微退后一步，说，好吧，什么是量子计算，因为我认为这里有来自不同背景的人。为了回答这个问题，无论好坏，由于我的博客，我每隔几天就会和另一位记者通电话，让他们用一句话解释什么是量子计算机。我说，我已经做了 20 年了。我说，我能有 10 分钟吗，因为我只能压缩到这个程度。但事实是，为了回答这个问题，我们必须稍微退后一步，说，好吧，什么是量子力学？量子力学已经存在了我们整整一个世纪了，但我认为它仍然是科学中最被误解或最被错误解释的事情之一。
我尝试教授量子力学的方式，以及许多我的同事在量子计算和量子信息领域教授的方式，是将其教授为一旦你摆脱了物理学，它实际上会简单得多。所以我喜欢将其教授为概率规则的一种特定推广，一种涉及负号的概率理论。所以，理查德·费曼曾经说过，所有量子力学都包含在这个一个实验中，著名的双缝实验，所以它只是涉及，比如说，一个光子。顺便说一句，这就是光子的样子，或者对我来说就是这样。现在我们一次又一次地将它射向一个有两条不同缝的屏幕，我们可以打开它们，然后我们看看这个光子落在第二个屏幕上的某个特定位置的概率是多少。让我们说，如果这条缝是打开的，那么光子就会以某种概率落在那个位置，这个概率是 P1。我并不真正关心它的细节。它可以穿过这条缝，然后它可以朝各种方向飞去，但有时它会落在那里。现在，有第二条缝。如果这条缝是打开的，那么光子就会以等于 P2 的概率落在同一个位置。现在我们打开两条缝。现在像我这样的人会倾向于说，这只是一个先验的数学事实。这是我们甚至不需要咨询物理学家的事情，我们只是坐在扶手椅上就知道，光子落在那个位置的概率现在是 P1 加 P2，因为我们只是把它可以走的两种方式加起来。唯一的问题是，你做了实验，结果并非如此。
那么，你反而发现了什么？嗯，你发现了这个在 1900 年到 1925 年间让人们抓狂的东西，有一个很长的故事，直到他们最终说，好吧，事情是这样的。事情是这样的，对于光子可以走的每条路径，你都必须附加一个复数。你必须附加一个叫做振幅的数字。所以，这些振幅与概率非常相关，但它们不是概率，正如我们可以通过它们是复数这一事实来证明的那样。现在，光子落在那个位置的总振幅确实等于它可以到达那里的所有单独路径的振幅之和。所以，那部分就像概率论一样。那么，当我看到光子的概率等于振幅绝对值的平方。所以，结果是，例如，可能会发生光子可以走一条路径，振幅为 1/2，另一条路径，振幅为 -1/2。现在，如果发生这种情况，那么总振幅 alpha 将实际上为 0，这意味着我看到光子在该位置的概率也将为 0。所以，这就像事件发生的两种方式相互干涉并相互抵消了。然而，你可能会注意到，如果我关闭两条缝中的一条，那么现在我有一个振幅，它只有 1/2 或只有 -1/2，这意味着现在概率等于该绝对值的平方，即 1/4，这意味着现在光子可以到达那里。所以，通过减少光子可以走的路径数量，我可以增加它到达那里的机会。而这就是我们不仅仅在处理粒子行为的细微之处的标志。我们正在处理概率规则本身的改变。
是的。
AUDIENCE: 你以前说过，我真的很喜欢，量子力学是带有复数的概率论。
SCOTT AARONSON: 是的，基本上。
AUDIENCE: 这比说带有负号更有启发性。有什么原因改变了吗？
SCOTT AARONSON: 嗯，我想任何一种说法都可以。但量子计算和信息中最有趣的事情，即使是带有正负实数的振幅，我们也能看到。我们真正需要的是振幅可以干涉和相互抵消的事实。它们也可以是复数这一事实确实增加了一些重要的细节。但是，对于我们关心的大部分内容来说，仅仅是它们有符号的事实就足够了。
所以，我们今天早些时候有过一次谈话，谈到了上帝。我说，关于上帝，我最确定的事情是，上帝确实非常非常偏爱复数而非实数，以及 2-范数而非 1-范数。然后他们敦促我在这次讲座中说出来，所以我现在就说了。
好的。那么，什么是量子计算呢？嗯，这里我有一个量子计算机的基本构件，叫做量子比特。量子比特就是一个有概率为 0 和另一个概率为 1 的比特。所以，正如我们所说，它可以处于 0 状态和 1 状态的叠加态，我们写成 alpha 0 加 beta 1，我们使用这些尖括号，它们实际上只是向量的符号。这些 x，这是一组在 2 的 n 次方维空间中的正交基向量，现在我只是取我的基向量的线性组合。所以，关键点是，要描述一个量子比特，我需要两个振幅。我需要一个它为 0 的振幅，一个它为 1 的振幅。它处于两者的叠加态，直到我进行测量，届时自然必须根据这个规则（称为玻恩规则）以概率选择其中一个。
但现在，如果我有两个量子比特，我需要四个振幅，或者我需要 00、01、10 和 11 的振幅。如果我有三个量子比特，我需要八个振幅，四个，我需要 16 个，以此类推。如果我有 1000 个量子比特，我需要 2 的 1000 次方个振幅，这比可观测宇宙中能写下的数量还要多。但从某种意义上说，我们 100 年来最好的物理理论告诉我们，它们都存在，对于“存在”的某种定义，当然，我们想回到这一点。
所以，量子计算的起始想法，理查德·费曼、大卫·杜奇和其他几位物理学家在 45 年前就开始谈论的想法是，如果你真的需要一个 2 的 n 次方个复数的向量来跟踪 n 个粒子在做什么——比如说，每个粒子可能编码一个量子比特。1000 个粒子，我可能很容易需要 2 的 1000 次方个振幅来描述它们。那么，这似乎是自然界要付出的惊人的计算努力。似乎仅仅是为了跟踪这 1000 个粒子，自然界就必须维护一个大小为 2 的 1000 次方的草稿纸。每当粒子发生什么事情时，自然界就必须划掉草稿纸上的所有数字，并将它们替换为新数字。事实上，化学家和物理学家几代人以来都知道这一点。他们主要将其视为一个实际问题，即如果你试图使用经典计算机来模拟量子系统，那么你可能很快就会遇到你能够存储或操纵的量子态大小的限制。
所以，然后问一个问题是很自然的，嗯，如果自然界给了我们这个柠檬，我们能用它来制作柠檬水吗？我们能建造一台本身就包含这些巨大的叠加态的计算机吗？如果能，它有什么用呢？
嗯，费曼和杜奇当时只能给出一个很好的答案，那就是，嗯，它将用于模拟量子力学本身。几十年来，我们一直在努力改进这个答案，取得了一些成功。但理解这一点非常重要，因为不幸的是，你读到的几乎任何关于这个主题的流行文章都会说，嗯，看，经典计算机只使用 0 或 1 的比特，但量子计算机使用可以同时是 0 和 1 的量子比特。所以，如果我有 100 个量子比特，这意味着我并行探索 2 的 100 次方个答案，当然这很有用。这只会加速一切。不幸的是，事情并非如此简单。我一直在推着一块巨石上山，已经 20 年了。无论我向多少记者解释，他们仍然会按照他们想要的方式写故事。但既然你在这里听我讲，我告诉你真相，那就是整个麻烦在于你永远无法直接看到振幅。事实上，振幅只与观察有关，因为我们需要它们来计算我们看到的那些结果的概率。但如果我观察 n 个量子比特，我不会看到这个 2 的 n 次方个振幅的列表，我只看到 n 个比特。我迫使自然界做出一个决定，它给我什么结果。每个结果 x 以概率绝对值 alpha x 的平方出现，然后就结束了。所以，是的，我可以对我的计算问题的所有答案做一个等概率叠加，即使有指数多的答案。用量子计算机做这件事甚至很容易。但如果我这样做然后我测量，那么规则非常清楚，我只会看到一个随机答案。如果我只是想要一个随机答案，我应该只抛几次硬币。我可以节省建造量子计算机的数十亿美元。
所以，从量子计算机获得加速的唯一希望是利用振幅，无论是复数还是带有负号的，与概率不同的工作方式。对于每一种量子算法，基本目标是编排一种干涉模式，使得对于每个错误答案，其振幅的某些贡献是正的，而另一些是负的，所以它们相互抵消。而对于正确的答案，我想要的那个，其振幅的不同贡献指向同一个方向，所以它们相加。棘手的部分是，我必须做到这一点，即使我自己事先不知道哪个答案是正确的。如果我已经知道了，那还有什么意义呢？而且我必须比最快的经典算法更快地做到这一点。
所以，这是大自然递给我们的一把非常奇怪的锤子，我们可以用它来寻找，有没有什么钉子可以敲？但宇宙并没有——我们无权要求宇宙会提供任何有用的东西。我的意思是，我们应该对我们所拥有的感到感激。
那么，量子计算机的主要已知应用是什么？所以我有一个小幻灯片，我会把它们分成三类。所以，量子计算最著名的应用，也是 30 年前它真正被世界广泛认识的东西，是这样的，嗯，有快速的量子算法可以分解巨大的复合数成其素数因子，以及解决数论和群论中一些密切相关的问题，如离散对数，涉及椭圆曲线的问题。这是彼得·肖尔的突破，这使得像情报机构这样的人对量子计算产生了兴趣。所以，每当我们访问一个网站时，我们都在使用 HTTPS，或者我们发送一个 Signal 聊天，我们发送我们的信用卡号，我们的数据被加密，这些加密代码取决于这样一个信念，即这些特定的数论问题是困难的。肖尔的算法表明，如果有人能够构建一个可扩展的量子计算机，那么情况就不再是这样了。
因此，这促使了一项已经进行的努力，即尝试将我们整个安全基础设施迁移到所谓的后量子或抗量子密码学。我们确实有一些好的后量子密码系统的候选者，例如，基于格问题的，美国国家标准与技术研究院（NIST）和其他政府机构以及谷歌等公司已经开始尝试迁移。即使你认为可扩展的量子计算机要到 10 年后才会出现。我认为现在就应该开始迁移了。所以，例如，据称有价值约 2000 亿美元的早期比特币，包括中本聪的原始比特币，无论中本聪是谁，都存储在仅受椭圆曲线密码学保护的钱包中，而量子计算机大概能够破解它。所以，如果有人负责比特币并且能够做出迁移的决定，那么解决这个问题会更容易，但根据设计，没有人负责它。所以这将是一个问题。但量子计算的这个应用，虽然它具有巨大的地缘政治和网络犯罪兴趣，但很难说它是人类的福音。它是一个巨大的头痛，如果我们解决了它，那么希望我们都能回到原点。
所以，这带来了第二个应用，这是费曼最初的应用，我认为它仍然是我们所知的经济上最重要的应用，那就是量子计算机将是一个通用的可编程设备，可以高效地模拟你感兴趣的几乎任何量子系统。这可能对研究高温超导、光伏、电池、用于制造肥料的化学反应等领域的人有用。在我看来，这是我们在短期内用量子计算机做一些有经济价值的事情的最佳途径。所以我希望这会奏效，但它的应用范围比许多人希望的要窄。
这带来了第三类，即其他所有一切。所以，当你阅读，比如说，量子计算初创公司在说什么时，特别是那些现在上市并估值达到 200 亿美元或更高的公司，或者在商业界人们在说什么时，都是关于量子计算将彻底改变机器学习和优化，以及几乎所有——以及人工智能和金融，以及我们用计算机做的几乎所有实际事情。在这里，我认为，至少基于我们所知的量子算法，情况要模糊得多。我们确实知道一些量子算法可以为这些任务提供一些优势，特别是有一个叫做格罗弗算法的，它是继肖尔算法之后第二重要的量子算法，它的应用范围要广泛得多。格罗弗算法可以用来搜索任何包含 n 个可能解决方案的列表，其步骤数量只与 n 的平方根成比例增长，而经典暴力搜索需要 n 步。所以，这就像你翻开一本计算机科学教科书，几乎任何算法中都有一个 for 循环，你在检查数据库中的大量条目或问题的大量可能解决方案。几乎你能想到的任何算法都有一个可以被格罗弗化的步骤。缺点是，这不是指数级加速。它仅仅是平方根加速，从 n 到平方根 n。你可能会说，嗯，这听起来不错。我接受。事实上，这最终可能会相关，但可能要过一段时间。问题是，要构建一台能够运行肖尔或格罗弗算法的量子计算机，你需要所谓的量子纠错。在过去一两年里，我们才开始看到量子纠错实际上能够保护一个量子比特，大致上。所以，它开始像理论所说的那样工作，但它会带来巨大的开销，乐观地说，可能是百万倍的开销。所以，现在的问题不是比较 n 和平方根 n。问题是比较 n 和一百万倍的平方根 n。最终，一百万倍的平方根 n 确实小于 n，但这只发生在 n 达到万亿时。所以，这就是格罗弗加速的问题。当你超越这一点时，我们几十年来一直在努力寻找用于优化和机器学习问题的量子算法，这些算法能获得比格罗弗算法更多的加速，但这非常具有挑战性。
长话短说，我们所知的绝大多数加速要么是针对非常非常专业的问题，要么是适度的，要么是推测性的。比如，我们不知道加速是否真的存在。有时量子加速会持续一段时间，然后就会被某人发现更好的经典算法来解决同一个问题而打破。Ewin Tang，她是这个系的毕业生，现在是普林斯顿大学的教授，在她还是本科生和我一起工作的时候，我在“反量子化”一个量子机器学习算法方面取得了最大的突破之一。所以，这是这里的挑战的一部分。你必须在 Ewin 的攻击下生存下来。
但现在，我个人来说，我最关心的“零号应用”，比以上任何一个都更关心，就是反驳那些说量子计算不可能的人。如果我们能做到这一点，我认为就值得所有投资。任何有用的东西，那只是锦上添花。这不是我们对资助机构提出的理由，但再次说明。
所以，这里有一张小图。在计算机科学中，我们喜欢将事物组织成这些类，并用不同的字母大写来称呼它们。所以，我们有 P，即经典计算机可以在多项式时间内解决的问题，然后是 NP，即经典计算机至少可以有效验证答案的所有问题。然后，在 NP 的顶端是这些著名的 NP 完全问题。当然，我们最著名的未解问题是 P 是否等于 NP。但与此同时，我们也有这个 P 的量子推广，称为 BQP，有界误差量子多项式时间。我用波浪线边框画它，因为所有量子东西都是诡异而奇怪的。但 BQP 至少包含一些 NP 问题，这些问题目前不知道是否属于 P。那是肖尔的突破，但我们不认为 BQP 包含 NP 完全问题。至少，如果它包含，那将是一场几乎与 P 等于 NP 的发现一样伟大的革命。
在另一个方向上，我们不知道 BQP 是否包含在 NP 中。可能存在量子计算机可以解决但经典计算机甚至无法检查答案的问题。模拟量子系统可能是这样一个问题的例子。
那么，我们现在处于什么位置？也许我为量子计算理论做出的最著名的贡献，我想，在我从事这项工作的大约 27 年里，是导致我们现在称为量子霸权实验的许多理论。顺便说一句，我不是这个名字的发明者。如果你不喜欢它，你可以责怪 John Preskill。但这些实验实际上已经被几个不同的实体进行了。你们中的一些人知道，第一个是由谷歌完成的，就在一年前，他们能够构建一个拥有 103 个超导量子比特的芯片，并且他们能够使用这个芯片获得一些数学信息，而我们不知道如何从现有的最大经典超级计算机那里获得这些信息，需要花费大约 10 的 25 年。
那么，我们得到的信息是什么呢？嗯，我希望你坐好了。这些 103 个比特的字符串，统计上不太可能不是这个量子电路的输出。所以，我没有说它会是很有趣的信息。事实上，即使是验证量子计算机是否按预期工作，在这种情况下，据我们所知，也需要 10 的 25 年。
现在，就在去年，Quantinuum 使用其捕获离子设备和谷歌都改进了这一点。事实上，我认为 Dave Bacon 就在这里，他参与了其中一些工作，但他们现在开始进行实际的物理系统模拟，例如 Quantinuum 的费米-哈伯德模型，或者所谓的“时间顺序相关函数”（OTOC）电路，你实际上只是计算一个特定的数字，而不是对这些奇怪的分布进行采样。你计算这个数字的速度比任何人都知道如何用经典方法计算它的速度还要快，而且你可以验证量子计算机是否在做正确的事情，至少可以通过将其输出与第二个量子计算机的输出进行比较，或者与实际的物理实验进行比较。
我们还没有达到能够运行肖尔分解算法的规模。那可能需要纠错。
所以，现在我可以回到哲学部分了。所以，自从量子计算的早期以来，一直存在一个问题，即这对世界的本质意味着什么。所以，有一个著名的，所谓的量子力学的多世界解释，它起源于埃弗雷特这个人，他发表这篇文章时还是一个研究生。但尼尔斯·玻尔讨厌它，所以他的导师惠勒告诉他必须审查。你是什么意思？然后他对此感到厌恶，所以他离开了物理学，转而成为核武器战略家。
多世界解释说了什么？它说的关键是，这个巨大的振幅向量就是最基本的本体论现实。所以，特别是，人们争论量子力学意义的原因是，正如我所说，当你观察时，当你测量时，你以概率绝对值 alpha sub x 的平方看到结果 x。你可能会说，你到底是什么意思，当你观察时？物理定律不应该有“当你观察时”这样的条款。它们不应该谈论观察者、意识或测量设备。我们也是由原子组成的，它们遵循与一切相同的定律。所以，多世界只是说，是的，绝对的。我们同意这一点。一切都遵循相同的定律。定律就是振幅的定律。它们是振幅向量的线性演化的定律。而我们称之为测量，我们认为测量一个量子比特实际上只是你与该量子比特纠缠在一起。所以，你应该把测量看作是一个普通的量子态的线性变换，酉变换，现在它也将包括你所有的原子，你的身体，你的大脑，或者其他什么。
所以，这里是你被视为一个量子态。这里是你正在测量的量子比特，在测量中发生的一切就是两者纠缠在一起，这意味着，现在，以振幅 alpha，量子比特处于 0 状态。而且，你，你的大脑，也许还有你周围房间里的空气和辐射，都记录了量子比特是 0。然后，以 beta 振幅，量子比特是 1，你和你的测量设备以及房间等等都记录了量子比特是 1。然后，这是一个分支事件，然后一大堆分支事件继续下去，没有任何东西能阻止它们。多世界论者会说，所有这些结果都会永远存在，因为数学就是这么说的。所以，特别是，你应该有数万亿个你的替身，他们的生活与你的不同，他们都同样真实。
现在，可能很难向人们传达——你可以对这个观点说或反对它很多，但从某种意义上说，这只是保守的选择，而其他任何选择都有些激进。所以我认为这主要的替代方案是，要么是所谓的玻姆力学，玻姆-德布罗意，它基本上承认存在这个巨大的波函数，这个巨大的振幅向量。但然后它说，好吧，但在大多数分支中没有人。它们只是鬼城。然后有一个分支是真实的，被意识之光照亮，即我们所在的那个。而所有其他分支都只是因为数学需要它们来推动真正的分支，以一种完全符合标准量子力学预测的方式，所以无法测试。所以，这是一种可能性。
第二种可能性是我称之为“新物理学”。所以，可能是当你的规模达到你，或者说，一个盒子里的一只猫，它可以是活的或死的，或者别的什么，那么一些尚未知的物理学就会接管，而这个规模的叠加态根本就不稳定。它们只会动态地坍缩成一个状态或另一个状态。这实际上做出了一个原则上可以测试的经验预测。到目前为止，我们还没有看到任何迹象。但当然，如果建造量子计算机能导致新物理学的发现，我认为这会比仅仅成功建造量子计算机更令人兴奋。我希望量子计算能以这种方式失败。如果它成功了，相比之下就会是一种失望。
是的。
AUDIENCE: [听不清] 当你进入宏观尺度时，它只是发生了一个相变？
SCOTT AARONSON: 嗯，我会说，如果薛定谔方程普遍成立，那么它可能会在我们看来，发生了一个相变，但物理学的真正定律会说所有其他分支仍然存在。它们并没有消失。如果你希望它们消失，那么你需要某种物理机制来做到这一点。这就是我所说的。我没有告诉你哪个选项是正确的。我只是告诉你，这些是选项。
然后，量子力学的真正原始观点，玻尔和海森堡等等，就像一种非常、非常复杂的“闭嘴，别再问这个问题”的版本。我喜欢说“闭嘴，去计算”，但除了不闭嘴之外。所以，也许这些只是坏问题。
但现在我想谈谈大卫·杜奇在 1997 年提出的一个著名挑战，他是量子计算的联合创始人。他说：“对于那些仍然坚持单一宇宙世界观的人，我发出这个挑战——解释肖尔算法是如何工作的。我不仅仅是预测它会起作用，这仅仅是解决一些没有争议的方程的问题。”杜奇从来不是一个注重细节的人。“我的意思是，提供一个解释。当肖尔算法分解一个数字时，使用了可见的 10 的 500 次方倍的资源，这个数字在哪里被分解了？如果可见宇宙是物理现实的全部范围，那么物理现实将远远不足以分解如此大的数字。那么，谁分解了它呢？计算是在哪里以及如何进行的？”
那么，我们对这种挑衅性的论点能说些什么呢？首先，杜奇并不是说，如果你建造一台量子计算机，那么这就是对多世界解释的实验检验。他并没有说那么简单的事情。为什么不呢？嗯，因为每个同意量子力学的人，无论他们的解释如何，他们都同意肖尔算法会起作用，正如他所说。要让它不起作用，我们的量子力学理解就必须在经验上出错。
现在，杜奇实际上说过，在他看来，双缝实验证明了多世界解释。以任何其他方式谈论它已经很荒谬了。但然后他补充说，对于许多在心理上太软弱而看不到这一点的人来说，看到一台量子计算机分解一个 10000 位数的数字将有助于他们。所以，我想说哲学问题是，是否存在任何意义上的可扩展量子计算，无论是今天的概念还是明天有望被证实的现实，都能增加支持多世界解释的理由？
我的观点是，埃弗雷特的图景的核心是振幅向量的指数性。是的，量子计算在如何使量子力学的这一方面无法回避方面是独一无二的。但是，如果你问更形而上的问题，比如，其他分支里有人吗？那么量子计算对此完全沉默。事实上，我们甚至可以再说一点，那就是，讽刺的是，在某种程度上，量子计算起作用，比如肖尔算法，它之所以起作用，是因为我们让所有这些分支相互干涉，建设性和破坏性地干涉，这意味着它们在某种程度上从未完全确立自己作为独立宇宙的身份。它们只是一个巨大的、相互干涉的量子力学团块。而就它们真正分支成宇宙而言，在那个程度上，我们只看到了其中一个。所以，以此为基础来论证多世界是有趣的。
所以，剩下的内容会更快一些。但我想谈谈计算复杂性理论的奥卡姆剃刀。所以，我们是否应该对预测计算超能力的物理理论持有一种归纳偏见？你可能会想，物理定律的改变怎么会产生计算超能力呢？为了回答这个问题，我想向你介绍芝诺的有限时间哥德巴赫判定器。
所以，哥德巴赫猜想说，所有大于或等于四的偶数都可以写成两个素数的和。这是初等数论中最著名的未解问题之一。它已经被检查到万亿的级别，但当然，问题是仍然有无穷多个案例。但假设我们可以拥有一台我们可以任意加速的计算机。那么一个想法就会出现。为什么我们不花一秒钟来测试哥德巴赫的第一个案例，然后花半秒钟来测试第二个案例，花四分之一秒来测试第三个案例，然后下一个案例花 1/8 秒，以此类推，这样在两秒钟后我们就尝试了无穷多的案例？比如，为什么没有人尝试呢？嗯，有人尝试。有人超频他们的微处理器。但你们中的一些人可能会遇到问题。如果你过度超频你的处理器，它会熔化。这就是为什么所有这些正在建造的数据中心都有那么多冷却设备。但冷却需要能量。事实上，计算本身，我们通常的方式，需要能量。你可能会想，这里的最终限制是什么？据我们所知，基于已知的物理学，最终限制似乎发生在普朗克时间左右，即 10 的负 43 秒。发生的情况是，如果你尝试以比这更快的速度运行你的计算机，比每秒 10 的 43 次操作还要快，那么构成你计算机的任何东西都在使用如此多的能量来循环状态，以至于它超过了它自身的史瓦西半径。这意味着什么？这意味着你的计算机坍缩成一个黑洞，我一直喜欢把它看作是大自然告诉你不要做某事的办法。
另一个想法是我们称之为相对论计算，这就是你启动你的计算机来处理一个困难的问题，你把它留在地球上，然后你登上一个加速到接近光速的飞船。你减速，返回地球。现在，在地球的参考系中，已经过去了数十亿年。文明已经崩溃，如果它没有在 2028 年左右崩溃的话。但那时，肯定已经崩溃了。你所有的朋友早就死了。但如果你能在废墟中找到你的计算机，并且它仍然有某种能源，那么你就可以得到困难问题的答案。
所以，问题是，嗯，为什么没有人尝试呢？我认为，再次，问题在于能量。问题在于加速到接近光速需要多少能量才能获得这种指数级加速，你可以计算出来，再次，你需要指数级的能量。所以，我们又在用一个指数换另一个。
有一个古老的想法，你可以利用时间旅行，闭合类时曲线，来解决困难的计算问题。这并不像，哦，如果我能回到过去，我就可以一遍又一遍地重复使用相同的时间，因为这没有认真对待祖父悖论。比如，如果你回到过去并杀死你的祖父怎么办？那么自然界就必须找到一个一致的解决方案。
所以，大卫·杜奇，就是那个关于量子计算的，他有一篇关于闭合类时曲线的著名论文，他说，看，量子力学在这里又来拯救了，因为它允许解决方案，比如，如果你回到过去并杀死你的祖父，那真正意味着你只是处于一个量子态，其中一半的概率，你回到过去，杀死你的祖父，一半的概率，你从未存在过。所以，这意味着什么？这意味着你出生的一半概率。一切都是一致的。没有悖论。而且你可以证明，至少在有限维空间中，至少会有一个这样的不动点总是存在。
但然后你遇到了一个新的问题，那就是，自然界必须付出多大的努力才能找到那个不动点？而在找到那个不动点时，事实证明，自然界可能再次被迫解决一个困难的计算问题。你可以基本上做到——通常的故事是想象你回到过去，然后你告诉莎士比亚他将要写什么戏剧。他说，老兄，谢谢你为我节省了很多时间。然后你只是抄下你告诉他的东西，然后那些戏剧就来到了你这里。所以，与这里的祖父悖论不同，没有矛盾。一切都是一致的。唯一的问题是，哈姆雷特和麦克白不知怎么出现了，而没有人写过它们。所以，你可以利用同样的思路，用多项式资源强迫自然界解决一个 NP 完全问题。事实上，你甚至可以做得更多。所以，约翰·沃特鲁斯和我有一篇 2009 年的论文，我们说你可以用这种方式解决 P-space 类中的所有问题，而这正是正确的答案，即用多项式内存完成经典计算机可以做的所有事情。然后我们
在后来的一篇论文中，我们说，如果闭合类时曲线所通过事物的规模是无界的，那么你实际上可以解决停机问题。通过这种方式，你可以真正地做一些图灵不可计算的事情。但现在的问题是，我们是否应该仅仅将这些结果视为支持闭合类时曲线在现实中可能不存在的额外论据？所以这是奥卡姆剃刀与复杂性后遗症的问题。我们是否应该不仅因为描述复杂性高而惩罚物理假设，也因为计算复杂性高而惩罚它们？我自己的观点是，我们不能过于教条，因为如果我们那样做，我们也会排除量子计算，事实上，许多量子计算的怀疑论者就是这样做的。他们说量子计算行不通。为什么行不通？嗯，因为如果它行得通，那么因式分解就可以在多项式时间内解决，这是一个显而易见的荒谬。但这种立场，其中一些人仍在坚持，但随着实验的进展，他们似乎被逼入了越来越狭窄的境地。所以，我可能想对大自然能够用多项式资源解决 NP 完全问题持有一些偏见，但不是无限的偏见。量子计算仅仅似乎稍微扩大了 P 的范围，让我们能够解决因式分解，但不能解决 NP 完全问题，这对我来说是将其视为更合理的原因。另一方面，NP 完全问题没有快速解决方案，感觉与，比如说，没有超光速信号或没有永动机没有什么不同。值得注意的是，相同的物理假设，如闭合类时曲线，或量子力学的非线性修改，往往会违反所有这三个原则。所以似乎存在某种联系。这实际上把我带到了我将要告诉你的最后一件事。我将跳过关于黑洞信息问题的整个内容，因为我没有时间，而且我们没有黑洞来减缓时间。但我可以用这些幻灯片来诱惑你。这是爱丽丝带着防火墙跳进黑洞。这是丹尼尔·哈洛和帕特里克·海登在 13 年前提出的整个故事，试图解释这个关于黑洞的特定悖论是什么，他们说，这需要太长时间。进行实验需要太长的计算时间。这将导致量子场论和广义相对论崩溃，正如它们被预测的那样。因此，在某种意义上，我们的物理理论在黑洞附近受到保护，因为某些问题无法在仅仅 10 的 67 次方年内解决，比如说，一个太阳质量的黑洞需要蒸发的时间，而是需要 2 的 10 的 67 次方年才能解决。所以这是一个非常、非常巧妙的论证。如果人们以后想问我关于它的问题，他们可以。但现在，实际上就在过去的几个月里——我参观了圣达菲研究所。我与 Gulce Kardes 和 Harrison Hartle 合作了一个更平凡的计算复杂性作为一种保护我们物理学有效理论的装甲的例子。这与热力学第二定律有关，也就是盒子里的气体粒子。所以我们所做的是构建了一个玩具情境，如果 P 等于 NP，事实上，如果没有单向函数，也就是说，基本上没有基于困难问题的密码学，那么你就可以通过构建一个盒子来收集盒子里的所有气体到盒子的一侧，从而似乎可以逆转热力学第二定律。麦克斯韦妖是物理学中著名的悖论，你有一个盒子里的气体，然后有一个妖精，它通过战略性地开关一扇门，就能够将所有气体移动到盒子的一侧，这似乎减少了宇宙的总熵，违反了第二定律。我猜，兰道尔、贝内特等人对这个悖论有一个经典的解决方案，他们说，好吧，这实际上并没有违反第二定律。为什么没有呢？嗯，因为熵仍然存在，并没有消失。它去哪里了？进入了妖精的记忆。妖精必须记住信息。信息不会从宇宙中删除。它只是被转移到妖精计算机的记忆中。现在，我们可以展示一个情境，如果 P 等于 NP，那么我们可以计算妖精的记忆。所以我们可以从一个简单的初始条件开始。如果我们有确定性的、可逆的经典动力学，那么熵似乎会增加。但那种熵实际上只是伪熵。通过利用 P 等于 NP 的事实，我们可以揭开这种伪熵的面纱，也就是说，首先，妖精将所有粒子收集到一侧，然后妖精反计算或只是大规模、大规模地压缩其记忆中的内容。然后我们似乎就逆转了第二定律。我应该警告你，在实践中，混沌或量子力学可能会在我们大多数现实的物理系统中使我们的策略失败。但即便如此，我们也表明，第二定律的出现只能通过计算复杂性来保护，就像广义相对论和量子场论在哈洛-海登情境中的黑洞附近一样。这是我们系统的简图。我们对它进行了一个小模拟。好了，结论。一个多世纪以前，知识和信息，尽管它们表面上以人为中心，却悄悄地进入了我们最好的物理学解释中，例如，通过玻尔兹曼的统计热力学和相对论中的无信号原理。那么，如果计算限制同样悄悄地进入我们这个时代的物理学解释，我们是否应该感到惊讶呢？现在，一个区别是，纯数学的进展，比如 P 与 NP 问题的一个解决方案，将有助于阐明哪些计算限制是真实的。所以这里有一些未解决的数学问题。但我想故事的一部分很像早期的热力学故事。如果你想了解更多关于这方面的信息，你可能会喜欢我 2011 年的调查文章，尽管我谈论的很多内容实际上比那更新。但感谢您的聆听。[掌声] CHINMAY NIRKHE：我想也许有两个问题？SCOTT AARONSON：是的，当然。是的，我们在谈话中收到了一些问题。是的。听众：我一直想知道的一件事是，为什么我们似乎很难想出使用量子计算机的有用算法？这是否说明了该问题的实际复杂性、难度有什么根本性的问题，还是我们还没有更努力地尝试？SCOTT AARONSON：是的。我的意思是，正如我所说，大自然给了我们一个绝对奇特的锤子，它不必对任何事情有用。我们很幸运，有一些纯粹的经典问题恰好映射到这种干涉现象，以至于你可以编排干涉以获得加速。我认为在肖尔算法之后，你得到了一个类似鲁佩尔施特尔金的现象。你知道鲁佩尔施特尔金的寓言吗，如果你能把一些稻草纺成金子，那么就能把这 1000 倍更多的稻草纺成金子。如果你能进行因式分解，那么一定有更多、更多的事情你可以做。但问题的一部分是，如果你只看计算问题的景观，我们有大量的 P 类问题，你只能希望从量子计算机获得多项式加速，然后我们有大量的 NP 完全或更难的问题。我们说，我们通常不相信量子计算机能够解决 NP 完全问题。所以如果我们把这个排除在外，那么我们剩下的是 P 和 NP 完全之间的无人区。那里有什么？嗯，那里稀疏得多。我们有因式分解。我们有离散对数。对于这些，我们有量子算法。我们还有一些其他的东西，比如格问题，我们还没有量子算法。也许我们应该希望我们不会，因为如果我们这样做了，那么我们所有的公钥密码学都将消失。我们应该希望其中一些东西仍然很难。我们有图同构，一些人，包括这里的人，都研究过。我们还有一些其他的东西。但我认为任何真正想要更多量子算法的人，他们首先应该做的是扩大要研究的问题空间。这可能是人们没有怎么想过的奇怪的事情。七年前我有一个提议，你可以使用量子计算机来生成加密认证的随机数，然后你可以用它们来证明质押的加密货币，例如。所以这很奇怪，对吧？这甚至不是通常意义上的 P 和 NP 的计算问题。但如果有人真的足够关心，那么他们现在就可以做到，而且使用当前的硬件。这已经被实验证明了。所以我认为我们应该寻找更多真正奇怪的东西。有时，当果实太高挂在树上，因为所有低垂的果实都已经被摘完了，那么解决方案就是找到另一个果园。所以这将是我的最佳建议。是的。听众：NP 之外的东西怎么样？SCOTT AARONSON：是的，当然。我的意思是，我们当然可以去那里看看。我的意思是，量子模拟就在那里。但有时写下这些问题会变得不那么自然，因为我们甚至没有一个有效的标准来检查答案。是的。听众：所以物理学家必须考虑计算复杂性有一个更基本的原因，那就是一个理论的预测必须是可计算的才能被检验。事实上，它们大多不是。所以你实际上可以说，到目前为止被检验的不是理论本身，而是它们的泰勒近似。SCOTT AARONSON：是的。嗯，物理学家在实践中处理这个问题的方式是，他们说，看，我们不必检验我们理论的所有预测。找到我们理论的一些新颖的预测就足够了，这些预测超出了先前理论所说的，并且是我们可以计算的，并且我们可以进行实验，并且我们可以比较这两者。如果我们看到那里的一致性，那么我们就暂时接受该理论。这是几百年来一直这样做的方式，我们不检验人尺度上的量子场论，有它的阿伏伽德罗数个粒子，但我们在几个粒子尺度上检验它。我们看到，它完全可靠地工作，然后我们创建这些解释，就像软件一样，我们有抽象层的分离，每一层抽象都可以通过参考其下一层来解释，所以我们有这些我们称之为生物学、化学的东西，我们称之为生物学，每一个都试图在下面的基础上提供一个更高的抽象层。所以这就是我的——是的。听众：[听不清] 超越那个界限，正如你所暗示的？SCOTT AARONSON：嗯，我的意思是，量子计算改变了自然在最低层次上使用的计算的底层模型。是的，这就是它有趣的原因。CHINMAY NIRKHE：那么，让我们感谢 Scott Aaronson。 [掌声]