A binary integer programming-based method for qubit mapping in sparse architectures

It is a current trend of sparse architectures employed for superconducting quantum chips, which have the advantage of low coupling and crosstalk properties. Existing qubit mapping algorithms do not take the sparsity of quantum architectures into account. To this end, we propose a qubit mapping method based on binary integer programming, called QMBIP. First, we slice a given quantum circuit by taking into account the sparsity of target architectures. Then, the constraints and the objective function are formulated and rendered to the binary integer programming problem by matrix transformation. The behavior of a SWAP gate is characterized by an elementary row transformation on the mapping matrix between the physical and logical qubits. To reduce the search space, we introduce path variables and isomorphic pruning, as well as a look-ahead mechanism. Finally, we compare with typical qubit mapping algorithms such as SABRE and SATMAP on the sparse architectures ibmq_sydney, ibmq_manhattan, ibmq_singapore, and a dense architecture ibmq_tokyo. Experiments show that QMBIP effectively maintains the fidelity of the compiled quantum circuits. For example, on ibmq_sydney, the fidelity of the quantum circuits compiled by our approach outperforms SABRE and SATMAP by 53.9% and 46.8%, respectively.