Toward optimizing compilers for quantum computers

17/01/2019
Intervenant(s) : Sylvain Collange (Inria, Rennes)
 Quantum computers are not science-fiction any more. IBM provides cloud access to experimental quantum computers since 2016, while Google expects to reach commercial viability in niche markets within a few years. These concrete implementations hold the promise to apply the results of quantum computing theory that has been developed since the 1990s. Nevertheless, the availability of these first-generation quantum computers now requires that we develop a whole new software ecosystem, starting from compilers and runtimes. In particular, we consider an important building block of any quantum circuit compiler: qubit allocation. Like its classical counterpart register allocation, qubit allocation is the the problem of proper placement of program variables onto hardware resources. However, qubit allocation need to obey both physical constraints like the impossibility of state cloning, and technical constraints on the connectivity between qubits. We model qubit allocation as a combination of the Subgraph Isomorphism and Token Swapping problems and derive an efficient and scalable heuristic.