Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices

问题

不理解的名词

保留遍历搜索技术
全局优化初始映射

名词

quantum circuit：量子线路，是在抽象概念下，对量子信息存储单元进行操作的线路。组成包括：量子位、线路（时间线）、逻辑门。
Directed Acyclic Graph：DAG，有向非循环图

摘要

由于对量子计算的硬件条件考虑不足，比如说没有考虑二量子位操作的物理连接不足的问题，一般的NISQ无法执行大多数的量子算法。动态重映射策略被创建，来解决这些问题。但是动态重映射策略不能保证程序的可靠性，策略复杂度高，初始映射差，可控性和灵活性低。

提出了一种基于交换的双向启发式搜索算法(SABRE)，适用于量子位任意连接的NISQ设备。通过优化每一次搜索尝试，采用新型的反向遍历技术，全局优化了初始映射。引入了了衰减效应，能够衡量搜索的深度和整个系统的门的个数。SABRE比其他的已知最好的指数级算法好一些。

介绍

量子计算机虽然无法实现QEC，但是也可以干很多事情。软硬差距存在，现有的NISQ体系结构无法支持大型量子程序有效执行。本文章专注于由于NISQ设备限制而产生的二量子位操作问题。逻辑量子位分配到物理量子位上，类比传统计算机就是寄存器分配。

实际量子线路无法直接在NISQ上执行，因此需要进行量子电路转换，实现量子程序在NISQ设备上的使用，步骤有：

初始逻辑量子位到物理量子位的映射
映射变换，使要进行门运算的两个逻辑量子位重映射到两个相邻物理量子位上。

之前的方法有：

构建数学问题，采用求解器解决。缺点是求解速度慢，只能对小规模数据使用，不能利用问题内部特征。
启发式搜索算法，大多数是在理想的1D / 2D晶格模型上开发的，不适用于具有更多不规则和受限制的耦合连接的NISQ器件。
针对IBM QX的搜索算法，穷尽搜索，运行速度慢，缺少全局优化能力，在多目标优化条件下，无法保证生成的量子电路的质量。

本文提出了：

基于交换的双向启发式搜索算法，解决量子位映射问题。
穷尽搜索很多步骤是多余的，SABRE方法大量减少了搜索空间。
初始化映射极为重要，可以影响最终电路质量。采用创新的保留遍历搜索技术。通过遍历反向电路，可以产生高质量的初始映射。在这个过程中更重视电路开始的位置，不忽视电路其他部分。
引入衰减效应，可以使重叠的SWAP操作造成启发式代价函数值变高，因此更支持不重叠的SWAP操作。这种优化可以鼓励并行性，并且可以在电路深度和门数之间进行权衡，从而进一步生成不同的硬件兼容电路。

本文贡献在于：

对基于启发式搜索算法的量子位映射问题总结了目标和度量标准
提出了基于SWAP的搜索模式，比穷尽搜索模式优秀，允许向NISQ时代的可扩展性。
提出了反向遍历策略，利用量子位映射问题的内在可逆性，在初始映射解决方案中实现全局优化。
在启发式搜索策略中提出衰减代价函数，能产生适用于不同硬件的量子电路。

背景

软件基础

多种量子模型是数学等价的，量子电路模型是最流行的。

量子位
量子操作
量子线路

在NISQ时代的QC硬件

实现量子计算的硬件方法有：超导量子电路、离子阱、量子点、中性原子等。目前最可靠的技术是超导量子电路。

文章中考虑硬件约束包括：

量子位生存时间
量子位操作错误率，因为量子门会导致错误，因此要尽可能缩减量子门的数目
量子位连接。

问题分析

SWAP操作解决不连通问题
其他方法解决不连通问题：基于先前的架构，不予考虑。
SWAP操作带来如下问题：操作指令数增加，导致总体错误率增加；电路层次增加，总执行时间增加，由decoherence导致的错误增加。由此要尽量减少SWAP操作个数。

构建问题

找初始mapping、中间mapping的变换，最小化门操作个数，最小化量子线路层次。

目标和度量标准

灵活性：对以后的量子计算机也需适用
可靠性：要尽量减少门个数
并行性：减少量子线路层次，允许更多的操作
可扩展性：在不使用QEC的情况下，问题是不变的。使用了QEC，会将问题转化为另一个。

度量标准：门总数和量子线路深度。

找初始化映射和SWAP

预处理

使用Floyd-Warshall算法计算距离矩阵
使用有向非循环图（DAG）表示在一个量子线路中的双量子比特位门的执行限制。单量子位的操作在这不予考虑，因为他们不涉及到其他量子位。
找到第一层：没有前驱节点，即入度为零的控制非门可以被放在第一层中。
临时初始映射生成：随机产生初始映射，作为启发式搜索的起始状态。

基于SWAP的启发式搜索

算法1是一次遍历的搜索过程，从头到尾扫描，并插入SWAP操作，使得所有的CNOT都可以被执行。这个算法会被多次使用来更新优化初始映射。

拓扑排序方法

检查F是否为空，若是，则停止，若否，则初始化Execute gate list。
对于F中现在的所有的门，取出这个门涉及到的两个量子位，查看他们所在的物理量子位有没有连接，如果有，则加入Execute gate list，否则不加入。
如果Execute gate list不为空，则将里面的所有门从F中删除掉。接下来检查后继的门，对于后继门的两个量子位，如果如果F中没有任何门指向这两个量子位的其中一个，则把这个后继门添加到F中。回到2。
如果Execute gate list为空，则所有的F中的门在硬件中不能被执行。需要插入SWAP操作。
启发式搜索插入SWAP：初始化score。通过F和G找到SWAP的候选列表。对于F中的所有门的所有程序量子位，找到它对应的物理量子位，通过G找到和这个物理量子位相邻的其他物理量子位，根据映射找到这些物理量子位对应的程序量子位。原量子位和这些程序量子位可以被进行SWAP。加入到候选SWAP列表中。对于候选列表中的每一个候选SWAP，更新原映射，作为临时图，对其进行评分，选择评分最小的SWAP操作，并将原映射更新。回到1。

在这里每次启发式搜索只搜索一步SWAP，下一次可能还是处于EExecute gate list为空的状态，这样就需进行下一步的启发式搜索，如果不为空，则可以继续进行拓扑排序。

算法中：

Front layer F：其中的门都可以在逻辑上被执行
Mapping $\pi$：表示了从逻辑量子位到物理量子位的映射
Distance Matrix D：表示了两点间最少的SWAP数
Circuit Dag：有向无环图，代表量子线路结构
Chip Coupling Graph G：无向图，代表任意两个物理量子位之间的连接

算法的优势：

不是去搜索一个映射，而是去搜索在F中的量子位的SWAP。

解释关键设计决策

只有F中的门涉及到的量子位元参与的SWAP才有意义。
F后紧邻的量子位的距离也加入启发式函数的考虑，但不考虑再后面的，因为执行过程中，mapping的变化可能会很大。

时间复杂度分析（暂不理解）

时间复杂度上限可以通过最坏情况来估计，也就是每两个比特位门都需要单独满足。

满足一个比特位门的时间复杂度是满足在搜索空间中的潜在选项、最大可能搜索空间、二比特位最大数目的搜索步数的一次搜索的乘积。启发式代价函数的时间复杂度是O（N）。

搜索空间从可以从O(exp(N))降到O(N)（最坏情况下所有量子比特位都在首层），

初始映射的反遍历

Siraichi没有考虑时间因素，Zulehner只考虑了最初映射，没有全局考虑。

量子电路是可逆的，可以获取到一个量子电路的逆电路。如果知道了最终电路，我们就可以把最终电路作为初始电路，解决映射问题。如果一次执行完成，得到的结果映射，可以作为我们开始执行时的初始映射，这样能够提供更好的效果。

首先随机生成初始映射，进过原量子线路，获得最终映射。将最终映射通过反向量子线路，获得更新后的初始映射。更新后的初始映射就在以后被作为优秀的映射方案。

量子线路深度和门数的衡量

深度优先
门数少优先

衰减效果被应用，来尽可能选择不相交的SWAP操作。

启发式函数设计

H应该能代表SWAP的移动步数
能够帮助后期的SWAP采用更少的步数
能够鼓励并行操作，考虑线路深度和并行度的取舍。

设计：

F中所有元素对之间的距离和（来自Distance Matrix）
扩展集中的距离和
swap是否被重复使用

$$ H=\max \left(\operatorname{decay}\left(SWAP . q_{1}\right), \operatorname{decay}\left(SWAP . q_{2}\right)\right)\ *\left{\frac{1}{|F|} \sum_{g a t e \in F} D\left[\pi\left(g a t e \cdot q_{1}\right)\right]\left[\pi\left(g a t e . q_{2}\right)\right]\ +W * \frac{1}{|E|} \sum_{g a t e \in E} D\left[\pi\left(g a t e . q_{1}\right)\right]\left[\pi\left(g a t e . q_{2}\right)\right] \right} $$

总结

物理量子位不能比程序量子位少
有限的物理连接