量子計算導論 (上下) 韓永建 郭光燦 9787030766403 【台灣高等教育出版社】

編輯推薦
適讀人群 ：量子科學與技術專業、物理專業及計算機專業的高年級本科生、研究生、大學教師和量子計算相關科技工作者
本書中的重要結論都給出了詳盡的證明，使讀者不僅能學到量子計算的相關知識，也能學到解決這類問題所需的典型技能，有能力解決未來科研中遇到的新問題。

內容簡介
《量子計算導論（上下冊）》全面系統地介紹了量子計算領域的基本理論、核心概念、關鍵方 法和重要結論，併兼顧近期的前沿進展。《量子計算導論（上下冊）》內容主要包括：**和量子 計算的複雜性理論、計算複雜度與物理理論間的關係；基本量子演算法；不 同量子計算模型及其與量子線路模型的等價；基於離子阱系統、超導系統 及光學系統的量子計算的物理實現；量子糾錯碼與容錯量子計算。《量子計算導論（上下冊）》既 突出了每個章節的邏輯完整性，也強調了不同章節間內容上的聯繫，保證 了量子計算學科的完整性和自洽性。本《量子計算導論（上下冊）》的重要結論都給出了詳盡的證 明，使讀者不僅能學到量子計算的相關知識，也能學到解決這類問題所需 的典型技能，有能力解決未來科研中遇到的新問題。

目錄

目錄
「量子信息前沿叢書」序言 前言
**章 計算模型及計算複雜度 1
1 1 普適**計算 1
1 1 1 圖靈機及可計算性 2
1 1 2 計算複雜度理論 11
1 1 3 線路模型與普適門 48
1 2 普適量子計算 54
1 2 1 可逆計算 55
1 2 2 量子線路模型及普適量子邏輯門 60
1 2 3 量子門的線路複雜度與精度 80
1 3 量子圖靈機與計算複雜度 92
1 3 1 量子圖靈機 92
1 3 2 量子圖靈機與線路模型的等價 95
1 3 3 量子計算複雜度 99
1 3 4 量子證明和交互證明系統 104
1 4 計算複雜度與物理理論 126
1 4 1 后選擇量子計算 127
1 4 2 宇稱時間反演對稱量子理論與計算複雜度 130
主要參考書目與綜述 133
第二章 基本量子演算法 134
2 1 量子搜索類演算法 135
2 1 1 Grover 演算法 136
2 1 2 量子振幅放大演算法 144
2 2 Hadamard Test 類演算法 146
2 2 1 Hadamard Test 146
2 2 2 SWAP Test 150
2 3 量子傅里葉變換類演算法 152
2 3 1 基於 Hadamard 變換的量子演算法 153
2 3 2 ZN 上量子傅里葉變換及其應用 159
2 4 量子相位估計演算法及哈密頓量模擬演算法 189
2 4 1 量子相位估計演算法 189
2 4 2 哈密頓量模擬演算法 193
2 4 3 量子信號處理演算法 208
2 4 4 哈密頓量模擬的應用 219
2 5 量子態的有效製備與量子優越性 234
2 5 1 量子態的有效製備 234
2 5 2 量子採樣與量子優越性 244
2 6 變分量子演算法 269
2 6 1 主要變分量子演算法 270
2 6 2 變分量子態的構造 274
主要參考書目與綜述 284
第三章 量子計算模型 285
3 1 One-way 量子計算 285
3 1 1 圖態及其性質 286
3 1 2 圖態的測量與普適量子門 302
3 2 拓撲量子計算 319
3 2 1 馬約拉納任意子與量子計算 320
3 2 2 拓撲量子計算的一般理論 329
3 2 3 Jones 多項式與拓撲量子計算 350
3 3 基於量子行走的量子計算 361
3 3 1 量子行走 362
3 3 2 基於量子行走的演算法 365
3 3 3 量子行走實現普適量子門 375
3 4 絕熱量子計算 387
3 4 1 量子絕熱定理 387
3 4 2 絕熱量子計算 389
3 4 3 絕熱量子計算與量子線路模型的等價 393
3 4 4 絕熱量子計算與量子退火演算法 396
3 4 5 絕熱量子計算與 QAOA 400
主要參考書目與綜述 401
附錄 403
Ib 線性代數及矩陣分析基礎 410
IIa 群論基礎 412
IIb 單量子比特*優量子控制 424
IIc 量子 Metropolis-Hastings 演算法 434
IId 費米系統到比特系統的映射 437
IIIa 絕熱哈密頓量 H (s) 的能隙估計 443
索引 451

精彩書摘
**章 計算模型及計算複雜度
Information is a physical entity —— Rolf Landauer
儘管計算模型及其計算能力都是抽象的數學問題，但將計算模型實現並用於解決實際問題，需通過真實的物理系統來完成（並非所有計算模型都可物理實現）：一個計算過程（演算法）的實現就是控制物理系統隨時間演化的過程（測量可看作特殊的演化）。因此，一個物理系統的計算能力既是一個數學問題，也是一個物理問題。
事實上，物理系統的計算能力具有普適性（universality）：它與具體物理系統的細節無關，僅與系統的動力學演化方式相關。量子系統和**系統遵循不同的動力學演化方式（分別遵循量子力學和**力學），人們普遍相信量子系統將提供比**系統更強大的計算能力。在包括Shor 演算法、Grover 演算法等在內的諸多演算法中，基於量子物理系統設計的演算法都明顯優於已知的基於**物理系統設計的演算法。為表徵不同計算模型的計算能力以及不同問題的計算複雜程度，在每個計算模型上，都可按計算問題所需消耗的時間、空間等資源進行分類，這樣的類稱為計算複雜類。研究不同計算複雜類之間的關係是計算理論的核心課題；而研究基於量子理論的計算複雜類與基於**理論的計算複雜類之間的關係則是量子計算的核心理論課題。
在這一章中，我們將*先介紹幾種不同的**計算模型：確定性圖靈機、非確定性圖靈機和含Oracle 的圖靈機。在這些圖靈機模型上定義不同計算複雜類，並介紹它們之間的一些已知關係。其次我們還將介紹**線路和量子線路模型（後面的量子演算法主要基於線路模型）以及不同的量子普適門集合。在量子圖靈機和量子線路模型基礎上，我們將定義不同的量子計算複雜類，並介紹它們與**複雜類之間的重要已知關係。*后我們還將討論計算能力與物理理論之間的關係，介紹基於特殊量子理論（未必對應于真實的物理世界）的計算模型及其計算能力。
1 1 普適**計算
現代計算理論的建立與發展是從**圖靈機（Turing machine）模型的建立開始的，我們下面*先就來介紹*簡單的**圖靈機。
1 1 1 圖靈機及可計算性
確定性圖靈機是現代計算理論的開端，它*早由英國數學家圖靈（Allen Turing）於1936 年提出且由Alonzo Church 命名為圖靈機?。而另外一名數學家EmilPost 也提出了與圖靈機模型類似的數學系統，並且很快證明了它們之間的相互等價性-。這種等價性是計算普適性的一個*早體現。
圖靈機的提出，與希爾伯特（Hilbert）二十三個問題中的第十問題密切相關?。
第十問題又稱整數解判定問題，其具體表述如下：
整數解判定問題任意給定一個丟番圖（Diophantine）方程，是否存在一種演算法可以在有限步驟內判定此方程是否有整數解？
此命題中的丟番圖方程是指整係數多項式方程，比如：x + 2y = 0 就是一個二元一次的丟番圖方程（x 的係數1 和y 的係數2 都是整數）。很容易判斷，此丟番圖方程有整數解，我們甚至能直接給出一個解，比如x = 2，y = ??1。然而，對一個一般的丟番圖方程，比如
x3 + y3 = z3 (1 1)
要判斷它是否有整數解就遠沒有這麼簡單。事實上，式（1 1）就是著名的費馬大定理n = 3 的特例，安德魯 懷爾斯（Andrew Wiles）證明了xn +yn = zn (n?3)沒有整數解，並由此獲得1995 年沃爾夫獎（Wolf prize）和1998 年世界數學大會菲爾茲特別獎（Fields medal）（當時其年齡已超過40 歲）。
要解決希爾伯特第十問題，需*先對演算法——或者說一系列確定性的（我們暫且要求其確定性）、按某種規則實施的步驟——這個詞給出精確且科學的定義。儘管演算法的實例早在古希臘時期就已出現，如著名的求*大公因子的歐幾里得演算法:
例1 1 歐幾里得演算法
問題：求兩個整數a 和b 的*大公因子。
演算法：假設a >b， 則下面一系列等式成立
其中ri 是除法中的非負餘數(ri+1 總小於等於ri)，這一除法操作一直持續到餘數rN = 0 為止。此時，rN-1 就是a 和b 的*大公因子。
但演算法的精確定義卻一直未出現。圖靈準確地意識到了演算法與執行此演算法的機器之間的密切關係（如果沒有機器，演算法就無從談起），基於此，他率先引入了我們今天稱為圖靈機的機器。圖靈機是一種自動機，它的下一步動作完全由機器的當前狀態確定，不需外界輸入任何額外的指令。如果圖靈機的下一步操作被它當前的狀態唯一確定，那麼，它就是一種確定性機器。在圖靈機上可以定義計算所遵循的規則表，在給定編碼方式下，不同的規則表就對應于不同的演算法（也是不同的圖靈機）。每個演算法（圖靈機）都能解決一類問題（通過輸入來區分同類問題中的不同特例），而不僅僅解決某一個特定的問題。
單帶圖靈機模型（圖1 1）。一個單帶圖靈機由三個主要部分構成。
圖1 1 圖靈機模型：它包含一個無窮長的記錄帶；一個含狀態的讀寫頭以及一個控制單元（規則表）
(1) 一條記錄帶。它由按順序排列的可列（無窮）個單元格子組成，每個單元格子僅容納一個記錄符號ai， ai 2 Σ，Σ = fa0， a1， a2， ， ang 是一個有限符號集且包含空白符號a0 = Blank。在任意圖靈機中，非空白的記錄格子數目均為有限。特別地，香農(Claude Elwood Shannon) 證明，任何的圖靈機都可以約化為兩字元的圖靈機，即Σ = f0， 1g（0 表示空白）。這可通過將原符號集Σ 中的符號ai編碼為二進位實現。為此，圖靈機可僅考慮Σ = f0， 1g 的情況。
(2) 一個含狀態的讀寫頭。讀寫頭狀態由一個有限集合S = fS0， S1， ， Smg描述。特別地，停機狀態S0 = Shalt（表示整個計算結束）必須在狀態集S 中。讀寫頭每次只能讀取記錄帶中一個單元格中的符號信息，讀取后，它按照控制單元中的指令（圖靈機第三個主要部分）在當前單元格中寫入Σ 中的一個符號（可以與當前符號相同），同時改變（不改變作為其特例）讀寫頭的狀態。若某時刻讀寫頭的狀態顯示為停機狀態（Shalt），則表明計算過程結束，整個記錄帶此時的狀態即為輸出結果。
(3) 一個控制單元（處理器）。控制單元確定讀寫頭的操作規則，它是圖靈機的核心部件。控制單元包括一個有限的控制指令集δ，也稱作狀態轉移函數δ（transition function）：
其中(Si， ai) 表示讀寫頭當前狀態為Si，當前被讀取單元格中符號為ai。而Sf表示讀寫頭的下一個狀態（它可與Si 相同，也可不同，由狀態轉移函數δ 決定）；af 取代ai 成為當前單元格中的符號；而γ 2 fL(左)，R(右)g 表示讀寫頭的下一步動作：左移一格或右移一格?。很顯然，狀態轉移函數δ 的輸入變數Si 和ai 僅與圖靈機的當前狀態相關，而與圖靈機的歷史狀態無關（即δ 具有馬爾可夫性）。在確定性圖靈機中，任意二元狀態組(Si， ai) 能且僅能轉移到唯一一個三元組(Sf ， af ， γ)（在隨機圖靈機中可（以一定概率）轉移到多個三元組中的一個）。
那麼，如何在一個圖靈機上實現計算過程呢？事實上，在編碼方式一定時，計算過程由狀態轉移函數（規則表）完全確定。利用前面的狀態轉移函數，我們以計算1 + 2 的過程為例來說明演算法在圖靈機上如何執行。
在這一計算中，圖靈機的輸入包含兩部分：記錄帶上的輸入（整數1 和2）和圖靈機讀寫頭的初始狀態。*先，我們把整數1 和2 用記錄帶上的符號（如0 和1）進行編碼，並作為記錄帶輸入。為簡便，用連續符號1 的個數來編碼不同的數（相對於二進位編碼，這是一種低效率的編碼方式）即
不同數之間用空白字元0 隔開。因此，記錄帶上的輸入為011010，而讀寫頭上的輸入為S1。在此編碼下，加法運算可通過兩態狀態轉移函數（表1 1）實現。具體的演算法過程如下：
(1) 讀寫頭從左往右讀記錄帶上的符號（此時讀寫頭狀態為S1），在讀到1之前（全為0），讀寫頭將保持狀態S1 且記錄帶上的符號也保持為0，僅讀寫頭向右移動一格，直到讀寫頭讀到記錄帶上的1 為止。