Swap Minimization in Nearest Neighbour Quantum Circuits: An ILP Formulation

Quantum computing (QC) represents a great challenge for both academia and private companies and it is currently pursuing the development of quantum algorithms and physical realizations of quantum computers. Quantum algorithms exploit the concept of quantum bit (qubit). They are implemented by designing circuits which consider an ideal quantum computer where no interaction restriction between qubits is imposed. However, physical realizations of quantum computers are subject to several technological constraints and adjacency between interacting qubits is one of the most common one. To this end, additional gates, referred to as swap, can be added to a quantum circuit to make it nearest neighbour compliant. These additional gates have a cost in terms of reliability of the quantum system, hence their number should be minimized. In this paper we first give some hints about this cutting edge topic. Then we provide a review of the literature solving approaches for the swap minimization problem in quantum circuits and propose an integer linear programming formulation for it. We conclude with some preliminary results on small test instances and future work perspectives.