BQA: a high-performance quantum circuits scheduling strategy based on heuristic search

Abstract

Quantum computing is currently a research hotspot in both academia and industry. The inherent parallelism of quantum computers and the resulting powerful computing power will bring new solutions to many problems that are difficult for classical computers. However, due to the limitations of technical conditions, it is difficult to achieve full direct coupling of all qubits on a quantum chip. When compiling a quantum circuit onto a physical chip, it is necessary to ensure those two-qubit gates act on pairs of directly coupled qubits by inserting SWAP gates. It will cause great additional cost when a large number of SWAP gates are inserted, leading to the execution time of quantum circuits longer. In this paper, we designed a strategy based on the business of each individual qubit to insert SWAP gates, named Busy-Qubits-Avoid Strategy. On the one hand, we try to hide the time overhead incurred by the inserted SWAP gates by exploiting the uneven distribution of quantum gates over qubits. On the other hand, we also expect the inserted SWAP gates to make as little negative impact on subsequent two-qubit gates as possible. We designed a heuristic function which takes into account both of these points. Compared with Sabre and tket, we achieved a better effect. In addition, as the number of two-qubit gates increases, better optimization results will be achieved. This implies higher execution efficiency and lower decoherence error rate.