  Mapping logical quantum circuits to Noisy Intermediate-Scale Quantum (NISQ)
devices is a challenging problem which has attracted rapidly increasing
interests from both quantum and classical computing communities. This paper
proposes an efficient method by (i) selecting an initial mapping that takes
into consideration the similarity between the architecture graph of the given
NISQ device and a graph induced by the input logical circuit; and (ii)
searching, in a filtered and depth-limited way, a most useful SWAP combination
that makes executable as many as possible two-qubit gates in the logical
circuit. The proposed circuit transformation algorithm can significantly
decrease the number of auxiliary two-qubit gates required to be added to the
logical circuit, especially when it has a large number of two-qubit gates. For
an extensive benchmark set of 131 circuits and IBM's current premium Q system,
viz., IBM Q Tokyo, our algorithm needs, in average, 0.4346 extra two-qubit
gates per input two-qubit gate, while the corresponding figures for three
state-of-the-art algorithms are 0.6047, 0.8154, and 1.0067 respectively.
