量子计算与量子信息：10周年版

《量子计算与量子信息：10周年版》介绍了量子计算和量子信息领域的主要思想和技术。该领域的快速发展及其跨学科的性质使得新来者很难全面地了解其中重要的技术和研究成果。本书共分为3 部分：第1 部分概述了量子计算和量子信息领域的主要思想和研究成果，并介绍了计算机科学、数学和物理学领域的相关背景材料，这些材料是深入理解量子计算和量子信息所必需的；第2 部分详细描述了量子计算；第3 部分是关于量子信息的，内容涉及什么是量子信息，如何使用量子态表示和交流信息，以及如何描述和处理量子信息和经典信息的破坏。

作者简介

Michael A．Nielsen ，昆士兰大学博士后研究员。出生于澳大利亚布里斯班，在昆士兰大学接受教育，在获得博士学位之前获得数学和物理研究生学位。他曾在洛斯阿拉莫斯国家实验室担任访问职务，并曾在加利福尼亚理工学院担任托尔曼博士后研究员。

Isaac L．Chuang，斯坦福大学的顾问教授。他在斯坦福大学获得了电气工程博士学位，赫兹基金会的研究员，同时还拥有麻省理工学院的物理学和电气工程学位。

译者介绍

孙晓明，中国科学院计算技术研究所研究员。主要研究领域为算法与计算复杂性、量子计算等。曾获首批国家自然科学基金优秀青年基金资助，入选zhongzubu首批万人计划青年拔尖人才，中国密码学会优秀青年奖、密码创新二等奖。目前担任中国计算机学会理论计算机科学专委会主任，全国量子计算与测量标准化技术委员会委员，还担任《软件学报》《计算机研究与发展》《中国科学:信息科学》《Information and Computation》《JCST》《FCS》等杂志编委或青年编委。

尚云，中国科学院数学与系统科学研究院研究员、CCF量子计算专委会常务委员、CCF杰出会员。主要研究兴趣是量子计算基础理论、量子游走、量子机器学习、量子点元胞自动机电路的自动设计与优化等，发表论文50多篇。获CCF科学技术奖自然科学二等奖(1/5，2021)，英国皇家物理学会IOP高引用作者奖(2021),王宽诚优秀女科学家专项奖(2012)等。

李绿周，中山大学计算机学院量子计算与计算机理论研究所教授、中国计算机学会（CCF）量子计算专业组副主任、CCF理论计算机科学专委会常务委员、CCF杰出会员。2009年6月毕业于中山大学计算机科学系，获博士学位。长期从事量子计算方面的研究，目前研究兴趣具体包括量子算法与复杂性、量子机器学习、量子线路优化等，在国内外知名学术期刊发表论文60余篇，出版学术专著1部，“量子计算模型与算法的研究”获得广东省杰出青年基金项目资助。

尹璋琦，北京理工大学物理学院量子技术研究中心教授，CCF 量子计算专委委员。1999 年到 2009 年，在西安交通大学先后获物理学学士、硕士和博士学位。2007 至 2009 年在美国密歇根大学公派联合培养。2010 到 2019 年先后在中科院武汉物理与数学研究所、中国科学技术大学和清华大学工作。2019 年调入北京理工大学，研究兴趣为量子信息与量子精密测量、宏观系统量子效应等，发表论文 70 余篇。入选教育部青年长江学者（2020），任《中国科学：物理学力学天文学（英文版）》青年编委。

魏朝晖，清华大学丘成桐数学科学中心助理教授、CCF量子计算专委委员。2009年于清华大学计算机系获得博士学位后前往新加坡量子研究中心任Research Fellow，于2018年返回清华任教。长期从事量子计算方面的理论研究，主要研究兴趣包括量子计算复杂性、量子信息论、量子算法、量子纠错、量子人工智能等，学术成果发表在包括

《IEEE Transactions on Information Theory》《Mathematical Programming》《Physical Review Letters》等在内的知名学术期刊上。2020年获得北京市优秀本科毕业论文指导教师奖。

田国敬，中科院计算所副研究员、CCF量子计算专业组委员、CCF理论计算机专委委员。主要研究方向是：量子算法设计、量子电路优化、量子非局域性、量子模拟等，目前共发表论文17篇，博士毕业论文被评为中国通信学会优秀博士学位论文（全国共10篇）。作为项目负责人，先后获得了北京市自然科学基金和国家自然科学基金青年项目的资助，并于2019年入选了博士后创新人才支持计划（全国计算机专业共16人）。

本书是量子计算与量子信息领域的经典著作。

本书是量子信息领域及物理领域被引用次数高的图书之一。

全球许多高校都使用该书作为量子计算课程的教材。

本书可以多种方式使用。它可以用作各种课程的基础，不管是有关量子计算和量子信息的特 定主题的短期讲座课程，还是涵盖整个领域的全年课程。对想要了解一点量子计算和量子信息的 读者，或者想要了解研究前沿的学者，它可以用来自学。它也可以用作该领域当前研究人员的参 考书。我们希望新进入这个领域的研究者会发现它作为一份介绍材料是十分有价值的。

给自学者的话

本书被设计为对自学者也是易于理解的。全书拥有大量的习题，可以作为理解正文内容的自 我测验。目录和章末的总结可用以快速确定要深入学习的章节。依赖图有助于确定书中 内容的阅读顺序。

给教师的话

本书涵盖了广泛的主题，因此可以用作各种课程的基础。 xviii前言 对于一学期的量子计算课程，可以根据班级的背景从第 1 章到第 3 章中选择部分内容，接着 是关于量子电路的第 4 章、关于量子算法的第 5 章和第 6 章，以及从关于物理实现的第 7 章中选 择的内容和理解量子纠错的第 8 章到第 10 章，其中第 10 章应特别关注。 对于一学期的量子信息课程，可以根据班级的背景从第 1 章到第 3 章中选择部分内容，接着 是关于量子纠错的第 8 章到第 10 章，以及分别关于量子熵和量子信息论的第 11 章和第 12 章。 对于一整年的课程，可以覆盖书中的所有内容，且有时间可从若干章节的“背景资料与延伸 阅读”部分选择额外的内容阅读。量子计算和量子信息也非常适合于学生的独立研究项目。 除了用于量子计算和量子信息的课程，我们还希望有另外一种使用本书的方式，即作为物理 系学生量子力学入门课的课本。传统的量子力学的介绍严重依赖于偏微分方程的数学框架，我们 认为这常常掩盖了其中的基本思想。量子计算与量子信息为理解量子力学的基本概念和独特之 处提供了一个出色的概念上的试验场，而无须基于繁重的数学机制。此类课程的重点是第 2 章中 的量子力学入门、第 4 章中关于量子电路的基础内容、第 5 章和第 6 章中关于量子算法的部分内 容、第 7 章中量子计算的物理实现，以及根据个人品味从本书第 3 部分中任意选取的内容。

给学生的话

我们编写这本书时尽可能使其自洽。主要的例外是，有时我们省略了那些需要读者自行验证 才能相信的论证，这些通常作为习题给出。建议读者在阅读本书时至少应该尝试所有的习题。除 少数例外，这些习题均可以在几分钟内完成。如果在大量习题中遇到很多困难，这可能表明需要 回顾一个或多个关键的概念。

本书介绍量子计算和量子信息领域的主要思想和技术。该领域的快速发展及其跨学科的性质 使得新来者很难全面地了解其中重要的技术和研究成果。

因此，写作本书的目的是双重的。第一个目的是介绍理解量子计算和量子信息所必需的计算 机科学、数学和物理学的背景材料，具有这三个学科中至少一科或多个学科背景知识的新研究生 都能够理解这些内容；最重要的要求是具备一定程度的数学基础，以及对学习量子计算和量子信 息的兴趣。第二个目的是详细介绍量子计算和量子信息的主要结果。通过全面的学习，读者应该 对这一令人兴奋的领域的基本工具和结果有实际的了解，这既可以作为其通识教育的一部分，也 可以作为开展量子计算和量子信息独立研究的序幕。

本书结构

本书的基本结构如图 1 所示。本书共分 3 部分。一般的策略是在可能的情况下从具体开始， 逐步抽象。因此，我们在研究量子信息之前先研究量子计算；在介绍量子信息理论更一般的结果 之前，先给出特定的量子纠错码。全书始终尝试在讨论一般理论之前先介绍实例。

第 1 部分概述量子计算和量子信息领域的主要思想和结果，并介绍计算机科学、数学和物理 学的背景材料，这些材料是深入理解量子计算和量子信息所必需的。第 1 章是导论性章节，概述 该领域的历史发展和基本概念，突出沿途的一些重要开放问题。相关材料的结构使得即使没有计 算机科学或物理学背景也可以理解。第 2 章和第 3 章拓展用于更详细理解的背景材料，分别深入 论述量子力学和计算机科学的基本概念。读者可以根据自己的背景，或多或少地阅读这一部分的 不同章节，并在必要时返回查阅，以弥补对量子力学和计算机科学基础知识的缺失。

第 2 部分详细描述量子计算。第 4 章介绍执行量子计算所需要的基本要素，并介绍许多可用 于开发更复杂的量子计算应用的基本运算。第 5 章和第 6 章分别介绍量子傅里叶变换和量子搜索 算法，这是目前已知的两种基本量子算法。第 5 章还解释如何使用量子傅里叶变换来解决大整数 素数分解和离散对数问题，以及这些结果对密码学的重要性。第 7 章以在实验室中成功演示的几 种实现为例，介绍量子计算机好的物理实现的一般设计原则和标准。

第 3 部分是关于量子信息的：什么是量子信息，如何使用量子态表示和交流信息，以及如何 描述和处理量子信息和经典信息的破坏。第 8 章介绍了解现实世界中的量子信息处理所需的量子 噪声的属性，以及量子运算形式主义，这是一种了解量子噪声的强大数学工具。第 9 章描述量子 信息的距离度量，它使我们能够在数量上精确地说出两个量子信息相似的含义。第 10 章介绍量 子纠错码，可用于保护量子计算不受噪声影响。本章的一个重要结果是阈值定理，它表明对于现 实的噪声模型，噪声在原则上不会严重阻碍量子计算。第 11 章介绍熵的基本信息论概念，解释 经典信息论和量子信息论中熵的许多性质。最后，第 12 章讨论量子态和量子通信通道的信息携 带特性，详细介绍这种系统对于经典信息和量子信息的传输，以及秘密信息的传输可能具有的许 多奇怪和有趣的特性。

大量的习题和问题贯穿整本书。习题旨在巩固对基本材料的理解，并出现在正文中。除少数 例外，只需要几分钟即可轻松解决这些习题。问题出现在每章的末尾，目的是介绍那些在正文中 没有足够的空间来介绍的新的有趣的材料。这些问题通常是多方面的，目的是在某种程度上深入 拓展特定的思路。在本书付印之时，一些问题仍未解决。在这种情况下，将在问题说明中予以注 明。每章都以本章主要结果的摘要作为结尾，并以“背景资料与延伸阅读”部分作为结束语，该 部分描述本章主要思想的发展，给出整章的引用和参考文献，并提供建议供进一步阅读。

本书的文前包含详细的目录，建议浏览。还有一个术语和符号指南，可以帮助你阅读本书。 本书的文后包含 6 个附录和一个参考文献列表。

第1章简介与概述

1.1全貌

1.1.1量子计算和量子信息的历史

1.1.2未来发展方向

1.2量子比特

1.3量子计算

1.3.1单量子比特门

1.3.2多量子比特门

1.3.3除计算基外的测量

1.3.4量子电路

1.3.5量子比特复制电路？

1.3.6示例：贝尔态

1.3.7示例：量子隐形传态

1.4量子算法

1.4.1量子计算机的经典计算

1.4.2量子并行性

1.4.3Deutsch算法

1.4.4Deutsch–Jozsa算法

1.4.5量子算法总结

1.5实验量子信息处理

1.5.1Stern-Gerlach实验

1.5.2实用量子信息处理的前景

1.6量子信息

1.6.1量子信息理论：一些问题

1.6.2更广泛背景下的量子信息

第1部分基础概念

第2章量子力学基础

2.1线性代数

2.1.1基和线性无关性

2.1.2线性算子和矩阵

2.1.3泡利矩阵

2.1.4内积

2.1.5特征向量和特征值

2.1.6伴随和厄米算子

2.1.7张量积

2.1.8算子函数

2.1.9对易式和反对易式

2.1.10极式分解和奇异值分解

2.2量子力学的假设

2.2.1状态空间

2.2.2演化

2.2.3量子测量

2.2.4区分量子状态

2.2.5投影测量

2.2.6POVM测量

2.2.7相位

2.2.8复合系统

2.2.9量子力学：总览

2.3应用：超密编码

2.4密度算子

2.4.1量子状态的系综

2.4.2密度算子的一般性质

2.4.3约化密度算子

2.5施密特分解与纯化

2.6EPR和贝尔不等式

第3章计算机科学简介

3.1计算模型

3.1.1图灵机

3.1.2电路

3.2计算问题的分析

3.2.1如何量化计算资源

3.2.2计算复杂性

3.2.3判定性问题与复杂性类P与NP

3.2.4更多的复杂性类

3.2.5能量与计算

3.3关于计算科学的观点

第4章量子电路

4.1量子算法

4.2单量子比特运算

4.3受控运算

4.4测量

4.5通用量子门

4.5.1两级酉门是通用的

4.5.2单量子比特和受控非门是通用的

4.5.3通用运算的一个离散集合

4.5.4逼近任意酉门一般是难的

4.5.5量子计算复杂度

4.6量子电路模型计算总结

4.7量子系统的模拟

4.7.1行为模拟

4.7.2量子模拟算法

4.7.3说明性示例

4.7.4量子模拟展望

第2部分量子计算

第5章量子傅里叶变换及其应用

5.1量子傅里叶变换

5.2相位估计

5.3应用：求阶与因子分解问题

5.3.1应用：求阶

5.3.2应用：因子分解

5.4量子傅里叶变换的一般应用

5.4.1周期查找

5.4.2离散对数问题

5.4.3隐含子群问题

5.4.4其他的量子算法？

第6章量子搜索算法

6.1量子搜索算法

6.1.1Oracle

6.1.2过程

6.1.3几何可视化

6.1.4性能

6.2作为量子模拟的量子搜索

6.3量子计数

6.4NP完全问题解的加速

6.5无结构数据库的量子搜索

6.6搜索算法的最优性

6.7黑盒算法的极限

第7章量子计算机：物理实现

7.1指导性原则

7.2量子计算的条件

7.2.1量子信息的表示

7.2.2执行酉变换

....

12.5.2纠缠蒸馏与稀释

12.5.3纠缠蒸馏与量子纠错

12.6量子密码学

12.6.1私钥密码学

12.6.2隐私放大和信息协调

12.6.3量子密钥分发

12.6.4隐私和相干信息

12.6.5量子密钥分发的安全性

附录A概率论基础

附录B群论

附录CSolovay-Kitaev定理

附录D数论

附录E公钥密码和RSA密码系统

附录FLieb定理的证明

参考文献