为非常好奇的人提供量子计算

如果人类与外星智能接触，这些外星人会拥有计算机吗？在科幻小说中，外星计算机司空见惯。如果这是正确的，这意味着外星人有某种方法可以独立于人类发现计算机。毕竟，如果外星人独立发明了可口可乐、精灵宝可梦或哈利波特系列书籍，我们会非常惊讶的。如果外星人有计算机，那是因为计算机是人类和外星文明自然产生的问题的答案。

在地球上，计算机的主要发明者是英国数学家艾伦·图灵。在他1936年发表的论文“论可计算的数字”(on Computable Numbers，With an Application to the EntscheidungsProblem，1936)中，图灵并没有试图发明一个聪明的小玩意儿或创建一个产业。相反，他是在攻击德国数学家大卫·希尔伯特(David Hilbert)在1928年提出的一个关于数学本质的问题。这听起来很深奥，但值得理解希尔伯特和图灵思想的主旨，因为它阐明了计算机从哪里来，以及计算机未来会变成什么样子。

在他的职业生涯中，希尔伯特对数学知识的终极极限感兴趣：原则上，人类可以知道什么关于数学，以及数学中哪些部分(如果有的话)是人类永远不知道的？粗略地说，希尔伯特1928年的问题是，是否存在一个数学家可以遵循的通用算法，让他们计算出任何给定的数学陈述是否是可证明的。希尔伯特希望的算法会有点像纸笔相乘两个数字的算法。除了不是从两个数字开始，而是从一个数学猜想开始，在经历了算法的步骤之后，你就会知道这个猜想是否可以证明。该算法可能太耗时而不能在实践中使用，但如果存在这样的算法，那么至少在原则上，数学在某种意义上是可知的。

1928年，算法的概念还相当模糊。在这之前，算法通常是由人用纸和笔来实现的，就像刚才提到的乘法算法或长除法算法。攻击希尔伯特的问题迫使图灵精确地解释了算法的含义。为了做到这一点，图灵描述了我们现在所说的图灵机：一种单一的、通用的可编程计算设备，图灵认为它可以执行任何算法。

今天，我们已经习惯了这样一种想法，即计算机可以被编程来做许多不同的事情。然而，在图灵的时代，通用可编程计算机的想法是引人注目的。图灵认为，只要提供了正确的程序，一个单一的固定设备就可以模拟任何算法过程。这是一次令人惊叹的想象力飞跃，也是现代计算的基础。

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

计算通常是通过在纸上写下某些符号来完成的。我们可以假设这张纸像孩子的算术书一样被分成正方形。在初等算术中，有时会用到纸的二维字符。但这样的使用总是可以避免的，我想人们会同意纸的二维特性不是计算的本质。我假设计算是在一维的纸上进行的，也就是说，是在分成正方形的磁带上进行的。…。计算机的行为[图灵指的是执行算法的人，而不是机器！]。任何时刻都是由他正在观察的符号和他那一刻的“精神状态”决定的。我们可以假设，计算机一次可以观察到的符号或正方形的数量有一个界限B、B。如果他想观察更多，他必须使用连续观察。我们还假设需要考虑的精神状态的数量是有限的。

显然，这是一个非正式的、启发式的争论！引用孩子的算术书或某人的精神状态不是一个严谨的、防弹的论点的素材。但图灵的论点足够令人信服，以至于后来的数学家和科学家在很大程度上都愿意接受它。图灵的机器成为了黄金标准：算法就是我们可以在图灵机器上执行的东西。从那时起，计算已经发展成为一个行业，基于图灵模型的计算机已经售出数十亿台。

尽管如此，图灵的分析还是有一些令人不安的地方。在他关于算法是什么的非正式推理中，他可能遗漏了什么？1985年，英国物理学家大卫·多伊奇(David Deutsch)提出了一种更深层次的方法来定义算法大卫·多伊奇(David Deutsch)所说的“量子理论、丘奇-图灵原理和万能量子计算机”(1985)。多伊奇指出，每一种算法都是由物理系统执行的，无论是纸和笔的数学家，还是算盘等机械系统，还是现代计算机。Deutsch然后考虑了以下问题(我稍微修改了一下措辞，以便于阅读)：

是否有(单一的)通用计算设备可以有效地模拟任何其他物理系统？

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

那么让我们回到我们的开场问题：外星人会有计算机吗？德奇的上述问题是一个关于宇宙本质的简单而根本的问题。这是Deutsch的外星人同行们可能会信以为真地思考的问题。他们所属的外星文明将被无情地引导去发明计算机。

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

这个故事有个问题。多伊奇是一位具有量子力学背景的物理学家。在试图回答他的问题时，Deutsch观察到，基于图灵模型的普通日常计算机在模拟诸如Yu Manin和Richard Feynman等研究人员之前观察到的量子力学系统方面有很多困难，因此他们对基于量子力学的计算机进行了猜测。具体地说，他们在做这样的模拟时似乎非常慢，效率也很低。为了肯定地回答他的问题，多伊奇被迫发明了一种新型的计算系统-量子计算机。这些量子计算机可以做传统计算机所能做的一切，但也能够有效地模拟量子力学过程。因此，它们可以说是一种比传统计算机更自然的计算模型。如果我们遇到外星人，我打赌他们会使用量子计算机(或者，也许会有量子计算大脑)。毕竟，外星人很可能会比现在的人类文明在技术上先进得多。因此，他们将使用任何技术先进的社会自然存在的计算机。

这篇文章解释了量子计算机是如何工作的。这不是一篇调查文章，也不是一篇基于手势比喻的通俗文章。我们将深入挖掘，以便您了解量子计算的细节。在此过程中，我们还将学习量子力学的基本原理，因为这些是理解量子计算所必需的。

学习这些材料很有挑战性。量子计算和量子力学是出了名的“难”学科，通常以神秘和令人望而生畏的形式出现。如果这是一篇传统的文章，你很可能很快就会忘记材料。但随笔也是随笔形式的一次实验。正如我将在下面详细解释的那样，这篇文章结合了新的用户界面理念来帮助您记住所读的内容。这听起来可能令人惊讶，但使用了认知科学中一个经过充分验证的想法，即间隔重复测试。下面将详细介绍它的工作原理。其结果是，任何有好奇心和决心的人都可以深入和长期地了解量子计算。

也就是说，你需要一些数学背景才能理解这篇文章。我假设您熟悉复数和线性代数-向量、矩阵等。我还假设您熟悉传统计算机中使用的逻辑门--AND、OR、NOT等逻辑门。

如果你没有那样的数学背景，你就需要掌握它。如何做到这一点取决于你以前的经验和学习偏好-没有万能的方法，你需要自己弄清楚。但是有两个资源可能会对你有帮助：(1)3Blue1Brown关于线性代数的YouTube系列视频；(2)吉尔·斯特朗(Gil Strang)更深入的线性代数讲座。试一试，如果你觉得它们有帮助，那就继续做下去。如果没有，请浏览其他资源。

试图回避这个数学问题似乎很有诱惑力。如果你环顾网络，有很多关于量子计算的华而不实的介绍，它们避开了数学。例如，YouTube上有很多相当圆滑的视频。它们看起来很有趣，更好的可以给你一些类比，帮助你理解量子计算。但是他们有一种空虚。坦率地说，如果他们不解释实际的基本数学模型，那么你可能要花几年时间反复观看这样的视频，而且你永远不会真正理解它。这就像和一群篮球运动员一起闲逛，听他们谈论篮球。你可能会喜欢它，感觉就像在学习篮球。但是，除非你真的花了很多时间打球，否则你永远学不会打篮球。要理解量子计算，你绝对必须精通数学模型。

如你所知，在普通的日常计算机中，信息的基本单位是位。这是一个熟悉但令人惊讶的事实，那些计算机做的所有事情都可以分解成0 0 0和11 1的模式，以及0 0 0和11 1的简单操作。对我来说，这一点在玩电子游戏时感受最强烈。当我突然意识到屏幕上可见的想象世界背后惊人的复杂性时，我会享受玩游戏的乐趣：

每一幅这样的图像背后都有数百万像素，用数千万比特来描述。当我移动游戏控制器时，我有效地指挥了一个数千万人的管弦乐队，通过许多层中介想法组织起来，以这种方式创造乐趣，有时甚至是纯粹的愉悦。

我已经把比特描述为一个抽象的实体，它的状态是00或111。但是在现实世界中，而不是在数学世界中，我们必须找到某种方法将我们的比特存储在物理系统中。这可以通过许多不同的方式来实现。在计算机的存储芯片中，位极有可能以微小电荷的形式存储在纳米级的电容器(即小电荷库)上，恰好位于芯片表面的上方。老式硬盘采取了不同的方法，使用微小的磁铁来存储比特。此外，不同类型的存储器使用不同类型的电容器；不同类型的硬盘使用不同的磁化方法。

大多数情况下，当您使用计算机时，您不会注意到这些不同之处。计算机设计人员非常非常努力地使位的物理实例化的细节不仅对用户是不可见的，而且(通常)甚至对程序员也是不可见的。许多程序员从不考虑位是存储在快速微处理器缓存中、存储在动态RAM芯片中，还是存储在某种类型的虚拟内存中(比如存储在硬盘上)。也有例外-从事高性能程序的程序员有时确实会考虑这些事情，以使他们的程序尽可能快。但对于许多程序员来说，如何存储位并不重要。相反，他们可以用纯粹抽象的术语认为该位的状态不是0 0 0就是1 1 1。

以类似于传统计算机由比特组成的方式，量子计算机由量子比特或量子比特组成。就像比特一样，量子比特也有状态。但是，比特的状态是一个数字(000或1111)，而量子比特的状态是一个矢量。更具体地说，量子比特的状态是二维矢量空间中的矢量。此向量空间称为状态空间。例如，下面是一个量子比特的可能状态：

这可能听起来很奇怪！量子位的状态是二维矢量是什么意思？我们将缓慢而渐进地揭开答案。当你想“啊哈，这就是量子比特！”的时候，你不会有任何顿悟。相反，你将逐渐在你的理解中建立起许多细节，直到你对使用量子比特、量子计算，以及更广泛地使用量子力学感到满意。

量子比特与比特有一种相似之处：我们完全没有说过量子比特实际上是什么，从物理上讲是什么。也许量子位的状态正以某种方式存储在电子、光子或原子上。或者它可能被储存在某种更陌生的东西中，也许储存在某种奇异的粒子或物质状态中，甚至更远离我们的日常经验。

就我们在本文中的目的而言，这些都无关紧要，就像您应该担心计算机RAM中存储比特的是哪种类型的电容器一样。你应该去掉的是：(A)量子比特有一个状态；(B)与比特非常相似，那个状态是一个抽象的数学对象；但是(C)比特的抽象状态是一个数字，0 0 0或1 1 1，而量子比特的状态是一个2 2 2维向量；(D)我们称状态居住在状态空间中的2 2 2维向量空间。

好的，让我们复习一下我们所学的内容。请允许我回答下面的问题。只需要几秒钟-对于每个问题，考虑一下你认为答案是什么，单击以显示实际答案，然后标记你是否记得。如果你能回想起来，那就太好了。如果没有，也没问题，只需记下正确答案，然后继续。

也许你刚才对这三个问题的回答都没记错。即使是这样，你能在一周内记住答案吗？一年之内？人类的记忆是容易出错的。如果你的记忆力和我的一样，你可能会模糊地记得一周后的答案：“一个量子比特的状态是什么，哦，是的，它是一个矢量！”但你在一个月或一年内记住的机会很低。如果你忘记了这些事情，你就不会对量子计算有任何持久的理解。

我们如何才能确保您不会在几分钟或几个小时内记住这些答案，而是在未来很长一段时间内，甚至是永久地记住这些答案呢？

一种方法是让你变得非常高尚，不断地回来，重新审视这些材料，直到它牢牢地锁在你的记忆中。如果你是这样一个善良的人，恭喜你！但对于我们其他99%的人来说，这是不太可能的。我们能做什么？

一个多世纪以来，认知科学家一直在研究人类记忆。他们已经想出了一些简单的策略，可以确保你永远记住一些事情。最重要的一个想法是重新测试你的知识，延长测试之间的时间间隔。

举个例子，考虑一下上面的问题：“一个量子比特的状态空间有多少维？”如果你答对了，你最好在5天内再做一次测试。如果你再答对的话，两周后你还会再做一次测试。然后在那之后的一个月。然后两个月。以此类推，日程表逐渐扩大。如果你在其中一次考试中答错了题，时间表就会缩水，所以你可以重新学习答案。换句话说，提问的日程安排如下所示：

事实证明，这样一个扩展的时间表是保留信息的最佳方式。每次重新测试，你的大脑都会将更好的答案巩固到长期记忆中，直到最终它是永久性的。

间隔重复测试是一个简单的想法，但却有深远的影响。首先，总体时间不会太长。由于考试日程不断扩大，通常只需要几分钟的总复习时间就能记住几年或几十年的问题答案。我不会通过数学计算来证明这一点，但你可以在其他地方看到它是可行的。

其次，间隔重复测试可以保证您记住问题的答案。在很大程度上，我们的记忆是以一种随意的方式工作的。我们读到或听到一些有趣的东西，希望将来能记住它。间隔重复测试使记忆成为一种选择。

这听起来不错，但你也需要非常自律地重新测试自己。幸运的是，计算机可以为你处理所有的日程安排。因此，这篇文章不仅仅是一篇传统的文章，它也是一种新的媒介，一种整合了间隔重复测试的助记媒介。媒介本身使记忆成为一种选择。

这是要付出一些代价的：您将致力于未来的审查。但想想这会给你带来什么。这篇文章可能要花你一两个小时才能读完。在一篇传统的作文中，你会忘记在接下来的几周里学到的大部分东西，也许会保留一些想法。但是，随着间隔重复测试内置到媒介中，少量额外的时间承诺意味着你将记住这篇文章的所有核心材料。这样做并不困难，它会比最初的阅读容易。此外，你还可以阅读建立在这些想法基础上的其他材料；它将打开一个完整的世界。

这种间隔重复的方法就是为什么这些问题只需要几秒钟的时间来阅读和回答。它们不是教科书风格的复杂练习。相反，这些问题有一个不同的观点：每个问题做出的承诺是，你将永远记住答案。这是永久性地改变你的想法。

因此，我邀请您通过在下面登录来设置帐户。如果你这样做了，你对论文中每个问题的复习时间表都会被跟踪，你每天(或几天)都会收到提醒，其中包含一个链接，可以把你带到一个在线复习环节。那个复习环节并不是完整的论文--相反，它看起来就像你上面回答的问题一样，而是包含了所有到期的问题，所以你可以快速地浏览一下。承诺的时间通常是每天几分钟-稍早一点，当问题需要频繁重新测试时，但很快就会减少。你可以边喝咖啡边用手机学习，或者排队，或者散步，或者在路上。对这一小时间承诺的回报是极大地提高了基础量子计算和量子力学的流畅性。而这种理解将被内化，成为你是谁的一部分，保留几年而不是几天。

为了信守这一承诺，我们正在跟踪您每个问题的审核计划。

..