Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices

文中所有图片引用自原文 Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices

问题描述

文章介绍了将编写的量子电路映射为运行在真实设备上的方法。

在真实设备上，一个量子位只能与物理上相连的量子位进行运算。单量子门并不受这一限制的影响，而对于多量子门，如CNOT门，参与运算的量子位必须直接相连。由于任意多量子门都可拆分为多个单量子门和CNOT门的运算，因此我们只需研究如何处理CNOT门。

解决方案

符号约定

符号	定义
$n$	逻辑量子位数量
$\{q_i\}_{i=1}^{n}$	逻辑量子位
$g$	电路量子门数量
$d$	电路深度
$N$	物理量子位数量
$\{Q_i\}_{i=1}^n$	物理量子位
$G(V,E)$	物理设备芯片抽象得到的图结构
$D(Q_i,Q_j)$	$Q_i$ 与 $Q_j$ 间距离
$\pi(q_i)$	$q_i$ 当前对应的物理量子位
$\pi^{-1}(Q_i)$	$Q_i$ 当前对应的逻辑量子位
$\mathbb F$	Front Layer
$\mathbb E$	Extended Set

简要思路

文中给出的方法是：对于逻辑上参与CNOT门的两个量子位 $q_i$ 和 $q_j$ ，若两者在物理上的映射并不相邻，则通过一系列SWAP操作，使得两者在物理上的映射相邻，即在电路中额外引入若干SWAP操作，使得电路在真实设备上可运行。

量子映射举例

文中使用一个DAG表示CNOT门之间的依赖关系，用拓扑排序的方式依次处理各个CNOT门。图中的结点表示一个CNOT门，边表示后继结点表示的CNOT门需要等待的量子位。

DAG生成

拓扑排序的队列为 $\mathbb F$ ，文中称为 Front Layer。在拓扑排序的循环中，从 $\mathbb F$ 中挑出可直接在物理设备上执行的CNOT门，放入集合 $\mathbb S_g$ ；若 $\mathbb S_g\neq\varnothing$ ，则执 $\mathbb S_g$ 中的CNOT门，并更新 $\mathbb F$ ；若 $\mathbb S_g=\varnothing$ ，则枚举所有可行的SWAP操作，执行评估函数值最优秀的SWAP操作，更新 $\pi$ 和 $\pi^{-1}$ 。

预处理

预处理阶段主要干四件事情：

计算距离矩阵 $D$ ，可简单认为芯片上的边都是双向的，边权都为 $1$ ，可用Floyd或者Johnson算法求全源最短路；
根据逻辑电路生成DAG；
初始化 $\mathbb F$ ；
初始化 $\pi$ 和 $\pi^{-1}$ 。

SWAP操作枚举方法

显然，只有使得 $F$ 中的CNOT门可执行的SWAP操作才能使得拓扑排序不断进行下去，因此枚举SWAP操作时仅考虑 $\mathbb F$ 中的门电路。

枚举 $F$ 中的CNOT门，设参与某一CNOT门运算的两比特为 $q_i$ 和 $q_j$ ，取其中一个比特的物理映射 $Q_x=\pi(q_i)$ ，找到 $Q_x$ 的邻接点集合 $\mathbb Q_{x\cdot}$ ， $q_i$ 可与 $\pi^{-1}\left(\mathbb Q_{x\cdot}\right)$ 进行SWAP操作。

评估函数 $H$

一个SWAP操作使用评估函数 $H$ 计算得分， $H$ 越小则SWAP操作越优秀。

假设执行SWAP之后的映射为 $\pi_t$ ，评价函数可表示为

$H(\text{SWAP}(q_x,q_y))=\max(\text{decay}(q_x),\text{decay}(q_y))\cdot\frac{1}{|\mathbb F|}\sum\limits_{\text{CNOT}(q_i,q_j)\in\mathbb F}D(\pi_t(q_i),\pi_t(q_j))+W\cdot\frac{1}{|\mathbb{E}|}\sum\limits_{\text{CNOT}(q_i,q_j)\in\mathbb E}D(\pi_t(q_i),\pi_t(q_j))$

总体来看， $H$ 体现了执行SWAP操作后参与运算的量子位之间的靠近程度。 $\text{decay}(q_i)$ 初始化为 $1$ ，当 $q_i$ 参与一次SWAP操作，则 $\text{decay}(q_i)$ 增加 $\delta$ ，这使得算法趋向于选择多个量子位运算不冲突的SWAP操作，使得多个SWAP操作可以并行执行。 $\mathbb E$ 是 Extended Set，即 $\mathbb F$ 的一部分后继；为了使得算法有较好的预见性，因此将 $\mathbb E$ 中的量子门也纳入评估。

初始映射 $\pi$ 优化

量子电路正向与反向等价

$\pi$ 的初始化对最终结果有很大影响，因此需要优秀的 $\pi$ 值。

文中运用了一个 trick：量子电路的正向执行与反向执行是等价的，因此首先随机初始化 $\pi=\pi_s$ ，用正向电路执行一遍上述算法得到 $\pi=\pi_f$ ， $\pi_f$ 对于反向电路来说是一个优秀的初始化映射；再用 $\pi_f$ 作为初始化映射，用反向电路运行上述算法得到 $\pi=\pi_u$ 得到优秀的正向电路初始化映射。