Qubit allocation as a combination of subgraph isomorphism and token swapping - INRIA - Institut National de Recherche en Informatique et en Automatique Accéder directement au contenu
Communication Dans Un Congrès Année : 2019

Qubit allocation as a combination of subgraph isomorphism and token swapping

Résumé

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.
Fichier principal
Vignette du fichier
Siraichi_QubitAlloc_OOPSLA19.pdf (1.33 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02316820 , version 1 (15-10-2019)

Identifiants

Citer

Marcos Yukio Siraichi, Vinicius Fernandes Dos Santos, Caroline Collange, Fernando Magno Quintão Pereira. Qubit allocation as a combination of subgraph isomorphism and token swapping. OOPSLA, Oct 2019, Athens, Greece. pp.1-29, ⟨10.1145/3360546⟩. ⟨hal-02316820⟩
214 Consultations
364 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More