作者：Andy Matuschak 和 Michael Nielsen

编译：Florence Wong – AICUG

本文系AICUG翻译原创，如需转载请联系（微信号：834436689）以获得授权

这是海外非常优秀的量子计算教程，我们会陆续更新，每一篇更新后的链接都将附在该文章后。

如果人类曾经和外星人智慧取得联系，这些外星人会拥有计算机吗？在科幻小说中，外星计算机很普遍。如果这是正确的，则意味着外星人可以通过某种方式独立于人类来发现计算机。毕竟，如果外星人已经独立发明可口可乐，Pokemon或哈利·波特书籍，我们会感到非常惊讶。如果外星人拥有计算机，那是因为计算机是人类和外来文明自然都会想到的问题的答案。

在地球上，计算机的主要创始人是英国数学家艾伦·图灵。在1936年，图灵发表的论文《论可计算数及其在判定问题上的应用》中，图灵并没有尝试发明一个聪明的小工具，或创建一个行业。相反，他是在抨击德国数学家戴维·希尔伯特（David Hilbert）在1928年提出的关于数学性质的问题。这听起来很深刻，但是值得了解希尔伯特和图灵的思想要旨，因为它阐明了计算机的来源以及计算机的未来。

在整个职业生涯中，希尔伯特（Hilbert）对数学知识的终极局限感兴趣：人类对数学有什么了解？从原理上讲，数学中哪些部分（如果有的话）是人类永远不知道的？粗略地说，希尔伯特（Hilbert）在1928年提出的问题是，是否存在一个数学家可以遵循的通用算法，该算法可以让他们可以知道，是否任何给定的数学陈述可证明。希尔伯特的希望算法有点像，用纸和铅笔去计算相乘两个数字。除了从两个数字开始之外，您将从一个数学猜想开始，在经过算法的步骤之后，您将知道该猜想是否可以证明。该算法可能太耗时，无法在实践中使用，但是，如果存在这样的算法，则至少在原理上，会有一种数学可以理解的感觉。

1928年，算法的概念非常模糊。那时候，算法通常是由人类使用纸和铅笔执行的，就像刚才提到的乘法算法或长除法算法一样。攻打希尔伯特（Hilbert）的问题，迫使图灵（Turing）精确地定义了算法的含义。为此，图灵描述了我们现在所说的图灵机：图灵认为，它是一个可以执行任何算法的通用可编程计算设备。

今天，我们已经习惯了可以对计算机进行编程，以执行许多不同操作的想法。然而，在图灵时代，通用可编程计算机的构想非常了不起。 图灵解释说，只要提供正确的程序，单个固定设备就可以模仿任何算法过程。这是想象力的惊人飞跃，也是现代计算的基础。

为了解释他的机器可以模仿任何算法过程，图灵考虑了，一个人类数学家在执行算法时可以执行哪些操作。对于每次这样的操作，他都不得不解释，他的机器总是可以做同样的事情。他的论点太长了，无法在此处完整再现，但是看到图灵的推理风格，是既有趣又有启发性：

“通常通过在纸上书写某些符号来完成计算。我们可以假设，本文像儿童的算术书一样分成正方形。在基本算术中，有时会使用纸张的二维特征。但是，这种使用总是可以避免的，我认为可以认同纸张的二维特性对计算不是必需的。然后，我假设计算是在一维纸上进行的，即在分成正方形的胶带上进行。 …在任何时候，计算机的行为[图灵指的是执行算法的人，而不是机器！]取决于他观察的符号以及当时的“心态”。我们可以假设，计算机在某一时刻可以观察到的符号数量或正方形的数量，有一个绑定的B。如果他希望观察更多，则必须使用连续观察。我们还将假设，需要考虑的心态数量是有限的。“

显然，这是一个非正式且启发式的论点！调用儿童的算术书，或某人的心理状态并不是严格的，无懈可击的论据。但是，图灵的论点足够令人信服，以至于后来的数学家和科学家大多愿意接受它。图灵的机器成为黄金标准：算法是我们可以在图灵机器上执行的工作。从那时起，计算机技术蓬勃发展，基于图灵模型的计算机销量已达数十亿。

尽管如此，对图灵的分析还是有些不满意。他可能在非正式推理中，错过了有关什么是算法的信息吗？ 1985年，英国物理学家戴维·德意志（David Deutsch）提出了一种更深层次的方法，来解决定义算法的含义。他指出，每一个算法都是由物理系统执行的，无论是具有纸笔的数学家，算盘等机械系统还是现代计算机。 Deutsch随后考虑了以下问题（为了便于阅读，我略作了表述）：

是否有一个（单一）通用计算设备，可以有效地模拟任何其他物理系统？

如果有这样的设备，则可以使用它执行任何算法，因为算法必须在某种物理系统上执行。因此，该设备将成为真正的通用计算机。更重要的是，Deutsch指出，您不需要像图灵那样，依靠非正式的启发式论据，来证明您的算法概念是正确的。您可以使用物理定律来证明您的设备具有通用性。

因此，让我们回到我们的开放性问题：外星人会拥有计算机吗？上面的Deutsch问题是关于宇宙本质的一个简单的基本问题。 Deutsch的外星人同行或许可以合理地思考这种问题。然后，作为他们的部分的外来文明，将不可避免地被引导发明计算机。

从这个意义上讲，计算机不仅仅是人类的发明。它们是宇宙的基本特征，是关于宇宙如何运作的一个简单而深刻的问题的答案。而且，它们很可能已经被许多外星智慧一再发现。

这个故事有一个问题。Deutsch是物理学家，具有量子力学背景。在试图回答他的问题时，Deutsch发现，基于图灵模型的普通日常计算机，在模拟量子力学系统时会遇到很多麻烦。诸如Yu Manin和Richard Feynman之类的研究人员此前已经观察到了这一点：即计算机在进行此类模拟时，似乎异常缓慢且效率低下。为了肯定地回答他的问题，Deutsch“被迫“发明了一种新型的计算系统，即量子计算机。那些量子计算机可以完成传统计算机可以做的所有事情，但也能够有效地模拟量子力学过程。因此，可以说他，们是比传统计算机更自然的计算模型。如果我们遇到外星人，我敢打赌，他们将使用量子计算机（或者，也许会有量子计算的大脑）。毕竟，外星人的技术水平可能会比当前人类文明高得多。因此，他们将使用的计算机，是适用于任何技术先进社会的。

本文介绍了量子计算机的工作原理。这不是调查论文，也不是基于类推的普及。我们将深入介绍，以便您了解量子计算的细节。在此过程中，我们还将学习量子力学的基本原理，因为他们是理解量子计算所必需的。

学习此材料具有挑战性。量子计算和量子力学是著名的“硬”学科，通常被认为是神秘而令人生畏的。如果这是一篇常规文章，那么您很可能会很快忘记该材料。但是，论文也是论文形式的实验。正如我将在下面详细解释的那样，本文结合了新的用户界面思想，可帮助您记住所读内容。这听起来可能令人惊讶，但是使用了认知科学中经过充分验证的想法，即间隔重复测试。有关其工作原理的更多详细信息，请参见下文。结果是，任何有好奇心和决心的人都可以长期深入地了解量子计算。

也就是说，您需要一些数学背景才能理解本文。我假设您对复数和线性代数（向量，矩阵等）都有基础。我还将假设您对常规计算机中使用的逻辑门话题感到舒服，例如和，与，或，非等门。

如果您没有数学背景，则需要掌握它。具体操作方式取决于您先前的经验和学习偏好-没有一种万能的方法，您需要自己弄清楚。但是，您可能会发现有两个有用的资源：

（1）3Blue1Brown关于线性代数的YouTube视频系列： https://www.youtube.com/playlist?list=PLZHQObOWTQDPD3MizzM2xVFitgF8hE_ab；

（2）吉尔·斯特朗（Gil Strang）更深入的线性代数讲座：https://ocw.mit.edu/courses/mathematics/18-06-linear-algebra-spring-2010/video-lectures/

试试看，如果发现有帮助，请继续。如果没有，请探索其他资源。

试图避免使用这种数学似乎很诱人。如果您在网上四处浏览，则会有很多关于量子计算的引人注目的介绍，他们避免了数学运算。例如，YouTube上有许多非常漂亮的视频。观看他们可能很有趣，更好的可以给您一些类比，以帮助理解量子计算。但是他们有些无聊。坦率地说，如果他们不解释实际的基本数学模型，那么您可能会花费数年的时间观看和重新观看此类视频，而您将永远无法真正获得它。这就像和一群篮球运动员闲逛，听他们谈论篮球。您可能会喜欢它，并且感觉好像您正在学习篮球。但是，除非您实际上花费大量时间在比赛上，否则您永远不会学习打篮球。要了解量子计算，您绝对必须精通数学模型。

本教程列表（陆续更新）：