摘要：量子计算能够在整数分解、数据库搜索、量子模拟以及其他重要领域、应用发挥重大作用，因此在最近几十年内，量子计算能够获得很多的关注、得到飞速的发展。然而，由于物理实现技术的不成熟，现今仍旧无法克服物理设备上的一些硬件约束，这导致大多数量子算法无法直接在嘈杂中型量子（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