Qubit Allocation

  • Marcos Yukio Siraichi UFMG
  • Fernando Magno Quintão Pereira UFMG
  • Vinicius dos Santos UFMG
  • Caroline Collange INRIA


The availability of the first prototypes of quantum computers, in 2016, with free access through the cloud, brought much enthusiasm to the research community. Yet, programming said computers is difficult. One core challenge is the so called qubit allocation problem. This problem consists in mapping the virtual qubits that make up a logical quantum program onto the physical qubits that exist in the target quantum architecture. To deal with this challenge, we have proposed one of the first algorithms to solve qubit allocation. This algorithm, together with its ensuing formulations, is today available in the Enfield compilera concrete product of this work. Our first paper in this field, titled Qubit Allocation, has inspired much research, and our latest qubit allocation design, called Bounded Mapping Tree, stands out today as one of the most effective qubit allocators in the world.

Palavras-chave: Quantum computing, qubit allocation, optimization, compiler


Devitt, S. J. (2016). Performing quantum computing experiments in the cloud. Phys. Rev. A, 94(3):032329.

Devoret, M. H., Wallraff, A., and Martinis, J. M. (2004). Superconducting qubits: A short review. arXiv, cond-mat/0411174:1-41.

Koch, J., Yu, T. M., Gambetta, J., Houck, A. A., Schuster, D. I., Majer, J., Blais, A., Devoret, M. H., Girvin, S. M., and Schoelkopf, R. J. (2007). Charge-insensitive qubit design derived from the cooper pair box. Phys. Rev. A, 76(1):04319.

Li, G., Ding, Y., and Xie, Y. (2019). Tackling the qubit mapping problem for nisq-era quantum devices. In ASPLOS, page 1001-1014. ACM.

Siraichi, M. Y., Santos, V. F. d., Collange, C., and Pereira, F. M. Q. (2019). Qubit allocation as a combination of subgraph isomorphism and token swapping. In OOPSLA, pages 120:1-120:29. ACM.

Siraichi, M. Y., Santos, V. F. d., Collange, S., and Pereira, F. M. Q. (2018). Qubit allocation. In Inter. Symp. on Code Generation and Optimization, page 113-125. ACM.

Siraichi, M. Y. and Tonetti, C. (2018). Enfield: An OpenQASM compiler. In Congresso Brasileiro de Software, Sessao de Ferramentas ̃ , Bento Gonc ̧alves, RS, Brazil. SBC.
Como Citar

Selecione um Formato
SIRAICHI, Marcos Yukio; PEREIRA, Fernando Magno Quintão; DOS SANTOS, Vinicius; COLLANGE, Caroline. Qubit Allocation. In: CONCURSO DE TESES E DISSERTAÇÕES (CTD), 33. , 2020, Cuiabá. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2020 . p. 49-54. ISSN 2763-8820. DOI: https://doi.org/10.5753/ctd.2020.11368.