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

前言 写书总是充满挑战，写一本关于量子计算的书更是如此。如果写得面面俱到，读者将不知所措，难以从中受益；如果写得过于简略，则难免挂一漏万。与量子计算有关的书（尤其是入门书）重在提供必备知识而非过于详尽的内容。我真诚希望自己实现了这个目标。 有的读者可能数学基础扎实，有的也许已涉足量子计算，不过对于那些缺乏背景知识的读者，也不用焦虑。本书旨在提供必备信息帮你跟上进度。这意味着本书每章的内容都精细入微。事实上，没有哪一章不能详尽到单独成书！ 如果某个章节对你而言比较陌生或者特别难以理解，也别气馁。在讨论复杂话题时，这种情况再正常不过了。如果不熟悉线性代数，本书第1章“线性代数入门”会介绍一些新概念或难以理解的概念。我时常告诫学生不要对自己太过苛刻。当你在某个概念上苦苦挣扎，却发现对他人（可能是教授或作者本人）似乎易如反掌，你就很容易气馁，认为自己并不适合这个领域。若确实如此，那么有朝一日你会不会也像其他人那样，轻松理解之前那些难以理解的概念呢？没有人会告诉你，如今成为专家的那些人，一开始接触这个领域时也学得很费劲。所以，你觉得学起来很吃力，那再正常不过了。请别灰心！你可能需要多次阅读本书某些章节。即使读完本书，大致了解整体内容，但在特定细节上也可能没有吃透。不必大惊小怪。这个话题本来就难。 数理知识丰富的读者可能会觉得本书的某些章节过于艰深或太过简略，的确如此。在写一本量子计算入门书时，难以权衡内容的深浅。阅读本书时，若发现某些章节内容的深浅程度与你现有的认知有所出入，还望海涵。 最重要的是，本书开启了一场惊心动魄的旅途，所涉内容均为计算机科学的前沿话题。无论你是否拥有深厚的背景知识，是否能够轻松掌握本书内容（在此之前你也许了解部分内容），是否会在每一页上挣扎，最终都会殊途同归。你将面对一个奇异的崭新世界。你将了解量子力学的基本原理，了解量子计算革命，甚至还能学到一些新的数学知识。所以，请别再纠结是否掌握了某个晦涩的概念，好好享受阅读过程吧！ 致谢 本书的顺利出版归功于大家的帮助。首先，我想感谢伊扎特·阿尔斯马迪（Izzat Alsmadi）教授（得克萨斯农工大学圣安东尼奥分校）和雷妮塔·穆里米（Renita Murimi）教授（达拉斯大学），他们谦逊又热情，以专业的眼光审读了本书每章内容。责任编辑克里斯·克利夫兰（Chris Cleveland）耐心且细致的工作对本书的出版至关重要。我必须承认，编辑本书不是件易事。此外，我还想感谢巴特·里德（Bart Reed）对本书进行的润色。以上各位成员都做得非常出色，帮助我写出了一本清晰而准确的书，使得读者能够学习量子计算这个极具挑战性的话题。

Credits............................................................................................................... 15 Chapter 1 线性代数入门 ................................................................................. 16 1.1 什么是线性代数 ................................................................................................. 17 1.2 代数入门 ............................................................................................................. 18 1.2.1 群、环和域 ............................................................................................. 20 1.3 矩阵数学 ............................................................................................................. 24 1.3.1 矩阵加法和乘法 ..................................................................................... 25 1.3.2 矩阵转置 ................................................................................................. 27 1.3.3 子矩阵 ..................................................................................................... 28 1.3.4 单位矩阵 ................................................................................................. 29 1.3.5 深入了解矩阵 ......................................................................................... 30 1.4 向量和向量空间 ................................................................................................. 37 1.5 集合论 ................................................................................................................. 39 1.6 小结 ..................................................................................................................... 43 Chapter 2 复数................................................................................................ 46 2.1 什么是复数 ......................................................................................................... 46 2.2 复数的代数运算 ................................................................................................. 48 2.3 用图形表示复数 ................................................................................................. 52 2.4 用向量表示复数 ................................................................................................. 59 2.5 泡利矩阵 ............................................................................................................. 62 2.5.1 泡利矩阵的代数性质 ............................................................................. 66 2.6 超越数 ................................................................................................................. 70 2.7 小结 ..................................................................................................................... 72 Chapter 3 量子计算的物理学基础 ................................................................... 74 3.1 量子之旅 ............................................................................................................. 75 3.2 量子物理学要点 ................................................................................................. 79 3.2.1 基本原子结构 ......................................................................................... 79 3.2.2 希尔伯特空间 ......................................................................................... 82 3.2.3 不确定性 ................................................................................................. 84 3.2.4 量子态 ..................................................................................................... 87 3.2.5 量子纠缠 ................................................................................................. 89 3.3 小结 ..................................................................................................................... 91 Chapter 4 量子计算的计算机科学基础............................................................ 94 4.1 数据结构 ............................................................................................................. 95 4.1.1 列表 ......................................................................................................... 95 4.1.2 二叉树 ................................................................................................... 102 4.2 算法 ................................................................................................................... 102 4.2.1 排序算法 ............................................................................................... 104 4.3 计算复杂性理论 ............................................................................................... 107 4.3.1 圈复杂度 ............................................................................................... 107 4.3.2 霍尔斯特德度量指标 ........................................................................... 108 4.4 编码理论 ........................................................................................................... 109 4.5 逻辑门 ............................................................................................................... 110 4.5.1 与 ........................................................................................................... 110 4.5.2 或 ........................................................................................................... 110 4.5.3 异或 ....................................................................................................... 110 4.5.4 逻辑门的应用 ........................................................................................ 111 4.6 计算机架构 ....................................................................................................... 114 4.7 小结 ................................................................................................................... 117 Chapter 5 信息论基础 ................................................................................... 120 5.1 基本概率 ........................................................................................................... 121 5.1.1 基本概率规则 ....................................................................................... 121 5.2 集合论 ............................................................................................................... 122 5.3 信息论 ............................................................................................................... 126 5.3.1 定理 1：香农的信源编码定理 ............................................................. 127 5.3.2 定理 2：有噪信道编码定理 ................................................................. 127 5.3.3 信息熵 ................................................................................................... 127 5.3.4 信息多样性 ........................................................................................... 130 5.4 量子信息论 ....................................................................................................... 132 5.5 小结 ................................................................................................................... 134 Chapter 6 量子理论基础 ............................................................................... 136 6.1 量子力学进阶 ................................................................................................... 137 6.1.1 狄拉克符号 ........................................................................................... 137 6.1.2 哈密顿算符 ........................................................................................... 138 6.1.3 波函数坍缩 ........................................................................................... 139 6.1.4 薛定谔方程 ........................................................................................... 142 6.2 量子退相干 ....................................................................................................... 143 6.3 量子电动力学 ................................................................................................... 145 6.4 量子色动力学 ................................................................................................... 147 6.5 费曼图 ............................................................................................................... 148 6.6 小结 ................................................................................................................... 150 Chapter 7 量子纠缠与量子密钥分发 ............................................................. 152 7.1 量子纠缠 ........................................................................................................... 152 7.2 诠释 ................................................................................................................... 157 7.2.1 哥本哈根诠释 ....................................................................................... 158 7.2.2 多重世界诠释 ....................................................................................... 158 7.2.3 退相干历史诠释 ................................................................................... 159 7.2.4 客观坍缩理论 ....................................................................................... 159 7.3 量子密钥交换 ................................................................................................... 160 7.3.1 BB84 协议 ............................................................................................ 160 7.3.2 B92 协议 ............................................................................................... 163 7.3.3 SARG04 协议 ....................................................................................... 163 7.3.4 六态协议 ............................................................................................... 165 7.3.5 E91 协议 ................................................................................................ 165 7.3.6 协议的实现 ........................................................................................... 165 7.4 小结 ................................................................................................................... 165 Chapter 8 量子架构 ...................................................................................... 168 8.1 深入了解量子位 ............................................................................................... 168 8.2 量子门 ............................................................................................................... 172 8.2.1 阿达玛门 ............................................................................................... 173 8.2.2 相移门 ................................................................................................... 175 8.2.3 泡利门 ................................................................................................... 175 8.2.4 交换门 ................................................................................................... 176 8.2.5 弗雷德金门 ........................................................................................... 177 8.2.6 托佛利门 ............................................................................................... 177 8.2.7 受控门 ................................................................................................... 177 8.2.8 伊辛门 ................................................................................................... 178 8.2.9 Gottesman-Knill 定理 ............................................................................ 179 8.3 与门有关的更多信息 ....................................................................................... 180 8.4 量子电路 ........................................................................................................... 181 8.5 D-Wave 量子架构 ............................................................................................. 183 8.5.1 超导量子比特 ....................................................................................... 184 8.6 小结 ................................................................................................................... 186 Chapter 9 量子硬件 ...................................................................................... 188 9.1 量子位 ............................................................................................................... 188 9.1.1 光子 ....................................................................................................... 189 9.1.2 电子 ....................................................................................................... 191 9.1.3 离子 ....................................................................................................... 192 9.1.4 核磁共振量子计算 ............................................................................... 193 9.1.5 玻色-爱因斯坦凝聚态量子计算 .......................................................... 193 9.1.6 砷化镓量子点 ....................................................................................... 195 9.2 需要多少个量子位 ........................................................................................... 195 9.3 解决退相干问题 ............................................................................................... 196 9.3.1 过冷 ....................................................................................................... 199 9.3.2 处理噪声 ............................................................................................... 199 9.3.3 过滤噪声 ............................................................................................... 200 9.4 拓扑量子计算 ................................................................................................... 200 9.4.1 编织理论基础 ....................................................................................... 200 9.4.2 编织理论进阶 ....................................................................................... 201 9.4.3 拓扑计算进阶 ....................................................................................... 201 9.5 量子计算机必备组件 ....................................................................................... 201 9.5.1 量子数据平面 ....................................................................................... 201 9.5.2 测量平面 ............................................................................................... 202 9.5.3 控制处理器平面 ................................................................................... 202 9.6 量子网络 ........................................................................................................... 202 9.6.1 东京量子密钥分发 ............................................................................... 202 9.6.2 京沪干线 ............................................................................................... 203 9.6.3 墨子号卫星 ........................................................................................... 203 9.6.4 分布式量子计算 ................................................................................... 204 9.7 小结 ................................................................................................................... 205 Chapter 10 量子算法 .................................................................................... 208 10.1 何为算法 ......................................................................................................... 208 10.2 多伊奇算法 ..................................................................................................... 211 10.3 多伊奇-约萨算法 ........................................................................................... 213 10.4 伯恩斯坦-瓦兹拉尼算法 ............................................................................... 215 10.5 西蒙算法 ......................................................................................................... 216 10.6 肖尔算法 ......................................................................................................... 217 10.6.1 量子周期查找函数 ............................................................................. 220 10.7 格罗弗算法 ..................................................................................................... 223 10.8 小结 ................................................................................................................. 225 Chapter 11 当代非对称算法 .......................................................................... 226 11.1 RSA ................................................................................................................. 227 11.1.1 RSA 示例 1 .......................................................................................... 229 11.1.2 RSA 示例 2 .......................................................................................... 229 11.1.3 因式分解 RSA 密钥 ............................................................................ 230 11.2 迪菲-赫尔曼算法 ........................................................................................... 230 11.2.1 艾尔加玛尔加密算法 .......................................................................... 231 11.2.2 MQV .................................................................................................... 233 11.3 椭圆曲线 ......................................................................................................... 233 11.3.1 椭圆曲线迪菲-赫尔曼算法 ................................................................ 238 11.3.2 椭圆曲线数字签名算法 ...................................................................... 239 11.4 小结 ................................................................................................................. 241 Chapter 12 量子计算对密码学的影响 ........................................................... 242 12.1 非对称密码学 ................................................................................................. 243 12.1.1 需要多少个量子位 ............................................................................. 244 12.2 特定算法 ......................................................................................................... 245 12.2.1 RSA ..................................................................................................... 245 12.2.2 迪菲-赫尔曼算法 ............................................................................... 245 12.2.3 椭圆曲线密码 ..................................................................................... 246 12.2.4 对称密码 ............................................................................................. 246 12.2.5 密码散列 ............................................................................................. 246 12.3 具体应用 ......................................................................................................... 247 12.3.1 数字证书 ............................................................................................. 247 12.3.2 SSL/TLS .............................................................................................. 248 12.3.4 公钥基础设施 ..................................................................................... 251 12.3.5 虚拟专用网络 ..................................................................................... 253 12.3.6 安全外壳协议 ..................................................................................... 254 12.4 小结 ................................................................................................................. 255 Chapter 13 基于格的密码学.......................................................................... 258 13.1 基于格的数学问题 ......................................................................................... 259 13.1.1 最短整数问题 ..................................................................................... 262 13.1.2 最短向量问题 ..................................................................................... 262 13.1.3 最近向量问题 ..................................................................................... 262 13.2 加密算法 ......................................................................................................... 263 13.2.1 NTRU .................................................................................................. 263 13.2.2 GGH ..................................................................................................... 266 13.2.3 佩克特环签名算法 ............................................................................. 267 13.3 解决格问题 ..................................................................................................... 270 13.3.1 LLL 算法 ............................................................................................. 270 13.4 小结 ................................................................................................................. 273 Chapter 14 多元密码学 ................................................................................. 276 14.1 数学 ................................................................................................................. 276 14.2 Matsumoto-Imai 算法 ..................................................................................... 278 14.3 隐域方程 ......................................................................................................... 280 14.4 多元二次数字签名方案 ................................................................................. 282 14.5 SFLASH .......................................................................................................... 283 14.6 小结 ................................................................................................................. 285 Chapter 15 后量子密码学的其他方法 ........................................................... 288 15.1 散列函数 ......................................................................................................... 288 15.1.1 Merkle-Damgaard ................................................................................ 289 15.1.2 SWIFFT ............................................................................................... 289 15.1.3 兰伯特签名 ......................................................................................... 291 15.2 基于编码的密码学 ......................................................................................... 293 15.2.1 McEliece .............................................................................................. 293 15.2.2 Niederreiter 密码系统 ......................................................................... 294 15.3 超奇异同源密钥交换 ..................................................................................... 295 15.3.1 椭圆曲线 ............................................................................................. 295 15.3.2 超奇异同源迪菲-赫尔曼算法 ............................................................ 299 15.4 小结 ................................................................................................................. 303 Chapter 16 使用 Q# ...................................................................................... 306 16.1 基本编程概念 ................................................................................................. 306 16.1.1 变量和语句 ......................................................................................... 306 16.1.2 控制结构 ............................................................................................. 309 16.1.3 面向对象程序设计 ............................................................................. 311 16.2 Q#入门 ............................................................................................................ 312 16.3 格罗弗算法 ..................................................................................................... 317 16.3.1 格罗弗算法回顾 ................................................................................. 317 16.3.2 格罗弗算法代码 ................................................................................. 318 16.4 多伊奇-约萨算法 ........................................................................................... 321 16.4.1 多伊奇-约萨算法回顾........................................................................ 322 16.4.2 多伊奇-约萨算法代码........................................................................ 322 16.5 位翻转 ............................................................................................................. 324 16.6 小结 ................................................................................................................. 325 Chapter 17 使用量子汇编语言 ...................................................................... 328 17.1 基本编程概念 ................................................................................................. 329 17.1.1 指令 ..................................................................................................... 329 17.1.2 命令行 ................................................................................................. 333 17.2 开始使用 QASM ............................................................................................. 333 17.3 量子纠错 ......................................................................................................... 334 17.4 格罗弗算法 ..................................................................................................... 336 17.4.1 格罗弗算法回顾 ................................................................................. 336 17.4.2 格罗弗算法代码 ................................................................................. 338 17.5 多伊奇-约萨算法 ........................................................................................... 340 17.5.1 多伊奇-约萨算法回顾........................................................................ 340 17.5.2 多伊奇-约萨算法代码........................................................................ 340 17.6 小结 ................................................................................................................. 342 Appendix A 章节测试答案 ............................................................................ 344