摘要:
研究背景 量子位映射的目标是在可接受的时间内通过插入最少的辅助量子门（以下称辅助门），将逻辑电路映射到物理设备。 我们提出了一种有效的方法，称为基于禁忌搜索的量子比特映射算法（TSA）。 它由两个关键步骤组成：一是利用组合子图同构和量子比特补全算法得到初始映射集，二是通过基于禁忌搜索来动态调整量子比特映射。 我们的实验表明，与最先进的方法相比，TSA生成的初始映射在调整过程中插入的门数量最少，并且对于大规模电路具有更好的可扩展性。
目的 由于量子算法的设计和实现之间存在差距，算法设计过程中通常不考虑任何硬件连接约束，所以在硬件上执行算法时，需要插入辅助门来满足硬件连接约束。由于量子门需要在相干时间内执行，量子比特保持相干状态的时间非常短。因此，插入的辅助门数量应该尽量少。
方法 我们将子图同构算法（IMSM）找到的逻辑电路和物理电路的部分同构子图作为一组部分初始映射并根据逻辑电路的交互图和物理电路的耦合图的连接性补全初始映射。然后通过使用禁忌搜索调整映射生成能在物理设备上执行的电路。我们设计了三个评估函数，并且考虑了look-ahead 机制。我们的实验使用 IBM Q Tokyo 和 Sycamore 设备作为目标物理结构与最新的调整算法进行对比实验。
结果 实验结果表明，考虑辅助门数量的评估函数插入的辅助门数量最少。我们测试了最先进的初始映射和调整算法的几种组合，旨在电路映射过程中插入更少的辅助门。一般来说，TSA的初始映射在各种调整算法上表现都是最好的。与MCPE和优化版本MCPE_OP作为启发式成本函数的最大连续正效应的动态前瞻启发式技术（DLH）相比，TSA插入的辅助门数量分别降低了 27.32% 和 12.42%。TSA具有可扩展性，在大型电路上也可以在几分钟内完成映射。
结论 我们提出了一种可扩展的量子位映射算法。首先使用子图同构算法和基于量子比特之间连通性补全初始映射。然后我们采用前瞻性启发式搜索来调整映射，以减少插入的辅助门的数量。 实验结果表明，TSA的生成的初始映射在各种调整算法上插入的SWAP门最少。大多数中小型电路可以在几秒钟内完成转换。对于大规模电路，也可以在几分钟内获得结果。我们发现如果交互图中节点的度数普遍大于物理耦合图的最大度数，则不太适合使用子图同构生成部分初始映射。未来，我们将研究如何减少插入的辅助门的数量并提高搜索速度，将提出的方法应用于更多NISQ 设备。
下载: