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 makes use of a combined subgraph isomorphism and completion to initialize some candidate mappings, and the other dynamically modifies the mappings by TSA. Our experiments show that, compared with state-of-the-art methods in the literature, TSA can generate mappings with a smaller number of additional gates and have better scalability for large-scale circuits.