目 录

第1章  量子计算的发展历史与潜在应用  1

1.1  量子计算的发展历史   1

1.2  量子计算的潜在应用   5

1.3  量子计算的硬件发展   6

1.4  小结   7

参考文献   7

第2章  量子计算基本概念   10

2.1  量子比特   10

2.2  经典的逻辑运算门和电路   13

2.3  基本量子门与电路   17

2.4  小结   21

参考文献   21

第3章  线性代数基础   22

3.1  线性无关与基  . 22

3.2  线性算子与矩阵   22

3.3  Pauli 矩阵   23

3.4  Cauchy-Schwarz 不等式   23

3.5  特征值与特征向量   24

3.6  伴随算子和Hermitian 算子   25

3.7  算子函数   25

3.8  算子分解定理  . 26

3.9  量子力学假设  . 31

3.10  密度算子   32

3.11  偏迹  . 35

3.12  超算子   37

3.13  小结  . 41

参考文献   42

第4章  基本的量子通信协议   43

4.1  BB84 协议   43

4.2  B92 协议   47

4.3  E91 协议   48

4.4  超密编码   50

4.5  量子隐形传态  . 51

4.6  小结   52

参考文献   53

第5章  量子计算模型   55

5.1  单向量子有限自动机（1QFA）   55

5.1.1  单次测量的1QFA  . 55

5.1.2  多次测量的1QFA  . 63

5.1.3  带经典状态的1QFA  . 69

5.1.4  其他几类重要的1QFA  . 71

5.2  双向量子有限自动机（2QFA）   76

5.3  带量子与经典状态的双向有限自动机  81

5.4  量子下推自动机   91

5.5  量子文法   94

5.5.1  上下文无关文法与正则文法   94

5.5.2  量子正则文法   95

5.5.3  *量子上下文无关文法   97

5.6  量子图灵机（QTM）   99

5.7  量子电路   103

5.7.1  量子门   103

5.7.2  多项式时间模拟QTM   105

5.8  小结  . 112

参考文献   113

第6章  量子算法   116

6.1  概率算法与量子算法的基本关系  116

6.2  量子查询模型   119

6.3  查询复杂度与多项式度的关系  120

6.4  Deutsch 算法   123

6.5  Deutsch-Jozsa 算法   126

6.6  Simon 算法   129

6.7  量子傅里叶变换   138

6.8  量子相位估计   142

6.9   *量子相位估计的详细概率分析  147

6.10  Shor 因数分解算法   155

6.11  Shor 离散对数算法   162

6.12  隐子群算法  . 166

6.13  Grover 算法   172

6.14  量子振幅扩大   176

6.15   *量子振幅估计   179

6.16  *HHL 算法  . 188

6.17  *变分量子特征值求解算法   194

6.18  *量子近似优化算法   199

6.19  小结   201

参考文献   201

第7章  量子计算复杂性   204

7.1  重访量子查询模型   207

7.2  量子状态区分   208

7.3  搜索问题下界   210

7.4  多项式法   216

7.5  敌对法   224

7.6  小结  . 233

参考文献   233

第8章  量子纠错   235

8.1  经典比特翻转纠错   235

8.2  量子比特翻转纠错   236

8.3  量子相位翻转纠错   239

8.4  Shor 码   241

8.5  线性码   245

8.6  CSS 码   254

8.7  *稳定子码   258

8.8  *二元量子MDS 码   261

8.9  小结  . 271

参考文献   271