Abstract Quantum Circuit Compilation is an important problem in Quantum Computing and its purpose is to make a quantum circuit executable by a quantum machine. In particular, the nearest-neighborhood constraint required by many quantum machines for the execution of binary quantum gates is enforced by inserting additional swap gates in the circuit. Despite swap gates allow to overcome the limited connectivity of quantum devices, they increase both the noise of the circuit and its depth, with a consequent loss of quantum coherence. In this paper we propose to use a new Ant Colony Optimization (ACO) algorithm to solve the compilation problem by optimizing the number of swaps and its depth . The algorithm includes two original contributions: a Divide-et-Impera strategy to compile the input quantum circuit and a novel iterated local search strategy to set its initial state.
Baioletti et al. (Sat,) studied this question.