摘要：量子計算能夠在整數分解、數據庫搜索、量子模擬以及其他重要領域、應用發揮重大作用，因此在最近幾十年內，量子計算能夠獲得很多的關注、得到飛速的發展。然而，由于物理實現技術的不成熟，現今仍舊無法克服物理設備上的一些硬件約束，這導致大多數量子算法無法直接在嘈雜中型量子（NISQ）設備上執行。之前改進量子線路以適應實際量子設備的解決方案復雜度高，并且初始映射質量、靈活性和可擴展性都較差。為了解決上述存在的問題，本文研究了一種基于SWAP操作的雙向啟發式搜索算法（SABRE），并提出了新穎的考慮波動誤碼率后的改進方法。

SABRE算法適用于具有不同物理量子位約束的NISQ設備，通過優化每次的搜索結果、使用新穎的反向遍歷技術全局優化初始映射、引入衰減效應以實現整個算法的深度和門數之間的折中，SABER在指數加速方面勝過了最著名的BKA算法，并且能夠在各種基準線路上取得可比或更好的結果。

關鍵詞：量子線路；NISQ量子設備；線路映射；最近鄰

目  錄

摘  要

ABSTRACT

第一章  緒論-1

1.1 研究背景-1

1.2 研究現狀-1

1.3 研究意義-2

1.4 論文組織結構-2

第二章 NISQ量子線路概述-4

2.1 量子比特-4

2.2 量子門-4

2.2.1 單量子位門-4

2.2.2 雙量子位門-5

2.2.3 多量子位門-5

2.3 量子線路-5

2.4 量子代價-6

2.5 NISQ量子設備-6

2.6 本章小結-7

第三章 量子位初始布局問題的研究-8

3.1 線路映射問題描述-8

3.2 映射問題解決策略-9

3.2.1 交換量子位映射-9

3.2.2 反轉操作等其他線路轉換方法-9

3.3 基于SWAP操作的啟發式搜索方法-9

3.4 量子位初始布局-11

3.4.1 計算距離矩陣-11

3.4.2 生成DAG線路-11

3.4.3 前層初始化-12

3.4.4 臨時初始映射的生成-12

3.4.5 最終初始映射的選擇-13

3.5 本章小結-14

第四章 量子線路局部近鄰化策略的研究-15

4.1 局部近鄰化的SWAP門插入方法-15

4.2 權衡線路深度與門數的方法-16

4.3 啟發式成本函數-18

4.3.1 根據最近鄰代價構造基本啟發式函數-18

4.3.2 考慮前瞻能力改進啟發式函數-19

4.3.3 考慮并行性改進啟發式函數-19

4.4 考慮波動誤碼率后的優化方法-20

4.5 實驗結果與算法分析-22

第五章 總結和展望-24

5.1 總結-24

5.2 展望-24

參考文獻-26

致  謝-28

附  錄-29