量子计算是当前十分活跃的领域，代表了计算科学未来发展的重要方向。本书由国内量子计算领域的9位知名专家学者共同撰写，着眼前沿，以简明的文字和公式介绍了量子计算领域的基本理论以及重要方法和应用，包括Shor素因数分解算法、Grover搜索算法、量子游走、量子通信等，帮助读者全面了解量子计算的主要思想和研究成果。 本书适合量子计算及相关领域的科研人员、研究生阅读，也适合从事相关工作的从业人员阅读。

孙晓明 中国科学院计算技术研究所研究员，量子计算与算法理论实验室主任，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　通信复杂性的“直和-直积”猜想/292　
9.5　量子通信复杂性的其他领域/296　
9.5.1　多方量子通信复杂性/297　
9.5.2　分布式量子计算/297　
9.5.3　嘈杂量子通信复杂性/298　
9.6　本讲小结/299　
参考文献/299　
第10讲　量子纠错
10.1　量子纠错的困难和挑战/306　
10.1.1　经典计算纠错的基本原理/306　
10.1.2　量子特性给量子纠错带来的困难/307　
10.2　量子纠错的基本原理/308　
10.2.1　Shor编码介绍/309　
10.2.2　量子纠错的一般性理论/314　
10.3　量子纠错码的构造/316　
10.3.1　稳定子编码理论/317　
10.3.2　稳定子编码的构造和分析/322　
10.4　容错量子计算介绍/328　
10.4.1　基本思想/328　
10.4.2　量子计算的阈值定理/331　
10.5　量子纠错的研究现状/333　
10.5.1　非可加性量子编码/333　
10.5.2　表面码/333　
10.5.3　定制纠错码/334　
10.5.4　量子噪声压制/334　
10.6　本讲小结/335　
参考文献/335