由于量子位具有连接脆弱、串扰和状态不稳定等特性^[14]，因而量子线路运行在实际量子硬件中可能会遇到以下3种错误类型：相干时间^[15]、量子位保真度^[16]与量子位耦合约束^[17]。相干时间与量子位保真度需要量子硬件的技术进步来改善，量子位的耦合约束则可以通过软件层面的量子线路映射算法解决。

结合一个小规模量子线路示例进一步解释量子线路映射问题，如图1和图2所示。4量子位硬件模的硬件架构采用图2a所示的硬件耦合图。该硬件模型允许在以下量子位对上使用双量子位门：$ \left\{ Q_1,Q_2 \right \} $,$ \left\{ Q_2,Q_4 \right \} $,$ \left\{ Q_4,Q_3 \right \} $,$ \left\{ Q_3,Q_1 \right \} $，不允许在$ \left\{ Q_1,Q_4 \right \} $和$ \left\{ Q_2,Q_3 \right \} $上使用双量子位门。假设有一个小规模量子线路要在图2所示的4量子位设备上执行。该量子线路由6个CNOT门组成(如图2b所示)，假设初始的逻辑量子位到物理量子线路映射为$ \left\{ q_1\rightarrow Q_1,q_2\rightarrow Q_2,q_3\rightarrow Q_3,q_4\rightarrow Q_4\right \} $。

图  1  更改映射关系的量子操作

图  2  更新前的量子线路及其硬件架构

由图2a可见，6个CNOT门中有4个可以直接执行，第3个和第4个CNOT门无法执行，因为相应的量子位对没有连接到硬件上。图2的量子线路示例中不存在满足所有双量子位门依赖关系的完美初始映射，需要在程序执行期间更改量子位映射，使所有CNOT门都可执行。

主流的更改映射方法为使用SWAP门(即交换门)，通过在两个量子位之间交换状态来改变量子线路映射(如图1a所示)。SWAP门由3个CNOT门组成。如果两个量子位在量子器件上并不相邻，可以使用多个SWAP门将1个逻辑量子位移动到任意物理量子位的位置，然后在线路中应用双量子位门。如图3所示，在第2个CNOT门之后的$ q_1 $和$ q_2 $之间插入1个SWAP门，更新后量子线路是可以执行的。前两个CNOT门可以在初始映射下执行。插入SWAP门后，映射更新为$\left\{ q_1\rightarrow Q_2,q_2\rightarrow Q_1,\right. \left. q_3\rightarrow Q_3,q_4\rightarrow Q_4\right \}$，所有剩余的4个CNOT门都可在此映射下执行。

当量子线路应用在非对称硬件模型时，即只允许运行方向符合连通关系的双量子位门时，可使用基变换技术，添加4个Hadamard门，将$ |01\rangle $基转换为$ |+-\rangle $，从而实现CNOT门换向操作，如图1b所示。

图  3  更新硬件映射后的量子线路

在量子线路中引入额外的SWAP门可以解决所有双量子位门的依赖性，并在不改变原有功能的情况下生成硬件兼容线路。由于NISQ硬件设备的限制，在量子线路中插入SWAP门会导致以下问题。1) 量子线路中的操作次数增加，由于操作不完美，会引入噪声，导致总体错误率会增加。2) 量子线路深度会增加，导致执行时间将增加，且量子线路的退相干可能会累积许多错误。

比较图2b和图3中的原始线路和更新线路，量子门的数量从6增加到9，线路深度从5增加到8。额外的SWAP门将在保真度和执行时间方面带来巨大的开销，需要量子线路映射算法来尽量减少额外SWAP门的数量，降低总体错误率和总执行时间。

本文在量子线路映射算法SABRE算法^[8]的基础上，保留SABRE算法双向遍历和就近搜索候选SWAP门空间的特点，使用前端层信息初始化量子线路映射代替随机初始化量子位映射，并对遍历流程和启发式代价函数进行改进，设计了基于交换门的前瞻双向启发式算法(SWAP-based prospective bidirectional heuristic algorithm, SPBHA)。SPBHA算法包含4个部分：预处理、单次遍历、双向遍历更新映射与启发式代价函数，表1定义了SPBHA算法使用的数学符号。

SPBHA算法预处理的具体步骤如下。

计算距离矩阵：给定量子器件的耦合图，通过Floyd-Warshall^[18]算法计算所有点对最短路径(all pairs shortest path, APSP)，以获得距离矩阵D，耦合图每条边距离为1。$D_{[i][j]}$表示将逻辑量子位从物理量子位$ Q_i $移动到$ Q_j $所需的最小SWAP数。

生成量子线路有向无环图(directed acylic graph, DAG)：使用DAG表示量子线路中受控非门CNOT门的依赖顺序。单量子位门只在一个量子位上执行，不会对其他量子位产生依赖，因而量子线路映射算法不考虑单量子位门。当CNOT门的两个量子位$ q_i $或$ q_j $上所有之前的CNOT门都已执行时，才能执行${\rm{CNOT}}(q_i,q_j)$。遍历整个量子线路，并构造一个DAG。图4b的DAG是由图4a的量子线路生成的。如由于量子位$ q_2 $同时存在于量子门$ g_1 $和量子门$ g_3 $中，而在$ g_1 $之前不能执行$ g_3 $，所以量子门$ g_3 $依赖于量子门$ g_1 $。以此类推，根据量子门之间的依赖关系生成DAG。

图  4  原始线路生成DAG的示例以及前端层初始化

初始化前端层：前端层(F)被定义为DAG中没有未执行前导的所有CNOT门的集合，意味着对应的双量子位门没有依赖性，可以立即在硬件上执行。对于${\rm{CNOT}}(q_i,q_j)$，当CNOT门的两个量子位$ q_i $或$ q_j $上所有之前的量子门都被执行时，它可以被放置在集合F中。遍历第二步得到DAG，并找到图中入度为0的所有顶点(量子门)，将这些量子门放入F，以初始化F。图4中，初始化的前端层包含$ g_1 $和$ g_2 $，因为它们没有前导。

利用前瞻机制初始化量子位映射：SPBHA算法使用前端层量子门的信息，在进行单次遍历算法之前利用前瞻机制对量子位映射进行出初始化。图5c线路使用图5a量子硬件架构，并根据定义(见表1)划分出前端层、前端层的后继门组成的短期层和远离前端层的长期层。在前端层的${\rm{CNOT}}(q_1,q_3)$中，将$ q_1 $映射到$ Q_1 $，并根据$ Q_1 $相邻的物理量子位情况，将$ q_3 $映射到$ Q_2 $，使得$ q_1 $和$ q_3 $的物理量子位相邻，该CNOT门无需插入任何SWAP门可以直接在硬件上运行。同理，${\rm{CNOT}}(q_2,q_6)$中，$ q_6 $映射到$ Q_6 $，$ q_2 $映射到$ Q_3 $。在满足前端层的量子门均可以直接在硬件上运行后，剩余未映射的量子位进行随机分配。图5b中虚线框的映射为利用前瞻信息初始化的映射，实线框映射为随机初始化映射。由于量子程序具有与经典程序类似的局部性原理，作用在相同量子位对上的量子门可能在短时间内再次运行。利用局部性原理，SPBHA算法可以进一步减少附加门的数量，提高算法效率。由于前端层的量子门之间没有依赖性，因此必然可以找到一个使得满足前端层量子门均可以直接在硬件上运行的初始量子位映射。

图  5  利用前瞻机制初始化量子位映射

算法1　单次遍历算法

　Input：距离矩阵D、线路DAG、初始F和初始映射$ \pi $

　Output：更新的量子映射$ \pi_u $，插入SWAP门的信息

　while $ {{{F}}=\varnothing} $ do

　　${{\rm{Execute}}\_{\rm{gate}}\_{\rm{list}}}\leftarrow\varnothing$/*初始化可执行门集合*/;

　　for $ \mathrm{gate} \in {{F}} $ do

　　　if 量子门可直接在硬件上运行 then

　　　　${{\rm{Execute}}\_{\rm{gate}}\_{\rm{list}}.{\rm{add}}({\rm{gate}})}$/*添加可执行门*/;

　　　end

　　end

　　if $ \mathrm{{Execute\_gate\_list}\neq\varnothing} $ then

　　　for $ \mathrm{gate\in {Execute\_gate\_list}} $ do

　　　　$F.{\rm{remove}}({\rm{gate}})$;

　　　　从DAG中获得F的后继门successor_gate;

　　　　$F.{\rm{add}}({\rm{successor}}\_{\rm{gate}})$; /*添加后继门*/;

　　　end

　　end

　　else

　　　${\rm{score}}\leftarrow\varnothing$/*初始化评分数组*/;

　　　${\rm{SWAP}}\_{\rm{Candidate}}\_{\rm{list}}\leftarrow\ {\rm{GetSWAP}}(F.G)$/*根据前端层和耦合图得到候选插入的SWAP门*/;

　　　for $ \mathrm{SWAP\in {SWAP\_Candidate\_list}} $ do

　　　　$\pi_{{\rm{temp}}}\leftarrow \pi.{\rm{update}}({\rm{SWAP}})$/*用当前SWAP门暂时更新映射*/;

　　　　${\rm{score}}[{\rm{SWAP}}]\leftarrow H(\pi_{{\rm{temp}}},F,{\boldsymbol{D}}, {\rm{DAG}},$${\rm{SWAP}})$; /*根据启发式代价函数获得SWAP门的评分*/;

　　　　F.add(successor_gate);

　　　end

　　　找到最佳评分的SWAP门;

　　　$\pi \leftarrow \pi .{\rm{update}}({\rm{SWAP}}))$/*用当前SWAP门更新映射*/;

　　end

　end

算法1描述了SPBHA的单次遍历算法流程，算法扫描整个DAG并插入SWAP门，以使所有CNOT门都可执行。

在单次遍历算法的每次迭代中，检查F中是否有任何可以直接在硬件上执行的量子门。若存在可直接执行的量子门，算法将执行这些量子门并将其从F中移除，然后向F添加新的后继门。如果F中所有量子门都不能直接在硬件上执行，算法将尝试搜索可能插入的SWAP门集合并进行评估，在量子线路中插入当前最适合的SWAP门更新映射。该算法将不断迭代，当前端层F为空时，说明量子线路中的所有量子门都已执行，算法停止。

双向遍历的过程如图6所示，SPBHA算法进行预处理初始化量子位映射，并使用单次遍历算法正向遍历原始线路。从正向遍历中获得的量子位映射将作为反向遍历中的初始映射。利用量子计算的可逆性，原始线路可生成对应的反向线路。反向线路中的两个量子位门完全相同，只有顺序相反。之后，再次使用单次遍历算法遍历反向量子线路，最终将经过反向遍历得到的映射作为最终映射。

图  6  双向遍历更新量子位映射

使用双向遍历的方式获得量子位映射可以全局考虑量子线路上所有量子位门的信息。由于在同一量子硬件模型上正反向运行同一线路，考虑了所有的量子位门信息，更新后的初始映射较单次遍历的初始映射使用的附加门更少。尽管位于量子线路中间的量子门对映射的影响小于两端的量子门，双向遍历对减少附加门数的效果依然明显。

启发式成本函数是SPBHA算法的核心，用来评估每个候选插入的SWAP门的分数，从而帮助SPBHA算法找到当前线路最适合插入的SWAP门。

基于最近邻代价(nearest neighbor cost, NNC)的启发式代价函数是最普遍与基本的启发式代价函数^[19]。评估时暂时改变量子位映射$ \pi $，然后对F中所有量子位对之间距离求和(量子位间的距离可通过预处理阶段计算的距离矩阵D求得)得到启发式代价函数的函数值。若函数值很小，意味着F中两个量子位对之间的距离很短，此SWAP门更可能使F中的量子门可执行，最终将选择具有最小函数值的SWAP门改变映射。基于NNC的启发式代价函数的形式为：

SABRE算法的启发式代价函数在式(1)的基础上考虑后续的量子门，引入了扩展集E，它包含了F中部分门的后继门。SABRE算法用F和E的大小来规范化F与E的总和，添加权重参数$ W(0\leq W<1) $以减少E的影响。为了选择可以并行执行的SWAP门，在函数中引入了衰减效应。如果一个量子位$ q_i $最近参与了SWAP门，那么它的衰变参数将增加$\delta({\rm{decay}}(q_i) = 1+\delta)$。该衰减参数将使启发式搜索倾向于选择不重叠的SWAP门，增加生成线路中的并行性。SABRE算法的启发式代价函数形式为：

然而，式(2)有可以继续改进的地方。式(2)只将部分F中量子门的后继门放入扩展集E，以体现前瞻能力的灵活性，实际上E设置为灵活大小并无必要，通常来说考虑F的全部后继门将更充分地考虑后续量子门的位置信息，从而插入更高效的SWAP门。因此SPBHA算法的启发式函数改为将F中所有量子门的后继门放入E中，得到具有最大前瞻能力的扩展集$E_{{\rm{max}}}$。

在SPBHA算法的启发式代价函数中，衰减函数定义为：

式中，$ n $为$ q_i $参与的SWAP门数；$ m $为当前已执行门数；$ \delta $为衰变参数；$ \varepsilon $为执行参数，且$ \delta = 4\varepsilon $。式(3)的设计目的是将衰变函数变得更加连续，相较于式(2)采用每5个搜索步骤或在执行CNOT门后重置函数，式(3)不重置函数，转而全局考虑$ q_i $参与过的所有SWAP门，结合已执行量子门数确定衰减函数值。当衰减函数值小于1时，说明最近插入的SWAP门距离当前量子门过远，因此衰减函数值设为1，不影响当前的并行选择，而且能够综合考虑量子位参与过的全部SWAP门以及到当前门的距离。

此外，将取衰变函值中最大值改为求和，从而同时考虑$ q_i $和$ q_j $的情况。最终SPBHA算法的启发式代价函数形式为：

在量子线路映射问题中，量子位映射$ \pi $具有指数级可能性：$\dfrac{N!}{(N-n)!}$。因此，精确求解最优解并不可行，往往使用启发式方法和其他优化方式降低计算复杂度并得到次优解。现有启发式算法^[12]使用穷举搜索，每个CNOT的候选SWAP门搜索空间与时间复杂度是$O({\rm{e}}^N)$，其中包括冗余的搜索空间，可以继续改进。设$ q_i $是F中CNOT门的一个逻辑量子位，SPBHA算法不搜索全部可能的逻辑量子位，而是通过量子位映射$ \pi $和耦合图G得到$ j $个近邻的物理量子位：

通过逆映射$ \pi^{-1} $获得$ q_i $在硬件上近邻的全部逻辑量子位：

将$q_{i_1},q_{i_2},\cdots,q_{i_j}$与$ q_i $构成候选SWAP门的量子位对，通过启发式代价函数评估候选SWAP门，得到当前最优的SWAP门并更改映射：

式(5)不考虑远离前端层的长期层中的量子门(见图4b)，因为$ \pi $在执行期间可能显著变化，在无法穷举搜索的情况下很难准确地估计当前映射对长期层的影响。由于SPBHA算法只搜索能帮助解决前端层中依赖关系的候选SWAP门(即物理上近邻的逻辑量子位)，因此搜索候选SWAP门的空间复杂度由$O({\rm{e}}^N)$降至$ O(N) $，大幅提升了算法执行速度。

SPBHA算法在最坏情况下，每个双量子位门都需要改变映射满足耦合约束。为方便分析，设CNOT门数量为$ m $；CNOT门的搜索空间中评估一个候选SWAP门的时间为$ t $；最大可能的SWAP门搜索空间大小为$ s $；每个CNOT门的最大搜索步数为$ k $。

SPBHA算法预处理阶段的4个步骤中，Floyd算法时间复杂度是$ O(N^3) $，生成量子线路DAG的时间复杂度为$ O(m) $，初始化前端层即在量子线路DAG中搜索入度为零的顶点，时间复杂度是$ O(m) $。利用前瞻机制初始化量子位映射的时间复杂度为$ O(N) $(最坏情况下前端层涉及所有物理量子位)，因此预处理阶段的时间复杂度可表示为$T_1(N,m) = O(N^3+m)$。

SPBHA算法中的单次遍历算法的时间复杂度可表示为$t \times s \times k \times m$，根据式(4)，最坏情况下所有量子位都出现在前端层和扩展集，则$ t $的时间复杂度为$ O(N) $。最坏情况下，CNOT门的两个逻辑量子位在物理上与其余全部的量子位近邻，故最大可能SWAP门搜索空间大小$ s $为$ O(N) $。单次遍历算法至多需要量子芯片耦合图直径数量的SWAP门为每个CNOT门移动两个量子位，对于2D网格布局来说最大搜索步数$ k $为$ O(\sqrt{N}) $。因此，单次遍历算法的时间复杂度$T_2(N,m) = O(N^{2.5} m)$。

SPBHA算法的总时间复杂度为：

主要计算开销来自3次运行单次遍历算法，而对于运行在NISQ设备上的量子程序，当量子位数处于100以内，量子线路中CNOT门数在10000以内时，时间复杂度是可以接受的。

量子线路运行平台使用IBM Quantum Experience平台，测试数据选自IBM的QisKit中的量子线路、RevLib^[20]中的函数以及Quipper^[21]和ScaffCC^[22]中编译的算法。实验在英特尔Core i7-8750H 2.2 GHz和16 GB内存的计算机上进行，操作系统为Windows 10。

所有实验均使用IBM Q20 Tokyo芯片的耦合图。该芯片为对称量子硬件模型，每对相连的物理量子位之间的两个方向上都允许使用CNOT门。实验进行了A*-based算法、SABRE算法和SPBHA算法的对比分析。由于SPBHA算法和SABRE均存在随机初始化量子线路映射过程，所以结果存在波动。实验将每种算法运行5次，取平均结果。

SPBHA算法经过多次测试，最终选取效果最佳的一组参数，具体如下：权重参数$ W = 0.5 $固定不变，执行参数$ \varepsilon = 0.000\;5 $，衰变参数$ \delta = 0.002 $，每次增加0.001。SABRE算法参数选择如下：权重参数$ W = 0.5 $固定不变，衰减参数$ \delta = 0.001 $。

表2列出了A*-based算法、SABRE算法和SPBHA算法在不同规模量子线路下的附加门添加数量。由表2可知SPBHA算法减少附加门数的效果远好于A*-based算法。小规模量子线路(量子规模小于1000)的附加门数降低百分比可以达到76%，中规模量子线路为71%，大规模量子线路则为57%。部分测试中SPBHA算法可通过双向遍历找到完美初始映射，无需额外附加门(如ising_model_10等)。

A*-based算法的附加门数多于SPBHA算法的原因是A*-based算法只考虑量子线路开头的两个量子位门，没有继续改进初始映射。对于ising_model基准，最优解的意义不大，因为量子力学中的ising_model只考虑附近的耦合能量。SPBHA算法和SABRE算法都可以找到完美初始映射，而A*-based不行，这从一个侧面反映了算法的性能。

与SABRE算法相比，SPBHA算法在小规模量子线路的附加门数降低百分比可以达到38%，中规模量子线路为48%，大规模量子线路则为16%。上述两个算法都有随机因素，因此进行5次实验取平均结果可以一定程度上反映算法的真实情况。如表2所示，在大多数测试中，SPBHA算法都有更低的附加门数量，仅在少数测试时略高于SABRE算法，其中一些测试结果显著低于SABRE算法。SPBHA算法的附加门数少于SABRE算法的原因是表2的部分测试中存在大量运行在相同量子位对上的CNOT门。根据局部性原理，SPBHA算法具有满足前端层CNOT门耦合的初始映射，在部分测试上(如cycle10_2_110)可大幅减少附加门数，符合算法分析。

SPBHA算法使用了双向遍历，即正向遍历线路得到初步的量子位初始映射，利用量子线路的可逆性反转线路并将正向遍历得到的映射作为输入反向遍历线路，最终得到更新的初始映射。

表3列出了使用不同遍历方式的SPBHA算法附加门数的影响。实验结果显示双向遍历得到的量子位映射相较单次遍历普遍具有更好的性能，更新的初始映射使得算法添加了更少的附加门。随着量子线路规模增大，双向遍历与单次遍历的附加门数差距逐渐减小，最差情况可以减少7%的CNOT门数。原因是量子线路规模增大，两端量子门的情况不足以代表全部量子门的情况，因此对附加门数的影响减小，较单次遍历的降幅不够明显。使用双向遍历方式的算法在附加门数上总体少于单次遍历方式的附加门数，与算法分析是一致的。

图7展示了6组测试在不同衰变参数$ \delta $值下产生的量子线路深度变化。每组测试的数据分别在$\delta = 0.002\text{，}\delta = 0.004\text{，}\delta = 0.006$的情况得到。

由于映射算法的改变，SABRE算法和SPBHA算法的选择能力难以比较。如图7所示，SPBHA算法可通过改变附加门的数量使得生成线路深度变化平均达到10.6%。根据文献[8]的实验，SABRE算法可提供约8%的生成量子线路深度变化，从量子线路深度变化的指标对比，可以反映出SPBHA算法可以根据量子位相干时间和门保真度数据来改变$ \delta $的值，因而具有相对更好的深度与量子门数的选择能力。

实验结果表明，如果继续增大$ \delta $值，量子线路深度和门的数量都可能增加，原因是$ \delta $过大导致启发式代价函数将过多地考虑未移动的量子位，而不是去满足当前与后继CNOT门的依赖性，这将带来冗余的附加门数，提高算法执行时间。

图  7  量子线路深度与附加门数的选择

本文提出了基于交换门的前瞻双向启发式算法，实现了量子线路的高效映射。为减少附加门的使用，降低算法复杂度，SPBHA算法利用前瞻的量子门信息进行量子位映射的初始化，采用就近寻找候选SWAP门的原则大幅缩小了交换门的搜索空间。为进一步优化量子位映射，SPBHA算法考虑全局量子门信息，利用量子计算的可逆性进行双向遍历。通过实验证明了SPBHA算法的可行性，为量子线路映射算法的设计提供了新思路。在量子编译过程中，量子线路映射与调度往往紧密相关，从时序与跨平台调度的角度优化用户的量子程序是未来量子线路映射算法一个可行的研究方向。此外，量子线路映射问题可进行更精准地建模，考虑量子位错误率及量子程序保真度，将在后续工作中进行深入地探索。