克里斯·伯恩哈特，美国费尔菲尔德大学教授，是《图灵的愿景：计算机科学的诞生》一书的作者。他在数学领域拥有深厚的研究成果，致力于探索计算机科学的起源与发展。通过这部作品，伯恩哈特向读者揭示了计算机科学诞生的历程，以及图灵这一伟大人物的贡献。

这是你一定能读懂的量子计算！ 量子计算是量子物理与计算机科学的完美融合，将20世纪物理学中那些令人惊叹的观点融入一种全新的计算思维方式中。不过，量子计算不是一种新型的计算，而是对计算本质的发现。 本书由数学家Bernhardt撰写，用简明的数学语言来描述量子世界，只要求读者具备高中数学知识。书中从量子计算的基本单位——量子比特开始，然后讨论量子比特测量、量子纠缠和量子密码学。之后回顾了经典计算中的标准主题——比特、门和逻辑，并描述了Edward Fredkin独创的台球计算机。最后定义了量子门，考虑量子算法的速度，以及量子计算对未来生活的影响。 是时候用一种新的方式来思考计算到底是什么了，因为量子计算的时代就在我们面前。

量子计算机的起源和发展，从Feynman提出量子计算机的概念，到牛津大学的Deutsch建立量子计算机的数学模型，再到量子算法的提出和发展，量子计算逐渐成为一门重要的学科。量子计算机在硬件设计方面也取得了显著进展，如谷歌设计的53个比特的量子芯片Sycamore。目前，世界各国都在积极研究量子计算，以期实现量子优势，量子计算已成为大众应该了解和学习的知识之一。



译者序

量子钟这一概念，它与传统时钟不同，只能回答指针是否指向特定数字或其相反方向。通过类比电子自旋，我们探讨了量子比特的测量问题。在重复测量同一方向时，结果始终一致，而在不同方向测量时，结果呈现随机性。这揭示了量子力学中的随机性和测量对结果的影响。同时，我们也探讨了经典力学和量子力学在测量和随机性方面的差异，以及量子比特如何通过电子自旋或光子偏振来表示。通过简单的实验，我们能够观察到量子现象，并认识到量子计算在生成真随机字符串方面的优势。



第1章 自旋

实数和复数的基本概念，强调了实数直接使用的便捷性，而复数则更加复杂，并解释了复数为何在量子计算中并非必需。文中通过三维空间与二维平面的类比，说明了复数在描述某些物理现象时的优越性。接着，详细介绍了向量和矩阵的概念，包括向量的长度、标量乘法、向量加法、正交向量以及bra-ket内积等。此外，还探讨了标准正交基和有序基，以及如何使用矩阵来检验向量集合是否构成标准正交基，以及如何用矩阵表示向量。最后，介绍了正交矩阵和酉矩阵的概念，并总结了使用线性代数工具箱进行计算的方法。



第2章 线性代数

量子力学中，概率与向量模型描述了实验结果，通过向量表示，并用概率说明其出现可能性。此模型基于二维向量空间，测量可改变粒子状态。在自旋实验中，通过测量获取不同方向的自旋状态，计算出特定结果在不同方向测量的概率。等价状态概念被提出，某些状态在特定测量下无法区分。光子偏振与电子自旋被类比，光子偏振的数学模型被介绍，量子比特概念进一步阐述。

Alice和Bob利用量子通信交换信息。他们随机选择基，相同则信息正确传递，不同则错误或丢失。Eve试图窃听，但无法完全复制量子比特，只能通过测量改变其状态。通过对比比特，他们可判断Eve是否在窃听，进而决定是否继续使用通信线路。

第3章 自旋与量子比特

量子比特的基本概念，通过Alice和Bob的量子比特测量实验，展示了非纠缠和纠缠量子比特的区别。非纠缠量子比特是指两个量子比特的状态相互独立，测量一个不会影响另一个；而纠缠量子比特则不同，一个量子比特的测量会立即影响到与之纠缠的另一个量子比特。文中还介绍了如何用张量积来表示量子比特的状态，以及如何通过量子门制备纠缠的量子比特。此外，还讨论了超光速通信的可能性，指出即使纠缠量子比特可以瞬间传递信息，但也不能用于实际通信。最后，通过量子钟的比喻，展示了纠缠量子比特之间存在的神秘相关性，并引入了贝尔实验来进一步探讨这一问题。



第4章 纠缠

量子纠缠现象揭示了纠缠态在不同基下的表现。通过量子比特的实例，展示了Alice和Bob在不同测量方向选择时，得到的答案存在差异，且概率均等。同时，文章探讨了爱因斯坦的定域实在性观点，提出了EPR悖论，指出量子力学中概率的使用可能存在未知的隐变量。此外，文章还讨论了经典力学中确定性与概率性的关系，并尝试用经典模型解释纠缠现象。贝尔不等式被提出，以区分量子力学模型和经典模型，实验结果支持了量子力学模型的预测。

文章简要介绍了量子力学的解释，包括多世界解释和Bohmian力学，但指出目前尚未有实验能够区分这些解释。量子密钥分发Ekert协议，一种基于量子纠缠的安全通信方式，使得Alice和Bob能够通过纠缠量子比特进行通信。若两人选择相同的测量基，他们将得到完全相同的结果。为防止窃听，他们在三个基中随机选择一个进行测量。如果Eve窃听，她会破坏纠缠态，Alice和Bob可以通过对比测量结果来检测Eve的存在。Ekert协议无需预生成数字，能有效防止加密威胁，已在实验室中成功实现。

第5章 贝尔不等式

19世纪末，乔治·布尔揭示了逻辑与代数之间的紧密联系，部分逻辑运算可以通过代数表示。文章深入剖析了三种基本逻辑运算：非、与和或，并利用真值表阐释了它们的真假情况。真值表使得逻辑运算的真假变得一目了然。随后，文章介绍了布尔代数，通过构建¬（¬P∧¬Q）的真值表，阐述了逻辑等价的概念。此外，文章还探讨了布尔函数的功能完备性，证明了仅使用¬和∧可以生成任何布尔函数。文章最后介绍了逻辑门的概念，如非门、与门、或门和与非门，并展示了如何利用这些门构建电路，以实现布尔函数的计算。

与非门是一种通用门，可以用来实现任何布尔函数。文章还介绍了如何使用与非门替代非门和与门，以及扇出操作在经典电路和量子比特中的不同实现方式。接着，讨论了逻辑门在现代计算机中的基本作用，并举例说明了如何使用异或门构造半加器。半加器是一种简单的加法电路，它不考虑进位，是构建完整加法器的基础。文章还介绍了存储数据的方法，即构建触发器，并简单描述了其工作原理。此外，阐述了可逆计算的概念，包括可逆门和可逆函数，并介绍了受控非门、Toffoli门和Fredkin门这三种可逆门的特点。最后，讨论了如何使用台球和镜子构建逻辑门，即台球计算机的概念，并解释了其背后的原理和局限性。

第6章 经典逻辑、门和电路

量子比特，作为量子系统的基本单元，与经典计算机中的比特有着显著区别。与经典比特只能处于0或1状态不同，量子比特能够同时存在于0和1的叠加态，这一特性赋予了量子计算机在处理复杂问题上的巨大潜力。

文中深入探讨了量子比特的表示方法，包括基向量的选择和量子态的概率振幅。此外，还详细介绍了量子门的概念，特别是受控非门和作用于单个量子比特的量子门，如Pauli变换和Hadamard门。

量子计算的基本原理，如量子纠缠、非克隆定理以及与经典计算的差异，也在文章中得到了阐述。这些内容为理解量子计算的基础提供了重要的理论基础。

在量子计算中，量子比特可以同时处于多个状态，而经典比特只能处于单一状态。量子CNOT门和Fredkin门等量子门在量子计算中扮演着重要角色，它们的量子版本与经典版本的效果一致。

贝尔电路是一种特殊的量子电路，可以将输入的量子比特转换为纠缠态，称为贝尔基。贝尔电路在超密编码和量子隐形传态等量子通信过程中发挥关键作用。超密编码允许Alice向Bob发送两个经典比特的信息，而量子隐形传态则允许Alice将她的量子比特传输给Bob。

量子纠错是量子计算中的一个重要问题，因为量子比特容易与环境相互作用而损坏。重复码和量子比特翻转校验是两种基本的量子纠错方法。

在量子通信中，量子比特的纠缠与操作至关重要。特定条件下，量子比特不会与前三个量子比特纠缠，而第五个量子比特则根据特定逻辑状态确定。Bob可以对底部两个量子比特进行测量，并根据测量结果在相应的量子比特上施加X门操作，纠正比特翻转错误。

量子计算通过量子门和量子电路展现出超越经典计算的能力，成为更基本的计算形式。未来，我们将探讨量子计算机在计算速度上的优势以及如何衡量计算速度。

第7章 量子门和电路

P与NP问题在计算机科学中占据核心地位。P问题能在多项式时间内解决，而NP问题则能在多项式时间内验证答案。这一对问题至今未解，被视为计算机科学最关键难题之一。量子计算机的崛起，尤其是Shor分解算法的提出，展示了量子计算机可能比经典计算机更高效地解决某些问题。这激发了人们对量子算法与经典算法速度的对比，以及算法复杂度新挑战的思考。

量子算法在特定问题上的应用引人注目，如Deutsch算法和Simon算法。这些算法通过查询特定函数（或称为oracle）的值来解决问题。量子算法在解决某些特定问题上展现出速度上的优势，例如，在识别常值函数或平衡函数的问题上，量子算法只需查询一次oracle，而经典算法可能需要多次查询。这些算法不仅展示了量子计算的优势，也为量子计算机的发展提供了新的思路。

Simon算法是量子算法的经典代表。以n=5为例，Simon算法能够通过查询oracle找到特定的字符串s。算法通过多次运行电路，得到一系列线性无关的方程，从而求解s。虽然Simon算法在最坏情况下可能需要指数级查询，但在一定误差概率范围内，其查询次数是关于n的线性函数，因此Simon算法被归类为BQP，即有界误差的量子多项式时间算法。与经典算法相比，Simon算法在查询复杂性上具有优势，能够解决经典算法难以解决的问题。

量子算法的加速不仅仅源于量子并行性，还涉及更多复杂工作。研究中最基本的算法并非简单，其发展历程揭示了量子计算领域的突破。1985年，Deutsch算法首次证明量子算法能超越经典算法。随后，Shor和Grover算法等里程碑式作品涌现，展示了量子计算在密码破解等领域的潜力。正交矩阵在量子计算中扮演关键角色，为我们提供了更多观察问题的视角。逆向工程问题在量子计算中变得易于解决，而构建比经典算法更快的量子算法则是研究目标。

第8章 量子算法

量子计算在密码分析领域取得突破性进展，Shor算法的出现对RSA加密算法构成威胁，同时也展示了量子计算机在解决数学问题上的巨大潜力。量子傅里叶变换门等量子操作在此过程中发挥了关键作用，使寻找大数因子成为可能。此外，Grover算法专注于数据检索，通过量子操作实现二次加速，在大量数据搜索中展现出优势。这些算法的提出推动了后量子密码学的发展，并引领量子密钥分发技术迈向实际应用。

量子计算机的构建面临着诸多挑战。从量子比特的选取到量子门的构造，再到量子电路的设计，每个环节都需要克服困难。光子虽然具有优良特性，但在储存和操控方面存在困难；电子自旋虽然被尝试，但可扩展性受限；离子阱计算则要求极低的温度。超导量子比特因其独特的量子特性成为热门选择，IBM和Google在此领域取得显著进展。

量子计算机的研究不仅带来了新的计算方式，还引发了关于宇宙计算和量子霸权的讨论。量子计算的发展预示着计算领域的一次重大变革，未来充满无限可能。尽管目前量子计算机仍处于初级阶段，但它们在化学模拟等领域的应用前景令人期待。

人人可懂的量子计算