量子计算是当前十分活跃的领域，代表了计算科学未来发展的重要方向。本书由国内量子计算领域的9位知名专家学者共同撰写，着眼前沿，以简明的文字和公式介绍了量子计算领域的基本理论以及重要方法和应用，包括Shor素因数分解算法、Grover搜索算法、量子游走、量子通信等，帮助读者全面了解量子计算的主要思想和研究成果。
本书适合量子计算及相关领域的科研人员、研究生阅读，也适合从事相关工作的从业人员阅读。
中国工程院院士郑纬民作序
李国杰院士、陆汝黔院士 联袂推荐
量子计算领域专家学者携手打造，系统构建知识体系
综述当下领域前沿研究方向、理论与技术
以宏观视野把握领域前沿，获取领域底层逻辑
量子计算是一个跨越计算机科学、物理学、数学、材料科学等多学科的新兴交叉研究领域，其利用物理学中量子叠加、量子纠缠、量子酉变换等量子力学特性来完成计算及信息处理任务，通过设计高效的量子算法来降低完成计算任务所需的时间、空间或其他资源消耗，构建新的计算体系范式，帮助提升计算效率和性能，有望从根本上解决计算中的一些困难问题。量子计算并非经典计算的单纯加速版，而是一种全新的计算模型，其核心是如何借助量子力学的基本规律巧妙地设计量子算法来求解计算问题，在信息科技飞速发展的今天，量子计算为解决日益凸显的算力瓶颈问题提供了新的可能方案。
本书从计算机专业角度出发，较为全面和系统地介绍了量子计算所需的数学基础、常用量子算法、量子复杂性理论和量子纠错原理。具体来说，第1讲详细介绍了量子计算的理论基础，包括量子计算中的基本数学概念、假设和符号，为读者阅读后续章节提供了便利；第2讲Shor素因数分解算法，介绍Shor提出的求解大整数素因数分解问题的量子算法，该算法比当前最好的经典算法具有指数量级加速效果，充分展示了量子计算理论上的优越性；第3讲Grover搜索算法，系统介绍Grover提出的量子搜索算法相关内容，包括算法步骤、正确性、复杂性分析、最优性证明，以及Grover算法的进一步扩展和典型应用；第4讲线性方程组的量子求解算法，介绍两类具有指数量级加速效果和一类具有多项式量级加速效果的求解线性方程组的量子算法；第5讲和第6讲量子游走基础与应用，集中讲解量子游走算法，包括量子游走的各种模型及其之间的转换关系、量子游走的通用性等，以及基于量子游走的算法和协议，如三角形搜索算法、多硬币量子游走的通信理论和协议等；第7讲量子计算复杂性，包括量子图灵机与量子电路模型、量子多项式时间复杂性类BQP、量子交互式证明系统QIP等；第8讲量子查询复杂性模型，介绍在量子计算中普遍采用的量子查询模型、几个常见的量子查询算法，以及两种证明量子查询复杂度下界的重要方法——多项式方法与对手法；第9讲量子通信复杂性，介绍量子通信复杂性模型、高效通信协议、通信复杂度下界，并探讨信息不完备与计算困难性之间的关系；第10讲量子纠错，介绍量子纠错基本原理、纠错码构造、容错量子计算和量子纠错的研究现状。上述十讲的每一部分内容都保持相对独立，各自构成一个完整的章节体系，同时各讲之间又紧密联系，共同构成一个有机整体。由于涉及多个不同的专题，本书对各专题领域内的素材选取可能未能全面反映该专题的最新前沿进展。但每一章节末尾均附有详尽的参考文献资料，以供有兴趣的读者进一步深入钻研。我们深知，任何一本书都无法完全涵盖一个领域的全部知识或理论，仍有许多未知问题有待挖掘。因此，我们希望本书能成为激发读者对量子计算领域兴趣与好奇心的火花，引导读者勇敢探索和研究其中的未解难题。
本书由9位量子计算领域资深研究人员共同撰写完成，具体分工如下：第1讲由陕西师范大学席政军教授撰写，第2讲由中国科学院计算技术研究所田国敬副研究员撰写，第3讲由中山大学李绿周教授撰写，第4讲由北京邮电大学高飞教授撰写，第5讲和第6讲由中国科学院数学与系统科学研究院尚云研究员撰写，第7讲由清华大学季铮锋教授撰写，第8讲由中国科学院计算技术研究所孙晓明研究员撰写，第9讲由南京大学姚鹏晖副教授撰写，第10讲由清华大学魏朝晖助理教授撰写。孙晓明担任本书主编，负责规划本书的内容结构和召集、组织编写组撰写。他们均是量子计算领域的一线科研人员，拥有丰富的实践经验和深厚的科研背景，近年来承担了多个与量子计算紧密相关的国家重大科研项目，取得了一系列重要科研成果，而且还常年致力于高校量子计算课程的教学工作，积累了丰富的教学经验，培养了一批优秀的量子计算人才。
本书可作为高等院校计算机、数学、物理和信息安全等专业一年级研究生或高年级本科生学习量子计算的教材或参考书，总学时数建议为48~64学时；也可根据所在专业的培养目标和需求，选择其中的部分章节进行教学，每一章建议的学时数为4~6学时。本书也可作为量子计算领域从业人员的参考书。
在此我们要向参与本书撰写、审稿、校对等工作的专家学者致以诚挚的感谢！感谢你们的专业精神和辛勤付出，为本书的质量提供了坚实的保障。同时，也要感谢中国计算机学会（CCF）、CCF“计算机科学前沿丛书”编委会、理论计算机科学专委会和北京西西艾弗信息科技有限公司。感谢本书所有读者的包容与理解，尽管我们已经尽力确保内容文字的准确性，但书中难免仍存在小的纰漏，期待并欢迎您提出宝贵的意见和建议。最后，衷心希望这本书能够对您有所启发和帮助，感谢您的阅读！
全体作者
2023/12/31
孙晓明
中国科学院计算技术研究所研究员，量子计算与算法理论实验室主任，CCF理事， 理论计算机科学专委会主任。主要研究领域为算法与计算复杂性、量子计算等。获国家杰出青年科学基金资助，曾获王选杰出青年科学家奖等。
尚云
中国科学院数学与系统科学研究院研究员，博士生导师，CCF杰出会员，量子计算专 业委员会常委。长期从事量子计算及其基础理论、量子游走、量子机器学习的研究，已在高 水平期刊发表60多篇论文。曾获中国计算机学会CCF科学技术奖自然科学二等奖、英国皇家物理学会IOP高被引奖，王宽诚优秀女科学家专项奖，陕西省优秀博士论文等。
李绿周
中山大学计算机学院教授，量子计算与软件研究所所长，CCF杰出会员，量子计算专委会副主任。长期从事量子计算研究，主要研究兴趣为量子算法、量子计算模型、量子电路编译与优化等，在国际主流学术期刊发表学术论文70余篇，出版学术专著1部。
丛书序
“十讲”序
前言
第1讲 量子计算理论基础
1.1 量子计算的数学基础/2
1.1.1 Hilbert空间及线性算子/2
1.1.2 随机变量及其函数/8
1.2 量子力学的基础/11
1.2.1 量子力学基本假设/11
1.2.2 密度算子上的度量/15
1.2.3 量子线路/17
1.3 本讲小结/19
参考文献/19
第2讲 Shor素因数分解算法
2.1 量子傅里叶变换/22
2.2 相位估计/25
2.2.1 相位估计电路图/26
2.2.2 相位估计精度分析/28
2.2.3 相位估计算法过程/30
2.3 量子求阶算法/31
2.3.1 求阶中用到的数论知识/31
2.3.2 求阶问题与量子算法/32
2.3.3 模幂运算/34
2.3.4 连分式分解/35
2.3.5 求阶量子算法及性能分析/36
2.4 Shor素因数分解算法详解/38
2.4.1 算法过程/38
2.4.2 一个分解实例/40
2.5 Shor素因数分解算法的实验进展/42
2.6 Shor素因数分解算法的经典模拟/48
2.6.1 乘法器的构造/50
2.6.2 带模加法器的构造/51
2.7 本讲小结/53
参考文献/54
第3讲 Grover搜索算法
3.1 原始Grover算法/58
3.1.1 预备知识/58
3.1.2 算法描述与分析/60
3.1.3 目标点个数未知的处理方法/64
3.1.4 最优性证明/66
3.2 Grover算法的扩展/70
3.2.1 精确量子搜索/70
3.2.2 鲁棒量子搜索/74
3.2.3 量子计数/76
3.2.4 量子振幅放大/78
3.3 Grover算法的应用/80
3.3.1 NP完全问题加速求解/80
3.3.2 量子算法搜索最小值/82
3.3.3 其他问题/84
3.4 本讲小结/85
参考文献/85
第4讲 线性方程组的量子求解算法
4.1 HHL算法/89
4.1.1 量子模拟/89
4.1.2 算法假设/90
4.1.3 算法思想/91
4.1.4 算法步骤/91
4.1.5 复杂性分析/92
4.1.6 讨论/94
4.2 CKS算法/97
4.2.1 算法思想/97
4.2.2 傅里叶方法/99
4.2.3 算法实现和复杂性分析/101
4.2.4 讨论/103
4.3 量子奇异值估计算法和WZP算法/104
4.3.1 量子奇异值估计算法/104
4.3.2 WZP算法/110
4.3.3 讨论/112
4.4 本讲小结/112
参考文献/113
第5讲 量子游走基础
5.1 量子游走模型/119
5.1.1 离散量子游走模型/119
5.1.2 连续量子游走模型/138
5.1.3 模型之间的转化/139
5.2 基于量子游走的通用量子计算/141
5.2.1 基于连续量子游走的通用量子计算/141
5.2.2 基于离散量子游走的通用量子计算/145
5.3 本讲小结/148
参考文献/148
第6讲 量子游走应用
6.1 基于量子游走的算法/152
6.1.1 元素区分/152
6.1.2 三角形搜索/156
6.1.3 连续量子游走搜索算法/158
6.1.4 基于Markov链随机游走的量子化/160
6.1.5 mixing time/170
6.2 基于多硬币量子游走的通信协议/171
6.2.1 基于量子游走的隐形传输框架/171
6.2.2 基于两硬币量子游走的完美状态转移/177
6.2.3 基于多硬币量子游走的高维纠缠态的生成/181
6.3 本讲小结/187
参考文献/187
第7讲 量子计算复杂性
7.1 量子图灵机与量子电路/192
7.1.1 量子图灵机/192
7.1.2 量子电路/193
7.1.3 量子图灵机与量子电路的等价性/194
7.2 量子多项式时间复杂性类/197
7.2.1 量子多项式时间类的性质/197
7.2.2 量子计算与计数复杂性/199
7.3 量子梅林亚瑟与哈密顿量复杂性/203
7.3.1 量子梅林亚瑟的定义/203
7.3.2 量子Cook-Levin定理/204
7.3.3 强完备性可靠性间隙放大定理/208
7.3.4 量子梅林亚瑟的上界/210
7.3.5 关于QMA及其相关复杂性类的讨论/212
7.4 量子交互证明系统/213
7.4.1 单证明人量子交互证明系统/213
7.4.2 量子交互证明系统的并行化/216
7.4.3 多证明人量子交互证明系统与贝尔不等式的复杂性问题/219
7.5 其他问题/229
7.6 本讲小结/231
参考文献/232
第8讲 量子查询复杂性模型
8.1 经典查询复杂性与量子查询复杂性/240
8.1.1 经典查询复杂性模型/240
8.1.2 量子查询复杂性模型/242
8.2 常见量子查询算法/243
8.2.1 Deutsch-Jozsa问题/243
8.2.2 Grover搜索/246
8.2.3 权重判定问题/247
8.2.4 碰撞问题/250
8.3 证明量子查询复杂性下界的多项式方法/252
8.3.1 布尔函数的精确/近似多项式表示/252
8.3.2 量子查询复杂性与近似多项式次数/253
8.3.3 无结构搜索问题的量子查询复杂性下界/258
8.4 证明量子查询复杂性下界的对手方法/261
8.4.1 原始量子对手方法/261
8.4.2 AND-OR树的量子查询复杂性下界/266
8.4.3 通用量子对手方法/268
8.5 本讲小结/271
参考文献/271
第9讲 量子通信复杂性
9.1 通信复杂性模型/276
9.2 量子通信复杂性模型/279
9.3 高效量子通信协议/280
9.4 量子通信复杂性下界/283
9.4.1 基于矩阵分析方法的量子通信复杂性下界/283
9.4.2 基于量子信息论方法的量子通信复杂性下界/286
9.4.3 通信复
书单推荐
