量子计算是量子物理与计算机科学的完美融合，将20世纪物理学中那些令人惊叹的观点融入一种全新的计算思维方式中。本书由数学家Bernhardt撰写，用简明的数学语言来描述量子世界，只要求读者具备高中数学知识。书中从量子计算的基本单位——量子比特开始，然后讨论量子比特测量、量子纠缠和量子密码学。之后回顾了经典计算中的标准主题——比特、门和逻辑，并描述了Edward Fredkin独创的台球计算机。最后定义了量子门，考虑量子算法的速度，以及量子计算对未来生活的影响。本书涵盖量子计算方方面面的基础知识，适合所有感兴趣的初学者阅读。

无

本书的目的是介绍量子计算，使得任何一个熟悉高中数学知识和愿意投入一点时间的人都能理解。我们将会学习量子比特、量子纠缠、量子隐形传态和量子算法，以及其他量子相关的主题。我们的目标不是对这些概念给出一些不明确的想法，而是使它们清晰明了。
量子计算经常出现在新闻中：中国通过隐形传态将一个量子比特从地球传送到一颗卫星上；Shor算法使我们目前的加密方法面临风险；量子密钥分发将使加密再次变得安全；Grover算法将加速数据检索。但这一切究竟意味着什么？这一切是如何运作的？所有这些都将在本书中得到解释。
不使用数学能做到这一点吗？如果我们想真正了解发生了什么，那就需要使用数学。量子力学的基本思想往往与直觉相悖。试图用文字来描述这些是行不通的，因为我们在日常生活中对它们没有经验。更糟糕的是，文字描述常常给人留下这样的印象：我们貌似理解了一些东西，而实际上我们还没有理解。好消息是，我们并不需要引入太多的数学知识。作为一名数学家，我的职责是尽可能地简化数学（坚持绝对的本质）并给出基本的例子来说明它的用法与含义。也就是说，这本书可能包含你以前从未见过的数学概念，而且和所有的数学知识一样，新的概念一开始可能看起来很奇怪。重要的是不要忽略这些例子，而且要仔细阅读计算的每一步。
量子计算是量子物理与计算机科学的完美融合，将20世纪物理学中一些最令人惊叹的观点融入一种全新的计算思维方式中。量子计算的基本单位是量子比特。我们将看到什么是量子比特以及测量量子比特时会发生什么。一个经典比特要么是0，要么是1。如果是0，我们测量它，得到0；如果是1，我们测量它，得到1。在这两种情况下，比特都保持不变。量子比特的情况则完全不同。一个量子比特可能是无限多个状态中的某一个——0和1的叠加态，但是当我们测量它时，和经典情况一样，我们只得到两个值中的一个——0或1。测量会改变量子比特，一个简单的数学模型可以精确地描述这一切。
量子比特还可能纠缠。当我们对其中一个进行测量时，会影响另一个的状态。这是我们在日常生活中没有经历过的，但我们的数学模型完美地描述了这种现象。
这三个概念——叠加、测量和纠缠——是量子力学的核心。一旦我们理解了这些概念，就能知道如何在计算中使用它们。这正体现了人类的聪明才智。
数学家通常认为：证明是美丽的，而且经常包含意想不到的见解。对于我们将要讨论的许多主题，我有完全相同的看法。贝尔定理、量子隐形传态和超密编码，这些都是珍宝。纠错线路和Grover算法更是相当惊人的。
读完本书，你应该理解了量子计算的基本概念，并会看到一些巧妙而漂亮的结构。同时，你还将认识到量子计算和经典计算并不是两个截然不同的学科。量子计算是计算的一种更基本的形式——任何经典计算机可以计算的都可以在量子计算机上计算。计算的基本单位是量子比特，而不是比特。从本质上讲，计算就是量子计算。
最后应该强调的是，本书是关于量子计算理论的介绍。它是关于软件的，而不是硬件的。虽然我们在某些地方简要地提到了硬件，偶尔也会讨论如何在物理上纠缠量子比特，但这些只是题外话。这本书讲的不是如何构建量子计算机，而是如何使用量子计算机。
以下是对这本书内容的简要描述。
第1章。经典计算的基本单位是比特。比特可以表示为处于两种可能状态之一的任何东西，标准例子是一个可以打开或关闭的电子开关。量子计算的基本单位是量子比特。这可以用电子的自旋或光子的偏振来表示，但自旋和偏振的性质对我们来说并不像开关打开或关闭那样熟悉。
我们先来看看自旋的基本性质。从奥托·斯特恩（Otto Stern）和瓦尔特·格拉赫（Walther Gerlach）的经典实验开始，他们在实验中研究了银原子的磁性。我们可以看到在不同方向上测量自旋会发生什么。测量会影响量子比特的状态。我们还会解释与测量相关的随机性。
该章的结论是，类似于自旋的实验可以用偏振滤光片和自然光来完成。
第2章。量子计算基于线性代数。幸运的是，我们只需要一小部分概念。该章介绍我们需要的线性代数知识，并说明在后面的章节中如何使用这些知识。
我们将介绍向量、矩阵、如何计算向量的长度以及如何判断两个向量是否垂直。首先介绍向量的初等运算，然后介绍矩阵是如何同时进行这些运算的。
起初这些知识的作用并不明显，但确实有用。线性代数是量子计算的基础。由于本书其余部分使用了这里介绍的数学知识，因此需要仔细阅读。
第3章。该章介绍前两章是如何联系在一起的。线性代数给出了自旋或偏振的数学模型，这使我们能够定义量子比特，并准确地描述测量时会发生什么。
接下来书中举了几个在不同方向上测量量子比特的例子。最后介绍量子密码学，并描述BB84协议。
第4章。该章描述两个量子比特纠缠的含义。使用文字很难描述纠缠，与之相对，使用数学描述则很简单。张量积是一种新的数学思想，这是将单量子比特组合成多量子比特最简单的方法。
虽然纠缠的数学描述很直观，但我们在日常生活中并不会接触到。当测量一对纠缠量子比特中的某一个时，会影响另一个。阿尔伯特·爱因斯坦（Albert Einstenin）不喜欢这种现象，并称之为“幽灵般的超距作用”。我们会看几个例子。
该章最后指出，我们不能使用纠缠来实现超光速通信。
第5章。我们看看爱因斯坦对纠缠的担忧，以及隐变量理论能否保持定域实在性。我们研究贝尔不等式的数学原理——这是一个显著的结果，它提供了一种实验方法来确定爱因斯坦的论点是否正确。虽然贝尔当时认为爱因斯坦的观点可能会被证明是正确的，但是爱因斯坦的观点是错误的。
阿图尔·埃克特（Artur Ekert）意识到，测试贝尔不等式的装置还可以用于生成密码学中使用的安全密钥，并同时测试是否存在窃听者。在该章的最后，我们描述了这种加密协议。
第6章。该章从计算的标准主题开始：比特、门和逻辑。然后简要地介绍可逆计算和爱德华·弗雷德金（Edward Fredkin）的想法。我们证明了Fredkin门和Toffoli门都是通用的——你可以仅使用Fredkin门（或Toffoli门）来构建一台完整的计算机。最后介绍Fredkin的台球计算机。尽管这并不是书中余下内容真正需要的，但它十足的独创性值得介绍。
这台计算机是由相互碰撞的球和很多墙组成的。它使人联想起粒子之间的相互作用。这激发了理查德·费曼（Richard Feynman）对量子计算的兴趣，费曼写了该领域最早的一些论文。
第7章。该章开始学习使用量子电路进行量子计算，并定义了量子门。我们将看到量子门如何作用于量子比特，并意识到我们一直在使用这种思想。我们只需要改变观点：不再认为正交矩阵作用于测量装置，而是作用于量子比特。我们还证明了一些有关超密编码、量子隐形传态、克隆和纠错的惊人结果。
第8章。这可能是最具挑战性的一章。我们会看到一些量子算法，并看到它们与经典算法相比计算的速度有多快。为了讨论算法的速度，我们需要引入复杂性理论中的思想。我们定义了查询复杂性后，就开始学习三个量子算法，并证明它们的查询复杂性比经典算法的更低。
量子算法揭示了正在解决的问题的基本结构，它不仅仅是量子并行的思想——把输入放进所有可能状态的叠加中。该章介绍了最后一部分数学知识——矩阵的Kronecker积。实际上，这部分知识的困难源于我们正在以一种全新的方式进行计算，而我们并没有使用这些新思想来解决问题的经验。
第9章。最后一章着眼于量子计算将对生活带来的影响。我们首先简要描述两个重要的算法，一个是彼得·肖（Peter Shor）发明的，另一个是洛夫·格鲁弗（Lov Grover）发明的。
Shor算法提供了一种将大数分解为质因数的方法。这似乎并不重要，但我们的互联网安全依赖于分解质因数是个难以解决的问题。能够分解大质数的乘积威胁到我们当前计算机之间的安全交易。可能还要等一段时间，我们才能拥有足够强大的量子计算机来分解目前正在使用的这些大数，但这一威胁是真实存在的，而且它已经迫使我们思考如何重新设计计算机之间的安全对话方式。
Grover算法适用于特殊类型的数据检索。我们展示了它是如何在一个小样例中工作的，并说明了它是如何在一般情况下工作的。Grover算法和Shor算法都很重要，不仅因为它们可以解决问题，还因为它们引入了新思想。这些基本思想正在被纳入新一代算法中。
学习算法之后，我们转个话题，简要地看一下如何使用量子计算来模拟量子过程。究其本质，化学就是量子力学。经典计算化学的工作原理是利用量子力学方程，并用经典计算机进行模拟。这些模拟是近似的，忽略了细节。这种方法在很多情况下都很有效，但在某些情况下就行不通了。在这种情况下，你需要这些细节，而量子计算机应该能够提供。
该章还简要地介绍了实际机器的构建。这是一个快速发展的领域，第一批机器正在出售，“云”上甚至有一台人人都可以免费使用的机器。看来我们很快就会进入量子霸权时代。（我们会解释这意味着什么。）
本书的结论是，量子计算不是一种新型的计算，而是对计算本质的发现。

计算机/量子

【内封署名】邱道文 周旭 萧利刚 林一诺 朱祎康 译

最近，媒体正在热议即将到来的量子计算革命。这本薄薄的小书适合所有对这一迷人的领域感兴趣的读者，你不需要知道比高中数学更复杂的东西，就能轻松开启学习之旅，为了解量子计算的方方面面打下基础。
——Noson S. Yanofsky，布鲁克林学院教授，著有Quantum Computing for Computer Scientists和The Outer Limits of Reason

这本关于量子计算和量子信息的书既简洁又严谨，手把手地帮助初学者掌握量子隐形传态、贝尔不等式、Simon算法等知识。如果再有朋友向我请教，我一定要向他们推荐此书！
——Scott Aaronson，得克萨斯大学教授，量子信息中心主任，著有Quantum Computing Since Democritus

“比特会被量子比特所取代吗?”在技术的地平线上，量子计算机的身影若隐若现。这本书为我们打开了一扇门，漫步于量子效应的长廊，近距离领略量子计算的锋芒。
——Alexander Keewatin Dewdney，西安大略大学计算机科学系教授

诺贝尔奖获得者Feynman于20世纪80年代初指出使用经典计算机难以有效模拟量子系统的演化，从而提出量子计算机的想法——遵循量子力学规律调控量子信息单元进行计算。1985年，牛津大学的Deutsch建立了量子计算机的数学模型——量子图灵机，并提出量子Church-Turing命题：量子图灵机可以有效模拟现实中的任何计算模型。因此，量子计算不仅是新的计算模式，更是人类对计算更深刻的认识。
理论上已经证明量子计算至少不比经典计算弱。第一个量子算法是Deutsch提出的。之后Deutsch和Jozsa于1992年提出了比经典算法有指数优势的量子算法解决D-J问题，其后Simon提出了比经典算法有指数优势的量子算法——Simon算法。特别是，受Simon算法思想的启发，Shor于1994年提出了大数分解的多项式时间量子算法，而目前所知道的经典算法分解大数都是指数时间的。1996年Grover发现了与经典算法相比具有平方加速的量子搜索算法。可以说，Deutsch、Jozsa和Simon首先给出了量子算法的基本设计过程，Shor和Grover分别发现了量子算法设计的两个基本方法：量子相位估计和振幅放大方法。2009年，Harrow、Hassidim和Lloyd提出了具有指数加速的HHL量子算法求解线性方程组。量子计算的硬件设计也在不断发展，特别是最近谷歌设计的53个比特的量子芯片——Sycamore，进一步显示了量子计算的优势。这或许也是发展通用量子计算机给人类带来实际应用的曙光。
21世纪的今天，世界各国都意识到研究量子计算的重要性和可行性，从而纷纷发布各自的量子计算科技战略，争取实现有实际应用价值的“量子优势”。世界各高校也在大力发展量子计算学科。如今，量子计算已经成为大众应该了解和学习的知识之一。本书是Chris Bernhardt教授撰写的Quantum Computing For Everyone的中译本。原著共有九章，分别介绍了自旋，高等代数，自旋与量子比特，量子纠缠，Bell不等式，经典逻辑，门和电路，量子门和电路，量子算法以及量子计算的作用，一般理工科本科学生都能读懂。中译本继承了原著者的思想和内容，旨在向读者介绍量子计算的基本知识，希望读者通过阅读本书对量子计算有基本的了解。
量子计算在我国引起了广泛重视，越来越多的高校和科研院所正在开展量子计算的研究，在理论和硬件方面已经取得了不少的成果。同时，各界的专家学者也关注和学习量子计算。虽然通用量子计算机的研发远未成熟，而且理论上还需要大力发展新的量子算法和量子计算模型，但是我们已经看到了量子计算机的发展充满希望。本书以尽可能浅显的方式向一般读者介绍量子计算的基本知识，译者希望本书能引起更多读者对量子计算的兴趣，吸引更多的人才投身于量子计算的研究之中。

邱道文　　
2019年11月　　
于广州中山大学

译者序
前言
致谢
第1章　自旋 …… 1
1.1　量子钟 …… 7
1.2　同一方向的测量 …… 7
1.3　不同方向的测量 …… 8
1.4　测量 …… 10
1.5　随机性 …… 11
1.6　光子与偏振 …… 13
1.7　小结 …… 17
第2章　线性代数 …… 19
2.1　复数与实数 …… 20
2.2　向量 …… 21
2.3　向量的图解 …… 22
2.4　向量的长度 …… 23
2.5　标量乘法 …… 23
2.6　向量加法 …… 24
2.7　正交向量 …… 25
2.8　bra-ket内积 …… 26
2.9　bra-ket与长度 …… 27
2.10　bra-ket与正交 …… 28
2.11　标准正交基 …… 30
2.12　向量的基表示 …… 31
2.13　有序基 …… 34
2.14　向量的长度 …… 35
2.15　矩阵 …… 36
2.16　矩阵运算 …… 39
2.17　正交矩阵与酉矩阵 …… 41
2.18　线性代数工具箱 …… 42
第3章　自旋与量子比特 …… 44
3.1　概率 …… 44
3.2　量子自旋的数学表示 …… 45
3.3　等价状态 …… 49
3.4　自旋方向与基 …… 51
3.5　装置旋转60° …… 54
3.6　光子偏振的数学模型 …… 55
3.7　偏振方向与基 …… 56
3.8　偏振滤波实验 …… 57
3.9　量子比特 …… 59
3.10　Alice、Bob与Eve …… 61
3.11　概率偏振与相干性 …… 64
3.12　Alice、Bob、Eve和BB84协议 …… 65
第４章　纠缠 …… 69
4.1　非纠缠量子比特 …… 70
4.2　非纠缠量子比特的计算 …… 72
4.3　纠缠量子比特的计算 …… 74
4.4　超光速通信 …… 77
4.5　张量积的标准基 …… 79
4.6　如何制备纠缠的量子比特 …… 80
4.7　使用CNOT门制备纠缠的量子比特 …… 82
4.8　纠缠的量子钟 …… 84
第5章　贝尔不等式 …… 87
5.1　不同基下的纠缠量子比特 …… 89
5.2　爱因斯坦与定域实在性 …… 93
5.3　爱因斯坦和隐变量 …… 95
5.4　纠缠的经典解释 …… 95
5.5　贝尔不等式 …… 97
5.6　量子力学的解释 …… 98
5.7　经典的解释 …… 100
5.8　测量 …… 105
5.9　量子密钥分发的Ekert协议 …… 106
第6章　经典逻辑、门和电路 …… 109
6.1　逻辑 …… 110
6.2　布尔代数 …… 112
6.3　功能的完备性 …… 115
6.4　门 …… 119
6.5　电路 …… 121
6.6　与非门是一个通用门 …… 123
6.7　门与计算 …… 123
6.8　存储 …… 126
6.9　可逆计算 …… 127
6.10　台球计算 …… 135
第7章　量子门和电路 …… 141
7.1　量子比特 …… 142
7.2　受控非门 …… 143
7.3　量子门 …… 145
7.4　作用于一个量子比特的量子门 …… 146
7.5　是否存在通用量子门 …… 149
7.6　非克隆定理 …… 149
7.7　量子计算与经典计算 …… 153
7.8　贝尔电路 …… 153
7.9　超密编码 …… 156
7.10　量子隐形传态 …… 160
7.11　纠错 …… 165
第8章　量子算法 …… 173
8.1　P与NP …… 174
8.2　量子算法是否比经典算法快 …… 177
8.3　查询复杂性 …… 178
8.4　Deutsch算法 …… 178
8.5　Hadamard矩阵的Kronecker积 …… 184
8.6　Deutsch-Jozsa算法 …… 188
8.7　Simon算法 …… 194
8.8　复杂性类 …… 206
8.9　量子算法 …… 209
第9章　量子计算的作用 …… 212
9.1　Shor算法与密码分析 …… 213
9.2　Grover算法与数据检索 …… 218
9.3　化学与模拟 …… 224
9.4　硬件 …… 226
9.5　量子霸权与平行宇宙 …… 231
9.6　计算 …… 232