量子線路映射及優(yōu)化是量子算法部署到量子計算設(shè)備的關(guān)鍵環(huán)節(jié)。本書主要研究滿足量子計算設(shè)備物理約束的量子線路變換和映射問題。在給出量子線路映射的發(fā)展歷史和相關(guān)預(yù)備知識的基礎(chǔ)上,把研究內(nèi)容分為上下兩篇:上篇聚焦于量子線路邏輯變換,主要探討如何將可逆/量子線路轉(zhuǎn)換為滿足量子計算設(shè)備物理約束的低級量子線路,包括可逆/量子線路變換與優(yōu)化、分解變換與優(yōu)化、線性最近鄰量子線路變換等問題;下篇針對當前量子計算設(shè)備普遍存在的多種物理局限性,提出相應(yīng)的解決方案,包括量子線路初始映射、量子比特近鄰化及路由、噪聲約束的量子線路映射及優(yōu)化、分布式映射及優(yōu)化等。本書試圖站在計算機工程技術(shù)視角對量子線路映射與優(yōu)化工作進行系統(tǒng)闡述,為讀者提供該領(lǐng)域較為全面的基本知識、研究思路和研究方法。
更多科學出版社服務(wù),請掃碼獲取。
教育背景:
1982/09 - 1986/07,哈爾濱師范大學數(shù)學系,本科/學士學位
2003/07 - 2004/03,美國科羅拉多礦業(yè)大學數(shù)學與計算機系,訪問學者
2004/09 - 2007/12,南京航空航天大學信息科學學院,研究生/博士學位
2007/03 - 2008/12,南京大學,軟件新技術(shù)國家重點實驗室,博士后
目錄
前言
第1章 引言 1
1.1 研究背景 1
1.2 發(fā)展歷史 2
1.3 量子線路映射的任務(wù) 9
1.4 量子線路映射的方法 10
1.5 全書結(jié)構(gòu) 11
第2章 預(yù)備知識 13
2.1 幾個重要概念 13
2.1.1 計算模型 13
2.1.2 可逆計算 13
2.1.3 量子計算 14
2.1.4 量子計算模型 14
2.1.5 量子算法 15
2.2 布爾函數(shù) 15
2.2.1 一般布爾函數(shù) 16
2.2.2 可逆(布爾)函數(shù) 16
2.2.3 可逆邏輯門 17
2.2.4 可逆邏輯線路 19
2.2.5 可逆邏輯綜合 20
2.3 量子態(tài)與量子比特 20
2.3.1 量子態(tài) 20
2.3.2 量子比特 21
2.4 量子門 25
2.4.1 量子門的概念 25
2.4.2 恒等門 25
2.4.3 Pauli門 25
2.4.4 NCV門 26
2.4.5 交換門(SWAP門) 27
2.4.6 Clifford+T門 28
2.4.7 相位門 29
2.4.8 量子門的可逆性 30
2.4.9 量子門的通用性 30
2.5 量子線路 30
2.5.1 基本概念 30
2.5.2 量子線路的表示 31
2.5.3 量子線路類型 32
2.5.4 量子代價 32
2.5.5 量子門計數(shù) 33
2.5.6 量子線路分層 33
2.5.7 量子線路深度 34
2.5.8 量子門序列互逆 34
2.5.9 邏輯量子線路的等價性 36
2.5.10 量子線路變換 36
2.5.11 量子線路化簡 37
2.5.12 可逆/量子門分解 38
2.5.13 量子線路優(yōu)化 42
2.6 量子計算體系結(jié)構(gòu) 43
2.6.1 線性最近鄰架構(gòu) 43
2.6.2 二維網(wǎng)格結(jié)構(gòu) 43
2.6.3 拓撲結(jié)構(gòu)圖 44
2.6.4 量子比特近鄰結(jié)構(gòu) 45
2.6.5 量子代價 47
2.6.6 量子不可克隆原理 47
2.7 NISQ計算設(shè)備 48
2.7.1 計算噪聲 48
2.7.2 量子門約束 49
2.7.3 連通性約束 50
2.7.4 退相干約束 51
2.7.5 串擾約束 51
2.7.6 計算結(jié)果保真度 51
2.7.7 相關(guān)約束分析 52
2.8 量子線路映射 53
2.8.1 初始映射 54
2.8.2 量子比特分配 54
2.8.3 量子比特近鄰化 55
2.8.4 線性最近鄰 56
2.8.5 線性最近鄰代價 57
2.8.6 量子比特近鄰化代價 57
2.8.7 量子比特路由 58
2.8.8 量子門執(zhí)行調(diào)度 58
2.8.9 量子線路調(diào)度 59
2.8.10 量子線路分布式映射 59
上篇 量子線路邏輯變換
第3章 可逆/量子線路變換與優(yōu)化 63
3.1 基于規(guī)則的MCT線路變換 63
3.1.1 門關(guān)系與變換規(guī)則 63
3.1.2 門序列與變換規(guī)則 64
3.1.3 基于規(guī)則的線路化簡算法 70
3.1.4 實例驗證 72
3.1.5 實驗結(jié)果及分析 74
3.2 基于模板的線路變換 75
3.2.1 模板定義 75
3.2.2 模板構(gòu)建 76
3.2.3 基于模板線路優(yōu)化 97
3.3 本章小結(jié) 109
第4章 分解變換與優(yōu)化 110
4.1 MCT門分解 110
4.1.1 基本分解方法 110
4.1.2 MCT門分解優(yōu)化 111
4.1.3 示例分析 113
4.1.4 實驗結(jié)果與分析 114
4.2 線性近鄰約束下的MCT門分解 114
4.2.1 問題描述 114
4.2.2 基本概念 115
4.2.3 近鄰交互約束下的MCT門分解 116
4.3 基于設(shè)備拓撲感知的MCT門分解 125
4.3.1 問題描述 125
4.3.2 基本概念 126
4.3.3 硬件子拓撲選擇 126
4.3.4 MCT線路關(guān)聯(lián)門對生成 130
4.3.5 MCT線路分解映射 136
4.3.6 實驗和結(jié)果分析 142
4.4 本章小結(jié) 145
第5章 線性最近鄰量子線路變換 146
5.1 NCV線路的LNN構(gòu)造和優(yōu)化 146
5.1.1 NCV量子門三線分布 146
5.1.2 LNN線路最優(yōu)綜合算法 150
5.1.3 實驗結(jié)果及分析 152
5.2 線性最近鄰量子線路綜合 154
5.2.1 N門前瞻最近鄰方法 154
5.2.2 聯(lián)合考慮最近鄰方法 162
5.2.3 換門序原則 163
5.2.4 優(yōu)化近鄰化策略 163
5.2.5 量子線路化簡 168
5.2.6 實驗結(jié)果與分析 169
5.3 LNN排布的線路近鄰化 172
5.3.1 線序重排代價度量模型 172
5.3.2 基于LNN排布的線路近鄰化 175
5.3.3 線路優(yōu)化 179
5.3.4 實驗結(jié)果及分析 182
5.4 本章小結(jié) 186
下篇 量子線路物理感知映射
第6章 量子線路初始映射 189
6.1 基本概念 189
6.2 問題描述 194
6.2.1 概述 194
6.2.2 問題分析 195
6.3 量子比特分配的精確方法 197
6.3.1 線性化表示 197
6.3.2 精確量子比特分配算法 199
6.3.3 實驗結(jié)果與分析 205
6.4 考慮時序權(quán)重的量子比特分配 207
6.4.1 時序交互圖 207
6.4.2 量子比特分配算法 207
6.4.3 實驗結(jié)果與分析 210
6.5 考慮活躍度的量子比特分配 211
6.5.1 量子比特分配順序 211
6.5.2 量子比特布局 215
6.5.3 舉例 217
6.6 本章小結(jié) 219
第7章 量子比特近鄰化及路由 220
7.1 問題描述與分析 220
7.1.1 問題描述 220
7.1.2 問題分析 222
7.2 量子比特路由方法 226
7.2.1 量子比特路由的CNOT門優(yōu)化問題 226
7.2.2 量子比特路由策略 227
7.3 迭代尋優(yōu)近鄰化與路由策略 233
7.3.1 基本思想 233
7.3.2 局部搜索算法 233
7.3.3 CNOT門數(shù)優(yōu)化算法 235
7.3.4 實驗結(jié)果與分析 237
7.4 基于活躍度量子比特近鄰化與路由 243
7.4.1 近鄰化代價 243
7.4.2 雙量子比特門序列的選擇 244
7.4.3 量子比特近鄰化 246
7.4.4 復(fù)雜度分析 248
7.4.5 實驗結(jié)果及分析 249
7.5 本章小結(jié) 251
第8章 噪聲約束的量子線路映射及優(yōu)化 252
8.1 噪聲約束分析 252
8.2 基于ESP的提高保真度路由策略 254
8.2.1 CNOT門的ESP估算 254
8.2.2 ESP估算 261
8.2.3 量子比特路由 263
8.2.4 實驗結(jié)果 267
8.3 基于變換與調(diào)度的保真度優(yōu)化 268
8.3.1 串擾與噪聲 268
8.3.2 量子門交換規(guī)則 269
8.3.3 面向串擾約束的量子線路調(diào)度 280
8.3.4 量子比特狀態(tài)更新 285
8.3.5 實驗結(jié)果和分析 288
8.4 本章小結(jié) 289
第9章 分布式映射及優(yōu)化 291
9.1 分布式映射概述 291
9.2 分布式架構(gòu)模型 292
9.2.1 模型構(gòu)建 292
9.2.2 分布式量子線路映射 295
9.3 分布式量子線路劃分與優(yōu)化 298
9.3.1 線路劃分策略 298
9.3.2 傳輸代價優(yōu)化策略 302
9.3.3 傳輸代價優(yōu)化算法 307
9.4 分布式量子比特分配 313
9.4.1 全局量子態(tài)路由代價 313
9.4.2 分布式量子比特分配算法 314
9.5 分布式量子態(tài)路由 316
9.5.1 QPU內(nèi)量子態(tài)路由策略 316
9.5.2 QPU間量子態(tài)路由策略 320
9.5.3 量子態(tài)路由算法 322
9.6 實驗結(jié)果與分析 324
9.6.1 實驗配置 324
9.6.2 算法性能 325
9.7 本章小結(jié) 328
參考文獻 330