量子计算导论：从线性代数到量子编程

本书清晰介绍了量子计算的核心概念、术语和技术，涵盖数学、物理学和信息论的基础知识，同时还提供量子编程动手实践。本书揭开了隐藏在量子计算中的技术概念和数学原理的神秘面纱，展示了量子计算系统的设计和构建方式，解释了量子计算系统对网络安全的影响，同时预览了抗量子密码学的进展。本书还扼要介绍了当今领先的量子编程语言Microsoft Q#和QASM。各章包含的习题测试和示例项目有助于读者深入理解和运用所学知识。本书文字浅显易懂，是量子计算初学者的完美指南。

查克??伊斯特姆（Chuck Easttom）博士在计算机安全、取证和密码学等领域出版了 31 部著作，其中部分著作已被 60 多所高校用作教材。伊斯特姆博士还在数字取证、网络战、密码学和应用数学等领域发表过大量学术论文（超过 70 篇），同时拥有 22 项计算机科学发明专利。他拥有 3 个博士学位：网络安全方面的科学博士学位（论文题目为《用于后量子计算的基于格的密码算法研究》），纳米技术方面的技术博士学位（论文题目为《复杂性对碳纳米管故障的影响》），以及计算机科学博士学位（论文题目为《关于图论在数字取证中的应用》）。此外，他还拥有应用计算机科学、教育学和系统工程等 3 个专业的硕士学位。伊斯特姆博士还是电气电子工程师学会（IEEE）和国际计算机协会（ACM）资深会员，国际密码研究协会（IACR）和系统工程国际委员会（INCOSE）会员，以及国际计算机协会杰出演讲者和电气电子工程师学会杰出访问者。伊斯特姆博士现任乔治城大学兼职讲师。

译者简介

王仁强，四川外国语大学副校长、教授、博士、博士生导师，兼任中国高等教育学会外语教学研究分会副理事长、中国辞书学会常务理事兼学术委员会委员，是国内外多种重要期刊匿名审稿专家；重庆市学术技术带头人，重庆英才??创新领军人才，重庆市高校哲学社会科学协同创新团队（语言大数据研究与应用创新团队）带头人；主要从事词典学、语料库语言学、认知语言学和语言类型学研究，近年来转向从事量子语言学研究；主持国家社科基金项目3项，出版著作8部，发表论文50余篇，获得省级教学科研成果奖4次；英国爱丁堡大学和美国新墨西哥大学访问学者。

吴铭，四川外国语大学英语学院外国语言学及应用语言学专业在读博士生，研究方向为语料库语言学和词典学，在核心期刊发表论文多篇。

本书聚焦量子计算如下内容：

◎清晰阐释核心概念、术语和技巧；

◎涵盖必备的物理、数学和信息论基础知识；

◎提供量子编程操作练习；

◎一本适合量子编程初学者的完美指南。

Chuck Easttom博士的著作涵盖量子计算的基础概念、术语、问题和操作要领。

凭借30多年计算机科学讲师、顾问和研究员经历，Chuck Easttom在书中对量子计算中的技术概念和数学原理进行了解密，展示了量子计算系统的设计和构建方式，解释了量子计算系统对网络安全的影响，同时概括了抗量子密码学的进展。该书扼要介绍了Microsoft Q#和QASM两种当今先进的量子编程语言，同时引导读者完成示例项目。全书各章的习题测试和示例项目有助于读者深入理解和运用所学知识。

不论你是在校生、专业人士还是管理人员，这本指南都有助于你为量子革命做好准备，同时增加你的就业机会。

前言

写书总是充满挑战，写一本关于量子计算的书更是如此。如果写得面面俱到，读者将不知所措，难以从中受益；如果写得过于简略，则难免挂一漏万。与量子计算有关的书（尤其是入门书）重在提供必备知识而非过于详尽的内容。我真诚希望自己实现了这个目标。

有的读者可能数学基础扎实，有的也许已涉足量子计算，不过对于那些缺乏背景知识的读者，也不用焦虑。本书旨在提供必备信息帮你跟上进度。这意味着本书每章的内容都精细入微。事实上，没有哪一章不能详尽到单独成书！

如果某个章节对你而言比较陌生或者特别难以理解，也别气馁。在讨论复杂话题时，这种情况再正常不过了。如果不熟悉线性代数，本书第1章“线性代数入门”会介绍一些新概念或难以理解的概念。我时常告诫学生不要对自己太过苛刻。当你在某个概念上苦苦挣扎，却发现对他人（可能是教授或作者本人）似乎易如反掌，你就很容易气馁，认为自己并不适合这个领域。若确实如此，那么有朝一日你会不会也像其他人那样，轻松理解之前那些难以理解的概念呢？没有人会告诉你，如今成为专家的那些人，一开始接触这个领域时也学得很费劲。所以，你觉得学起来很吃力，那再正常不过了。请别灰心！你可能需要多次阅读本书某些章节。即使读完本书，大致了解整体内容，但在特定细节上也可能没有吃透。不必大惊小怪。这个话题本来就难。

数理知识丰富的读者可能会觉得本书的某些章节过于艰深或太过简略，的确如此。在写一本量子计算入门书时，难以权衡内容的深浅。阅读本书时，若发现某些章节内容的深浅程度与你现有的认知有所出入，还望海涵。

最重要的是，本书开启了一场惊心动魄的旅途，所涉内容均为计算机科学的前沿话题。无论你是否拥有深厚的背景知识，是否能够轻松掌握本书内容（在此之前你也许了解部分内容），是否会在每一页上挣扎，最终都会殊途同归。你将面对一个奇异的崭新世界。你将了解量子力学的基本原理，了解量子计算革命，甚至还能学到一些新的数学知识。所以，请别再纠结是否掌握了某个晦涩的概念，好好享受阅读过程吧！

致谢

本书的顺利出版归功于大家的帮助。首先，我想感谢伊扎特·阿尔斯马迪（Izzat Alsmadi）教授（得克萨斯农工大学圣安东尼奥分校）和雷妮塔·穆里米（Renita Murimi）教授（达拉斯大学），他们谦逊又热情，以专业的眼光审读了本书每章内容。责任编辑克里斯·克利夫兰（Chris Cleveland）耐心且细致的工作对本书的出版至关重要。我必须承认，编辑本书不是件易事。此外，我还想感谢巴特·里德（Bart Reed）对本书进行的润色。以上各位成员都做得非常出色，帮助我写出了一本清晰而准确的书，使得读者能够学习量子计算这个极具挑战性的话题。

第1章 线性代数入门 1
1．1 什么是线性代数 2
1．2 代数入门 3
1．2．1 群、环和域 5
1．3 矩阵数学 9
1．3．1 矩阵加法和乘法 10
1．3．2 矩阵转置 12
1．3．3 子矩阵 13
1．3．4 单位矩阵 14
1．3．5 深入了解矩阵 15
1．4 向量和向量空间 22
1．5 集合论 24
1．6 小结 27
第2章 复数 31
2．1 什么是复数 31
2．2 复数的代数运算 33
2．3 用图形表示复数 37
2．4 用向量表示复数 44
2．5 泡利矩阵 47
2．5．1 泡利矩阵的代数性质 51
2．6 超越数 54
2．7 小结 55
第3章 用于量子计算的物理学基础 57
3．1 量子之旅 58
3．2 量子物理学要点 62
3．2．1 基本原子结构 62
3．2．2 希尔伯特空间 65
3．2．3 不确定性 67
3．2．4 量子态 70
3．2．5 量子纠缠 72
3．3 小结 74
第4章 用于量子计算的计算机科学基础 77
4．1 数据结构 78
4．1．1 列表 79
4．1．2 二叉树 85
4．2 算法 85
4．2．1 排序算法 87
4．3 计算复杂性理论 90
4．3．1 圈复杂度 91
4．3．2 霍尔斯特德度量指标 91
4．4 编码理论 92
4．5 逻辑门 93
4．5．1 与 94
4．5．2 或 94
4．5．3 异或 94
4．5．4 逻辑门的应用 95
4．6 计算机架构 98
4．7 小结 100
第5章 基本信息论 103
5．1 基本概率 104
5．1．1 基本概率规则 104
5．2 集合论 106
5．3 信息论 109
5．3．1 定理1：香农的信源编码定理 110
5．3．2 定理2：有噪信道编码定理 110
5．3．3 信息熵 110
5．3．4 信息多样性 114
5．4 量子信息论 116
5．5 小结 117
第6章 基本量子理论 120
6．1 量子力学进阶 121
6．1．1 狄拉克符号 121
6．1．2 哈密顿算符 122
6．1．3 波函数坍缩 123
6．1．4 薛定谔方程 126
6．2 量子退相干 127
6．3 量子电动力学 129
6．4 量子色动力学 132
6．5 费曼图 133
6．6 小结 134
第7章 量子纠缠与量子密钥分发 137
7．1 量子纠缠 137
7．2 诠释 142
7．2．1 哥本哈根诠释 143
7．2．2 多重世界诠释 144
7．2．3 退相干历史诠释 144
7．2．4 客观坍缩理论 145
7．3 量子密钥交换 145
7．3．1 BB84 协议 146
7．3．2 B92 协议 148
7．3．3 SARG04 协议 148
7．3．4 六态协议 150
7．3．5 E91协议 150
7．3．6 协议的实现 150
7．4 小结 151
第8章 量子架构 153
8．1 深入了解量子位 153
8．2 量子门 157
8．2．1 阿达玛门 158
8．2．2 相移门 160
8．2．3 泡利门 160
8．2．4 交换门 161
8．2．5 弗雷德金门 162
8．2．6 托佛利门 162
8．2．7 受控门 162
8．2．8 伊辛门 163
8．2．9 Gottesman-Knill 定理 164
8．3 与门有关的更多信息 165
8．4 量子电路 166
8．5 D-Wave量子架构 168
8．5．1 超导量子比特 169
8．6 小结 170
第9章 量子硬件 172
9．1 量子位 172
9．1．1 光子 173
9．1．2 电子 175
9．1．3 离子 176
9．1．4 核磁共振量子计算 177
9．1．5 玻色-爱因斯坦凝聚态量子计算 178
9．1．6 砷化镓量子点 179
9．2 需要多少个量子位 180
9．3 解决退相干问题 181
9．3．1 过冷 183
9．3．2 处理噪声 184
9．3．3 过滤噪声 185
9．4 拓扑量子计算 185
9．4．1 编织理论基础 185
9．4．2 编织理论进阶 186
9．4．3 拓扑计算进阶 186
9．5 量子计算机必备组件 186
9．5．1 量子数据平面 187
9．5．2 测量平面 187
9．5．3 控制处理器平面 187
9．6 量子网络 187
9．6．1 东京量子密钥分发 187
9．6．2 京沪干线 188
9．6．3 墨子号卫星 188
9．6．4 分布式量子计算 188
9．7 小结 188
第10章 量子算法 191
10．1 何为算法 191
10．2 多伊奇算法 194
10．3 多伊奇-约萨算法 197
10．4 伯恩斯坦-瓦兹拉尼算法 198
10．5 西蒙算法 200
10．6 肖尔算法 201
10．6．1 量子周期查找函数 204
10．7 格罗弗算法 207
10．8 小结 209
第11章 当代非对称算法 211
11．1 RSA 212
11．1．1 RSA示例1 214
11．1．2 RSA示例2 214
11．1．3 因式分解RSA密钥 215
11．2 迪菲-赫尔曼算法 216
11．2．1 艾尔加玛尔加密算法 217
11．2．2 MQV 218
11．3 椭圆曲线 219
11．3．1 椭圆曲线迪菲??赫尔曼算法 223
11．3．2 椭圆曲线数字签名算法 224
11．4 小结 225
第12章 量子计算对密码学的影响 227
12．1 非对称密码学 228
12．1．1 需要多少个量子位 229
12．2 特定算法 230
12．2．1 RSA 230
12．2．2 迪菲-赫尔曼 230
12．2．3 椭圆曲线密码 231
12．2．4 对称密码 231
12．2．5 密码散列 231
12．3 具体应用 232
12．3．1 数字证书 232
12．3．2 SSL/TLS 233
12．3．4 公钥基础设施 236
12．3．5 虚拟专用网络 238
12．3．6 安全外壳协议 239
12．4 小结 240
第13章 基于格的密码学 242
13．1 基于格的数学问题 243
13．1．1 最短整数问题 245
13．1．2 最短向量问题 246
13．1．3 最近向量问题 246
13．2 加密算法 247
13．2．1 NTRU 247
13．2．2 GGH 250
13．2．3 佩克特环签名算法 251
13．3 解决格问题 254
13．3．1 LLL算法 254
13．4 小结 256
第14章 多元密码学 259
14．1 数学 259
14．2 Matsumoto-Imai算法 261
14．3 隐域方程 263
14．4 多元二次数字签名方案 265
14．5 SFLASH 266
14．6 小结 268
第15章 后量子密码学的其他方法 270
15．1 散列函数 270
15．1．1 Merkle-Damgaard 271
15．1．2 SWIFFT 271
15．1．3 兰伯特签名 274
15．2 基于编码的密码学 275
15．2．1 McEliece 275
15．2．2 Niederreiter密码系统 277
15．3 超奇异同源密钥交换 278
15．3．1 椭圆曲线 278
15．3．2 超奇异同源迪菲-赫尔曼算法 281
15．4 小结 284
第16章 使用Q# 287
16．1 基本编程概念 287
16．1．1 变量和语句 288
16．1．2 控制结构 290
16．1．3 面向对象程序设计 292
16．2 Q#入门 293
16．3 格罗弗算法 298
16．3．1 格罗弗算法回顾 298
16．3．2 格罗弗算法代码 300
16．4 多伊奇-约萨算法 303
16．4．1 多伊奇-约萨算法回顾 303
16．4．2 多伊奇-约萨算法代码 304
16．5 位翻转 306
16．6 小结 307
第17章 使用量子汇编语言 309
17．1 基本编程概念 310
17．1．1 指令 310
17．1．2 命令行 313
17．2 开始使用QASM 314
17．3 量子纠错 315
17．4 格罗弗算法 317
17．4．1 格罗弗算法回顾 317
17．4．2 格罗弗算法代码 318
17．5 多伊奇-约萨算法 320
17．5．1 多伊奇-约萨算法回顾 320
17．5．2 多伊奇-约萨算法代码 321
17．6 小结 322
附录 章节测试答案 324