Qubit Mapping Based on Subgraph Isomorphism and Filtered Depth-Limited Search

Understand

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.