量子线路映射及优化是量子算法部署到量子计算设备的关键环节。《量子线路映射与优化》主要研究满足量子计算设备物理约束的量子线路变换和映射问题。在给出量子线路映射的发展历史和相关预备知识的基础上，把研究内容分为上下两篇：上篇聚焦于量子线路逻辑变换，主要探讨如何将可逆/量子线路转换为满足量子计算设备物理约束的低级量子线路，包括可逆/量子线路变换与优化、分解变换与优化、线性*近邻量子线路变换等问题；下篇针对当前量子计算设备普遍存在的多种物理局限性，提出相应的解决方案，包括量子线路初始映射、量子比特近邻化及路由、噪声约束的量子线路映射及优化、分布式映射及优化等。《量子线路映射与优化》试图站在计算机工程技术视角对量子线路映射与优化工作进行系统阐述，为读者提供该领域较为全面的基本知识、研究思路和研究方法。

信息是物理的!——罗尔夫?？?朗道尔(Rolf Landauer)
　　如果你想模拟自然，你*好用量子力学!——理查德?？?费曼(Richard P.Feynman)
　　“缘天梯兮北上，登太一兮玉台”，量子线路映射工作或许就是在为天梯砌砖。——作者
　　第1章引言[M1]
　　随着量子计算技术的飞速发展，量子线路作为量子算法与量子计算设备之间的桥梁，其重要性日益凸显，见图1-1。量子线路映射与优化①作为量子计算领域的关键技术，直接关系到量子算法的有效实现与量子计算机的性能提升。
　　1.1 研究背景
　　在量子计算的研究中，物理学家从物理层面实现量子比特的存储、传输、操作和测量，计算机工作者则大多致力于面向计算问题的量子算法研究。很长一段时间以来，量子计算物理层面和算法层面的研究是相对割裂的，没有形成有效的相互感知。近年来，随着多种NISQ计算设备的诞生，量子计算开始进入全新的时代[1，2]，如何让量子算法在真实的量子计算设备上执行，成为现实而重要的课题，也是量子线路映射这项工作的关键内容之一。
　　量子线路[3，4](quantum circuit)是由量子逻辑门序列以及若干测量操作构成的量子计算模型，是量子算法的一种通用表示形式。量子算法可以表示成高级可逆逻辑门的级联，理想的高级可逆门可以作用在任意的多个量子比特上。在目前的量子技术条件下，理想状态下的量子算法要在量子计算机上执行，主要存在两个方面的问题：一方面，由于量子线路是量子算法理想化的描述，和在量子计算设备上实际执行的量子线路存在差异，必须通过一系列变换过程，将高级可逆/量子逻辑线路表示的量子算法变换为与量子物理计算设备适配的低级量子线路，才能将量子算法部署到符合具体物理约束的量子计算设备中执行，从而实现量子计算；另一方面，当前可用的量子计算设备主要属于NISQ设备范畴。这类设备在量子比特数量、相干时间、连通性、门操作错误率以及纠错容错能力等方面存在诸多物理局限性。这些局限性对量子线路映射与优化提出了特定的要求，需要我们充分考虑量子比特之间的连接关系、量子门的执行效率以及噪声产生的错误等因素。量子线路映射与优化旨在通过深入研究量子线路的映射方法和优化策略，提高量子算法在NISQ设备上的执行效率和准确性。
　　1.2 发展历史
　　量子线路映射与优化研究的发展历史可以追溯到量子计算理论的初步形成时期。随着量子计算概念的提出，人们开始认识到量子线路作为量子算法描述和执行方式的重要性。然而，在量子计算发展初期，由于量子计算机的物理实现尚不成熟，量子线路映射与优化的研究相对较少。进入21世纪后，随着量子计算技术的快速发展，特别是量子计算机的物理实现取得了重要进展，量子线路映射与优化的研究逐渐受到关注，一系列重要的研究成果相继涌现，相关研究仍在不断发展和深化中。
　　1980年，Benioff[5]提出了一个量子力学模型，可以实现**图灵机的每一步过程。Feynman[6]发明的可逆计算全量子模型推动了量子计算研究的发展。物理学家Deutsch[7]提出了量子图灵机和通用量子图灵机的概念，并在1989年提出了由量子门组成的量子计算的线路模型，成为量子计算的基本计算模型。Yao[8]则证明了量子图灵机模型和量子线路模型的等价性。随着Shor[9]的大数质因子分解和Grover及Long的数据库搜索等量子算法的提出[10，11]，如何实现量子算法成为一个备受关注的热门话题，从而推动了可逆/量子逻辑综合的相关研究[12-16]。近年来，由于量子计算设备的快速发展，量子线路映射问题得到了广泛关注。根据量子算法和底层物理架构的演化，将量子线路映射的研究分为五个阶段，如图1-2所示。
　　1)可逆/量子线路的综合与化简
　　早期研究者对量子算法的研究基本不考虑量子系统的物理实现方式，仅通过可逆逻辑综合[17，18]或量子逻辑综合[19]得到算法的量子线路表现形式，并假设量子门可以作用在任意的量子比特上。近年来，随着量子计算设备研究进展的加快和量子算法实现要求的提高，满足物理约束的量子线路研究成为热点。例如，在超导[20，21]、离子阱[22，23]、量子点[24]和中性原子[25]等物理实现技术上，都只支持特定的基本量子门集，要求两量子比特量子门的控制比特和目标比特必须作用在相邻的量子比特上，量子比特相干时间较短，量子门操作存在错误和延迟等。为了实现将表示量子算法的高级可逆线路表示为物理相关的低级量子线路，研究者做了大量的工作。
　　可逆/量子线路一般基于模板匹配或化简规则对线路进行化简，以减少线路中的门数或量子代价。基于模板匹配的化简方法中，*先定义模板，然后将模板以特定顺序应用于输入线路，在线路中彻底搜索各种可能的替换[26-33]。基于化简规则的化简方法中，通过门的移动、合并和删除等规则，实现线路的化简[34，35]。前者适用于小规模的线路，算法时间复杂度较大，后者可用于大规模线路的化简，需要不断发现新的规则来提高优化效果。
　　逻辑综合生成的网表中通常包含多比特的高级量子门，如广义Toffoli门等。虽然这些高级量子门便于构建量子线路，但是它们在物理上极难实现。由于单量子比特门和双量子比特门即可构成量子计算的通用门库[36]，且易物理实现，因而基于特定低级量子门库的量子门分解[37-41]成为量子线路研究的重要内容。量子门分解所采用的低级门库主要包括NCV门库[42]、Clifford+T门库[43]以及一些含参量子门库，这些门库均由少量的单量子比特门和双量子比特门组成，在物理上相对容易实现，甚至支持表面码等量子容错计算技术[44-46]，因此其上的量子门分解研究更为普遍。文献[47]中给出了高级可逆门分解为基本量子门的方法，为复杂高级可逆门的分解奠定了理论基础。文献[48]实现了将NCV线路变换到具有容错性的Clifford+T线路，由于T门的容错实现成本较高，因此线路变换中以*小化T门计数和T门深度为目标。文献[49]实现了改进的任意规模MCT门分解为NCV门的方法。文献[50]提出了一种将Toffoli线路和NCV线路映射为Clifford+T线路的方法，以较低的代价使它们符合给定的IBM架构，只在5量子比特的IBMQX4上进行了测试。文献[51]给出了MCT门的容错分解方法，基于新给出的容错量子门库Clifford+ZN，实现了一种新的MCT到线性相位深度容错线路的无辅助位的分解算法，为实现量子算法的可扩展浅相位深度线路构建铺平了道路。
　　2)面向线性*近邻架构的线路映射
　　在早期的离子阱、液态核磁共振等具有线性*近邻（linear nearest neighbor，LNN）架构的量子系统上，要求相互作用的量子比特必须在物理位置上相邻。因此，文献[52]～[56]考虑线性的连通性约束，开展线性近邻约束下的量子线路变换研究，使量子算法能够在LNN架构的量子系统上运行。在线性近邻架构中，每个量子比特至多只有两个近邻，将逻辑量子线路变换为符合线性近邻约束的量子线路时，需要插入大量额外的量子门保证近邻交互，线路的门数急剧增长。由于LNN架构在物理上*易实现，因此量子线路映射的研究始于LNN架构，在LNN架构上一个量子比特*多有两个近邻比特。Saeedi等[57]提出了以减少SWAP（交换）门数为目标的量子比特全局排序和局部排序策略，这两个策略明确了量子线路映射的关键步骤，对后续研究有着重要影响。Shafaei等[58]将量子线路分解成若干子线路，并使用*小线性安排(minimum linear arrangement)算法为每个子线路生成量子比特的全局排序，*后通过插入SWAP门完成局部排序和各子线路的整合，该方法较基线算法平均减少了28%的SWAP门数。Kole等[59]在进行量子比特局部排序时使用了前瞻n个后续量子门的搜索策略，从而平均减少了27%的SWAP门，Wille等[60]提出了类似的前瞻策略，该前瞻策略为后续研究中基于前瞻式代价函数的量子线路映射方法提供了启发。
　　3)面向二维网格架构的线路映射
　　由于LNN架构上的量子比特连通性过于受限，架构上的每个量子比特*多仅有两个相邻比特，而在二维网格架构上每个量子比特*多可以有四个近邻比特，因此，二维网格架构逐步取代LNN架构成为线路映射的主要目标平台。在二维体系结构的量子系统中，每个量子比特至多有四个近邻，能够减少线路变换中额外插入门的个数。因此，对于超导、中性原子以及光子等具有二维*近邻架构的量子系统，文献[61]～[67]在考虑连通性约束的前提下，通过对量子比特的初始分配和量子比特动态路由的研究，将量子算法部署到二维*近邻架构量子系统中。Farghadan和Mohammadzadeh[68]构建了二维架构上的线路映射流程，包括量子比特优先级排序、量子比特分配(即全局排序)和量子门近邻化调度(即局部排序)，并在实现近邻化调度时使用了基于前瞻窗口的代价函数协助SWAP门的选择。Ding和Yamashita[69]提出了一种二维架构上的量子线路映射*优化方法，该方法将量子线路映射问题描述为布尔可满足性(Booleansatisfiability，SAT)问题，并通过可满足性模理论(satisfiability modulo theories，SMT)求解器获得SWAP门*少的结果线路。然而，由于SAT求解器的耗时随问题规模呈指数级增长，该方法无法适用于大规模量子线路，为了克服这点不足，文献[69]还提出了另外一种基于线路划分的映射方法，该方法将大规模线路分解成若干可由SAT求解器有效求解的小规模线路，实验结果表明该方法可以在有效时间内大幅减少SWAP门数。
　　4)面向NISQ计算设备的线路映射
　　随着IBM[70]、Google[71]以及Rigetti[72]等科技公司超导NISQ架构的推出，量子线路映射的研究开始进入以真实NISQ设备为目标平台的发展阶段。相较于抽象的网格架构，NISQ架构存在更多的物理约束：一方面，其量子比特连通拓扑并不仅局限于规则的一维或二维网格结构，而可能采用任意结构；另一方面，其上的量子比特和量子门在操作时长和操作质量等方面均存在不容忽视的物理限制。量子线路映射方法通常以量子门数、线路深度(时延)以及保真度等作为优化目标，根据问题求解方式可分为两类：*优化方法和启发式方法，如表1-1所示。
　　量子线路映射的*优化方法通常将线路映射问题描述成其他优化问题，并使用专门的*优化工具求解。例如，部分研究[73-81]将映射问题描述成伪布尔优化(pseudo Boolean optimization，PBO)/SAT/SMT问题，并通过现有的SAT/SMT求解器进行求解；部分研究[75]为映射问题构建了解的*优子结构，并通过动态规划算法求解；部分研究[82-84]将映射问题表述成整数线性规划(integer linear programming，ILP)或混合整数规划(mixed integer programming，MIP)问题，并通过已有的数学工具进行求解；还有部分研究[85-87]将映射问题表述为时间规划(temporal planning，TP)/约束规划(constrained planning，CP)问题，并通过相应的TP/CP算法进行求解。这类方法虽然可以输出*优解或近似*优解，但由于其超多项式级的时间复杂度，通常仅适用于求解极小规模的量子线路映射问题。
　　相较于*优化方法，启发式方法具有更好的可扩展性，其时间复杂度一般是量子比特数和量子门数的多项式函数，因此可适用于各种规模的量子线路映射问题。Zulehner等[91]面向IBM的量子计算架构提出了一种启发式映射方法，该方法将量子线路分成若干层，并通过A*算法逐层搜索满足连通性约束的*优SWAP门序列，*后在前瞻策略等优化技术的辅助下较IBM的Qiskit软件平均减少了19

目录
前言
第1章 引言 1
1.1 研究背景 1
1.2 发展历史 2
1.3 量子线路映射的任务 9
1.4 量子线路映射的方法 10
1.5 全书结构 11
第2章 预备知识 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 布尔函数 15
2.2.1 一般布尔函数 16
2.2.2 可逆(布尔)函数 16
2.2.3 可逆逻辑门 17
2.2.4 可逆逻辑线路 19
2.2.5 可逆逻辑综合 20
2.3 量子态与量子比特 20
2.3.1 量子态 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 量子门计数 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 量子线路优化 42
2.6 量子计算体系结构 43
2.6.1 线性*近邻架构 43
2.6.2 二维网格结构 43
2.6.3 拓扑结构图 44
2.6.4 量子比特近邻结构 45
2.6.5 量子代价 47
2.6.6 量子不可克隆原理 47
2.7 NISQ计算设备 48
2.7.1 计算噪声 48
2.7.2 量子门约束 49
2.7.3 连通性约束 50
2.7.4 退相干约束 51
2.7.5 串扰约束 51
2.7.6 计算结果保真度 51
2.7.7 相关约束分析 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 量子门执行调度 58
2.8.9 量子线路调度 59
2.8.10 量子线路分布式映射 59
上篇 量子线路逻辑变换
第3章 可逆/量子线路变换与优化 63
3.1 基于规则的MCT线路变换 63
3.1.1 门关系与变换规则 63
3.1.2 门序列与变换规则 64
3.1.3 基于规则的线路化简算法 70
3.1.4 实例验证 72
3.1.5 实验结果及分析 74
3.2 基于模板的线路变换 75
3.2.1 模板定义 75
3.2.2 模板构建 76
3.2.3 基于模板线路优化 97
3.3 本章小结 109
第4章 分解变换与优化 110
4.1 MCT门分解 110
4.1.1 基本分解方法 110
4.1.2 MCT门分解优化 111
4.1.3 示例分析 113
4.1.4 实验结果与分析 114
4.2 线性近邻约束下的MCT门分解 114
4.2.1 问题描述 114
4.2.2 基本概念 115
4.2.3 近邻交互约束下的MCT门分解 116
4.3 基于设备拓扑感知的MCT门分解 125
4.3.1 问题描述 125
4.3.2 基本概念 126
4.3.3 硬件子拓扑选择 126
4.3.4 MCT线路关联门对生成 130
4.3.5 MCT线路分解映射 136
4.3.6 实验和结果分析 142
4.4 本章小结 145
第5章 线性*近邻量子线路变换 146
5.1 NCV线路的LNN构造和优化 146
5.1.1 NCV量子门三线分布 146
5.1.2 LNN线路*优综合算法 150
5.1.3 实验结果及分析 152
5.2 线性*近邻量子线路综合 154
5.2.1 N门前瞻*近邻方法 154
5.2.2 联合考虑*近邻方法 162
5.2.3 换门序原则 163
5.2.4 优化近邻化策略 163
5.2.5 量子线路化简 168
5.2.6 实验结果与分析 169
5.3 LNN排布的线路近邻化 172
5.3.1 线序重排代价度量模型 172
5.3.2 基于LNN排布的线路近邻化 175
5.3.3 线路优化 179
5.3.4 实验结果及分析 182
5.4 本章小结 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 实验结果与分析 205
6.4 考虑时序权重的量子比特分配 207
6.4.1 时序交互图 207
6.4.2 量子比特分配算法 207
6.4.3 实验结果与分析 210
6.5 考虑活跃度的量子比特分配 211
6.5.1 量子比特分配顺序 211
6.5.2 量子比特布局 215
6.5.3 举例 217
6.6 本章小结 219
第7章 量子比特近邻化及路由 220
7.1 问题描述与分析 220
7.1.1 问题描述 220
7.1.2 问题分析 222
7.2 量子比特路由方法 226
7.2.1 量子比特路由的CNOT门优化问题 226
7.2.2 量子比特路由策略 227
7.3 迭代寻优近邻化与路由策略 233
7.3.1 基本思想 233
7.3.2 局部搜索算法 233
7.3.3 CNOT门数优化算法 235
7.3.4 实验结果与分析 237
7.4 基于活跃度量子比特近邻化与路由 243
7.4.1 近邻化代价 243
7.4.2 双量子比特门序列的选择 244
7.4.3 量子比特近邻化 246
7.4.4 复杂度分析 248
7.4.5 实验结果及分析 249
7.5 本章小结 251
第8章 噪声约束的量子线路映射及优化 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 实验结果 267
8.3 基于变换与调度的保真度优化 268
8.3.1 串扰与噪声 268
8.3.2 量子门交换规则 269
8.3.3 面向串扰约束的量子线路调度 280
8.3.4 量子比特状态更新 285
8.3.5 实验结果和分析 288
8.4 本章小结 289
第9章 分布式映射及优化 291
9.1 分布式映射概述 291
9.2 分布式架构模型 292
9.2.1 模型构建 292
9.2.2 分布式量子线路映射 295
9.3 分布式量子线路划分与优化 298
9.3.1 线路划分策略 298
9.3.2 传输代价优化策略 302
9.3.3 传输代价优化算法 307
9.4 分布式量子比特分配 313
9.4.1 全局量子态路由代价 313
9.4.2 分布式量子比特分配算法 314
9.5 分布式量子态路由 316
9.5.1 QPU内量子态路由策略 316
9.5.2 QPU间量子态路由策略 320
9.5.3 量子态路由算法 322
9.6 实验结果与分析 324
9.6.1 实验配置 324
9.6.2 算法性能 325
9.7 本章小结 328
参考文献 330