量子计算在近年来蓬勃发展，它针对特定计算任务展现出了强大的计算加速能力，可用于加速求解经典计算中的难解问题，如数据库搜索[1]、机器学习[2-3]、化学反应模拟[4-5]、加密解密[6]、优化问题[7]等.量子计算机(量子芯片)是实施量子计算的物理设备，量子位是量子计算机的基本运算单元，量子门操作用于操控量子位状态，由量子门操作序列组成的量子程序可完成特定的量子计算任务.Intel,Google,IBM等企业已相继发布了5～72量子位的量子计算机[8-10].IBM提供了量子计算云服务[11]，用户可通过接口向云服务提交执行量子计算任务.在过去数10年中，量子计算的理论研究取得了较大进展；但量子计算机物理机的相关研究却始终难以克服噪声问题带来的影响.现在的量子计算机属于中等规模带噪声量子计算机(noisy intermediate-scale quantum computer,NISQ computer)类型的量子计算机[12].在该类量子计算机中，量子位状态不稳定，量子门操作可能出现错误.虽然量子纠错编码可以使量子计算机获得容错能力，但其成本太高(构造一个容错量子位需要20～100个物理量子位)，无法在现阶段的量子计算机上实施.
量子计算机有超导[13]、离子阱[14]、光量子[15]等物理实现方式.本文主要关注超导量子计算机.面向超导量子计算机的量子程序映射策略可将高级语言编写的量子算法转换为能在超导量子计算机上直接执行的量子门操作指令序列.通常，量子程序映射策略的优化目标包括：1)将量子程序映射至具有低错误率的量子位和连接上执行，以提升量子程序的执行保真度.2)缩减映射过程中插入的SWAP操作数，降低映射后量子线路的复杂度，间接提升执行保真度.3)缩减映射后量子线路深度，以减少由较短的量子位状态保持时间引发的错误.
量子计算云服务的出现和兴起为传统量子程序映射策略[16-19]带来了新的挑战.传统量子程序映射策略通常仅支持映射单个量子程序.在执行量子程序时，量子计算机上未被分配的物理量子位会被闲置，这导致量子计算机中的资源未得到充分利用.此外，对量子计算云服务的访问请求越来越多，延长了服务等待时间.因此有必要通过并发机制，同时映射、执行多个量子程序来提升量子计算机的通量和资源利用率.然而并发量子程序映射带来了不可忽视的可靠性下降的问题.这是由于：量子计算机中健壮资源稀缺，不足以为每个量子程序分配足够的健壮资源；并发量子程序之间的串扰[20]；映射并发量子程序时，启发式搜索的搜索空间被限制，造成更高的量子程序映射开销.先前的工作[21]表明，同时执行2个并发量子程序会导致平均保真度降低12%.
本文重点讨论面向超导量子计算机的量子程序映射技术，对先前技术进行归纳、分析和对比.针对并发量子程序映射问题，本文提出一种新的并发量子程序映射策略，在提升量子计算机通量的前提下尽可能保证量子程序的执行保真度.本文的主要贡献可以归纳为3点：
1)深入分析了近年来面向超导量子计算机的量子程序映射工作，并进行分类，深入剖析了不同类别映射策略的特点.
2)揭示了并发量子程序映射可能导致映射成本提升和保真度下降的问题；据此设计并发量子程序映射策略，包括社区发现辅助的量子位划分(community detection assisted qubit partition,CDAQP)算法、引入跨程序SWAP操作的映射转换算法X-SWAP，帮助提升并发量子程序的执行保真度，降低映射成本.
3)提出了量子程序映射任务调度器，可从待执行任务队列中选择最佳量子程序组合并发执行；允许在量子计算机通量和保真度2方面进行权衡.
本文设计的系统是一个初步的面向NISQ量子计算机的操作系统原型(quantum operating system,QuOS).
1 量子计算概述
1.1 量子计算
量子位是量子计算机中的基本运算单元.如图1所示，布洛赫球面用于表示单个量子位的状态.布洛赫球面上下2个极点分别代表2个量子计算基态：|0〉和|1〉.一个量子位的状态为2个基态|0〉和|1〉的叠加，即|ψ〉=α|0〉+β|1〉.其中，α和β为复数，且满足|α|2+|β|2=1,α和β分别为该量子位|0〉和|1〉两个量子基态对应的概率幅.当采用读出操作对量子位状态进行测量时，测量结果为0的概率为|α|2，测量结果为1的概率为|β|2.类似地，2个量子位的状态可以表示为4个量子计算基态的叠加：|ψ〉=α00|00〉+α01|01〉+α10|10〉+α11|11〉.单量子位门操作(如H，X，Y，Z门等)可改变单个量子位的状态.受控非(controlled-not,CNOT)门为双量子位门操作，它作用于2个量子位.若其中控制量子位被置为1，目标位的状态将会被翻转.涉及3个或更多量子位的门操作可被分解为单量子位门和双量子位门操作的组合序列[22].
Fig.1 The Bloch representation of a single qubit
图1 单量子位的布洛赫球面表示
1.2 量子计算机
IBM系列量子计算机属于超导量子计算机，具有基于约瑟夫森环结的transmon量子位[13]和基于微波的量子门操作[23].超导量子计算机仅在相邻物理量子位之间存在连接.涉及2个量子位的双量子位门操作仅能在具有相互连接的2个相邻物理量子位上执行.图2展示了IBMQ Melbourne(后文称IBM-Q16)超导量子计算机的量子位拓扑结构.
Fig.2 Qubit topology of IBMQ Melbourne
图2 IBMQ Melbourne的量子位拓扑结构
1.3 量子计算机中的错误
由于量子计算机的物理量子位状态不稳定，量子位间的连接脆弱且易受干扰.在量子计算机上运行的量子程序可能会发生3种类型的错误：1)由较短的量子位状态保持时间导致的保持错误.保持错误主要受到在量子计算机上执行的量子程序深度的影响.量子程序深度越深，执行时间越长，可靠性就越低.2)由易错的量子门操作导致的操作错误.操作错误主要受到在量子计算机上执行的量子程序复杂度的影响.量子程序中包含的门操作越多，出错的概率越高.3)测量操作带来的读出错误.量子程序在执行结束后需要执行测量操作以获取量子位状态.测量操作不可靠，可能读出错误的状态.
IBM量子计算云服务提供了错误率标定数据，可通过接口获取.标定数据约每24 h更新一次.
1.4 量子程序映射
量子程序由一系列量子门操作组成，可用量子线路表示.图3(a)展示了三量子位Toffoli门操作分解为单、双量子位门操作序列后的量子线路.其中每条横线代表一个逻辑量子位，横线上的节点代表单、双量子位门操作.图3(b)展示了该量子线路的有向无环图(directed acyclic graph,DAG).DAG用于表示量子程序中量子门操作的执行顺序依赖关系，其中每个节点代表一个量子门操作.当一个量子门操作在DAG中有前驱节点未被执行时，该量子门操作无法执行.当一个量子门操作在DAG中没有未执行的前驱节点时，它在逻辑上才可被执行.
Fig.3 The quantum circuit and DAG of decomposed Toffoli gate
图3 Toffoli门分解后的量子线路和DAG
求解量子程序映射问题需要遵循3个约束：1)每个逻辑量子位都需要被映射至量子计算机中的一个物理量子位上，且该物理量子位不能再映射其他的逻辑量子位.2)若一个量子门操作未执行，其后继的量子门操作也不能被执行.3)当一个双量子位门操作涉及到的逻辑量子位的映射位置在物理上相邻时，该双量子位门操作才能被执行，否则可在量子线路中插入SWAP操作(一个SWAP操作由3个CNOT操作组成，用于交换2个逻辑量子位的映射位置)，使涉及到的逻辑量子位在物理上相邻.
解决量子程序映射问题一般包括构建初始映射和映射转换2个步骤：
1)构建初始映射.即把每个逻辑量子位映射至一个物理量子位.初始映射对量子程序的后续映射成本和执行保真度具有重要影响.初始映射需要满足：程序被分配在量子计算机中最健壮的量子位上；初始分配的量子位邻近，便于节约后续映射成本.
2)映射转换.即在量子线路中插入SWAP操作，满足所有双量子位门操作的逻辑量子位映射位置约束，使所有双量子位门操作均可执行.映射转换时插入的SWAP操作会导致量子程序执行保真度降低，因此需保证插入的SWAP操作尽可能少，且尽可能使用量子计算机中的健壮资源.
1.5 量子操作系统
量子操作系统是量子计算机中软硬件资源的管理者，负责管理、配置具有不同物理实现方式的量子位；调度量子程序；为量子程序提供最可靠的映射方案.量子计算机操作系统与经典计算机操作系统在设计原则和设计目标上具有较大区别.本文设计的系统是一个初步的面向NISQ量子计算机的操作系统原型QuOS.在后续工作中，作者将进一步对量子操作系统和量子计算技术栈中的其他技术进行探索.
2 量子程序映射技术概览
量子程序映射技术属于量子计算技术栈[24]中的软件栈层次，位于高级语言(用于表示特定的量子算法)和量子计算机系统结构(包括量子位、量子门操作、量子纠错等)层次之间.量子计算软件栈覆盖范围广，涉及多量子位门操作分解[22,25]、量子线路映射前/后优化[26-27]、量子程序调试与断言[28-29]、量子缓存[30]、并发量子程序映射[21,31-32]等问题.本文针对量子程序映射问题进行研究，假设量子线路中的多量子位门操作已被分解，线路中的门操作均能在目标量子计算机上执行；不进行映射前/后优化；仅考虑在量子线路中插入SWAP操作，满足所有双量子位门操作的逻辑量子位映射位置约束.
量子程序映射问题已被证明为NP-完全问题(NP-Complete problem)[33-34].文献[35]综述了常见的量子计算机物理实现技术及相应的量子位拓扑结构，包括一维、二维拓扑结构.针对具体的物理量子位拓扑结构，以保真度或插入SWAP数为优化目标的量子程序映射策略陆续被提出.这些量子程序映射技术可分为2类：
1)基于数学问题求解器的最优化方法.该类方法可根据量子程序映射问题设计约束条件和优化目标，将量子程序映射问题转换为等价的数学优化问题，并采用求解器求解.这类方法可求得小型量子程序映射问题的最优解或近似最优解.但算法时间复杂度高，运行时间长，无法支持求解大型量子程序(具有数十个以上量子位的量子程序)映射问题.此外，该类方法难以同时对多个优化目标进行优化，且难以实现多个优化目标之间的权衡.
2)启发式方法.启发式方法采用启发式信息辅助搜索.量子程序映射策略依据启发式信息或贪心策略确定逻辑量子位初始映射位置，后根据启发式信息筛选出最合适的SWAP操作插入程序进行映射转换.启发式方法更为灵活，具有更佳的可扩展性，不受限于量子芯片和量子程序的规模，有处理更大规模量子程序映射问题的能力.然而启发式策略无法保证求解所得的结果为最优解.可能存在保真度更高、映射成本更低的映射方案.
2.1 最优化方法
本文对具有代表性的最优化方法进行了整理汇总，如表1所示.现有工作中，量子程序映射问题可等价转化为如下类型数学问题：可满足性(Boolean satisfiability,SAT)问题、可满足性模理论(satis-fiability modulo theories,SMT)问题、伪布尔优化(pseudo Boolean optimization,PBO)问题、动态规划(dynamic programming,DP)问题、时序规划(temporal planning,TP)问题、约束规划(constrained planning,CP)问题、整数线性规划(integer linear programming,ILP)问题、混合整数规划(mixed integer programming,MIP)问题等.
Table 1 Optimization Methods for Quantum Program Mapping
表1 量子程序映射最优化方法
文献方法时间转换问题优化目标特点Shafaei等人的工作[36]2014MIPSWAP数针对2D架构优化,采用启发式方法优化求解器求解结果Wille等人的工作[37]2014PBO∕SATSWAP数构建了量子程序映射问题到PBO问题的转换,为启发式与最优化方法的对比提供依据Lye等人的工作[38]2015PBOSWAP数对比了启发式方法和最优化方法实例Booth等人的工作[39]2018TP∕CP线路深度∕SWAP数结合2种求解器的优点,提供高质量的映射方案Qubit Allocation[33]2018DPSWAP数采用动态规划计算,存储计算中间结果,避免重复运算MUQUT[40]2019ILP线路深度∕SWAP数结合求解器与启发式方法,提升执行保真度T∕R-SMT[18]2019SMT线路深度∕保真度将错误率引入优化目标,提升执行保真度IBM QX Mapping for Minimal Mapping[41]2019SMTSWAP数缩小搜索空间,提升执行效率,保证近似最优解TriQ[42]2019SMT保真度在多平台上对比实验,揭示了量子计算机结构对性能的影响XtalkSched[20]2020SMT保真度将串扰错误率加入优化目标,缓解串扰错误(TB-)OLSQ[43]2020SMT线路深度∕SWAP数∕保真度采用近似策略提升求解效率;支持多种优化目标
若从量子程序映射问题转化为等价数学优化问题，需转化的内容一般包括：1)待优化变量.量子程序映射过程中，逻辑量子位的映射位置、门操作的执行时刻、SWAP路径均需转换为等价数学优化问题中的待优化变量，以便于求解.2)约束条件.须将量子程序映射问题中的限制条件(如门操作需顺序执行、每个物理量子位仅允许映射一个逻辑量子位等)转换为等价数学优化问题中的限制条件.3)优化目标.优化目标通常包括程序执行保真度、映射过程中插入的SWAP操作数目、映射后线路深度(或程序执行时间)3种.
文献[36]将量子程序映射问题转化为MIP问题.该策略将量子线路按照数据依赖关系划分为多个层，每层中的门操作不涉及相同的逻辑量子位，可同时执行.该映射策略首先确定初始映射，然后利用求解器确定相邻2层之间的映射转换SWAP操作.映射所需的SWAP数目作为优化目标.MUQUT[40]根据量子程序映射问题构造ILP问题，并采用求解器Gurobi[44]求解.该策略同样采用将量子线路分层并在层间插入SWAP的方法进行量子程序映射.线路深度作为优化目标.该策略将量子程序映射位置所占矩形区域在量子芯片上滑动，来搜索可靠性最高的映射位置.
Wille等人[37]实现了量子程序映射问题到PBO问题的转化，实现了最优化方法与启发式方法的对比，为启发式方法结果的评价提供了依据，并在后续工作中[38]给出了与启发式方法对比的实际案例.
Booth等人[39]将量子程序映射问题转换为TP问题，结合线路深度和插入SWAP数，构建加权优化目标函数.该策略将TP问题和CP问题进行结合.首先求解TP问题，提供可靠的初始解决方案，在此基础上求解CP问题，进一步提升解决方案的质量.
Siraichi等人[33]对比了最优化方法与启发式方法，并给出了基于DP的最优化量子程序映射算法实现.DP执行过程中可存储中间结果，避免重复计算，提升计算效率.
文献[18,20,41-43]采用SMT求解器求解量子程序映射问题.常见SMT求解器包括Z3[45],vZ[46].文献[18]分别设计了T-SMT和R-SMT.T-SMT以程序执行时间为优化目标，使门操作序列中最后一个门操作的完成时间最小化.而R-SMT以程序执行保真度为优化目标，结合CNOT门和读出操作错误率数据，设计了CNOT错误率与读出操作错误率的加权目标函数，允许为不同种类的错误分配不同的权重.文献[20]对量子程序执行时的串扰错误进行了精准建模，并将串扰错误率结合至目标函数中，采用SMT求解器最小化串扰错误.文献[43]介绍了一种最优化方法OLSQ和近似最优化方法TB-OLSQ，可对程序执行保真度、插入SWAP数目、映射后线路深度三者中任一优化目标进行优化.TB-OLSQ在可被连续执行的门操作集合之间插入SWAP操作，提升求解器求解效率，求得近似最优解，保证程序执行的保真度.TB-OLSQ针对量子近似优化算法(quantum approximate optimization algorithm,QAOA)进行了特殊优化，可缩减映射成本及映射后线路深度.TriQ[42]构建了两两物理量子位之间交互的可靠性矩阵，并据此转化量子程序映射问题为SMT问题，优化程序的执行保真度.TriQ对比了多个量子程序在不同量子计算平台上的性能，揭示了量子芯片结构对性能的影响.
2.2 启发式方法
启发式方法的代表性工作如表2所示.针对目标平台，启发式方法可分为2类：
Table 2 Heuristic Methods for Quantum Program Mapping
表2 量子程序映射启发式方法
文献方法时间目标平台特点Shafaei等人的工作[47]2013简化模型针对一维芯片模型,将量子程序映射问题转化为图排序问题求解Wille等人的工作[48]2016简化模型采用前瞻算法,优化1D∕2D网格结构的SWAP成本Bhattacharjee等人的工作[49]2018简化模型针对2D网格结构,采用启发式策略缩减了映射成本QURE[17]2019简化模型采用同构子图搜索方法最大化保真度Qubit Allocation[33]2018特定芯片初始映射最大化已满足映射相邻关系的CNOT操作数IBM QX Mapping for Arbitrary Circuits[50]2018特定芯片采用A*算法,寻找低成本的层间映射转换IBM QX Mapping for SU(4) Circuits[27]2019特定芯片针对SU(4)量子线路进行映射策略优化VQA∕VQM[19]2019特定芯片考虑错误率数据,将量子程序映射至健壮资源上执行Smith等人的工作[51]2019特定芯片采用连通树映射算法寻找SWAP路径,在多个平台上进行评测Siraichi等人的工作[52]2019特定芯片基于子图同构和令牌交换建模量子位映射问题,简化映射问题SABRE[16]2019特定芯片设计更高效的启发式搜索空间,提供指数级别加速Greedy V∕E[18]2019特定芯片采用不同策略进行初始映射,提升执行保真度SQUARE[53]2020特定芯片采用启发式方法动态分配、回收量子位,优化资源占用
1)针对简化模型的启发式算法.该类算法通常将量子芯片的拓扑结构简化为1D线性模型或2D网格模型.Shafaei等人依据最小线性排序(minimum linear arrangement,MinLA)问题，设计启发式策略[47]，缩减映射时所需的SWAP操作数目.该策略将量子线路分割为多个子图，并在每个子图中应用MinLA问题求解最佳SWAP路径.Wille等人[48]采用前瞻算法，对1D和2D两种简化模型，优化插入的SWAP操作数，降低了56%的SWAP成本.Bhattacharjee等人[49]面向2D量子芯片网格模型，以插入的SWAP操作数为优化目标，设计新的启发式量子程序映射策略.通过3个步骤：选择量子位、映射量子位和插入SWAP，降低了映射开销.QURE[17]在为量子程序确定初始映射后，搜索2D网格模型中的同构子图.即在量子芯片上滑动包括了映射位置的矩形区域，预估不同位置下量子程序的执行保真度.选择可靠性最高的区域作为量子程序的最终映射区域.
2)针对特定量子芯片结构的启发式算法.该类算法可根据具体量子芯片架构和错误率数据完成映射.Siraichi等人提出启发式方法[33]，相比于最优化方法，能处理更大规模的量子程序映射问题.该策略在初始映射中，最大化已满足映射相邻关系的双量子位门数，之后插入SWAP进行映射转换.Zulehner等人针对任意量子线路，设计启发式映射策略[50].类似于文献[36,40]，该策略首先根据数据依赖关系将量子线路划分为多个相互独立的层，每个层中的门操作可同时执行；之后采用A*算法搜索相邻层之间成本最低的映射转换SWAP操作.此后，Zulehner等人针对特殊的SU(4)程序对映射策略进行了改进[27].该策略通过预处理步骤，对程序内门操作进行分组，减小映射复杂度.之后采用A*算法进行映射，并进行映射后优化，提升SU(4)程序执行保真度.Tannu等人的工作[19]在文献[50]的基础上，引入了对量子计算机中错误率数据的分析，提出了考虑噪声的量子程序映射算法，利用了健壮资源，提升了程序执行保真度.Smith等人[51]利用连通树映射算法，寻找最优SWAP路径，并在多个量子计算平台上进行了评测，策略适用于不同的量子芯片拓扑结构.Siraichi等人[52]将量子位映射问题转化为子图同构问题和令牌交换问题的组合，简化量子位映射问题，利用已有的启发式策略进行求解.SABRE[16]通过对量子程序映射转换问题的精准建模，缩减了启发式搜索空间，提供了更有效的SWAP操作，为量子程序映射算法带来了指数级别的加速.Murali等人的工作[18]中进行了不同种启发式策略和最优化策略的对比.对比了2种启发式映射方案的性能，分别为：优先映射最频繁使用的量子位和优先映射最频繁使用的连接.该工作认为启发式方法具有更高的可扩展性，具有处理更大型量子程序映射问题的能力.Ding等人提出启发式算法[53]，指导动态分配和回收量子位，利用量子位的局部性、量子程序的模块性和并行性，复用量子位，将量子程序的执行保真度提升了1.47倍.
3 基于社区划分的初始映射构建
3.1 先前策略的问题
量子程序的初始映射极为关键.对于单个量子程序而言，合适的初始映射可以帮助节约后续映射成本，提升量子程序的执行保真度.而对于并发量子程序映射问题，合适的初始映射不仅可以缩减映射成本，还可以尽可能地利用量子计算机中的健壮资源，避免资源浪费，减小并发量子程序之间的干扰，提升整体执行保真度.
量子计算机中健壮资源分布和物理拓扑结构各不相同，先前的量子位初始映射策略通常利用贪心算法或启发式搜索算法，将一个量子程序分配至量子计算机中最健壮的区域.图4中虚线连接代表具有高错误率的不可靠连接，虚线框代表量子程序的映射位置.若一个具有4个量子位的量子程序需要被映射至如图4所示的量子计算机上，它将会被映射至物理量子位Q1，Q2，Q5，Q6.映射策略通常选择具有可靠连接的物理量子位，以提升执行保真度.
Fig.4 An example for qubit mapping
图4 量子位映射示例
为了提升量子计算机的通量和资源利用率，并发量子程序映射策略应运而生[21].然而并发量子程序映射也为传统量子程序映射策略带来了新的挑战.尽管可以将并发量子程序合并为一个量子程序，采用传统的面向单个量子程序的映射策略[16,18]进行映射.但传统映射策略并不适合处理并发量子程序映射任务，可能导致3个问题：1)无法保证并发量子程序的执行保真度.量子计算机中健壮资源有限，无法保证不同规模的量子程序都被分配足够健壮的资源.2)并发量子程序数目无法在线进行调整.例如当并发量子程序执行时，其中一个量子程序保真度大幅降低，传统映射策略无法将并发量子程序组合回退为单独执行.3)传统映射策略无法利用并发量子程序映射问题中新的优化契机.例如，采用跨程序SWAP操作可减少并发量子程序的映射成本.
现有的并发量子程序映射策略[21]允许并发执行2个量子程序，但其资源利用率和执行保真度仍有待提升.下面在图5中以一个例子来说明现有的并发量子程序映射策略面临资源利用率低的问题.使用现有的并发量子程序映射算法时，大规模的健壮物理量子位集合可能会被割裂为规模较小的量子位集合碎片.这些碎片中仅包含很少的物理量子位，不足以映射任何量子程序，导致健壮资源未被利用.
Fig.5 Previous initial mapping technique incurs resource under-utilization
图5 先前的初始映射策略导致资源利用率低
图5展示了采用先前工作[21]中提出的FRP策略构建量子程序初始映射的例子.图5中有2个量子程序P1(5量子位)和P2(4量子位)需被映射至IBM-Q16上.图5中展示了量子计算机IBM-Q16的物理结构图，其错误率标定数据采集于2019年12月27日.具有较高错误率的不可靠连接在图中被标注为虚线，不可靠的量子位同样进行了标注.P1先被映射.FRP策略从量子计算机中的一个具有足够多高utility值的邻居的量子位开始，扩展分配区域.该策略定义指标utility为：一个量子位所包含的连接数/连接上CNOT操作错误率之和[21].因此，物理量子位Q3，Q4，Q5，Q9和Q10被用于映射量子程序P1.P1映射完成后，映射策略无法为P2找到映射位置.因为在Q0～Q2，Q11～Q14中无法找到一个具有足够多健壮邻居的分配起点；而Q6～Q8仅包含3个量子位，无法供P2分配，造成了资源浪费.实际上存在更好的映射方法，能使量子计算机中的可靠资源得到充分利用，减少资源浪费.
3.2 算法设计
对于并发量子程序映射，我们观察到3点现象：1)量子芯片上的健壮量子位和连接是有限的.2)量子芯片上的某些量子位与周围的量子位有更多的连接.如图2所示，Q1与3个相邻的物理量子位相连，而Q7仅与1个量子位相连.3)一个量子程序的量子位应当被映射到邻近的物理量子位上.并发量子程序之间的初始映射应避免相互干扰，公平利用量子计算机中的健壮资源.
本文针对并发量子程序映射问题提出了一种新的映射策略，即社区发现辅助的量子位划分(CDAQP)算法.该算法首先构造一棵由量子位组成的层次树，协助搜索量子计算机中紧密连接的健壮量子位集合.图6展示了CDAQP算法的框架.CDAQP根据从IBMQ接口[11]获得的量子芯片拓扑结构和错误率标定数据构建层次树.在层次树中，叶节点表示特定的物理量子位；中间节点表示其子节点的并集.层次树构建完成之后，CDAQP自底向上迭代层次树，查找可用于初始分配的社区.最后，根据贪心策略分配量子位.详细说明如下.
Fig.6 Qubit mapping framework by using CDAQP algorithm
图6 CDAQP算法量子位映射框架
1)层次树构建
层次树是对量子芯片中健壮资源分布的建模，有助于定位量子芯片上健壮的量子位和连接.算法1基于fast-Newman(FN)社区检测算法[54]构建层次树.该算法将物理量子位划分为社区.一个社区中的物理量子位具有可靠且紧密的相互连接.相反，社区与社区之间的连接具有相对较低的可靠度.
算法1.层次树构建算法.
输入：量子计算机拓扑结构图、错误率标定数据；
输出：层次树HT.
① HT←list()；/*初始化HT为空列表*/
② 为每个量子位在HT中创建一个叶节点；
③ while HT.length>1 do
④ 选择HT中能使f(A,B)值最大的
2项A和B；
⑤ 合并A，B为新节点New_Node，并将A，
B分别设置为New_Node的左右子树；
⑥ HT.append(New_Node)；
⑦ HT.remove(A)；
⑧ HT.remove(B)；
⑨ end while
⑩ return HT.
算法初始化时，每个物理量子位对应一个社区，即层次树中的一个叶节点.算法不断合并能够使奖励函数f最大化的2个社区，直到最终只剩下一个包含所有物理量子位的社区.在该过程中，每个社区对应层次树中的一个节点，该节点是可用于分配量子位的一个候选区域.奖励函数f被定义为合并2个社区所带来的收益：
f=Qmerged-Qorigin+ωEV,
(1)
其中，Q代表一种社区划分方案的模块度(即
其中eii代表该划方案中社区i内的边占量子计算机中所有边的比例，ai则代表所有涉及到社区i内节点的边占量子计算机中所有边的比例),Q的值越高，代表着一个社区划分方案越合适.Qorigin和Qmerged分别代表原划分情况和合并了2个社区之后的划分情况的模块度.E代表待合并的2个社区间的边上CNOT操作的平均可靠度(可靠度为1-操作错误率)，V代表2个待合并社区的量子位上的读出操作平均可靠度.奖励函数f使得CDAQP在划分时能够同时考虑物理拓扑和错误率.ω是一个权重参数.对于特定的量子芯片，我们可以通过改变ω的值来调整物理拓扑与错误率间的权重.如果ω=0，则CDAQP完全按照物理拓扑进行划分；随着ω的增加，社区划分算法开始逐渐依赖于错误率数据；如果ω持续增加，错误率的权重将超过物理拓扑的权重，导致其退化为基于错误率的贪心算法.ω值如何设置将在3.3节中进行讨论.
层次树有3个特点：1)层次树中的每一个节点都是可用于初始映射的候选量子位集合.2)在一个社区中的物理量子位相互连接紧密，能够帮助减小量子程序映射成本.3)具有低读出操作错误率和健壮连接的量子位会优先被合并.因此量子位集合越健壮，其在层次树中的深度就越深.层次树的这些特点能够帮助定位量子计算机上的健壮资源，为量子程序提供更优秀的初始映射.
接下来，采用图6中的例子解释为何层次树能帮助选择健壮的初始映射.图6中，左侧展示了IBMQ London的物理结构图，每个节点对应的数值代表该物理量子位上读出操作的错误率，在连接上的数值代表该连接上的CNOT操作错误率.接着展示了根据拓扑结构和错误率数据构建出的层次树.层次树构建过程为：①Q0和Q1之间具有最低的错误率，因此它们被首先合并为一个社区.②虽然Q1，Q3间的CNOT操作错误率低于Q1，Q2间的CNOT操作错误率，但Q2被首先加入社区{Q0，Q1}.这是因为算法倾向于将连接紧密的量子位合并为一个社区，从而避免量子计算机中健壮资源的浪费.同样，Q3，Q4也被合并为一个社区.③所有的物理量子位被合并为一个社区，形成层次树的根节点.算法不仅考虑量子计算机中的资源可靠性，也同样考虑量子计算机的物理拓扑结构，选取连接紧密的量子位.这可以避免量子计算机中健壮资源的浪费，提高资源利用率，能使量子计算机映射更多的量子程序.
错误率标定数据并非随时改变，IBM量子计算云服务约每24 h标定一次错误率数据.因此在错误率标定的一个周期内，构建的层次树可被存储，以供重复使用，不会造成不可接受的运算开销.
2)量子位划分和分配
算法2根据层次树将量子位划分为多个区域供并发量子程序进行初始映射.算法优先为具有高CNOT density的量子程序划分区域.CNOT density被定义为一个程序内CNOT操作数/该程序内量子位数.对于每个量子程序，算法自底向上搜索层次树，找到可供分配的量子位集合.选择具有最低平均错误率的候选量子位集合用于映射该程序.最后，使用最大权重边优先(greatest weighted edge first)策略[18]进行量子位映射.该策略将量子程序中交互数目最高的2个逻辑量子位映射到量子芯片上最健壮的边上，有助于生成具有高可靠性和低映射开销的初始映射.
算法2.量子位划分算法.
输入：层次树 HT、量子程序programs；
输出：量子位划分partition.
① 将programs按CNOT density降序排序；
② for program in programs
③ C←set()；
/*初始化候选节点C为空集*/
④ for l in HT.leaves
/*对于HT中的每个叶节点l */
⑤ candidate←search(l)；/*从l起自底向上搜索层次树，得到量子位数目满足待映射程序要求的节点candidate*/
⑥ C.add(candidate)；
⑦ end for
⑧ if C为空
⑨ 失败，回退至单独执行；
⑩ end if
node←node_with_the_max_fidelity(C)；
partition.add(node)；
将node中的量子位从HT的所有节点中移除；
if node的兄弟节点没有通向层次树中其
他节点的路径
将兄弟节点中包含的量子位从其祖先节点中移除；
移除兄弟节点到其祖先节点的链接；
end if
end for
return partition.
3.3 权重参数选择
在式(1)中，E表示量子位之间连接的可靠性，V表示量子位读出操作的可靠性.该设计能帮助在每次迭代中，将具有健壮连接和较低读出错误率的可靠量子位合并到一个特定的社区中.不可靠的量子位最终才将被添加到社区中.在执行量子位分配时，CDAQP自底向上搜索层次树，查找初始分配的候选区域.不可靠的量子位不易被选择，提高了整体可靠性.
使用CDAQP可能会导致分配给一个量子程序的物理量子位数目大于该量子程序真正所需的物理量子位数目.例如一个具有4个逻辑量子位的量子程序被映射到图6中所示的量子芯片上.唯一可能的分配区域是该层次树的根节点：{Q0，Q1，Q2，Q3，Q4}.这会导致一个量子位冗余.为了避免浪费，未被使用的冗余量子位会被标记，它们可以被添加到相邻的社区，用于其他量子程序的初始映射.
对于层次树中的一个节点，本文定义最大冗余量子位数，代表当一个量子位集合(一个层次树节点)被分配给一个量子程序进行初始映射时，可能导致的最大未被使用的物理量子位数目.一个层次树节点node对应的最大冗余量子位数可计算为：node.n_qubits-(1+max(node.left.n_qubits,node.right.n_qubits)).
奖励函数f中的权重参数ω的增大会导致层次树的退化，即层次树的每次合并过程中，仅有一个包含一个物理量子位的叶节点被合并入新社区.这时，新社区对应的层次树节点的最大冗余量子位数为0.即ω的增大可以导致平均最大冗余量子位数的减小.我们连续21天采集了IBM-Q16的错误率标定数据.对于每天的错误率标定数据，按0.05的步长从0～2.5变化ω的值，执行算法1，并记录层次树中冗余量子位的平均数量，如图7所示.图7中节点颜色越深代表越多结果重叠在该位置上.采取肘部原则，取ω=0.95.在这种情况下，CDAQP算法既考虑了物理拓扑结构，又考虑了错误率数据.平均冗余量子位数在这种情况下为0.29.在IBM-Q50上进行了相同的实验，ω=0.40.此外，CDAQP不仅可以为并发量子程序提供可靠的初始映射，同样可以处理只有一个量子程序需要映射的问题.
Fig.7 Select the knee solution as ω
图7 选取肘部方案为ω的值
4 跨程序SWAP映射转换
4.1 跨程序SWAP操作优势分析
并发量子程序映射问题为传统映射转换策略带来了新的挑战.当多个量子程序同时运行时，映射转换所需插入的SWAP数目可能增加.先前的并发量子程序映射转换策略[21]顺序处理每一个量子程序，后被处理的程序只能使用未被其他程序占用的量子位.对于一个特定量子程序来说，要使用SWAP操作移动量子位，使2个量子位相邻，最短SWAP路径可能涉及到多个量子位.SWAP操作只在相邻的量子位之间进行.如果最短SWAP路径上的任何一个量子位被其他程序占用，将引入更多的SWAP操作，导致整体的可靠性下降.
优秀的映射转换策略应当能够更好地利用所有可能的SWAP操作，在最大程度上降低量子程序映射转换的开销.本文提出了引入跨程序SWAP操作的映射转换算法X-SWAP.与先前映射转换策略不同，该算法并非单独处理每个量子程序，而是对所有并发量子程序同时进行映射转换.X-SWAP既允许程序内SWAP操作，又允许跨程序SWAP操作.SWAP操作涉及到的2个物理量子位可能分别属于2个量子程序(跨程序SWAP)，也可能只属于1个量子程序(程序内SWAP).SWAP所涉及到的逻辑量子位上的后续门操作都需在SWAP操作之后执行.
该算法允许在所有物理量子位上执行SWAP，避免了先前策略中由于量子位被占用而导致的额外SWAP开销.另外，当2个量子程序映射相邻时，启用跨程序SWAP操作能够帮助缩减映射转换成本.X-SWAP相比于之前的映射转换策略的主要优点在于扩大了启发式搜索空间，涵盖了更多的量子位，引入更多可能的SWAP操作.
在下面2种情况下，跨程序SWAP操作优于程序内SWAP操作：
1)1个跨程序SWAP操作可以替代2个程序内SWAP操作.图8展示了将2个量子程序映射到具有6个物理量子位的量子计算机上的例子.图8(a)展示了需要映射的2个量子程序，图8(b)展示了2个量子程序的初始映射，以及在不允许跨程序SWAP操作情况下的映射过程.对于量子程序P1，g1和g2可以直接执行，无需插入SWAP操作，但g3却不能直接执行，需在q2和q3之间插入SWAP操作.同理，对于量子程序P2，为了使g6能够执行，需要在q4和q6之间插入SWAP操作.
Fig.8 An inter-program SWAP can replace two intra-program SWAPs
图8 跨程序SWAP操作可替换2个程序内SWAP操作
然而，如果2个程序同时映射，可以引入跨程序SWAP操作降低量子程序的映射成本.图8(c)展示了使用跨程序SWAP操作进行映射转换的例子，只需要在q1与q5之间插入一个SWAP操作，即可完成映射转换.在这种情况下，q1与q5之间的一个SWAP操作代替了2个SWAP操作，降低了量子程序的映射成本，间接提升了量子程序执行保真度.
2)在进行映射转换时，跨程序SWAP操作可采取捷径.图9中，P1和P2被映射到具有9个物理量子位的量子计算机上.接下来需要处理门操作CNOT q1 q5.如图9(b)所示，先前工作中的映射转换策略[21]需引入{q1，q2}，{q1，q3}，{q1，q4}这3个SWAP操作才能完成映射转换，而跨程序SWAP操作仅需引入一个SWAP操作{q1，q9}.
Fig.9 Inter-program SWAPs take shortcuts
图9 跨程序SWAP可采取捷径
4.2 启发式搜索空间设计
由于单量子位门操作可以直接执行，无需SWAP操作.因此在映射转换过程中仅考虑CNOT门操作.对于一个量子程序P，图10展示了P中的关键门(critical gates,CG)操作.该量子线路的CNOT门操作可以分为4层(即l1～l4).同一层中的门操作不涉及相同的逻辑量子位，可以同时执行.l1是P的首层门操作(front layer，记为F)，它表示P的有向无环图(DAG)中没有未执行前驱节点的CNOT门操作的集合.DAG展示了P的数据依赖关系.关键门操作CG表示F中在第2层(l2)上拥有后继节点的门操作的集合.例如，在F中，g1在l2中拥有后继节点g3，而g2没有后继.因此，g1属于关键门操作，但g2不属于.如果执行了关键门操作g1，并将其从DAG中移除，g3就可被执行，首层门操作集合F也同时被更新.相比之下，优先处理g2不会帮助更新首层门操作F.
Fig.10 Critical gates
图10 关键门
对于每个程序Pi，如果其首层门操作集合中存在满足映射位置约束条件可直接执行的门操作，则执行该门操作，将其从DAGi中移除，并更新首层门操作集合.当所有程序的首层门操作集合中都没有可以直接执行的门操作时，需要插入SWAP，交换逻辑量子位的映射位置，将不可执行的门操作涉及的逻辑量子位移动到相邻的映射位置，从而使该门操作能被执行.为了快速更新首层门操作，缩小映射后线路深度，需要优先处理关键门操作.本文中的方法仅搜索与关键门操作涉及到的逻辑量子位相关的SWAP操作.
图11展示了一个量子程序映射转换的例子，其中g1和g3为关键门操作，所有与g1和g3中涉及到的逻辑量子位相关的SWAP操作被加入到候选SWAP操作中，通过启发式函数选出候选SWAP操作中的最优SWAP操作.当该SWAP操作被插入原线路后，量子程序映射被更新，一些原先不可执行的CNOT门操作可能变为可执行.重复迭代该过程，直到DAG中的所有CNOT操作都可执行.
Fig.11 SWAPs associated with critical gates
图11 与关键门操作相关的SWAP操作
4.3 启发式成本函数设计
启发式函数负责从启发式搜索空间中所有的候选SWAP操作中找到最佳SWAP.本文设计了新的启发式成本函数，利用并发量子程序映射问题的特点，鼓励高效跨程序SWAP操作的执行.
量子程序映射策略应使每个量子程序中各个量子位的映射位置相互靠近.否则，若2个量子位映射位置较远，如果要在这2个量子位之间执行CNOT操作，会引发很高的SWAP开销.SABRE[16]中使用了最近邻成本(nearest neighbor cost,NNC)函数来估算SWAP成本，进行量子程序映射.本文将SABRE[16]使用的NNC函数H用作启发式函数的一部分.H表示首层门操作集合的成本和扩展门操作集合的成本之和.扩展门操作集合是DAG中在首层门操作集合之后执行的n个(n默认等于逻辑量子位数)CNOT门操作的集合.每个门操作集合的成本计算为该集合中所有CNOT门的平均SWAP路径长度.
本文设计启发式函数，鼓励能够采取捷径的跨程序SWAP操作的执行.对于一个特定的量子计算机，已知其物理拓扑结构图和量子程序的初始映射，定义最短路矩阵D，矩阵中的每个元素代表量子计算机上任意2个物理量子位之间的最短路径长度.对于每个程序Pi，定义
为未被占用的物理量子位以及Pi映射到的物理量子位之间的最短路径矩阵.实质上，D表示允许跨程序SWAP情况下对并发量子程序执行映射转换的最短路径矩阵.表示对Pi独立执行映射转换，不允许跨程序SWAP操作时的最短路径矩阵.对于一个双量子位门操作g，将g中涉及的2个逻辑量子位表示为g.q1和g.q2.将逻辑量子位q映射到的物理量子位定义为σ(q).一个双量子位门操作中涉及的2个量子位的最短距离-1是满足其约束所需的最小SWAP操作数.
在本文的设计中，对于量子程序Pi中的一个CNOT操作
代表在处理g的映射约束时，跨程序SWAP操作所需的成本低于程序内SWAP操作.这时，应当启用跨程序SWAP操作，节省映射转换成本.
例如，在图9(b)中，由于需要1个跨程序SWAP或3个程序内SWAP来满足CNOT q1，q5的约束，
所以
本文定义跨程序SWAP策略相较于先前的策略带来的增益为
gain(g)=D[σ(g.q1)][σ(g.q2)]-
(2)
定义启发式函数为
score(SWAP)=H(SWAP)+
(3)
因为不同首层门操作集合的大小不同，因此采用首层门操作的大小对gain进行标准化.当SWAP处于门操作g的最短SWAP路径上时，指示函数I(SWAP,g)=1，否则指示函数I(SWAP,g)=0.在最短路上的SWAP操作被鼓励执行.候选SWAP中具有最小启发式函数值的SWAP操作是最优的SWAP操作.跨程序SWAP量子程序映射转换算法如算法3所示.
算法3.量子程序映射转换算法.
输入：量子芯片拓扑结构 G、量子程序programs、初始映射mapping；
输出：最终调度schedule.
① 为每个程序生成一个DAG；
② 为每个DAG生成一个首层门操作集合F；
③ while 并非所有的CNOT门操作都可执行
④ if 在F中存在能够直接执行的门操作
⑤ 添加能直接执行的门操作到schedule；
⑥ 将能直接执行的门操作从DAG中移除，更新F；
⑦ else
⑧ for each F
⑨ 将F中在第2层有邻接CNOT操作的CNOT操作添加入关键门操作集合CG；
⑩ end for
添加涉及到CG中逻辑量子位的
SWAP操作到候选SWAP集合；
从候选SWAP集合中选取
score(SWAP)最小的SWAP；
添加SWAP到schedule；
更新mapping；
end if
end while
return schedule.
5 映射任务调度器
尽管已有针对并发量子程序映射的机制[21]，但选择并发量子程序组合仍有挑战性.现在的并发量子程序组合由用户指定，这可能导致3个问题：1)量子计算机资源未得到充分利用.2)随机选择的组合可能会导致保真度大幅降低.3)必须引入结果验证机制，这会带来额外的系统修改开销.本文提出了一种并发量子程序映射任务调度器的设计，用来选择合适的并发量子程序组合.图12展示了其工作流程.
Fig.12 The framework of the quantum program mapping task scheduler
图12 量子程序映射任务调度器框架
我们的设计选择最优的量子程序组合，最大限度地提高了量子程序的执行保真度和量子计算机的资源利用率.对于调度队列首的任务，调度器检查任务队列中是否存在能够与队列首任务并发执行，且造成的保真度损失可被接受的其他量子程序.如果存在，则将它们与队列首任务同时映射到量子计算机上执行；否则，单独映射并执行队列首任务.
本文提出了预估实验成功率(estimated pro-bability of a successful trial,EPST)，用来估计在特定量子芯片上执行量子程序的保真度.Sep_EPST表示程序单独映射时可以达到的最高EPST.为了计算Sep_EPST，需要对任务集合中的每个量子程序单独调用一次算法2，为其分配一个物理量子位集合.而Co_EPST表示多个程序共同映射在量子芯片上时的EPST.为了计算Co_EPST，需要调用算法2，为集合中所有的并发量子程序共同划分初始映射区域.EPST定义为
(4)
其中,r2q,r1q和rro分别表示CNOT、单量子位门操作和所分配的物理量子位的读出操作的平均可靠度.|CNOTs|，|1q gates|和|qubits|分别表示量子程序的CNOT门数、单量子位门数和逻辑量子位数.EPST高表示量子程序被映射到更健壮的区域，并且在实际执行期间程序的执行保真度更高.
对于特定的量子程序组合，调度器根据Sep_EPST和Co_EPST计算预估实验成功率损失EPST_violation.如果EPST_violation小于阈值ε，则该量子程序组合可以并发执行.该调度器支持在1台量子计算机上并发执行2个以上的程序.为了确保调度器的效率和调度的公平性，仅搜索任务队列中的前N个任务(默认N=10)，限制并发程序数目不超过M(默认M=3).更多细节见算法4.
算法4.映射任务调度算法.
输入：调度任务队列 J.
① while J中仍有任务未被调度
② 初始化cur_job_set为仅包含J中第1项任务的列表；
③ idx←1；
④ while idx<J.length且idx<N且
cur_job_set.length<M
⑤ cur_job_set.append(J[idx]);
⑥ for job in cur_job_set
⑦ 计算job的Sep_EPST，Co_EPST;
⑧ 计算job的EPST_violation=1-(Co_EPST/Sep_EPST);
⑨ if EPST_violation>ε
⑩ cur_job_set.remove(J[idx]);
break；
end if
end for
idx←idx+1；
end while
调用算法3映射cur_job_set中的任务，提交执行；
从J中移除cur_job_set中的任务；
end while
6 实验评测
6.1 评测方法
1)评测指标
① 实验成功率(probability of a successful trial,PST).PST用于评估量子程序执行保真度，PST被定义为实验中能够产生正确结果的执行次数占总执行次数的比例.我们在量子计算机上对每个工作负载进行映射，执行8 024次，统计PST.
② 映射后量子门数量.我们使用映射后CNOT门操作的数量来评估映射策略在映射并发量子程序时缩减映射成本的能力.
③ 映射后量子线路深度.我们使用映射后量子程序的线路深度评估映射策略缓减保持性错误的能力.
④ 执行次数减小因数(trial reduction factor,TRF).TRF用于评估并发量子程序映射策略带来的通量的提升.TRF被定义为独立执行多个程序时所需的执行次数与启用并发量子程序映射时所需的执行次数之比.
2)量子芯片
我们在IBM-Q16[11]和IBM-Q50[11]上进行评估，它们的量子位拓扑结构分别如图2和图13所示，其中IBM-Q16可通过IBM接口[11]访问.而IBM-Q50并不公开，我们模拟了IBM-Q50芯片用于映射成本评估.模拟芯片包括拓扑信息和错误率数据.我们使用均匀分布随机模型，在IBM-Q16每个属性最大值和最小值的范围内生成了IBM-Q50的错误率数据.
Fig.13 Qubit topology of IBM-Q50
图13 IBM-Q50的量子位拓扑结构
3)数据集
我们采用先前研究中使用的数据集，包括SABRE[16],QASM-Bench[55],RevLib[56]和文献[50]中使用的数据集.如表3所示，微型/小型量子程序大约有5个量子位和数十个CNOT门；大型程序大约有10个量子位和数百个CNOT门.
Table 3 Benchmarks Used in the Evaluation
表3 实验评测中所用的工作集
类型工作集微型bv_n3,bv_n4,peres_3,toffoli_3,fredkin_3小型3_17_13,decod24-v2_43,4mod5-v1_22,mod5mils_65,alu-v0_27大型aj-e11_165,4gt4-v0_72,alu-bdd_288,ex2_227,ham7_104,bv_n10,ising_model_10,qft_10,sys6-v0_111,rd53_311,qft_16,alu-v2_31,C17_204,cnt3-5_180,sf_276,sym9_146
4)对比实验
① 单独执行.使用Qiskit[26]中优化级别最高的算法分别映射和执行工作负载中的每个程序.它们代表最可靠的情况，没有并发程序之间的干扰.
② 并发基准.采用文献[21]中提出的策略，用FRP策略生成并发量子程序的初始映射，用引进基于错误率的优化的SABRE进行映射转换.
③ SABRE[16].SABRE是一种以SWAP操作数为优化目标的启发式映射方法.该策略被用于映射多个并发量子程序合并成的量子线路.
本文中的策略被细分为：仅使用CDAQP、仅使用X-SWAP，以及同时使用CDAQP和X-SWAP.其中，仅使用CDAQP的方法采用了与SABRE相同的映射转换方法，仅使用X-SWAP的方法使用了与SABRE相同的初始映射策略.
6.2 程序执行保真度评测
本文使用微型/小型量子程序组合进行保真度评测.表4展示了在IBM-Q16上执行的包含2个程序的工作负载的PST.相同程序组合下的实验均在IBM-Q16的一个错误率标定周期内完成，即量子计算机的错误率标定数据相同.量子程序的两两组合可以使量子计算机的通量提高一倍.但是，由于资源冲突和串扰，量子程序的执行可靠性可能会降低.在大多数情况下，并发量子程序映射的平均PST低于单独执行情况下的平均PST.但本文的方法仍优于其他并发量子程序映射策略.对于微型程序组合，本文的方法(CDAQP+X-SWAP)、单独执行、SABRE和并发基准的平均PST分别为58.2%，69.8%，44.8%和45.3%；对于小型工作负载，相应的平均PST分别为16.8%，23.8%，10.3%和12.4%.本文方法的执行保真度比SABRE和并发基准分别平均高出9.9%和8.6%.这表明本文的方法提供了更可靠的结果，并且减少了保真度的损失.
Table 4 PST Comparison Between Multiple Strategies on IBM-Q16
表4 IBM-Q16上多种策略PST的对比 %
程序组合单独执行SABRE并发基准CDAQP+X-SWAP仅CDAQP仅X-SWAPW1W2PST1PST2平均PST1PST2平均PST1PST2平均PST1PST2平均PST1PST2平均PST1PST2平均bv_n3bv_n383.484.083.750.875.463.157.561.459.569.766.268.068.767.167.919.354.937.1bv_n3bv_n483.463.673.552.634.543.535.925.030.452.517.735.127.212.820.037.453.745.5bv_n3peres_383.981.282.556.351.253.849.361.055.263.971.167.565.170.867.967.976.872.4bv_n3toffoli_383.182.082.559.049.554.365.741.953.865.381.773.563.870.567.148.576.562.5bv_n3fredkin_383.246.264.740.956.148.569.739.154.466.181.974.064.982.173.546.464.155.2bv_n4bv_n450.751.351.030.451.841.149.228.739.051.152.852.048.537.743.149.641.645.6peres_3peres_363.159.061.141.420.330.945.746.946.351.254.452.851.152.952.044.013.228.6toffoli_3toffoli_364.365.564.921.933.727.822.833.628.250.251.050.652.441.346.939.151.245.2fredkin_3fredkin_365.463.064.239.640.039.840.941.341.152.048.150.148.522.135.352.342.047.1平均69.844.845.358.252.648.83_17_133_17_1343.144.643.812.910.811.914.011.612.833.311.322.37.022.214.623.015.619.33_17_134mod5-v1_2245.028.336.710.418.714.512.021.316.733.517.325.413.729.621.716.825.421.13_17_13mod5mils_6522.429.225.89.33.66.518.519.118.832.016.924.513.77.610.713.216.715.03_17_13alu-v0_2744.014.129.09.07.38.114.07.410.718.315.216.820.921.921.49.36.37.83_17_13decod24-v2_4343.66.224.918.27.813.011.59.310.414.711.213.027.26.616.97.619.113.44mod5-v1_224mod5-v1_2229.226.027.613.421.017.217.820.319.116.422.319.418.921.320.119.516.217.8mod5mils_65mod5mils_6511.68.610.16.89.38.14.114.79.48.712.010.47.57.77.67.810.29.0alu-v0_27alu-v0_279.110.09.69.93.46.78.86.67.78.812.910.87.710.59.15.15.05.0decod24-v2_43decod24-v2_436.06.86.46.96.16.57.75.36.57.59.48.410.16.28.17.27.67.4平均23.810.312.416.814.512.9
本文的方法主要受益于CDAQP策略.CDAQP提供了更好的初始映射来提高保真度，这使得并发量子程序执行时的保真度接近甚至超过单独执行情况下的保真度.如表4所示，在bv_n3和fredkin_3组合中，仅使用CDAQP的策略通过提供更好的初始映射，使保真度比并发基准显著提高了19.1%.CDAQP相对于并发基准的优势来自2个方面：1)在可靠量子位和连接上运行的量子门具有较低的错误率.2)较好的初始分配降低了映射转换时的SWAP开销.总体上，仅使用CDAQP的策略减少了并发量子程序映射带来的保真度下降，保真度相较于并发基准高出4.7%.
仅使用X-SWAP的策略在提升保真度方面没有体现出显著优势，这是因为：1)映射小型量子程序需要很少的SWAP操作，因此X-SWAP在这种情况下很难节省SWAP.2)在IBM-Q16这种结构简单的量子芯片上，初始映射对小型量子程序的可靠性有很大影响.3)量子程序映射位置可能不相邻，难以执行跨程序SWAP.但是，X-SWAP在具有更多量子位的芯片上却能有较好的表现.
6.3 映射成本评测
X-SWAP在更大的启发式搜索空间中表现更好.当多个更大规模的量子程序在具有更多量子位的量子芯片上并发运行时，X-SWAP能体现出更优的性能.本文将映射后量子门操作的数量和线路深度作为评价标准，评估IBM-Q50上4程序工作负载的映射开销.工作负载随机选择，旨在覆盖尽可能多的正交程序组合.对于每个工作负载和每个策略，本文采用5次实验中的最佳结果(类似于文献[16]).实验结果如表5所示.
Table 5 Mapping Overheads Comparison of 4-program Workloads on IBM-Q50
表5 IBM-Q50上的4程序工作集映射成本对比
组合工作负载中的量子程序SABRE并发基准CDAQP+X-SWAP仅CDAQP仅X-SWAPCNOTs深度CNOTs深度CNOTs深度CNOTs深度CNOTs深度Mix_1aj-e11_165,alu-v2_31,4gt4-v0_72,sf_27613867681303847116758611415301177629Mix_2alu-bdd_288,ex2_227,ham7_104,C17_20412225961266717123667112255811242717Mix_3bv_n10,ising_model_10,qft_10,sys6-v0_111387189382178351160419236341224Mix_4aj-e11_165,alu-v2_31,ising_model_10,cnt3-5_18097945010084379534801005450950496Mix_54gt4-v0_72,sf_276,sym9_146,rd53_31113656721429759125553612374971089450Mix_6alu-bdd_288,ex2_227,qft_10,sys6-v0_111871711862655780563862578809579Mix_7ham7_104,C17_204,bv_n10,ising_model_10713370963496668413723423677399Mix_8aj-e11_165,4gt4-v0_72,rd53_311,cnt3-5_1809964481052537916441894368940390Mix_9alu-v2_31,sf_276,sym9_146,qft_1614817381499769147871815457791325482Mix_10alu-bdd_288,ham7_104,ising_model_10,sys6-v0_111659392662315622248656306617325Mix_11ex2_227,C17_204,bv_n10,qft_109555371049630900569964531985599Mix_12aj-e11_165,sf_276,C17_204,sys6-v0_1111438834133782898450612677731063467
SABRE[16]使用反向遍历技术和启发式搜索方案，最小化插入SWAP的数量.然而，因SABRE在初始映射时并未考虑局部性原理，在映射并发量子程序工作负载时，并发量子程序的SWAP 路径存在交叠，引发了更多的SWAP操作，无法获得最优映射方案.并发基准在划分量子位时会考虑局部性，但在并发量子程序之间会引入资源冲突，导致冗余的SWAP操作.实验结果表明，并发基准的映射后CNOT门操作数平均比SABRE高4.0%，映射后线路深度平均比SABRE高6.8%.
平均而言，仅使用CDAQP在映射后CNOT门的数量上比SABRE高2.7%，在线路深度上比SABRE高6.8%.虽然CDAQP能够帮助找到量子位紧密相连的初始映射.帮助减小映射开销，但效果并不显著.在个别情况下(如Mix_9)，仅使用CDAQP反而造成了比其他策略还高的映射开销.其原因是：CDAQP的主要优化目标是提升初始映射的保真度.降低映射开销(即用最少的SWAP完成量子程序映射)并不是CDAQP的首要任务.仅采用X-SWAP的策略使用了与SABRE相同的初始映射方法，允许执行跨程序SWAP操作，优先处理关键门操作，有效地将映射后门操作的数量缩减了8.8%，并将映射后线路深度缩减了9.2%.原因包括2个方面：1)X-SWAP利用跨程序SWAP，采取捷径，节省映射开销.2)通过优先处理关键门操作，X-SWAP可提供更高效的SWAP，缩减映射开销和映射后线路深度.
在本文的设计中，CDAQP可以生成可靠且紧密相连的初始映射，而X-SWAP则用于减少映射开销.同时应用CDAQP和X-SWAP可提升性能：与并发基准和SABRE相比，映射后门操作数分别减少了11.6%和8.6%；与并发基准和SABRE相比，线路深度分别降低了16.0%和10.3%.表5展示了更详细的数据.
此外，本工作具有可扩展性。本工作不仅能够降低IBM-Q50上的4程序工作负载的映射开销，还能在更大规模的量子芯片上运行.这是因为：1)CDAQP中所采用的社区检测方法已被证明对于大型网络是有效的.2)无论量子芯片规模大小，只要量子程序映射位置邻接，X-SWAP就可以起到减少映射开销的作用.
6.4 任务调度器评测
本文采用表3中的微型/小型量子程序构造了一个映射任务队列，并使用任务调度器进行调度.从0.05～0.20变更阈值ε，在每种情况下分别进行调度，工作负载的PST均值和TRF如图14所示.图14还展示了在每个程序单独执行和程序两两随机组合情况下的性能.
Fig.14 Performance of the task compiler
图14 任务调度器性能
单独执行情况下，TRF为1(无并发)，平均PST为35.9%，是该任务队列能够达到的最高平均PST.程序两两随机组合情况下的平均PST最低，仅为25.1%，但TRF达到2(2个程序并发).当ε=0.15(即仅允许EPST损失小于15%的并发量子程序映射情况)时，调度器性能最好.在这种情况下，工作负载的平均保真度为30.1%，比两两随机组合的工作负载高出5.0%；TRF为1.429，与单独执行的情况相比，吞吐量提高了42.9%.实验结果表明，本文的映射任务调度器可以用于权衡量子计算机的吞吐量和保真度.
7 总 结
量子计算和量子计算云服务逐渐兴起.当前云环境下的量子计算机面临着资源利用率低、保真度低、错误率高等问题.本文对面向超导量子芯片的量子程序映射技术进行了综述，深入剖析了不同类别映射技术的特点和区别.并针对云环境下的并发量子程序映射问题提出了一种新的映射策略，提升并发量子程序的执行保真度和资源利用率.本文设计的系统是一个面向量子计算机的操作系统原型QuOS.希望我们的工作能帮助相关领域未来的研究人员.
[1]Grover L K.A fast quantum mechanical algorithm for database search[C] //Proc of the 28th Annual ACM Symp on Theory of Computing.New York:ACM,1996:212-219
[2]Biamonte J,Wittek P,Pancotti N,et al.Quantum machine learning[J].Nature,2017,549(7671):195-202
[3]Lloyd S,Mohseni M,Rebentrost P.Quantum algorithms for supervised and unsupervised machine learning[J].arXiv preprint arXiv:1307.0411,2013
[4]Kandala A,Mezzacapo A,Temme K,et al.Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets[J].Nature,2017,549(7671):242-246
[5]Peruzzo A,Mcclean J,Shadbolt P,et al.A variational eigenvalue solver on a photonic quantum processor[J].Nature Communications,2014,5(1):4213
[6]Wang Baonan,Hu Feng,Zhang Huanguo,et al.From evolutionary cryptography to quantum artificial intelligent cryptography[J].Journal of Computer Research and Development,2019,56(10):2112-2134 (in Chinese)(王宝楠,胡风,张焕国,等.从演化密码到量子人工智能密码综述[J].计算机研究与发展,2019,56(10):2112-2134)
[7]Du Weilin,Li Bin,Tian Yu.Quantum annealing algorithms:State of the art[J].Journal of Computer Research and Development,2008,45(9):1501-1508 (in Chinese)(杜卫林,李斌,田宇.量子退火算法研究进展[J].计算机研究与发展,2008,45(9):1501-1508)
[8]Hsu J.CES 2018:Intel’s 49-Qubit Chip Shoots for Quantum Supremacy[EB/OL].[2021-03-26].https://spectrum.ieee.org/tech-talk/computing/hardware/intels-49qubit-chip-aims-for-quantum-supremacy
[9]Kelly J.A Preview of Bristlecone,Google’s New Quantum Processor[EB/OL].[2021-03-26].https://ai.googleblog.com/2018/03/a-preview-of-bristlecone-googles-new.html
[10] Knight W.IBM Raises the Bar with a 50-Qubit Quantum Computer[EB/OL].[2021-03-26].https://www.technology review.com/2017/11/10/147728/ibm-raises-the-bar-with-a-50-qubit-quantum-computer/
[11]IBM.IBM Quantum Experience[CP/OL].[2021-03-26].https://quantum-computing.ibm.com/
[12]Preskill J.Quantum computing in the NISQ era and beyond[J].Quantum,2018,2:No.79
[13]Koch J,Terri M Y,Gambetta J,et al.Charge-insensitive qubit design derived from the Cooper pair box[J].Physical Review A,2007,76(4):042319
[14]Debnath S,Linke N M,Figgatt C,et al.Demonstration of a small programmable quantum computer with atomic qubits[J].Nature,2016,536(7614):63-66
[15]Zhong Hansen,Wang Hui,Deng Yuhao,et al.Quantum computational advantage using photons[J].Science,2020,370(6523):1460-1463
[16]Li Gushu,Ding Yufei,Xie Yuan.Tackling the qubit mapping problem for NISQ-era quantum devices[C] //Proc of the 24th Int Conf on Architectural Support for Programming Languages and Operating Systems.New York:ACM,2019:1001-1014
[17]Ash-Saki A,Alam M,Ghosh S.QURE:Qubit re-allocation in noisy intermediate-scale quantum computers[C] //Proc of the 56th Annual Design Automation Conf.New York:ACM,2019:1-6
[18]Murali P,Baker J M,Javadi-Abhari A,et al.Noise-adaptive compiler mappings for noisy intermediate-scale quantum computers[C] //Proc of the 24th Int Conf on Architectural Support for Programming Languages and Operating Systems.New York:ACM,2019:1015-1029
[19]Tannu S S,Qureshi M K.Not all qubits are created equal[C] //Proc of the 24th Int Conf on Architectural Support for Programming Languages and Operating Systems.New York:ACM,2019:987-999
[20]Murali P,Mckay D C,Martonosi M,et al.Software mitigation of crosstalk on noisy intermediate-scale quantum computers[C] //Proc of the 25th Int Conf on Architectural Support for Programming Languages and Operating Systems.New York:ACM,2020:1001-1016
[21]Das P,Tannu S S,Nair P J,et al.A case for multi-programming quantum computers[C] //Proc of the 52nd Annual IEEE/ACM Int Symp on Microarchitecture.New York:ACM,2019:291-303
[22]Barenco A,Bennett C H,Cleve R,et al.Elementary gates for quantum computation[J].Physical Review A,1995,52(5):3457-3467
[23]Rigetti C,Devoret M.Fully microwave-tunable universal gates in superconducting qubits with linear couplings and fixed transition frequencies[J].Physical Review B,2010,81(13):134507
[24]Chong F T,Franklin D,Martonosi M.Programming languages and compiler design for realistic quantum hardware[J].Nature,2017,549(7671):180-187
[25]Tucci R R.A rudimentary quantum compiler[J].arXiv preprint quant-ph/9805015,1998
[26]Abraham H,Offei-danso A,Agarwal R,et al.Qiskit:An Open-source Framework for Quantum Computing[CP/OL].[2021-03-26].https://github.com/Qiskit/qiskit
[27]Zulehner A,Wille R.Compiling SU(4)quantum circuits to IBM QX architectures[C] //Proc of the 24th Asia and South Pacific Design Automation Conf.New York:ACM,2019:185-190
[28]Huang Yipeng,Martonosi M.Statistical assertions for validating patterns and finding bugs in quantum programs[C] //Proc of the 46th Int Symp on Computer Architecture.New York:ACM,2019:541-553
[29]Liu Ji,Zhou Huiyang.Systematic approaches for precise and approximate quantum state runtime assertion[C] //Proc of the 27th IEEE Int Symp on High Performance Computer Architecture.Piscataway,NJ:IEEE,2021:179-193
[30]Travis L,Fang Qi,Lu Peng.Robust cache-aware quantum processor layout[C] //Proc of the 39th Int Symp on Reliable Distributed Systems.Piscataway,NJ:IEEE,2020:276-287
[31]Dou Xinglei,Liu Lei.A new qubits mapping mechanism for multi-programming quantum computing[C] //Proc of the 29th Int Conf on Parallel Architectures and Compilation Techniques.New York:ACM,2020:349-350
[32]Liu Lei,Dou Xinglei.QuCloud:A new qubit mapping mechanism for multi-programming quantum computing in cloud environment[C] //Proc of the 27th IEEE Int Symp on High Performance Computer Architecture.Piscataway,NJ:IEEE,2021:167-178
[33]Siraichi M Y,Santos V F D,Collange S,et al.Qubit allocation[C] //Proc of the 2018 Int Symp on Code Generation and Optimization.New York:ACM,2018:113-125
[34]Tan Bochen,Cong J.Optimality study of existing quantum computing layout synthesis tools[J].arXiv preprint arXiv:2002.09783v4,2020
[35]Meter R V,Oskin M.Architectural implications of quantum computing technologies[J].ACM Journal on Emerging Technologies in Computing Systems,2006,2(1):31-63
[36]Shafaei A,Saeedi M,Pedram M.Qubit placement to minimize communication overhead in 2D quantum architectures[C] //Proc of the 19th Asia and South Pacific Design Automation Conf.Piscataway,NJ:IEEE,2014:495-500
[37]Wille R,Lye A,Drechsler R.Optimal SWAP gate insertion for nearest neighbor quantum circuits[C] //Proc of the 19th Asia and South Pacific Design Automation Conf.Piscataway,NJ:IEEE,2014:489-494
[38]Lye A,Wille R,Drechsler R.Determining the minimal number of swap gates for multi-dimensional nearest neighbor quantum circuits[C] //Proc of the 20th Asia and South Pacific Design Automation Conf.Piscataway,NJ:IEEE,2015:178-183
[39]Booth K,Do M,Beck J,et al.Comparing and integrating constraint programming and temporal planning for quantum circuit compilation[C] //Proc of the 28th Int Conf on Automated Planning and Scheduling.Palo Alto,CA:AAAI,2018:366-374
[40]Bhattacharjee D,Saki A A,Alam M,et al.MUQUT:Multi-constraint quantum circuit mapping on NISQ computers[C] //Proc of the 38th IEEE/ACM Int Conf on Computer-Aided Design.Piscataway,NJ:IEEE,2019:1-7
[41]Wille R,Burgholzer L,Zulehner A.Mapping quantum circuits to IBM QX architectures using the minimal number of SWAP and H operations[C] //Proc of the 56th ACM/IEEE Design Automation Conf.Piscataway,NJ:IEEE,2019:1-6
[42]Murali P,Linke N M,Martonosi M,et al.Full-stack,real-system quantum computer studies[C] //Proc of the 46th Int Symp on Computer Architecture.New York:ACM,2019:527-540
[43]Tan Bochen,Cong J.Optimal layout synthesis for quantum computing[C] //Proc of the 39th IEEE/ACM Int Conf on Computer Aided Design.New York:ACM,2020:1-9
[44]Gurobi.Gurobi Optimizer Reference Manual[EB/OL].[2021-03-26].https://www.gurobi.com/documentation/9.1/refman/index.html
[45]De Moura L,Bjørner N.Z3:An efficient SMT solver[C] //Proc of the 11th Int Conf on Tools and Algorithms for the Construction and Analysis of Systems.Berlin:Springer,2008:337-340
[46]Bjørner N,Phan A-D,Fleckenstein L.vZ—An optimizing SMT solver[C] //Proc of the 18th Int Conf on Tools and Algorithms for the Construction and Analysis of Systems.Berlin:Springer,2015:194-199
[47]Shafaei A,Saeedi M,Pedram M.Optimization of quantum circuits for interaction distance in linear nearest neighbor architectures[C] //Proc of the 50th ACM/EDAC/IEEE Design Automation Conf.New York:ACM,2013:1-6
[48]Wille R,Keszocze O,Walter M,et al.Look-ahead schemes for nearest neighbor optimization of 1D and 2D quantum circuits[C] //Proc of the 21st Asia and South Pacific Design Automation Conf.Piscataway,NJ:IEEE,2016:292-297
[49]Bhattacharjee A,Bandyopadhyay C,Wille R,et al.A novel approach for nearest neighbor realization of 2D quantum circuits[C] //Proc of the 2018 IEEE Computer Society Annual Symp on VLSI.Piscataway,NJ:IEEE,2018:305-310
[50]Zulehner A,Paler A,Wille R.Efficient mapping of quantum circuits to the IBM QX architectures[C] //Proc of the 2018 Design,Automation Test in Europe Conf Exhibition.Piscataway,NJ:IEEE,2018:1135-1138
[51]Smith K N,Thornton M A.A quantum computational compiler and design tool for technology-specific targets[C] //Proc of the 46th Int Symp on Computer Architecture.New York:ACM,2019:579-588
[52]Siraichi M Y,Santos V F D,Collange C,et al.Qubit allocation as a combination of subgraph isomorphism and token swapping[J].Proceedings of the ACM on Programming Languages,2019,3(OOPSLA):1-29
[53]Ding Yongshan,Wu Xinchuan,Holmes A,et al.SQUARE:Strategic quantum ancilla reuse for modular quantum programs via cost-effective uncomputation[C] //Proc of the 47th ACM/IEEE Annual Int Symp on Computer Architecture.Piscataway,NJ:IEEE,2020:570-583
[54]Newman M E.Fast algorithm for detecting community structure in networks[J].Physical Review E,2004,69(6):066133
[55]Cross A W,Bishop L S,Smolin J A,et al.Open quantum assembly language[J].arXiv preprint arXiv:1707.03429,2017
[56]Wille R,Große D,Teuber L,et al.RevLib:An online resource for reversible functions and reversible circuits[C] //Proc of the 38th Int Symp on Multiple Valued Logic.Piscataway,NJ:IEEE,2008:220-225
