叢書序
“十講”序
前言
第1講　量子計算理論基礎(chǔ)
1.1　量子計算的數(shù)學(xué)基礎(chǔ)/2　
1.1.1　Hilbert空間及線性算子/2　
1.1.2　隨機變量及其函數(shù)/8　
1.2　量子力學(xué)的基礎(chǔ)/11　
1.2.1　量子力學(xué)基本假設(shè)/11　
1.2.2　密度算子上的度量/15　
1.2.3　量子線路/17　
1.3　本講小結(jié)/19　
參考文獻(xiàn)/19　
第2講　Shor素因數(shù)分解算法
2.1　量子傅里葉變換/22　
2.2　相位估計/25　
2.2.1　相位估計電路圖/26　
2.2.2　相位估計精度分析/28　
2.2.3　相位估計算法過程/30　
2.3　量子求階算法/31　
2.3.1　求階中用到的數(shù)論知識/31　
2.3.2　求階問題與量子算法/32　
2.3.3　模冪運算/34　
2.3.4　連分式分解/35　
2.3.5　求階量子算法及性能分析/36　
2.4　Shor素因數(shù)分解算法詳解/38　
2.4.1　算法過程/38　
2.4.2　一個分解實例/40　
2.5　Shor素因數(shù)分解算法的實驗進(jìn)展/42　
2.6　Shor素因數(shù)分解算法的經(jīng)典模擬/48　
2.6.1　乘法器的構(gòu)造/50　
2.6.2　帶模加法器的構(gòu)造/51　
2.7　本講小結(jié)/53　
參考文獻(xiàn)/54　
第3講　Grover搜索算法
3.1　原始Grover算法/58　
3.1.1　預(yù)備知識/58　
3.1.2　算法描述與分析/60　
3.1.3　目標(biāo)點個數(shù)未知的處理方法/64　
3.1.4　最優(yōu)性證明/66　
3.2　Grover算法的擴展/70　
3.2.1　精確量子搜索/70　
3.2.2　魯棒量子搜索/74　
3.2.3　量子計數(shù)/76　
3.2.4　量子振幅放大/78　
3.3　Grover算法的應(yīng)用/80　
3.3.1　NP完全問題加速求解/80　
3.3.2　量子算法搜索最小值/82　
3.3.3　其他問題/84　
3.4　本講小結(jié)/85　
參考文獻(xiàn)/85　
第4講　線性方程組的量子求解算法
4.1　HHL算法/89　
4.1.1　量子模擬/89　
4.1.2　算法假設(shè)/90　
4.1.3　算法思想/91　
4.1.4　算法步驟/91　
4.1.5　復(fù)雜性分析/92　
4.1.6　討論/94　
4.2　CKS算法/97　
4.2.1　算法思想/97　
4.2.2　傅里葉方法/99　
4.2.3　算法實現(xiàn)和復(fù)雜性分析/101　
4.2.4　討論/103　
4.3　量子奇異值估計算法和WZP算法/104　
4.3.1　量子奇異值估計算法/104　
4.3.2　WZP算法/110　
4.3.3　討論/112　
4.4　本講小結(jié)/112　
參考文獻(xiàn)/113　
第5講　量子游走基礎(chǔ)
5.1　量子游走模型/119　
5.1.1　離散量子游走模型/119　
5.1.2　連續(xù)量子游走模型/138　
5.1.3　模型之間的轉(zhuǎn)化/139　
5.2　基于量子游走的通用量子計算/141　
5.2.1　基于連續(xù)量子游走的通用量子計算/141　
5.2.2　基于離散量子游走的通用量子計算/145　
5.3　本講小結(jié)/148　
參考文獻(xiàn)/148　
第6講　量子游走應(yīng)用
6.1　基于量子游走的算法/152　
6.1.1　元素區(qū)分/152　
6.1.2　三角形搜索/156　
6.1.3　連續(xù)量子游走搜索算法/158　
6.1.4　基于Markov鏈隨機游走的量子化/160　
6.1.5　mixing time/170　
6.2　基于多硬幣量子游走的通信協(xié)議/171　
6.2.1　基于量子游走的隱形傳輸框架/171　
6.2.2　基于兩硬幣量子游走的完美狀態(tài)轉(zhuǎn)移/177　
6.2.3　基于多硬幣量子游走的高維糾纏態(tài)的生成/181　
6.3　本講小結(jié)/187　
參考文獻(xiàn)/187　
第7講　量子計算復(fù)雜性
7.1　量子圖靈機與量子電路/192　
7.1.1　量子圖靈機/192　
7.1.2　量子電路/193　
7.1.3　量子圖靈機與量子電路的等價性/194　
7.2　量子多項式時間復(fù)雜性類/197　
7.2.1　量子多項式時間類的性質(zhì)/197　
7.2.2　量子計算與計數(shù)復(fù)雜性/199　
7.3　量子梅林亞瑟與哈密頓量復(fù)雜性/203　
7.3.1　量子梅林亞瑟的定義/203　
7.3.2　量子Cook-Levin定理/204　
7.3.3　強完備性可靠性間隙放大定理/208　
7.3.4　量子梅林亞瑟的上界/210　
7.3.5　關(guān)于QMA及其相關(guān)復(fù)雜性類的討論/212　
7.4　量子交互證明系統(tǒng)/213　
7.4.1　單證明人量子交互證明系統(tǒng)/213　
7.4.2　量子交互證明系統(tǒng)的并行化/216　
7.4.3　多證明人量子交互證明系統(tǒng)與貝爾不等式的復(fù)雜性問題/219　
7.5　其他問題/229　
7.6　本講小結(jié)/231　
參考文獻(xiàn)/232　
第8講　量子查詢復(fù)雜性模型
8.1　經(jīng)典查詢復(fù)雜性與量子查詢復(fù)雜性/240　
8.1.1　經(jīng)典查詢復(fù)雜性模型/240　
8.1.2　量子查詢復(fù)雜性模型/242　
8.2　常見量子查詢算法/243　
8.2.1　Deutsch-Jozsa問題/243　
8.2.2　Grover搜索/246　
8.2.3　權(quán)重判定問題/247　
8.2.4　碰撞問題/250　
8.3　證明量子查詢復(fù)雜性下界的多項式方法/252　
8.3.1　布爾函數(shù)的精確/近似多項式表示/252　
8.3.2　量子查詢復(fù)雜性與近似多項式次數(shù)/253　
8.3.3　無結(jié)構(gòu)搜索問題的量子查詢復(fù)雜性下界/258　
8.4　證明量子查詢復(fù)雜性下界的對手方法/261　
8.4.1　原始量子對手方法/261　
8.4.2　AND-OR樹的量子查詢復(fù)雜性下界/266　
8.4.3　通用量子對手方法/268　
8.5　本講小結(jié)/271　
參考文獻(xiàn)/271　
第9講　量子通信復(fù)雜性
9.1　通信復(fù)雜性模型/276　
9.2　量子通信復(fù)雜性模型/279　
9.3　高效量子通信協(xié)議/280　
9.4　量子通信復(fù)雜性下界/283　
9.4.1　基于矩陣分析方法的量子通信復(fù)雜性下界/283　
9.4.2　基于量子信息論方法的量子通信復(fù)雜性下界/286　
9.4.3　通信復(fù)