新书上市｜当我们讨论“量子计算”时我们在讨论什么？

请收好，这是一份《量子计算公开课》阅读指南。

量子力学是对概率法则的精彩推广：基于2-范数而不是1-范数，基于复数而不是非负实数。它可以完全独立于物理学应用而被研究（并且事实上，这样做会为之后学习物理学应用提供一个很好的起点）。这种推广的概率理论自然地指向了一个新的计算模型——量子计算模型。它挑战了人们一直以来关于计算的先验性的想法，哪怕和物理学没有联系，它也足以使理论计算机科学家们为各自的目标埋头苦干。

总之，一个世纪前，人们为了解决物理的技术性问题而发明了量子力学，但是今天的量子力学可以从一个完全不同的角度卓有成效地被解释：作为思想史的一部分，在数学、逻辑、计算和哲学中探求可知的极限。

在《量子计算公开课》本书中，我将努力实践上述观点，并选择一段不慌不忙、弯弯绕绕的路径做到这一点。

量子计算理论先锋 

 2020年ACM计算奖得主

斯科特·阿伦森的经典之作

在第 1 章，我尽可能地以我所能靠近的“开端”——古希腊哲学家德谟克利特——开始。德谟克利特幸存下来的一些理论片段——其中包括，推测所有的自然现象都源于几种微小“原子”之间的复杂相互作用，它们在几乎空着的空间中尽情呼啸——比其他任何古代思想都更接近现代科学的世界观（当然比柏拉图或亚里士多德的任何思想都更接近）。

然而，还没等到德谟克利特确切地阐述原子论的假设，他就不安地发现，这个假设想要将他可能原本想首先解释的感官经验“整个吞下”。那些东西怎么可能被简化成原子的运动呢？德谟克利特将这个困境以理性和感觉之间的对话的形式表现了出来。

理性：“感觉上存在的是浓郁的芬芳、深深的痛苦、缤纷的色彩，但实际上存在的是原子和虚空。”

感觉：“愚蠢的理性，你是想要推翻我吗？不要忘了，你只有从我这里才能得到确证！” 

这两行对话将成为整本书的某种试金石。我的一个主题将是，在理性与感觉2300 年之久的辩论中，量子力学看上去如何给了它们双方意想不到的新武器，同时（我认为）仍然没有产生明显的胜者。

在第 2 章和第 3 章中，我继续讨论了我们所拥有的不明显依赖于物理世界“残酷事实”的最深层次的知识——数学。即使在那两章中，我内心里（并且我怀疑，还有许多其他计算机科学家内心里）还是对那些明显有物理学印记的数学持有怀疑，比如偏微分方程、微分几何、李群，或其他任何“太连续”的东西。因此，我转而开始用一些到目前为止发现的最为“免物理”的数学：集合论、逻辑和可计算性。

我讨论了康托尔、弗雷格、哥德尔、图灵、邱奇和科恩的伟大发现，这有助于了解数学推理本身的轮廓。并且，在说明为什么所有的数学都不能被约化为一个固定的“机械过程”的课程里，这还展示了它们中有多少可能被约化，并从根本上阐明了我们说“机械过程”的意思。

在第 4 章中，既然无法抗拒，我也就开始涉足人脑是否也被“固定的机械过程”所掌控这一古老的辩论。我尽量公正地给出了不同的立场（但无疑也暴露了我自己的偏见）。

第 5 章介绍了可计算性理论现代版的“表亲”——计算复杂性理论，它在这本书的剩余部分中起着核心的作用。尤其是我试图说明，计算复杂性如何可以让我们系统地考虑关于知识范围的“深刻的哲学之谜”，并将其转换为“仅仅是”极度困难的、尚未解决的数学问题，而且抓住大部分我们想知道的东西！关于这种转换，没有比 P 与 NP 问题更好的例子了，于是，我在第 6 章讨论了它们。然后，作为量子计算的热身，第 7 章探讨了“经典”随机性在计算复杂性和生活其他部分中的多种用途。然后，第 8 章介绍了从 20 世纪 70 年代起，计算复杂性的想法如何被应用于对密码学理论和实践的革命。

2021年4月15日

国际计算机协会（ACM）宣布

斯科特·阿伦森

荣获2021年ACM计算奖

这一切只是为了给本书最“臭名昭著”的部分——第 9 章——搭建舞台。它介绍了我对于量子力学是“推广了的概率论”的观点。然后，第 10 章介绍了我自己领域的基础知识——量子计算理论，它可以被简单地定义为量子力学与计算复杂性理论的合并。作为坚持读完这么多技术材料的“回报”，在第 11 章里，我仔细检查了罗杰·彭罗斯爵士著名的想法，即大脑不仅是量子计算机，还是量子引力计算机，能够解决图灵不可计算问题。而这，或类似的东西，可以利用哥德尔不完备性定理来证明。指出这些想法的问题是小菜一碟，并且我也这样做了，但我发现更有趣的是去问，彭罗斯的猜测中是否可能有真理的金子？

第 12 章面对的是我所认为的量子力学的核心概念问题：不是说未来是不确定的（谁在乎呢？），而是说，过去也是不确定的！我考察了两种对于这个问题截然不同的反应：第一种是在物理学家中受欢迎的，即诉诸“退相干”，以及由热力学第二定律提供的“有效时间箭头”；第二种是“隐变量理论”，如玻姆机制。虽然隐变量理论被拒绝了，但我发现它们会指向一些非常有趣的数学问题。

该书的剩余部分是对早期的观点的应用，针对的是数学、计算机科学、哲学和物理学中各种大的、令人振奋或有争议的问题。后面的各章与前面的相比，更多地讨论了更新的研究——主要在量子信息和计算复杂性方面，但也有一点儿量子引力和宇宙学——这都是令我震惊的研究，且在我看来为那些“大问题”的解决提供了一点儿希望。因此，我希望后面各章的内容能比前面各章先过时！虽然有一点儿轻微的相关性，但后面各章基本可以按照任何顺序去读。

第 13 章讨论了数学证明的新概念（包括概率证明和零知识证明），然后利用这些概念来理解隐变量理论的计算复杂性。

第 14 章讨论的是量子态“大小”的问题——它们能否编码指数多的经典信息？然后，我把这个问题一方面与关于量子力学诠释的辩论联系了起来，另一方面与最近对于量子证明和建议的复杂性理论研究联系了起来。

第 15 章探讨了量子计算“怀疑论者”的论点：他们不仅认为建造一个实用的量子计算机是困难的（每个人都同意这点），而且认为由于某种根本的原因，这永远都是不可能实现的。

第 16 章探讨了休谟的归纳问题，并将其作为起点讨论了计算学习理论，以及最近关于量子态可学习性的工作。

第 17 章讨论了我们对经典和量子交互证明系统（即 IP=PSPACE 以及 QIP=PSPACE定理）理解的一些突破，但最大的兴趣点在于那些已经导致了非相对化电路下界的突破——因此，这可能会给 P 与 NP 问题带来一些曙光。

第 18 章考察了著名的人择原理和“末日论”。讨论以高度的哲学性开始（当然得这样），但最终迂回到对后续选择量子计算以及 PostBQP=PP 定理的讨论。

第 19 章由对纽科姆悖论和自由意志的讨论，通向康威 – 科亨的“自由意志定理”，以及贝尔不等式在生成“爱因斯坦认证的随机数”时所起的作用。

第 20 章讨论了时间旅行：用一种现在已经熟悉的模式，从一个广泛的哲学讨论开始，以一个证明结束，该证明是说，拥有封闭类时曲线的经典或量子计算机产生的正是 PSPACE 的计算能力（它所依托的假设对那些有趣的反对意见是开放的，我会对此详细讨论）。

第 21 章讨论了宇宙学、暗能量、贝肯斯坦界以及全息原理。但是，并不奇怪的是，这些讨论都着眼于这一切对于“计算的极限”意味着什么。比如，一个人可以储存或者搜索多少比特，以及一个人可以对这些比特执行多少操作，而无须使用创造一个黑洞那么大的能量？

第 22 章是“甜点”：它是基于这门课的最后一节而写的，其中学生可以随便问我任何问题，看我如何挣扎着回应。讨论的主题包括：量子力学垮台的可能性、黑洞与“模糊球”、计算复杂性理论中谕示结果的相关性、NP 完全问题和创造性、“超量子”的关联、随机算法的去随机化、科学、宗教以及理性的本质，以及为什么计算机科学不是物理学系的一个分支。

最后说几句。有一件事情，你不会在这本书中找到——对于量子计算“实用性”的广泛讨论：无论是物理实现，还是纠错，或者肖尔算法、格罗弗算法以及其他基本量子算法的细节。造成这一疏忽的原因之一是以下情况附带的：这本书是基于我在滑铁卢大学量子计算研究所的讲座而写的，那些学生已经在其他课上学习了所有关于那些方面的知识。第二个原因是，这些知识在许多其他的书和网上课堂笔记（包括我自己的一些）中都有 ，我认为没有必要推倒重来。但第三个原因是，坦率地说，建立一种新型计算机的技术前景尽管非常令人振奋，但那不是我进入量子计算领域的根本原因。（嘘，请不要把我说的话告诉任何资助机构的董事。）

需要明确的是，我认为我在有生之年看到实用量子计算机是完全有可能的（当然，也有可能不会看到）。如果我们确实有了可扩展的、通用的量子计算机，那么它们几乎肯定会找到真正的用武之地（破译密码甚至都不算）：我认为主要是对于像量子模拟这样的专业研究，不过退一步，也包括解决组合优化问题。一方面，如果那真的发生了，那么我希望我会跟世上所有的人一样兴奋——当然，如果我做过的工作可以在新的世界里找到应用的话，我会乐疯了的。另一方面，如果有人明天给我一个实用的量子计算机，那么就我个人而言，我承认我想不出自己会拿它来做什么：我只能想到其他人可以用它来做的事情！

部分出于这个原因，如果可扩展的量子计算被证明是不可能的，那么这将让我比听到它被证明为可能时的感觉兴奋一千倍以上。因为这样的失败将意味着我们对量子力学本身理解的错误和不完备：一场物理学革命！不过作为一个先天的悲观主义者，我的猜测是，大自然不会对我们如此好心，可扩展的量子计算终将成为可能。

总之，你可以说，比起我们可以对量子计算机做的事情，我待在这个领域更多的原因在于量子计算机出现的可能性为我们对世界的理解已经做的事情。要么，实用的量子计算机可以被造出来，可知的极限不是我们所认为的那样；要么，它们不能被造出来，量子力学原理本身需要被修订；要么，就是有一个迄今还难以想象的方法来利用现有计算机有效地模拟量子力学。所有这三种可能性听起来都像是狂人猜想，但其中至少有一个是对的！所以不管结果是什么，有哪句话比这句“这真有趣”更贴切（逆向抄袭某电视广告）？

本文节选自《量子计算公开课》引言部分，应编辑邀约，作者在中文版出版前做了内容修订和增补，详情了解请参阅更多书籍内容。

购买直达

互动福利

• 关于“量子计算”你有哪些想知道的问题？

• 欢迎大家踊跃提问，您的问题不仅有机会得到作者本人的正面回答，还将获得新书《量子计算公开课》一本（7月6日抽取2位幸运鹅）！
  

推荐阅读

喜欢这篇文章？点个“在看”吧~▼