量子计算十讲

丛书序
“十讲”序
前言
第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　通信复