Qubit Mapping Based on Tabu Search

The goal of qubit mapping is to map a logical circuit to a physical device by introducing additional gates as few as possible in an acceptable amount of time. We present an effective approach called Tabu Search Based Adjustment (TSA) algorithm to construct the mappings. It consists of two key steps: one is making use of a combined subgraph isomorphism and completion to initialize some candidate mappings, and the other is dynamically modifying the mappings by TSA. Our experiments show that, compared with state-of-the-art methods, TSA can generate mappings with a smaller number of additional gates and have better scalability for large-scale circuits.