Qubit allocation as a combination of subgraph isomorphism and token swapping
Qubit allocation as a combination of subgraph isomorphism and token swapping
复制标题
量子比特分配作为子图同构和令牌交换的组合
DOI：
10.1145/3360546
复制
发表时间：
2019
影响因子：
--
通讯作者：
Fernando Magno Quintão Pereira
中科院分区：
文献类型：
--
作者：
Marcos Yukio Siraichi;V. F. Santos;Caroline Collange;Fernando Magno Quintão Pereira
2016年，第一批量子处理器向公众开放。对实际量子设备进行编程的可能性引起了人们的极大热情。然而，这种可能性也带来了挑战。一个挑战是所谓的量子比特分配问题：将虚拟量子电路映射到实际量子架构。这个问题存在解决方案;然而，在我们看来，他们未能利用几十年来对图论的改进。相比之下，本文展示了如何将量子比特分配建模为子图同构和令牌交换的组合。2016年发表的后一个问题的近似解决方案使这一想法成为可能。我们将我们的算法与其他五个量子比特分配器进行了比较，这些量子比特分配器都是在过去两年中独立设计的，包括IBM挑战赛的赢家。当在具有20个量子位的量子架构“东京”中进行评估时，我们的技术在找到的解决方案的质量和使用的内存量方面优于这些最先进的方法，同时显示实际的运行时间。
In 2016, the first quantum processors have been made available to the general public. The possibility of programming an actual quantum device has elicited much enthusiasm. Yet, such possibility also brought challenges. One challenge is the so called Qubit Allocation problem: the mapping of a virtual quantum circuit into an actual quantum architecture. There exist solutions to this problem; however, in our opinion, they fail to capitalize on decades of improvements on graph theory. In contrast, this paper shows how to model qubit allocation as the combination of Subgraph Isomorphism and Token Swapping. This idea has been made possible by the publication of an approximative solution to the latter problem in 2016. We have compared our algorithm against five other qubit allocators, all independently designed in the last two years, including the winner of the IBM Challenge. When evaluated in "Tokyo", a quantum architecture with 20 qubits, our technique outperforms these state-of-the-art approaches in terms of the quality of the solutions that it finds and the amount of memory that it uses, while showing practical runtime.