Qubit allocation

By Marcos Yukio Siraichi, V. F. Santos, Caroline Collange, Fernando Magno Quintão Pereira. IEEE/ACM International Symposium on Code Generation and Optimization, 2018

350 citations recorded by the source corpus.

In May of 2016, IBM Research has made a quantum processor available in the cloud to the general public. The possibility of programming an actual quantum device has elicited much enthusiasm. Yet, quantum programming still lacks the compiler support that modern programming languages enjoy today. To use universal quantum computers like IBM's, programmers must design low-level circuits. In particular, they must map logical qubits into physical qubits that need to obey connectivity constraints. This task resembles the early days of programming, in which software was built in machine languages. In this paper, we formally introduce the qubit allocation problem and provide an exact solution to it. This optimal algorithm deals with the simple quantum machinery available today; however, it cannot scale up to the more complex architectures scheduled to appear. Thus, we also provide a heuristic solution to qubit allocation, which is faster than the current solutions already implemented to deal with this problem.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/5158dec16707ac7031d33727a077b4a703fc41ef

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Not All Qubits Are Created Equal: A Case for Variability-Aware Policies for NISQ-Era Quantum Computers (2018, methodology): “Moreover, recent works provide an excellent theoretical understanding of the mapping problems [4, 8, 20, 26, 28, 32].”
Noise-Adaptive Compiler Mappings for Noisy Intermediate-Scale Quantum Computers (2019, background): “Recently, [42] compiled small benchmarks for IBM systems, based on only qubit topology information, not calibration data.”
Software Mitigation of Crosstalk on Noisy Intermediate-Scale Quantum Computers (2020, methodology): “[2, 15, 37, 45] optimize abstract program IR, without considering hardware constraints, while [9, 38, 41, 55, 59, 61] develop optimizations for mapping programs to hardware qubits to reduce the circuit size or depth.”
Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices (2018, methodology): “2) Reverse Traversal for Initial Mapping: It has been proved that initial mapping could have a huge impact on the final result [12], [33].”