科学呈现了这个时代最富冒险精神的哲学思辨。它是一种完全由人类建构的，在信仰的驱使下，通过追寻梦想—发现—解释—梦想……的不断循环，从而不断开拓新的领域，世界将以某种方式变得越来越清晰，我们也将最终掌握宇宙的真正奥秘。所有的奥秘将被证明是有联系，有意义的。
——爱德华•威尔逊（Edward O.Wilson）
信息是物理的。
——罗夫•兰道尔（Rolf Landauer）
量子计算和量子信息的基本概念有哪些？它们是如何发展的？有什么用途？本书将如何展现这些内容？本章的目的是通过粗线条勾勒出量子计算和量子信息的蓝图来回答这些问题，从而使读者对该领域的基本概念，发展过程能有基本的理解，并引导读者如何阅读本书的其他部分。
1.1 节讲述量子计算和量子信息发展的历史背景。本章其他小节简要介绍该领域的基本概念：量子比特（ 1.2 节），量子计算机，量子门和量子电路（ 1.3 节），量子算法（ 1.4 节），实验量子信息处理（ 1.5 节），以及量子信息和通信（ 1.6 节）。
沿着这一思路，通过本章讲述的数学基础知识，将给出对于量子隐形传态和一些简单量子算法的易于理解的展示。本书内容自成体系，即使没有计算机科学和物理学背景也可以读懂。随着论述的展开，我们还将指明在后面对应的章节中会有更深人的讨论，还可以找到参考文献和推荐阅读的材料。
在阅读本书时，遇到晦涩难懂的内容不妨先跳过。有些地方我们会不可避免地使用一些技术术语，并且要到本书后面才能完全阐明。对于这些行话，可以暂且简单接受，待深人理解所有术语后再回来。本章的重点是该领域的全貌，细节留待后面章节详细阐述。
量子计算与量子信息的研究对象是使用量子力学系统能够完成的信息处理任务。听起来很简单明了，对吗？但像许多简单而深刻的思想一样，人们花费了很长时间才想到使用量子力学系统来进行信息处理。要了解其中的缘由，我们必须回顾历史，逐一考察为量子计算和量子信息提供基本概念的所有领域——量子力学，计算机科学，信息论和密码体系。在此过程中，为了对已自成一体的量子计算和量子信息的各方面有所了解，我们需要先后采用物理学家，计算机科学家，信息论学家和密码学家的视角。
20 世纪初叶，科学经历了一场出人意料的革命。物理学遇到了一系列危机。问题在于当时的物理学理论（现称为经典物理学）做出了一些荒谬的预言，例如存在包含无限能量的＂紫外灾难＂，或电子必然会螺旋进人原子核内部。起初，通过在经典物理学中加人特殊假设，这些问题得以解决，但随着人们对原子和辐射有了更好的理解，这些解释越来越使人困惑。在经历了四分之一世纪的混乱后，危机于 20 世纪 20 年代早期到达顶峰，最终导致了量子力学这一现代理论的创立。自此以后，量子力学一直是科学不可或缺的一部分，并已有无数成功应用的例子，包括原子结构，恒星核聚变，超导体，DNA 结构，以及自然界基本粒子等几乎所有方面。
什么是量子力学？量子力学是一个数学框架或物理理论构建的规则集。例如，量子电动力学就是一套以极其精确的方式刻画原子与光的相互作用的物理理论。量子电动力学是在量子力学的框架下建立起来的，但还包含量子力学未规定的一些特殊规则。量子力学与像量子电动力学那样的特定物理理论的关系，更像是计算机操作系统与特定应用软件的关系——操作系统设置某些基本参数和操作模式，而应用软件则完成特定任务。
量子力学的规则很简单，但即使专家有时也会感到它违背直觉，量子计算和量子信息的先驱一直期朌能对量子力学有更好的理解。最著名的量子力学批判者阿尔伯特•爱因斯坦（Albert Einstein ），直到去世都不能接受他帮助发展起来的这一理论。几代物理学家一直在努力使量子力学的预言更加令人满意。量子计算和量子信息的目标之一是开发工具以增进对量子力学的直观把握，并使其预言对人们更通俗易懂。
例如，在 20 世纪 80 年代早期，人们开始关注是否有可能使用量子效应进行超光速的信号传递一一根据爱因斯坦的相对论，这是不可能的。这个问题的解决最终取决于是否有可能克隆未知量子态，即复制量子态。如果克隆是可能的，那么就有可能借助量子效应进行超光速的信号传递。尽管克隆对于经典信息很容易实现（想想看本书中的信息来自哪里！），但在量子力学的一般意义下是不可能的。这条在 20 世纪 80 年代早期就发现的不可克隆定理是量子计算和量子信息的早期成果之一。此后不可克隆定理有了许多改进，我们现在已经有了可以了解量子克隆设备（必然是不完美的）能力的工具。这些工具反过来已被用于理解量子力学的其他方面。
有助于量子计算和量子信息发展的相关历史链可追溯到 20 世纪 70 年代对单量子系统的完全操控的兴趣。在那之前，量子力学的应用通常涉及对包含大量量子力学系统的批量样品的总体
控制，而单个量子力学系统则无法单独访问。例如，超导现象具有极好的量子力学解释，但由于超导体涉及导电金属的巨大样本（与原子尺度相比），所以只能探测到其量子力学性质的几个方面，而无法触及构成超导体的单个量子系统。虽然粒子加速器可以让我们有限度地访问单个量子系统，但是几乎无法对其实施控制。
自 20 世纪 70 年代以来，有许多用于控制单量子系统的技术诞生。例如，用于捕获单个原子的＂原子陷阱＂，可使原子与其环境隔离，并对原子行为的很多方面进行极其精密的探测。扫描隧道显微镜可用于移动单个原子，按要求设计原子阵列。还有可以转移单个电子的电子器件。
为何要试图完全控制单量子系统？抛开许多技术的原因，从纯粹科学的角度看，主要原因是研究人员预感到，科学上最深刻的见解往往出现在开发探索新的自然领域的方法之时。例如， 20世纪 30 年代到 40 年代的射电天文学发明导致了一系列惊人的发现，包括银河系的中心，脉冲星和类星体等。低温物理学的惊人成就也是在人们寻找降低不同系统温度的方法时取得的。同样地，通过完全控制单量子系统，我们正在探索自然的未知领域，希望发现新的和意外的现象。我们在这些方向上刚迈出第一步，就已经在这个领域中有了几项有趣的发现。一旦能够完全操控单量子系统，我们又会发现什么呢？
量子计算和量子信息研究天然适合这一计划。它为人们设计更好地操纵单量子系统的方法提供了一系列有价值的挑战，促进了新的实验技术的发展，并指出了实验研究中最有趣的方向。反过来，操控单量子系统对于把量子力学的威力应用于量子计算和量子信息研究是必不可少的。
尽管人们有着浓厚的兴趣，但建立量子信息处理系统的努力迄今只取得了初步的成功。能够在几个量子比特（或量子位）上进行几十次操作的小型量子计算机代表了目前量子计算的最高水平。用于长距离保密通信的量子密码学（quantum cryptography）的实验原型已经出现，并且可用于某些实际应用。然而，如何制造可解决实际问题的大规模量子信息处理设备，仍是物理学家和工程师未来面临的巨大挑战。
让我们把注意力从量子力学转移到 20 世纪另一项伟大的智慧成就——计算机科学。计算机科学的起源可以追溯到很久以前。例如，楔形文字片表明，在汉谟拉比（Hammurabi，约公元前 1750 年）时代，巴比伦人（Babylonian）已有相当复杂的算法思想，有些思想甚至可以追溯到更早的年代。
伟大的数学家阿兰•图灵（Alan Turing）在 1936 年发表的一篇令人瞩目的论文宣告了现代计算机科学的诞生。图灵以抽象的方式详细描述了我们现在所说的可编程计算机，即以他的名字命名的图灵机的计算模型。图灵证明了存在一台通用图灵机，可用于模拟任何其他图灵机。此外，他宣称通用图灵机完全刻画了算法手段所能完成的所有任务。即任何可以在硬件（如现代个人计算机）上执行的算法，在通用图灵机上都有等效算法来完成。这个论断被称为丘奇－图灵论题（Church－Turing thesis），以图灵和另一位计算机科学先驱阿隆佐•丘奇（Alonzo Church）的名字命名，它断言了在某一物理设备上可以实现的算法与数学上严格定义的通用图灵机概念的等价关系。人们普遍认为，该论题为计算机科学丰富的理论发展奠定了基础。
在图灵的论文发表后不久，第一台电子计算机诞生。约翰•冯•诺伊曼（John von Neumann）设计了一个简单的理论模型，用实际元件实现了通用图灵机的全部功能。到了 1947 年，在 John Bardeen，Walter Brattain 和 Will Shockley 发明晶体管后，硬件才开始蓬勃发展。从那时起，计算
机硬件的能力以惊人的速度增长，以至于 1965 年戈登•摩尔（Gordon Moore）将其概括为摩尔定律，即计算机的能力将以恒定的速率增长，大约每两年增长一倍。
令人惊讶的是，自 20 世纪 60 年代开始，摩尔定律在几十年里都近似成立。尽管如此，但大多数研究人员都预计这将在 21 世纪的前 20 年内终结。传统的计算机制造方法在解决线宽尺度所带来的根本性困难时开始显得力不从心。随着电子器件越来越小，其功能会受到量子效应的干扰。
解决摩尔定律最终失效问题的一个可能方案是采用不同的计算模式。量子计算理论就是这样的一种范例，它基于量子力学而不是经典物理学的思想来执行计算。事实证明，虽然普通计算机可用于模拟量子计算机，但似乎不能以一种有效的方式去模拟。因此，量子计算机相比传统计算机在速度上有本质的超越。这种速度优势非常显著，以至于许多研究人员认为，经典计算机和量子计算机的能力之间存在着无法跨越的鸿沟。
量子计算机的＂有效＂与＂非有效＂模拟是指什么？早在量子计算机的概念出现之前，回答这个问题所需的许多关键概念实际上就已被定义。特别是计算复杂性领域在数学上精确地定义了 ＂有效＂和＂非有效＂算法。粗略地说，有效算法解决问题所用的时间是关于问题规模的多项式量级。相反，非有效算法需要超多项式（通常是指数量级）的时间。
在 20 世纪 60 年代末到 70 年代初，人们注意到通过用图灵机来模拟其他计算模型，在其他模型上能够有效解决的问题也能够在图灵机上高效解决，这意味着图灵机这一计算模型并不逊色于任何其他计算模型。这一观点可概括为加强版丘奇－图灵论题：
使用图灵机可以有效地模拟任何算法过程。
强丘奇－图灵论题的加强之处在于＂有效＂一词。如果这一论题正确，就意味着无论用何种机器执行算法，都可以使用标准图灵机有效模拟。这一强化很重要，因为它意味着要分析给定的计算任务是否可以有效完成，可以限定在图灵机的计算模型上进行。
强丘奇－图灵论题面临的一类挑战来自模拟计算领域。在图灵所处的时代，许多不同的研究团队已经注意到某些类型的模拟计算机可以有效地解决在图灵机上没有有效解决方案的问题。表面上看，这些模拟计算机似乎违反了强丘奇－图灵论题。不幸的是，对于模拟计算机，在对噪声做出符合实际的假设后，其计算能力在所有已知的例子里都会消失，它们也不能有效地解决图灵机无法有效解决的问题。这个教训——在评估计算模型的效率时必须考虑现实噪声的影响——是量子计算和量子信息初期面临的最大挑战之一，这一挑战随着量子纠错码和容错量子计算理论的发展得到了有效的解决。因为与模拟计算不同，量子计算原则上可以容忍有限的噪声并保持其计算优势。
对强丘奇－图灵论题的第一个重大挑战出现在 20 世纪 70 年代中期，当时 Robert Solovay 和 Volker Strassen 证明了可以使用随机算法测试一个整数是否是素数。也就是说，随机性是 Solovay－ Strassen 测试算法的实质部分。该算法并不能确定给定的整数是素数还是合数。相反，它可以给出一个数是素数或合数的概率。通过重复 Solovay－Strassen 测试，几乎可以确定一个数是素数还是合数。Solovay－Strassen 测试算法的重要意义在于该算法提出时，素数判定问题并没有有效的确定型算法。于是，似乎带有随机数发生器的计算机能够有效执行某个计算任务，而这一任务在经
典的确定型图灵机上却不能有效解决。这一发现激励着人们去寻找其他随机算法并获得了丰厚的回报，它也因此成为了一个活跃的研究领域。
随机算法形成了对强丘奇－图灵论题的挑战，这暗示着存在一些可以有效求解的问题，但它们不能被确定型图灵机有效地求解。这一挑战可以通过对强丘奇－图灵论题稍做修改来解决：
任何算法都可以用概率图灵机有效模拟。
对强丘奇－图灵论题的这种即兴修改令人深感不安。将来难道一定不会有另外一种计算模型能有效解决图灵计算模型中无法有效解决的问题？有没有什么途径可以找到一个能有效地模拟其他任何计算模型的计算模型？
受这个问题的启发，David Deutsch 在 1985 年提出，是否可以用物理学定律推导出更强的丘奇－图灵论题。Deutsch 没有用特定假设的方法，而是通过物理学理论为丘奇一图灵论题建立和当今物理学理论前沿相当的基础。特别地，Deutsch 试图定义一种能够有效模拟任意物理系统的计算设备。由于量子力学是物理学的最终规律，Deutsch 自然而然地考虑了基于量子力学原理的计算设备。这些设备，仿照 49 年前图灵定义的机器，最终引导出了本书中现代量子计算机的概念。
在撰写本文时，尚不清楚 Deutsch 的通用量子计算机概念是否足以有效地模拟任何物理系统。证明或否定这个猜想是量子计算和量子信息领域的一个重要的未解决问题。例如，量子场理论的某些效应或基于弦论的更奇特效应，量子引力或其他物理理论，都可能为我们提供比 Deutsch 的通用量子计算机更强大的计算模型，只是我们现在并不知道。
Deutsch 的量子计算机模型确实对强丘奇－图灵论题提出了挑战。Deutsch 曾询问量子计算机是否可以有效解决在经典计算机上不能有效解决的计算问题，甚至是概率图灵机不能有效解决的计算问题。然后他举了一个简单的例子，表明量子计算机的计算能力确实超过了传统计算机。
随后的十年内许多人努力改进 Deutsch 令人瞩目的初步结果，直到1994年 Peter Shor 展示了两个非常重要的问题——寻找整数的素因子问题和所谓的离散对数问题——可以在量子计算机上有效解决，而达到顶点。这方面的研究之所以受到广泛关注，是因为人们普遍认为这两个问题在经典计算机上没有有效的解决方案。Shor 的成果是量子计算机比图灵机及概率图灵机更强大的有力证据。量子计算机功能强大的进一步证据出现在 1995 年，Lov Grover 证明了另一重要问题——在非结构化搜索空间进行搜索的问题——也可以在量子计算机上得到加速。虽然 Grover的算法并没有像 Shor 算法那样有惊人的加速，但搜索方法的广泛应用引起了人们对 Grover 算法的极大兴趣。
在 Shor 和 Grover 算法被发现的同时，很多人都在研究理查德•费曼（Richard Feynman）在 1982年提出的一个想法。费曼指出，似乎在经典计算机上模拟量子力学系统存在本质困难，并建议建立基于量子力学原理的计算机以克服这些困难。在 20 世纪 90 年代，几个研究小组使这一思想具体化，表明确实有可能使用量子计算机去有效模拟一些在经典计算机上没有已知有效模拟方法的系统。未来量子计算机的主要应用之一很有可能是模拟在经典计算机上难以模拟的量子力学系统，这对科学和技术领域有深远意义。
与传统计算机相比，量子计算机还能更快地解决其他哪些问题？简短的回答是我们不知道。找出好的量子算法似乎很难。悲观主义者可能会认为除了已发现的应用，量子计算机并没有其他
好处！设计量子计算机算法的困难之处在于，设计者面临经典计算机算法所未遇到的两方面难题。首先，人类的直觉植根于经典世界。如果借助于直觉来构建算法，则只能想到经典思想。为设计好的量子算法，我们必须至少部分地＂关闭＂经典直觉，利用量子效应去达到期望的算法目的。其次，要想真正有意义，光设计出一个纯粹的量子算法是不够的。这些算法必须优于任何现有的经典算法！因此，人们或许可以找到一种利用纯量子力学的算法，但由于已经存在性能具有可比性的经典算法而未引起广泛关注。这两个问题的结合使得新量子算法的设计成为未来的挑战。
更一般地说，是否可以归纳出量子计算机与经典计算机能力的差别。如果量子计算机真的比传统计算机更强大，那让它更强的原因是什么？什么类型的问题可以在量子计算机上有效地解决，与经典计算机上可有效解决的问题相比如何？量子计算和量子信息中最激动人心的事情之一，就是对这些问题的答案知之甚少！更好地理解这些问题是未来的一个巨大挑战。
谈到量子计算的前沿之后，让我们切换到对量子计算和量子信息做出贡献的另一种思想：信息论。1940 年，人们探索计算机科学的同时，通信正在进行另一场革命。1948 年，克劳德•香农 （Claude Shannon）发表了两篇令人瞩目的现代信息与通信理论奠基性论文。
香农迈出的关键一步也许是在数学上定义了信息的概念。数学的很多分支在基本定义的选择上具有相当大的灵活性。试着凭直觉思考一下以下问题：如何从数学的角度定义信息源？几种不同的答案都有着广泛的用途；但香农的定义似乎具有更丰富的内容，因为该定义更好理解，并引发了深刻结果，建立了层次丰富的理论，而且准确反映了现实通信问题。
香农关注的是与信息通过信道传送有关的两个关键问题。首先，通过信道传送信息需要哪些资源？例如，电话公司需要知道一根给定的电话电缆能可靠地传输多少信息。其次，在信道上传送信息时可以避免噪声的干扰吗？
香农通过证明信息论的两个基本定理回答了这两个问题。第一个是他的无噪声信道编码定理，它定量地给出了用于存储从信源发出信息所需的物理资源。香农的第二个基本定理——有噪声信道编码定理，定量给出了有噪声的信道能可靠传输的信息量。为了在有噪声的情况下实现可靠的传输，香农证明可以用纠错码来保护正在发送的信息。有噪声信道编码定理给出了纠错码提供保护的一个上限。不幸的是，香农定理并没有给出实际能达到这个极限的一组纠错码。从香农的论文发表到今天，研究人员不断推出更多更好的纠错码，试图接近香农定理给出的极限。复杂的纠错码理论为用户提供了多种选择。这些纠错码用途广泛，如用于光盘播放器，计算机调制解调器和卫星通信系统等。
量子信息理论也有类似的发展过程。1995 年，Ben Schumacher 证明了与香农无噪声信道编码定理类似的结果，并定义了＂量子比特＂作为切实的物理资源。但并没有针对量子信息的对应于香农的有噪声信道编码定理的结果。与经典对应物类似，学者们发展出了前面已提过的量子纠错码，允许量子计算机在有噪声的情况下能有效计算，也允许在带噪声的量子信道进行可靠通信。
实际上，经典的纠错码思想已被证明在研究和理解量子纠错码上非常重要。1996年，两个独立的工作小组——Robert Calderbank 和 Peter Shor，以及 Andrew Steane，发现了一类重要的量子编码，现称为 CSS 码。此后，这项工作被包含在由 Robert Calderbank，Eric Rains，Peter Shor 和 Neil Sloane，以及 Daniel Gottesman 分别独立发现的稳定子码（stabilizer code）中。由于建立在经
典线性编码理论的基本思想基础上，这些发现极大地促进了对量子纠错码及其在量子计算和量子信息中的应用的理解。
研究量子纠错码理论的目的是保护量子态免受噪声干扰。那么在量子信道传输普通经典信息会怎样？能多高效？在这方面有几个惊人的发现。1992 年，Charles Bennett 和 Stephen Wiesner 解释了如何通过只将一个量子比特从发送方发送到接收方，来传输两个经典的比特，这一结果称为超密编码（superdense coding）。
更有趣的结果来自分布式量子计算方面。设想你有两台联网的计算机来解决一个特定的问题。为求解问题需要多少通信量？最近的结果表明，量子计算机可以用比经典计算机指数少的通信量来求解某些问题！不幸的是，这些问题在实际中并不是特别重要，而且会受到一些技术上的限制。量子计算和量子信息在未来面临的主要挑战是，寻找现实中重要且分布式量子计算比经典计算有实质性优势的问题。
让我们适时回顾一下信息论。信息论始于对单个信道的研究。但实际应用中我们通常不会碰到单个信道，而是要处理许多信道构成的网络。网络化信息论的主题是研究信道网络的信息承载特性，这已成为一个内容丰富而复杂的主题。
相比之下，网络化量子信息论的研究还非常初步。即使是对量子信道网络的信息承载能力，我们也知之甚少。在过去几年中取得了一些令人瞩目的初步结果；但还没有针对量子信道的统一的网络化量子信息论。网络化量子信息论的一个例子就足以让人相信这样一套理论所具有的价值。设想我们正试图通过带噪声的量子信道将 Alice 的量子信息发送给 Bob，如果该信道的量子信息容量为零，就不可能将 Alice 的任何信息可靠地发送给 Bob。再设想我们有同步操作的该信道的两个副本，很明显（并且可以严格证明）这样的信道也没有发送量子信息的能力。但是，如果我们将其中一个信道反向，如图 1－1 所示，某些情况下，我们可以获得从 Alice 到 Bob 的非零容量的信息传输！这种违反直觉的特性说明了量子信息的奇特。更好地理解量子信道网络的信息承载特性是量子计算和量子信息的一个主要的未解决问题。
图 I－1 在经典中，如果两个噪声很大的零容量信道并行运行，那么联合信道发送信息的容量为零。如果将其中一个信道反向，那么发送信息的容量仍为零，这并不奇怪。但是在量子力学里，把其中一个零容量信道反向将真的允许我们发送信息！
让我们最后一次切换领域，来看古老的密码学中的科学和技术。广义上讲，密码学是涉及彼此不一定信任的两方或多方的通信或计算的问题。最著名的加密学问题是保密通信。假设有两方
希望秘密通信。例如，您可能希望将信用卡号码交给商家以换取商品，但不希望任何有恶意的第三方拦截您的信用卡号码。上述的保密通信使用加密协议完成。本书后面会详细描述加密协议的工作原理，现在只需弄清一些简单的区别就行了。最大的区别在于私钥密码系统和公钥密码系统。
私钥密码系统的工作方式是通信双方 Alice 和 Bob 共享一个只有他们知道的私钥。密钥的确切形式在这里无关紧要——不妨认为是一个 0 和 1 的串。重点是 Alice 用此密钥将希望传送给 Bob 的信息进行加密。Alice 将加密后的信息发送给 Bob，Bob 必须恢复原始信息。Alice 对消息加密的确切方式取决于私钥，因此，未来要恢复原始消息，Bob 需要知道私钥，以便消除 Alice施加的变换。
不幸的是，私钥密码系统在许多情况下都存在严重的问题。最基本的问题是如何分配密钥？在许多情况下，密钥分发问题与原始的保密通信问题难度相同——恶意的第三方可能在密钥分发时窃听，然后使用截获的密钥来解密传送的某些信息。
量子计算和量子信息最早的发现之一是量子力学可以用于密钥分配，使 Alice 和 Bob 的秘密不会受到威胁。该过程称为量子加密或量子密钥分发。基本思想是利用观测一般会破坏被观测系统的量子力学原理。因此，如果在 Alice 和 Bob 要传送密钥的时候有窃听者偷听，窃听者就会因对 Alice 和 Bob 用于建立密钥的信道的干扰而被发现。Alice 和 Bob 可以丢弃掉那些有窃听者出现时建立的密钥位，并重新确定密钥。Stephen Wiesner 在 20 世纪 60 年代后期首次提出了量子密码的概念，但遗憾的是论文没有能被接受发表！1984年，Charles Bennett 和 Gilles Brassard 在 Wiesner 早期工作的基础上，提出了利用量子力学在 Alice 和 Bob 之间分配密钥而不怕任何攻击的协议。从那以后，出现了无数的量子密码协议，并开发了实验原型机。在撰写本书时，实验原型机已接近适用于有限规模的实际应用的阶段。
密码系统的第二个主要类型是公钥密码系统。公钥密码系统不需要 Alice 和 Bob 预先共享一个密钥。相反，Bob 只需公布一个＂公钥＂，让所有人都可以得到。Alice 用此公钥来加密她发送给 Bob 的消息。有趣的是，第三方不可能用 Bob 的公钥来解密此消息！严格来说，我们不应该说不可能，而是加密变换取得非常巧妙，以致仅根据公钥来逆向解密非常之困难（尽管不是完全不可能）。为了使逆向过程变得容易，Bob 有一个与该公钥配对的私钥，这使他能很容易地解密。这个密钥只有 Bob 知道，故而在别人不太可能有公钥就能解密的前提下，Bob 可以相信只有他能读取 Alice 传送的内容。公钥密码系统通过让 Alice 和 Bob 不必在通信之前共享私钥来解决密钥分发问题。
值得注意的是，公钥密码系统直到 20 世纪 70 年代中期才被广泛使用，由 Whitfield Diffie 与 Martin Hellman，以及 Ralph Merkle 等人分别独立提出的这一技术彻底改变了密码学领域。之后， Ronald Rivest，Adi Shamir 和 Leonard Adleman 提出了 RSA 密码系统，这是直到撰写本书时最为广泛采用的公钥密码系统，它被认为在安全性和实用性之间取得了微妙的平衡。1997年披露的信息显示，这些思想——公钥密码系统，Diffie－Hellman 密码系统和 RSA 密码系统——实际上是英国情报机构 GCHQ 的研究人员在 20 世纪 60 年代末到 70 年代初发明的。
公钥密码系统的安全性的关键在于，仅利用公钥进行解密是困难的。例如，对 RSA 来说，逆向解密过程是一个与素因子分解密切相关的问题。对 RSA 的安全性的假定建立在用经典计算机
分解因子是困难的这一假设下。但 Shor 在量子计算机上分解因子的快速算法可用于破解 RSA！类似地，如果知道一个求解离散对数的快速算法——比如 Shor 的针对离散对数的量子算法，有些其他公钥密码系统就会被破坏。量子计算机在破解密码系统的这项应用，引起了人们对量子计算和量子信息的极大兴趣。
我们一直在回顾量子计算和量子信息的发展历史。当然随着该领域的发展和成熟，已经产生了它自己的研究子领域，它们的历史基本上包含在量子计算和量子信息的历史中。
最引人注目的或许是对量子纠缠的研究。纠缠是量子力学独特的资源，在量子计算和量子信息的许多有意义的应用上起着关键作用，相当于经典世界青铜时代中铁的地位。近年来，人们为更好地理解纠缠现象付出了巨大的努力，纠缠现象已被认为是一种基本的自然资源，其价值可以和能量，信息，嫡及任何其他基本资源相当。尽管还没有完整的纠缠理论，但在理解这一量子力学的奇特性质方面已经取得了一些进展。许多研究人员希望对纠缠特性的进一步研究会促进发展量子计算和量子信息新应用的见解。
我们已回顾了量子计算和量子信息的历史和现状，未来会如何？量子计算和量子信息会给科学，技术和人类带来什么？量子计算和量子信息能对产生它的计算机科学，信息论和物理学诸领域带来什么好处？量子计算和量子信息有哪些关键问题尚未解决？在展开细节之前，我们将对这些全局性问题做简短的评注。
量子计算和量子信息教会我们以物理的方式对计算进行思考，我们发现这种做法能为信息处理和通信带来许多新的令人鼓舞的动力。计算机科学家和信息论专家有了一个值得探索的内容丰富的新模型。实际上广义来说，我们学到的任何物理理论，不仅仅是量子力学，都可以作为信息处理和通信的基础。这种探索的结果，也许有朝一日会导致发明远超出当今计算和通信系统能力的信息处理装置，并对整个社会相应带来正面和负面的影响。
量子计算和量子信息无疑给物理学家带来了很多挑战，但从长远来看它对物理学做出何种贡献却有些微妙。我们相信，正如我们学会用物理的方式思考计算一样，我们也能学会用计算的方式思考物理学。虽然传统物理学主要集中于弄清基本物体和简单系统，但自然的许多有趣方面只会在事物变得更大和更复杂时出现。化学和工程在某种程度上处理了这种复杂性，但大多数情况下都是以就事论事的方式。量子计算和量子信息传达的一个信息是，新的工具可以用来跨越微小和相对复杂的事物之间的鸿沟：计算与算法为构建和理解此类系统提供了系统化的手段。应用这些领域的思想已经开始对物理学带来新的见解。我们希望多年后它将发展成为一个理解物理学所有分支的富有成果的方向。
本节中我们简要地考察了量子计算和量子信息背后的一些关键思想和研究动机。在本章的其他小节我们将对这些动机和想法给出一个更具技术性但仍容易理解的介绍，以期待读者能一览该领域的现状。
比特是经典计算和经典信息的基本概念。量子计算和量子信息建立在量子比特（quantum bit或 qubit）的基础上。在本节中我们介绍单量子比特和多量子比特的属性，并与经典比特进行对比。
什么是量子比特？我们将量子比特描述为具有某些特定属性的数学对象。也许你会说：＂我认为量子比特是物理对象。＂像比特一样，量子比特是用实际物理系统来实现的，在 1.5 节和第 7章将详细描述量子比特的抽象数学观点和实际系统之间是如何联系的。在本书的大部分内容中，量子比特被视为抽象的数学对象。将量子比特视为抽象对象的美妙之处在于，我们将能够构建不依赖于特定实现系统的量子计算和量子信息的一般理论。
那么什么是量子比特？正如经典比特有一个状态——0或1——量子比特也有一个状态，量子比特的两个可能的状态是 $|0\rangle$ 和 $|1\rangle$ ，如你所想，它们分别对应于经典比特的状态 0 和 1 。记号 ＂｜＞＂被称为 Dirac 记号，我们会常碰到它，它是量子力学中状态的标准符号。比特和量子比特之间的区别在于量子比特可以处于除 $|0\rangle$ 或 $|1\rangle$ 外的状态，量子比特是状态的线性组合，通常称为叠加态，如：
$$ \begin{equation*}|\psi\rangle=\alpha|0\rangle+\beta|1\rangle \tag{1.1}\end{equation*} $$
其中 $\alpha$ 和 $\beta$ 是复数，尽管很多时候将它们视为实数也没有太大问题。换句话说，量子比特的状态是二维复向量空间中的向量。特殊的 $|0\rangle$ 和 $|1\rangle$ 状态被称为计算基矢态，是构成该向量空间的一组正交基。
我们可以通过检查一个比特来确定它处于 0 态还是 1 态。例如，计算机读取其内存内容时始终执行此操作。但值得注意的是，我们不能通过检查量子比特来确定它的量子态，即 $\alpha$ 和 $\beta$ 的值。相反，量子力学告诉我们，我们只能获得有关量子态的有限信息。在测量量子比特时，我们以 $|\alpha|^{2}$ 的概率得到结果 0 ，以 $|\beta|^{2}$ 的概率得到结果 1 。显然，$|\alpha|^{2}+|\beta|^{2}=1$ ，因为概率和为 1 。从几何上看，我们可以将此解释为量子比特的状态归一化长度为 1 。因此，通常量子比特的状态是二维复向量空间中的单位向量。
量子比特的不可观测状态和我们能够进行的观测之间的对立是量子计算和量子信息的核心。现实世界的大多数抽象模拟中，抽象和真实模型间存在直接的对应关系，就像建筑师蓝图与最终建筑之间的对应关系。没有这种直接关系，使得难以直观地了解量子系统的行为。不过好在存在间接对应关系，因为量子比特的状态可以被处理和转换，按照状态的不同属性，会出现可区分的测量结果。因此，这些量子态具有真实的，实验上可验证的效应，它们对量子计算和量子信息的功能是必不可少的。
量子比特处于叠加态的性质与我们理解周围物理世界的常识背道而驰。经典比特就像一枚硬币：要么正面朝上，要么反面朝上。对不均匀的硬币可能依赖边缘的平衡存在中间状态，但在理想情况下可以忽略这些情况。相比之下，量子比特可以处于 $|0\rangle$ 和 $|1\rangle$ 之间的连续状态中，直到观测到它为止。这里再次强调，当量子比特被观测时，只能得到＂ 0 ＂或＂ 1 ＂的测量结果——每
个结果都有一定的概率。例如，量子比特可以处于状态
$$ \begin{equation*}\frac{1}{\sqrt{2}}|0\rangle+\frac{1}{\sqrt{2}}|1\rangle \tag{1.2}\end{equation*} $$
经过测量，会以 $50 \%\left(|1 / \sqrt{2}|^{2}\right)$ 的概率出现 0 ，以 $50 \%$ 的概率出现 1 。后面会经常用到这个状态，有时该状态也记作 $|+\rangle_{\circ}$
尽管如此奇特，但是量子比特确实是真实存在的，它们的存在和行为被大量实验所证实 （在 1.5 节和第 7 章会有讨论），并且可以使用许多不同的物理系统来实现量子比特。为便于直观感受，这里列出某些实现方式：如光子的两种极化；在均匀电磁场中核自旋的取向；如图 1－2所示绕电子轨道运行的两个状态。在原子模型中，电子可以处于基态或激发态，分别称为 $|0\rangle$ 和 $|1\rangle$ 。用适当的能量在适当的时间内将光照射在原子上，可以使电子在 $|0\rangle$ 态与 $|1\rangle$ 态之间移动。但更有趣的是，减少光照时间，最初处于状态 $|0\rangle$ 的电子可以移动到 $|0\rangle$ 和 $|1\rangle$ 态的中间，即 $|+\rangle$ 态。
图 1－2 用原子的两个电能级来表示量子比特
叠加态的可能含义或解释及量子系统观察的固有概率性质很自然地引起了极大的关注。但本书并不考虑这些内容。相反，我们的目的是给出具有预见性的数学和概念上的框架。
量子比特的一个有用的构想是如下的几何表示。由于 $|\alpha|^{2}+|\beta|^{2}=1$ ，式（1.1）可以改写为
$$ \begin{equation*}|\psi\rangle=\mathrm{e}^{\mathrm{i} \gamma}\left(\cos \frac{\theta}{2}|0\rangle+\mathrm{e}^{\mathrm{i} \varphi} \sin \frac{\theta}{2}|1\rangle\right) \tag{1.3}\end{equation*} $$
其中 $\theta, \varphi, \gamma$ 都是实数。在第 2 章会看到因子 $\mathrm{e}^{\mathrm{i} \gamma}$ 可以省去，因为它不能引起任何可观测的效应，因此可以写出其等效形式
$$ \begin{equation*}|\psi\rangle=\cos \frac{\theta}{2}|0\rangle+\mathrm{e}^{\mathrm{i} \varphi} \sin \frac{\theta}{2}|1\rangle \tag{1.4}\end{equation*} $$
其中 $\theta$ 和 $\varphi$ 定义了单位三维球上的一个点，如图 1－3 所示，该球面通常被称为布洛赫球面（Bloch sphere）。它是使得单个量子比特可视化的有效方法，也是量子计算和量子信息思想很好的测试平台。本章后面要讲的单量子比特的许多操作都在布洛赫球面的框架中描绘。不过切记这种直观想象有很大的局限，因为尚不清楚如何将布洛赫球面简单推广到多量子比特的情形。
一个量子比特代表了多少信息？看似荒谬，单位球上有无穷个点，因此原则上可以用 $\theta$ 的无限二进制扩展来存储莎士比亚的所有著作。然而，鉴于量子比特被观测时的行为，这个结论实际上是一种误导。回想一下，量子比特的测量只会给出 0 或 1 。此外，测量会改变量子比特的状态，将其从 $|0\rangle$ 和 $|1\rangle$ 的叠加态坍缩到与测量结果一致的特定状态。例如，如果 $|+\rangle$ 的测量值为 0 ，则量子比特测量后的状态将为 $|0\rangle$ 。为什么会发生这种坍塌？没有人知道。正如第 2 章所讨论的，这种行为只是量子力学的基本假设之一。与之相关的是，单次测量只能得到关于量子比特状态的一比特信息，从而解决了上述的佯谬。事实证明，只有在测量了无数多个完全相同的量子比特后，才能确定式（1.1）中的 $\alpha$ 和 $\beta$ 。
图 1－3 量子比特的布洛赫球面表示
但更有趣的问题可能是：如果不进行测量，一个量子比特能表示多少信息？这是个棘手的问题，因为如果不能测量，如何量化信息呢？尽管如此，这里还是包含了某些重要的观念，因为量子比特组成的封闭的量子系统在自然界中的演化，在未进行任何测量时，显然该系统会保持描述该状态的所有连续变量，如 $\alpha$ 和 $\beta$ 。从某种意义上说，在一个量子比特的状态里，大自然隐藏了大量的＂隐含信息＂。更有趣的是，我们很快就会看到这些额外信息的潜在数量随着量子比特的增长而指数式增长。弄清隐含的量子信息是本书许多部分所要解决的问题，是使量子力学成为信息处理的有力工具的核心。
希尔伯特空间很大。
－Carlton Caves
假设有两个量子比特。如果这两个量子比特是经典的，则有 4 种状态： $00,01,10,11$ 。相应地，一个两量子比特的系统有 4 个基本状态（简称基矢态），依次表示为：$|00\rangle,|01\rangle,|10\rangle,|11\rangle_{\circ}$ 一对量子比特还可以是这 4 个态的任意叠加形式，因此，两量子比特的量子态涉及将复系数（有时称为振幅）与每个计算基矢态相关联，因此一个描述两量子比特的态向量可以表示为
$$ \begin{equation*}|\psi\rangle=\alpha_{00}|00\rangle+\alpha_{01}|01\rangle+\alpha_{10}|10\rangle+\alpha_{11}|11\rangle \tag{1.5}\end{equation*} $$
类似于单量子比特，测量到 $x(=00,01,10,11)$ 的概率为 $\left|\alpha_{x}\right|^{2}$ ，测量后量子比特将变成 $|x\rangle_{\text {。 }}$ 此时由归一化条件可得，概率和满足 $\sum_{x \in{0,1}^{2}}\left|\alpha_{x}\right|^{2}=1$ ，其中记号 ${0,1}^{2}$ 表示每个字符取 0 或 1 的长度为 2 的串。对于一个两量子比特的系统，也可以测量一个量子比特的子集，比如说第一个量子比特。容易猜出它如何工作：测量第一个量子比特会以 $\left|\alpha_{00}\right|^{2}+\left|\alpha_{01}\right|^{2}$ 的概率得到 0 ，测量后
的状态为
$$ \begin{equation*}\left|\psi^{\prime}\right\rangle=\frac{\alpha_{00}|00\rangle+\alpha_{01}|01\rangle}{\sqrt{\left|\alpha_{00}\right|^{2}+\left|\alpha_{01}\right|^{2}}} \tag{1.6}\end{equation*} $$
注意到测量后的态被因子 $\sqrt{\left|\alpha_{00}\right|^{2}+\left|\alpha_{01}\right|^{2}}$ 正规化后仍满足归一化条件，正如我们对一个标准的量子比特所期待的一样。
贝尔态（Bell state）或 EPR 对是一个很重要的两量子态
$$ \begin{equation*} \frac{|00\rangle+|11\rangle}{\sqrt{2}} \tag{1.7} \end{equation*} $$
这个不起眼的状态与量子计算和量子信息中很多惊人的发现有关，是量子隐形传态和超密编码的关键要素，还是其他很多有趣的量子状态的原型，这些将在 1.3.7节和2.3节分别介绍。贝尔态的性质是当测量第一个量子比特时，以 $1 / 2$ 的概率得到 0 ，测量后得到态 $\left|\varphi^{\prime}\right\rangle=|00\rangle$ ，以 $1 / 2$ 的概率得到 1 ，测量后得到态 $\left|\varphi^{\prime}\right\rangle=|11\rangle$ 。因此第二个量子比特的测量结果总是和第一个相同，也就是说这两个量子比特的测量结果是相关的。事实上，通过先对第一个量子比特或第二个量子比特单独做一些操作来对贝尔态进行其他方式的测量，可以发现这两量子比特的测量结果之间有趣的相关性仍然存在。自从爱因斯坦，Podolsky 和 Rosen 的著名论文首次提出像贝尔态这种奇怪的性质，这类相关性成为大量研究的主题。EPR 的见解被约翰•贝尔（John Bell）继承并发扬光大，后者证明了一个惊人的结果：贝尔态测量的相关性比任何经典系统存在的相关性都更强。这一结果首次宣告量子力学允许的信息处理能力远超过经典世界，这些结果会在 2.6 节进行详细介绍。
更一般地，考虑 $n$ 量子比特的系统。系统的计算基矢态可表示为 $\left|x_{1} x_{2} \cdots x_{n}\right\rangle$ ，且这一系统的量子态可以用 $2^{n}$ 个振幅来刻画。当 $n=500$ 时，这个数就已超过整个宇宙原子的估算总数！任何现有的计算机都不可能存下所有这些复数。希尔伯特空间确实是一个很大的空间。但原则上即使是仅包含几百个原子的系统，自然界也需要计算这么大量的数据。自然界执行系统的演化就像在手里放了 $2^{500}$ 张不可见的草稿纸。我们渴望能利用这一巨大的潜在计算能力，但如何把量子力学过程看成计算呢？
量子态的变换可以用量子计算的语言来描述。量子计算机是由包含电路和基本量子门的量子电路构造的，类似于经典计算机是由包含连线和逻辑门的电路构造的。本节介绍简单的量子门，并举几个电路的例子来说明其应用，其中包含一个量子隐形传态的电路。
经典计算机电路由电路和逻辑门构成。连线用于在电路间传送信息，而逻辑门用于操控信息，把信息由一种形态转换成另一种形态。例如，考虑一个经典的单比特逻辑门，其中唯一非平凡成员是非门，非门的操作由真值表来定义，其中 $0 \rightarrow 1$ 和 $1 \rightarrow 0$ ，即将 0 态和 1 态交换。
可以类似地定义量子比特的量子非门吗？想象我们有一些过程可以把 0 态和 1 态交换，这一过程很显然是量子模拟非门的很好选项。但如果没有对量子门性质更多的认识，在 $|0\rangle$ 和 $|1\rangle$ 态上定义门的作用对 $|0\rangle$ 和 $|1\rangle$ 的叠加态不能起到作用。事实上，量子非门的作用是线性的，即可以把状态
$$ \begin{equation*} \alpha|0\rangle+\beta|1\rangle \tag{1.8} \end{equation*} $$
变换到 $|0\rangle$ 和 $|1\rangle$ 互换角色的新状态
$$ \begin{equation*} \alpha|1\rangle+\beta|0\rangle \tag{1.9} \end{equation*} $$
为什么量子非门是线性的而不是非线性的是一个非常有趣的问题，但答案并不显然。已经证实线性性质是量子力学的一般性质，也非常符合经验，更重要的是，非线性行为会导致譬如时间旅行，超光速通信和违反热力学第二定律等很多悖论。在后面章节还会更深人地阐述这一点，现在我们暂且先接受它。
基于量子门的线性性质，量子非门可以很方便地用矩阵表示，定义矩阵 $X$ 来表示非门如下：
$$ X \equiv\left[\begin{array}{ll} 0 & 1 \tag{1.10}\\ 1 & 0 \end{array}\right] $$
（用 $X$ 记号来表示量子非门是出于历史原因。）量子态 $\alpha|0\rangle+\beta|1\rangle$ 写成向量形式为
$$ \left[\begin{array}{l} \alpha \tag{1.11}\\ \beta \end{array}\right] $$
其中上面一项对应 $|0\rangle$ 的振幅，下面一项对应 $|1\rangle$ 的振幅，故量子非门的输出为
$$ X\left[\begin{array}{l} \alpha \tag{1.12}\\ \beta \end{array}\right]=\left[\begin{array}{l} \beta \\ \alpha \end{array}\right] $$
注意到非门的作用是把 $|0\rangle$ 态变成矩阵 $X$ 第 1 列对应的状态，而把 $|1\rangle$ 变成矩阵 $X$ 第 2 列对应的状态。
因此，量子门可以由一个 $2 \times 2$ 矩阵给出。对于用作表示量子门的矩阵有什么限制吗？答案是肯定的。回顾对量子态 $\alpha|0\rangle+\beta|1\rangle$ 归一化的要求是 $|\alpha|^{2}+|\beta|^{2}=1$ ，这对于作用了量子门后的状态 $\left|\psi^{\prime}\right\rangle=\alpha|0\rangle+\beta|1\rangle$ 也适用。事实上，表示单量子门的矩阵 $U$ 需要满足西性条件，即 $U^{\dagger} U=I$ ，其中 $U^{\dagger}$ 是 $U$ 的共轭转置（取 $U$ 的转置，再取复共轭得到），$I$ 是 $2 \times 2$ 的单位阵。例如，很容易验证对于非门有 $X^{\dagger} X=I$ 。
令人惊奇的是，这一西性限制是量子门的唯一限制。任何西矩阵都可以定义一个有效的量子门，一个有趣的推论是：和经典世界只有一个非平凡的单比特门——非门——相比，有很多非平凡的单量子比特门。其中两个我们后面会用到的重要门是 $Z$ 门
$$ Z \equiv\left[\begin{array}{cc} 1 & 0 \tag{1.13}\\ 0 & -1 \end{array}\right] $$
（其中保持 $|0\rangle$ 不变，翻转 $|1\rangle$ 的符号变为 $-|1\rangle$ ）和阿达玛门
$$ H \equiv \frac{1}{\sqrt{2}}\left[\begin{array}{cc} 1 & 1 \tag{1.14}\\ 1 & -1 \end{array}\right] $$
该门有时被描述为非门的平方根，它把 $|0\rangle$ 变到 $|0\rangle$ 和 $|1\rangle$ 的中间态 $(|0\rangle+|1\rangle) / \sqrt{2}$ ，而把 $|1\rangle$ 同样变到 $|0\rangle$ 和 $|1\rangle$ 的中间态 $(|0\rangle-|1\rangle) / \sqrt{2}$ 。不过需要注意，$H^{2}$ 不是非门，经过简单计算可发现 $H^{2}=I$ ，即两次作用 $H$ 等价于什么都没做。
阿达玛门是最有用的量子门之一，有必要在布洛赫球面上把它的作用展示出来。从图中可以看到，单量子比特门对应于球面上的旋转和反射。阿达玛操作恰好是先绕 $\hat{y}$ 轴旋转 $90^{\circ}$ ，再绕 $\hat{x}$轴旋转 $180^{\circ}$ ，等价地，也可以描述为绕轴＂$(\vec{x}+\vec{z}) / \sqrt{2}$＂旋转 $180^{\circ}$ ，如图 1－4 所示。图 1－5 比较了一些重要的单量子门和经典门的作用。
图 1－4 阿达玛门作用在输人态 $(|0\rangle+|1\rangle) / \sqrt{2}$ 上，在布洛赫球面上的可视化表达
图 1－5 单比特（左）和量子比特（右）逻辑门。其中 $\bar{x}$ 表示 $x$ 的逻辑非
因为存在无穷多个 $2 \times 2$ 的西矩阵，因此量子门的种类也是无穷的。不过，整个集合的属性可以从一个小很多的集合得到。例如，如专题 1.1 所示，任何单量子比特酉门都可以分解成一个旋转
$$ \left[\begin{array}{cc} \cos \frac{\gamma}{2} & -\sin \frac{\gamma}{2} \tag{1.15}\\ \sin \frac{\gamma}{2} & \cos \frac{\gamma}{2} \end{array}\right] $$
和一个可以理解为绕 $\hat{z}$ 轴旋转的门（后文中将会介绍）
$$ \left[\begin{array}{cc} \mathrm{e}^{-\mathrm{i} \beta / 2} & 0 \tag{1.16}\\ 0 & \mathrm{e}^{\mathrm{i} \beta / 2} \end{array}\right] $$
再加上一个（全局）相移——形如 $\mathrm{e}^{\mathrm{i} \alpha}$ 的常系数的乘积。这些门还可以进一步分解，不需要直接实现任意的 $\alpha, \beta, \gamma$ ，只需用一些特定的 $\alpha, \beta$ 和 $\gamma$ 来无限逼近任意的门。在该意义下，任意单量子门都可用一个有限的门集合来构造。更一般地，任意量子比特上的任何量子计算，都可以用一组通用的有限个门构成的集合生成。为获得这样的通用集合，我们首先要引人涉及更多量子比特的量子门。
在 4.2 节开始处，我们证明了任何 $2 \times 2$ 酉矩阵可以分解为
$$ U=\mathrm{e}^{\mathrm{i} \alpha}\left[\begin{array}{cc} \mathrm{e}^{-\mathrm{i} \beta / 2} & 0 \tag{1.17}\\ 0 & \mathrm{e}^{\mathrm{i} \beta / 2} \end{array}\right]\left[\begin{array}{cc} \cos \frac{\gamma}{2} & -\sin \frac{\gamma}{2} \\ \sin \frac{\gamma}{2} & \cos \frac{\gamma}{2} \end{array}\right]\left[\begin{array}{cc} \mathrm{e}^{-\mathrm{i} \delta / 2} & 0 \\ 0 & \mathrm{e}^{\mathrm{i} \delta / 2} \end{array}\right] $$
其中 $\alpha, \beta, \gamma$ 和 $\delta$ 都是实数。注意第二个矩阵仅是一次普通的旋转，第一个和最后一个矩阵都可以理解为不同平面上的旋转。该分解可对任何单量子比特逻辑门的操作进行精确描述。
现在我们将单量子比特拓展到多量子比特。图 1－6 展示了 5 种多比特经典门——与（AND），或（OR），异或（XOR），与非（NAND）和或非（NOR）门。一个重要的理论结果是任意布尔函数可以仅用 NAND 门的复合得到，所以 NAND 门也被称为通用门。相比之下，异或门自身或加上非门都不是通用门。一种理解这一点的方法是，作用一个异或门不会改变比特位整体的奇偶性。因此如果两个输人 $x$ 和 $y$ 具有相同的奇偶性，那么任何仅含非门和异或门的电路的输出也具有相同的奇偶性，所以排除了电路的通用性。
多量子比特量子逻辑门的原型是受控非（controlled－NOT 或 CNOT）门。此门有两个输入量子比特，分别是控制量子比特和目标量子比特。图 1－6 右上部分为受控非门的电路表示；上方的线表示控制量子比特，下方的线表示目标量子比特。受控非门的描述如下：如果控制量子比特被置为 0 ，那么目标量子比特不变；如果控制量子比特被置为 1 ，那么目标量子比特翻转。用公式表示为
$$ \begin{equation*} |00\rangle \rightarrow|00\rangle ;|01\rangle \rightarrow|01\rangle ;|10\rangle \rightarrow|11\rangle ;|11\rangle \rightarrow|10\rangle \tag{1.18} \end{equation*} $$
另外一种描述受控非门的方式是将它作为经典异或门的拓展，因为该门的作用可以总结为 $|A, B\rangle \rightarrow$ $|A, B \oplus A\rangle$ ，其中 $\oplus$ 表示模 2 加法，这正是异或门的作用结果。也就是说，控制量子比特与目标量子比特做异或运算，并存储到目标量子比特上。
（a）
（c）
（b）
（d）
（e）
（1）
图 1－6 图左边为一些标准单比特和多比特门，图右边为多量子比特门的原型，受控非门（controlled－NOT）。
矩阵 $U_{\mathrm{CN}}$ 为受控非门的矩阵表示，分别依次针对状态 $|00\rangle,|01\rangle,|10\rangle$ 和 $|11\rangle$ 的状态改变
还有一种描述受控非门作用的方法是矩阵表示，如图 1－6 右下方所示。很容易验证 $U_{\mathrm{CN}}$ 的第一列描述了对 $|00\rangle$ 的变换，对其他计算基矢态 $|01\rangle,|10\rangle,|11\rangle$ 也类似。和单量子比特的情况一样，如果要保持概率特性，需要满足 $U_{\mathrm{CN}}$ 是一个西矩阵，即 $U_{\mathrm{CN}}^{\dagger} U_{\mathrm{CN}}=I$ 。
我们注意到受控非门可以看成一种拓展的异或门。其他经典门，如与非门和通常的异或门，是否能在某种意义上以类似于量子非门表示经典非门的方式被视为西门呢？事实上这是不可能的，因为异或门和与非门本质上是不可逆的。例如，给定异或门的输出 $A \oplus B$ ，不可能确定输人 $A$ 和 $B$ ；异或门的不可逆性带来了信息的损失。另一方面，西量子门总是可逆的，因为西矩阵的逆仍然是西矩阵，所以量子门的逆总可以由另一个量子门表示。理解如何在这种可逆和不可逆意义下做经典逻辑运算，是懂得如何利用量子力学优势来进行计算的关键步骤。我们将在 1.4.4节解释如何做可逆运算的基本思想。
当然，除了受控非门，还有许多其他有趣的量子门。然而，在某种意义下受控非门和单量子比特门是其他所有门的原型，这是因为如下著名的通用性结果：任何多量子比特逻辑门可以由受控非门和单量子门组成。该结果的证明在 4.5 节，是与非门通用性的量子对应。
我们已经描述了对单比特量子态 $\alpha|0\rangle+\beta|1\rangle$ 的量子测量，最终分别以概率 $|\alpha|^{2}$ 和 $|\beta|^{2}$ 测得 0 和 1 ，并得到对应的状态 $|0\rangle$ 和 $|1\rangle$ 。事实上，量子力学允许更多种类的测量，尽管不能从单次测量中恢复 $\alpha$ 和 $\beta$ 。
注意到 $|0\rangle$ 和 $|1\rangle$ 仅仅是量子比特基的可能选择中的一种。另一种选择是集合 $|+\rangle \equiv(|0\rangle+$ $|1\rangle) / \sqrt{2}$ 和 $|-\rangle \equiv(|0\rangle-|1\rangle) / \sqrt{2}$ 。任意态 $|\psi\rangle=\alpha|0\rangle+\beta|1\rangle$ 都可以在状态 $|+\rangle$ 和 $|-\rangle$ 下重新表示为
$$ \begin{equation*} |\psi\rangle=\alpha|0\rangle+\beta|1\rangle=\alpha \frac{|+\rangle+|-\rangle}{\sqrt{2}}+\beta \frac{|+\rangle-|-\rangle}{\sqrt{2}}=\frac{\alpha+\beta}{\sqrt{2}}|+\rangle+\frac{\alpha-\beta}{\sqrt{2}}|-\rangle \tag{1.19} \end{equation*} $$
结果说明可以将 $|+\rangle$ 和 $|-\rangle$ 态看成计算基矢态，并且可以在这组新的基下进行测量。自然地，在
之后分别得到量子态 $|+\rangle$ 和 $|-\rangle$ 。
更一般地，给定任意一组基 $|a\rangle$ 和 $|b\rangle$ ，可以把任意态表示为这组基的线性组合的形式 $\alpha|a\rangle+$ $\beta|b\rangle$ 。此外，如果 $|a\rangle$ 和 $|b\rangle$ 是相互正交的，那么可以相对基 $|a\rangle$ 和 $|b\rangle$ 进行测量，以概率 $|\alpha|^{2}$ 得到 $a$ ，而以概率 $|\beta|^{2}$ 得到 $b$ 。为了满足概率限制 $|\alpha|^{2}+|\beta|^{2}=1$ ，正交性是必要的。类似地，多量子比特系统相对于任意正交基的测量原则上也是可能的。但这仅仅是在原则上是可能的，并不意味着这样的测量是容易实现的。我们之后还会回到如何有效地实现在任意基下的测量的问题上。
有很多理由需要用到这种推广形式的量子测量，但是根本上的理由是：这种形式可以让我们描述观测到的实验结果，正如 1.5.1 节我们对 Stern－Gerlach 实验的讨论一样。在 2.2.3节中，将会给出一个更复杂但是更方便（但本质上等价）的形式来描述量子测量。
我们已经讨论了几个简单的量子电路，现在让我们来更仔细地研究量子电路元件。图 1－7 是一个包含 3 个量子门的简单量子电路。该电路的读法是从左到右。电路中的每一条线代表量子电路的连线。这些连线不一定对应到物理的连线；它可能对应时间段，或者从空间的一处移动到另一处的物理粒子，比如光子。为了方便起见，假设电路的输人态全部为基矢态，一般是由 $|0\rangle$ 组成的态。这一规则常常在量子计算和量子信息的文献中被打破，但在这种情况下最好礼貌地告知读者。
图 1－7 交换两个量子比特的电路，以及表达这一常见而有用的电路的等价图解符号
图 1－7 中的电路实现了一个简单但是有用的任务——交换两个比特的量子态。为了明白该电路完成了交换操作，需要注意到这一串门在计算基 $|a, b\rangle$ 上的一系列作用，
$$ \begin{align*} |a, b\rangle & \longrightarrow|a, a \oplus b\rangle \\ & \longrightarrow|a \oplus(a \oplus b), a \oplus b\rangle=|b, a \oplus b\rangle \\ & \longrightarrow|b,(a \oplus b) \oplus b\rangle=|b, a\rangle \tag{1.20} \end{align*} $$
其中所有的加法为模 2 加法。综上所得，这个电路的作用是交换两个量子比特的状态。
一些经典电路的特征在量子电路中通常不会出现。首先，我们不允许＂环路＂，即从量子电路的一部分反馈到另一部分；我们称电路为非周期的（acyclic）。其次，经典电路允许连线汇合，即扇人操作（FANIN），导致单线包含所有输人位的按位或（bitwise OR）。显然这个操作不是可逆的，因此也不是西操作，所以我们不允许量子电路中有扇人操作。第三，与上面相反的操作，扇出操作（FANOUT），即产生一个比特的多个拷贝在量子电路中也是不允许的。事实上，量子
力学禁止量子比特的拷贝，因此扇出操作是不可能的。在下一小节中我们将会看到尝试设计拷贝量子比特的电路的例子。
现在我们需要引人新的量子门。为了方便起见，我们引人新的约定，如图 1－8 所示。假定 $U$是任意作用在 $n$ 量子比特的酉矩阵，因此 $U$ 可以看成作用在这些量子比特上的量子门。接下来我们可以定义受控 $U$（controlled－U）门，它是受控非门的一种自然的拓展。这样的门有单量子比特控制位，由带黑点的线表示，和 $n$ 量子比特目标位，由盒子 $U$ 表示。如果控制位置 0 ，则目标量子比特什么也不发生。如果控制位置 1，则门 $U$ 作用在目标量子比特上。受控 $U$ 门的原型是受控非门，它将 $U$ 门代替为 $U=X$ ，如图 1－9 所示。
图 1－8 受控 $U$ 门
图 1－9 受控非门的两种不同表示
另外一个重要的操作是测量，用仪表符号表示，如图 1－10 所示。正如前面所说，这个操作将单量子比特态 $|\psi\rangle=\alpha|0\rangle+\beta|1\rangle$ 转化为一个经典比特 $M$（与单量子比特区分，画为双线），它以 $|\alpha|^{2}$ 的概率为 0 ，以 $|\beta|^{2}$ 的概率为 1 。
$$ |\psi\rangle-\alpha \underline{\underline{M}} $$
图 1－10 表示测量的量子电路符号
我们将看到量子电路可用作描述所有量子过程的有用模型，包括但不限于计算，通信，甚至量子噪声。下面是几个简单的示例。
受控非门在说明量子信息的特有属性时非常有用。考虑复制经典比特的任务。它可以用一个经典受控非门完成，将待复制的比特（处于未知状态 $x$ ）和初始化为 0 的中间缓存器比特输人到该门即可，如图 1－11 所示。输出结果是两个比特，它们都具有相同的态 $x$ 。
图 1－11 经典和量子电路＂复制＂未知比特或量子比特
假定我们想通过相同的方法，利用受控非门来复制末知态 $|\psi\rangle=a|0\rangle+b|1\rangle$ 。两个输人量子比特可以写作
$$ \begin{equation*} [a|0\rangle+b|1\rangle]|0\rangle=a|00\rangle+b|10\rangle \tag{1.21} \end{equation*} $$
受控非门的作用是当第一个量子比特是 1 时翻转第二个量子比特，因此输出是 $a|00\rangle+b|11\rangle$ 。我们成功地复制了 $|\psi\rangle$ 吗？或者说，我们制备了态 $|\psi\rangle|\psi\rangle$ 吗？当 $|\psi\rangle=|0\rangle$ 或 $|\psi\rangle=|1\rangle$ 时，该电路确实做到了；因为用量子电路复制经典信息如 $|0\rangle$ 或 $|1\rangle$ 是可能的。然而对一般的量子态 $|\psi\rangle$ ，我们发现
$$ \begin{equation*} |\psi\rangle|\psi\rangle=a^{2}|00\rangle+a b|01\rangle+a b|10\rangle+b^{2}|11\rangle \tag{1.22} \end{equation*} $$
与 $a|00\rangle+b|11\rangle$ 相比，我们发现除了 $a b=0$ ，上述＂复制电路＂不能复制量子比特输人。事实上要制备一个未知量子态的拷贝是不可能的。量子态不能被复制的这条性质被称为不可克隆（no－ cloning）定理，是量子信息和经典信息的主要区别之一。不可克隆定理在专题 12.1 中将进行更详细的讨论；证明非常简单，我们建议你跳过这部分，现在去阅读证明。
基于量子比特以某种方式包含不能被测量直接得到的隐藏信息的直觉，还可以从另外的角度来看待图 1－11 电路的失败。考虑当我们测量量子态 $a|00\rangle+b|11\rangle$ 的任一比特时会发生什么。由前面的描述，我们以概率 $|a|^{2}$ 或概率 $|b|^{2}$ 得到 0 或 1 。然而，一旦一个量子比特被测量，量子态的另一个比特也就被确定，因而不能得到 $a$ 和 $b$ 的额外信息。在这个意义下，原始量子比特 $|\psi\rangle$ 承载的额外隐藏信息在第一次测量中丢失了，且不能恢复。然而，如果这个量子比特已经被复制，那么这个量子态的另一个比特仍然包含着隐藏信息。因此，量子态不能被复制。
让我们考虑一个略为复杂的电路，如图 1－12 所示，一个阿达玛门后面跟着一个受控非门，并按照所给的表变换 4 个计算基矢态。一个具体的例子，阿达玛门将输入 $|00\rangle$ 转化为 $(|0\rangle+|1\rangle)|0\rangle / \sqrt{2}$ ，随后受控非门输出量子态 $(|00\rangle+|11\rangle) / \sqrt{2}$ 。注意到：阿达玛变换使得第一个比特变成叠加态；然后该状态作为受控非门的控制输入，仅仅当控制位为 1 时目标位翻转。输出的态
$$ \begin{align*} \left|\beta_{00}\right\rangle & =\frac{|00\rangle+|11\rangle}{\sqrt{2}} \tag{1.23}\\ \left|\beta_{01}\right\rangle & =\frac{|01\rangle+|10\rangle}{\sqrt{2}} \tag{1.24}\\ \left|\beta_{10}\right\rangle & =\frac{|00\rangle-|11\rangle}{\sqrt{2}} \tag{1.25}\\ \left|\beta_{11}\right\rangle & =\frac{|01\rangle-|10\rangle}{\sqrt{2}} \tag{1.26} \end{align*} $$
被称为贝尔态，有时也被称为 EPR 态或 EPR 对，这是根据首次提出这些状态的奇特性质的学者贝尔，以及 Einstein（爱因斯坦），Podolsky 和 Rosen 的名字命名的。状态的记号 $\left|\beta_{00}\right\rangle,\left|\beta_{01}\right\rangle,\left|\beta_{10}\right\rangle,\left|\beta_{11}\right\rangle$可以由如下公式记忆
$$ \begin{equation*} \left|\beta_{x, y}\right\rangle \equiv \frac{|0, y\rangle+(-1)^{x}|1, \bar{y}\rangle}{\sqrt{2}} \tag{1.27} \end{equation*} $$
其中 $\bar{y}$ 是 $y$ 的非。
| 输入 | 输出 |
|---|---|
| $|00\rangle$ | $(|00\rangle+|11\rangle) / \sqrt{2} \equiv\left|\beta_{00}\right\rangle$ |
| $|01\rangle$ | $(|01\rangle+|10\rangle) / \sqrt{2} \equiv\left|\beta_{01}\right\rangle$ |
| $|10\rangle$ | $(|00\rangle-|11\rangle) / \sqrt{2} \equiv\left|\beta_{10}\right\rangle$ |
| $|11\rangle$ | $(|01\rangle-|10\rangle) / \sqrt{2} \equiv\left|\beta_{11}\right\rangle$ |
图 1－12 制备贝尔态的量子电路和输入输出量子＂真值表＂
接下来我们将用前几页提到的技术来理解一个令人惊奇且非常有趣的现象——量子隐形传态！量子隐形传态是在发送方和接收方之间甚至没有量子通信信道连接的情况下，进行量子态的传输。
量子隐形传态的工作原理如下。Alice 和 Bob 很久以前遇到过但是现在住得很远。当他们相遇时产生一个 EPR 对，当分开时他们各自拿走 EPR 对的一个量子比特。很多年以后，Bob 藏匿了起来。现在 Alice 有一项任务，是向 Bob 传递一个单比特量子态 $|\psi\rangle$ 。她不知道这个量子态的状态，并且只能向 Bob 发送经典信息。Alice 应当接受这项任务吗？
直观上来看，这对 Alice 来说很糟糕。她不知道将要发送给 Bob 的量子态 $|\psi\rangle$ 的状态，量子力学的定律又使她无法确定这个量子态，因为她手中只有一个 $|\psi\rangle$ 。更糟糕的是，即使她知道 $|\psi\rangle$的状态，精确地描述它也需要无穷多的经典信息，因为 $|\psi\rangle$ 的取值是一个连续的空间。所以即使知道 $|\psi\rangle$ 的状态，Alice 也将要花费无穷长的时间向 Bob 描述这一状态。这对 Alice 而言很不妙。幸运的是，量子隐形传态为 Alice 提供了利用 EPR 对向 Bob 发送 $|\psi\rangle$ 的一种方法，仅比经典通信多做一点工作。
解决方法可以概括为如下步骤：Alice 令量子比特 $|\psi\rangle$ 和她的一半 EPR 对相互作用，然后对她的两个比特进行测量，得到 4 种经典结果 $00, ~ 01, ~ 10$ 和 11 中的一种。根据 Alice 的经典信息， Bob 对他所持有的一半 EPR 对进行 4 种操作中的一种。令人惊讶的是，这样做他可以恢复原始的 $|\psi\rangle$ 。
图 1－13 所示量子电路给出了量子隐形传态更加精确的描述。将要进行隐形传态的态是 $|\psi\rangle=$ $\alpha|0\rangle+\beta|1\rangle$ ，其中 $\alpha$ 和 $\beta$ 是未知的振幅。电路的输人态 $\left|\psi_{0}\right\rangle$ 为
$$ \begin{align*} \left|\psi_{0}\right\rangle & =|\psi\rangle\left|\beta_{00}\right\rangle \tag{1.28}\\ & =\frac{1}{\sqrt{2}}[\alpha|0\rangle(|00\rangle+|11\rangle)+\beta|1\rangle(|00\rangle+|11\rangle)] \tag{1.29} \end{align*} $$
其中约定前两个（在左边）量子比特属于 Alice，第 3 个量子比特属于 Bob。由之前所述，Alice的第 2 个量子比特和 Bob 的量子比特是从一个 EPR 态中来的。Alice 将她的态送到一个受控非门，得到
$$ \begin{equation*} \left|\psi_{1}\right\rangle=\frac{1}{\sqrt{2}}[\alpha|0\rangle(|00\rangle+|11\rangle)+\beta|1\rangle(|10\rangle+|01\rangle)] \tag{1.30} \end{equation*} $$
她随即将第一个量子比特送到阿达玛门，得到
$$ \begin{equation*} \left|\psi_{2}\right\rangle=\frac{1}{2}[\alpha(|0\rangle+|1\rangle)(|00\rangle+|11\rangle)+\beta(|0\rangle-|1\rangle)(|10\rangle+|01\rangle)] \tag{1.31} \end{equation*} $$
通过重组各项，该量子态可以写成
$$ \begin{align*} \left|\psi_{2}\right\rangle=\frac{1}{2} & {[|00\rangle(\alpha|0\rangle+\beta|1\rangle)+|01\rangle(\alpha|1\rangle+\beta|0\rangle)} \tag{1.32}\\ & +|10\rangle(\alpha|0\rangle-\beta|1\rangle)+|11\rangle(\alpha|1\rangle-\beta|0\rangle)] \end{align*} $$
该表达式自然地分为 4 项。第一项中 Alice 处在状态 $|00\rangle$ ，Bob 处在状态 $\alpha|0\rangle+\beta|1\rangle$ ——这恰好是最初的态 $|\psi\rangle$ 。如果 Alice 做测量得到结果 00 ，那么 Bob 的系统将会处在态 $|\psi\rangle$ 。类似地，从上面的表达式，我们可以在给定 Alice 测量结果的情况下，读出 Bob 测量后的状态：
$$ \begin{align*} 00 \longmapsto\left|\psi_{3}(00)\right\rangle & \equiv[\alpha|0\rangle+\beta|1\rangle] \tag{1.33}\\ 01 \longmapsto\left|\psi_{3}(01)\right\rangle & \equiv[\alpha|1\rangle+\beta|0\rangle] \tag{1.34}\\ 10 \longmapsto\left|\psi_{3}(10)\right\rangle & \equiv[\alpha|0\rangle-\beta|1\rangle] \tag{1.35}\\ 11 \longmapsto\left|\psi_{3}(11)\right\rangle & \equiv[\alpha|1\rangle-\beta|0\rangle] \tag{1.36} \end{align*} $$
根据 Alice 的测量输出，Bob 的量子比特将会落到这 4 种可能的状态之一。当然，如果 Bob 想知道处于哪个状态，必须将 Alice 的测量结果告诉他——我们稍后说明，正是由于这个事实，量子隐形传态传送信息的速率无法超过光速。一旦 Bob 知道了测量结果，就能利用合适的量子门来 ＂修正＂他的态，从而恢复态 $|\psi\rangle_{\circ}$ 例如，当测量结果为 00 时，Bob 不需要做任何事。如果测量结果是 01 ，那么 Bob 需要通过 $X$ 门来修正量子态。如果测量结果是 10 ，那么 Bob 需要通过 $Z$门来修正量子态。如果测量结果是 11 ，那么 Bob 需要首先作用 $X$ 门，然后作用 $Z$ 门来修理量子态。总之，Bob 需要应用变换 $Z^{M_{1}} X^{M_{2}}$ 到他的量子比特上（注意，在量子电路图上时间从左到右，但在矩阵乘积项中先乘右边），就能得到态 $|\psi\rangle$ 。
图 1－13 一个量子比特隐形传态的电路。上面两条连线代表 Alice 的系统，下面的连线代表 Bob 的系统。仪表盘表示测量，双线代表它承载经典比特（回想一下，单线代表量子比特）
隐形传态有许多有趣的特性，部分特性在本书后面会讨论。我们现在对其中几个方面进行评述。首先，隐形传态是否允许超光速传递量子态？这十分奇怪，因为相对论告诉我们，如果存在超光速信息传输，那么就可以将信息发回到过去。幸运的是，量子隐形传态不会导致超光速的信息传递，因为为了完成隐形传态，Alice 必须通过经典信道将她的测量信息传递给 Bob。在 2.4 .3 节我们将看到，如果没有经典通信，量子隐形传态不能传递任何信息。经典信道受到光速的限制，导致了量子隐形传态不能超光速完成，这样就解决了这个佯谬。
量子隐形传态的第二个令人困惑的地方是它看上去生成了一个量子态的拷贝，这与 1.3.5 节所讨论的量子不可克隆定理相违背。这只是一种错觉，因为量子隐形传态过程后，只有目标量子比特处于状态 $|\psi\rangle$ ，而原始的数据比特依赖于对第一量子比特的测量结果，最终消失于计算基 $|0\rangle$或 $|1\rangle$ 中。
我们从量子隐形传态中能学到什么？很多！它不仅仅是可以实施在量子状态上的优雅技巧。量子隐形传态强调了量子力学中不同资源的互换性，显示出一个共享的 EPR 对加上两个经典比特的通信构成一个至少等于单量子比特通信的资源。量子计算和量子信息的研究揭示出大量资源转换的方法，其中许多建立在量子隐形传态的基础上。特别地，在第 10 章，我们将讨论量子隐形传态如何用于构造抗噪声的量子门，而在第 12 章将指出隐形传态与量子纠错码的性质紧密相关。尽管与其他主题有这些联系，但平心而论，我们才刚刚开始明白为什么量子隐形传态在量子力学中是可能的；在后面的章节中我们会尽力让读者真正理解。