本书在全面介绍量子计算与量子信息理论中用到的量子力学、线性代数、计算复杂性理论等背景知 

识的基础上，着重介绍几个代表性的量子算法：Deutsch-Jozsa 算法、Simon 算法、BV 算法、Grover 算 

法、量子傅里叶变换、HHL 算法等。同时，也介绍量子计算与量子信息实际应用所涉及的一些问题，包 

括量子通信中的量子密钥分发与量子随机数，以及安全量子计算协议，并简单介绍几种未来量子计算机 

可能的物理实现形式。 

全书共分 3 篇：第 1 篇（第 1~4 章）为基础知识背景篇，着重介绍量子计算与量子信息理论所用到 

的量子力学、线性代数、计算复杂性理论等背景知识；第 2 篇（第 5~8 章）为算法篇，着重介绍几个有 

代表性的量子算法，说明算法步骤，并对各个算法进行简单的分析；第 3 篇（第 9~12 章）为应用篇， 

介绍量子通信中的量子密钥分发与量子随机数、安全量子计算协议及几种未来量子计算机可能的物理实 

现形式。每章后均附有参考文献与习题。 

本书由浅入深，从基础理论到前沿，具有系统性、交叉性、前沿性等特点，适合作为高等院校电子、 

通信、计算机、数学及信息类交叉学科专业高年级本科生、研究生的教材，同时也可供其他从事量子计 

算研究的研究人员参考。

前  言

量子计算为现代信息技术提供了潜在的从量变到质变的巨大算力。由于这个研究方向的交叉学科性质，还未有一套比较完整的理论体系。为此，我们在课程体系、课程资源建设等方面进行了尝试性的工作，在前期科学研究的基础上编写了这本交叉学科教材——《量子计算导论》。

本书共12章。

第1章  绪论。概述量子信息处理过程、量子算法以及量子计算机等相关问题的研究背景、研究意义及研究现状。

第2章  量子力学引论。介绍量子计算与量子信息的基础知识，包括线性代数、量子力学基本原理、量子比特、量子测量、量子纠缠等。

第3章  计算复杂性。首先介绍两类计算模型，即图灵机模型和线路模型，然后讨论计算复杂性，根据求解的难度对问题进行分类，包括P类和NP 类问题等。

第4章  量子计算模型。介绍量子线路模型和一维量子计算模型。

第5章  基本的量子算法。介绍Deutsch-Jozsa 算法、Simon 算法、BV算法以及量子近似优化算法。

第6章  量子搜索算法。介绍Grover 量子搜索算法及相关改进算法。

第7章  量子傅里叶变换及其应用，介绍量子傅里叶变换，并给出利用量子傅里叶变换的两大基本算法：相位估计和Shor 因子分解算法。

第8章  量子机器学习。介绍HHL 算法、量子奇异值分解、量子主成分分析、量子支持向量机算法和量子神经网络。

第9章  量子噪声和容错。介绍量子噪声、量子纠错码基本理论以及容错量子计算。

第10章  量子密码学。介绍两种具有代表性的量子加密技术：量子密钥分配、量子随机数发生器。

第11章  安全量子计算。介绍安全委托量子计算。

第12章  量子计算机的物理实现。介绍量子计算机可能的物理实现形式：离子阱量子计算机、超导量子计算机和核磁共振量子计算机。

本书旨在提供量子计算的相关理论知识基础，并介绍几种典型的量子算法，总结最新研究成果，使读者能够掌握量子计算的基础理论及发展。本书由浅入深，从基础理论到前沿，具有系统性、交叉性、前沿性等特点，可以作为电子、通信、计算机、数学及信息类交叉学科专业高年级本科生、研究生的教材，也可作为从事量子计算研究人士的入门级读物。

本书在编写过程中得到了清华大学出版社的大力支持，获得了暨南大学教务处的教材项目资助，还得到了暨南大学信息科学技术学院/网络空间安全学院的有力支持，在此对以上单位一并表示感谢。同时，特别感谢许青山同学、黄睿同学、曾晓丹同学、陶红同学、田悠然同学的积极参与，他们为本书的出版付出了努力。

鉴于量子计算的交叉学科性质，本书中的矩阵和向量均使用白斜体表示，特此说明。

由于编者知识水平有限，书中的缺点与错误在所难免，望读者不吝批评、指正。

作者

2021年5月

目   录

第1章  绪论  1   

1.1   引言  1   

1.2   量子信息处理  3 

1.3   量子算法简介  5 

1.4   量子计算机 6   

参考文献  7 

第2章  量子力学引论  9 

2.1   线性代数  9 

2.1.1   向量 10 

2.1.2   内积 11 

2.1.3   线性算子与 Pauli 矩阵  12 

2.1.4   伴随与 Hermite 算子  13 

2.1.5   外积 16 

2.1.6   张量积  17 

2.1.7   对易式和反对易式  18 

2.2   量子力学理论框架  19 

2.2.1   量子力学基本假设  20 

2.2.2   量子力学基本原理  22 

2.3   量子比特  24 

2.3.1   量子比特的数学表示  24 

2.3.2   量子比特的 Bloch 球面表示 .25 

2.3.3   密度矩阵 26 

2.4   量子测量  26 

2.4.1   一般测量 27 

2.4.2   投影测量 27 

2.4.3   POVM  28 

2.4.4   相位 29 

2.5   量子纠缠  29

2.5.1   纠缠态与可分离态  30 

2.5.2   纠缠交换  30 

2.5.3   Bell 不等式 31 

习题  33 

参考文献  34 

第3章  计算复杂性  36 

3.1   计算模型  37 

3.1.1   图灵机 38 

3.1.2   线路模型  41 

3.2   计算复杂性类  43 

3.2.1   P 类和 NP 类 44 

3.2.2   其他复杂性类  48 

3.3   计算科学的发展与展望  51 

习题  53 

参考文献  54 

第4章  量子计算模型  55 

4.1   量子线路模型  55 

4.1.1   单量子比特门  55 

4.1.2   旋转算子的 Clifford 性质  59 

4.1.3   具体的旋转算子分解形式  59 

4.1.4   多量子比特门  60 

4.1.5   通用量子门  62 

4.2   其他量子计算模型 67 

4.2.1   量子隐形传态  67 

4.2.2   单向量子计算模型 70 

习题 75 

参考文献  76 

第5章  基本的量子算法 78 

5.1   Deutsch-Jozsa 算法 78 

5.1.1   量子并行性 78 

5.1.2   Deutsch 算法简介  80 

5.1.3   Deutsch-Jozsa 算法简介  82 

5.2   Simon 算法  84 

5.3   Bernstein-Vazirani 算法  85 

5.4   QAOA 算法  86

习题  91 

参考文献  91 

第6章  量子搜索算法  92 

6.1   Grover 量子搜索算法  92 

6.1.1   Grover 算法的基本思想  92 

6.1.2   算法的性能分析  94 

6.1.3   算法的程序实现  96 

6.2   量子搜索算法的最优性  98 

6.3   Grover 量子搜索算法的改进 101 

6.3.1   基于 =2 相位旋转的改进算法  101 

6.3.2   基于局部扩散算子的量子搜索算法  103 

6.4   Grover 量子搜索算法的应用 107 

6.4.1   非结构化数据库搜索  108 

6.4.2   NP 完全问题上的应用 109 

6.4.3   其他相关应用  110 

6.5   量子随机行走  111 

6.5.1   经典随机行走  111 

6.5.2   量子随机行走简介 112 

6.5.3   量子随机行走搜索算法 116 

习题  117 

参考文献  117 

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

7.1   量子傅里叶变换 121 

7.1.1   经典傅里叶变换  121 

7.1.2   量子傅里叶变换原理  122 

7.1.3   量子傅里叶变换线路  123 

7.1.4   量子傅里叶变换实例  126 

7.2   相位估计  127 

7.2.1   算法过程  128 

7.2.2   算法分析  129 

7.3   因子分解  131 

7.3.1   Shor 算法 132 

7.3.2   Shor 算法实例 134 

7.3.3   Shor 算法分析 135 

7.4   离散对数问题  135

7.5   隐含子群问题  137 

7.5.1   循环群的 HSP  138 

7.5.2   Abel 群的 HSP  139 

习题  140 

参考文献  140 

第8章  量子机器学习  142 

8.1   量子计算与人工智能  142 

8.2   机器学习  143 

8.2.1   机器学习的发展与分类  143 

8.2.2   机器学习的实现  144 

8.2.3   机器学习中的算法 145 

8.3   量子机器学习概述  146 

8.3.1   HHL 算法  147 

8.3.2   量子奇异值分解算法  149 

8.3.3   量子主成分分析算法  154 

8.3.4   量子支持向量机算法  159 

8.3.5   量子神经网络  162 

习题  164 

参考文献  165 

第9章  量子噪声和容错  166 

9.1   量子噪声  166 

9.1.1   三量子比特的比特翻转码  167 

9.1.2   三量子比特的相位翻转码  169 

9.1.3   Shor 码  170 

9.2   量子纠错码理论  171 

9.2.1   量子纠错编码的基本方法  172 

9.2.2   CSS 量子纠错码 175 

9.2.3   稳定子量子纠错码 182 

9.2.4   Toric 码 188 

9.3   容错量子计算  189 

9.3.1   容错操作  190 

9.3.2   7-位CSS 码的指错子测量  191 

9.3.3   容错量子门操作  193 

9.3.4   CSS 类稳定子码的容错计算  193 

9.4   量子计算容错阈限定理  197

习题  199 

参考文献  200 

第10章  量子密码学  202 

10.1   量子密钥分配  202 

10.1.1   BB84 类协议  203 

10.1.2   实际 QKD 系统安全性分析  204 

10.1.3   产业化现状  208 

10.2   量子随机数发生器  209 

10.2.1   量子随机数发生器分类  209 

10.2.2   随机数的后处理  213 

10.2.3   产业化现状  214 

参考文献  215 

第11章  安全量子计算 217 

11.1   安全辅助量子计算协议 218 

11.2   协议改进  219 

11.3   安全量子计算发展趋势 222 

习题  222 

参考文献  223 

第12章  量子计算机的物理实现  224 

12.1   离子阱量子计算机  225 

12.1.1   离子阱 225 

12.1.2   离子作为量子信息的载体  227 

12.1.3   激光冷却与状态初始化  227 

12.1.4   单量子比特门  228 

12.1.5   离子量子比特的状态检测  229 

12.1.6   双量子比特门  229 

12.1.7   退相干 230 

12.2   超导量子计算机  231 

12.3   核磁共振量子计算机  232 

习题  233 

参考文献  234

1.由浅入深，从基础理论到研究热点问题，具有系统性、交叉性、前沿性等特点。

2.全面介绍了相关背景知识，降低读者的学习门槛，即使没有相关知识基础的读者，也可以理解。

3.内容丰富，着重介绍几个代表性的量子算法，也介绍了量子计算理论在实际应用中所涉及的一些问题。

4.受众甚广，具有交叉学科特色，适合作为高等院校电子、通信、计算机、数学及信息类交叉学科专业高年级本科生、研究生的教材。

谭晓青: 暨南大学信息科学技术学院教授，博士生导师。长期担任信息类本科课程的教学工作， 获得暨南大学第三届本科课程教学竞赛一等奖，取得暨南大学全英教学资格证，2009年被评为暨南大学优秀教师。