量子計算理論基礎

量子計算是基於量子力學原理調控量子比特進行信息處理的計算模式，是國內外重點關註的交叉 研究領域。本書介紹量子計算理論中最為重要的基礎知識和研究內容，並適當介紹密切相關的**研 究進展。全書共8 章，第1 章簡要介紹量子計算的發展歷史、背景及現狀，並指出量子計算的優勢及 潛在應用：第2 章描述與量子計算密切相關的基本概念，並指出經典計算是量子計算的特殊情形； 第3 章概述與量子計算密切相關的線性代數基礎知識，特別是系統地歸納了算子（矩陣）分解的相關 定理和超算子等內容；第4 章陳述基本的量子密碼和通信協議；第5 章闡述基本的量子計算模型，包 括量子有限自動機、量子圖靈機與量子電路等；第6 章介紹量子計算的核心內容——重要的量子算法， 主要包括Deutsch 算法、Deutsch-Jozsa 算法、Simon 算法、Shor 算法與Grover 算法，以及HHL 算法、 VQE 算法和QAOA 算法，同時還介紹隱子群算法，總結設計量子算法的基本工具，即量子相位估計 方法與量子振幅擴大方法；第7 章介紹量子計算復雜性的基本知識與方法；第8 章介紹量子糾錯碼的 基本概念和方法，並闡述它們的糾錯原理。 本書是一本關於量子計算基礎理論的書籍，非常適合作為面向電腦及相關專業的基礎教材，供高等 學校理工科大學本科生及研究生使用，同時，對有志於量子計算研究的學者也有很好的參考和引導作用。

目 錄

第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