量子計算十講

叢書序
「十講」序
前言
第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　通信複.......