Towards an optimal swap gate

Christopher J. Wood, David C. McKay, Sarah Sheldon +2 more

Hui Li, Kai Lü, Ziao Han +3 more

The conventional approach for initial qubit mapping in the Noisy Intermediate-Scale Quantum (NISQ) era typically uses a static heuristic strategy, overlooking insufficient qubit neighborhood in subsequent operations, resulting in excess additional SWAP gates. To address this, we introduce a multifactor interaction cost function considering qubit distance, interaction time, and gate operation error rates, enhancing SWAP gate selection in the traditional strategy. Considering quantum hardware constraints, we propose Batch SWAP Optimization Strategy (BSOS). BSOS tackles qubit mapping challenges by leveraging optimal SWAP gate selection and a SWAP-based batch update technique, effectively minimizing SWAP gates throughout circuit execution. Experimental results show that BSOS significantly reduces additional gates by intelligently selecting SWAP gates and using batch updating, with a 38.1% average decrease in inserted SWAP gates, leading to a 12% reduction in hardware gate counting overhead.

Ji Liu, Peiyi Li, Huiyang Zhou

Despite rapid advances in quantum computing technologies, the qubit connectivity limitation remains to be a critical challenge. Both near-term NISQ quantum computers and relatively long-term scalable quantum architectures do not offer full connectivity. As a result, quantum circuits may not be directly executed on quantum hardware, and a quantum compiler needs to perform qubit routing to make the circuit compatible with the device layout. During the qubit routing step, the compiler inserts SWAP gates and performs circuit transformations. Given the connectivity topology of the target hardware, there are typically multiple qubit routing candidates. The state-of-the-art compilers use a cost function to evaluate the number of SWAP gates for different routes and then select the one with the minimum number of SWAP gates. After qubit routing, the quantum compiler performs gate optimizations upon the circuit with the newly inserted SWAP gates.In this paper, we observe that the aforementioned qubit routing is not optimal, and qubit routing should not be independent on subsequent gate optimizations. We find that with the consideration of gate optimizations, not all of the SWAP gates have the same basis-gate cost. These insights lead to the development of our qubit routing algorithm, NASSC (Not All Swaps have the Same Cost). NASSC is the first algorithm that considers the subsequent optimizations during the routing step. Our optimization-aware qubit routing leads to better routing decisions and benefits subsequent optimizations. We also propose a new optimization-aware decomposition for the inserted SWAP gates. Our experiments show that the routing overhead compiled with our routing algorithm is reduced by up to 69.30% (21.30% on average) in the number of CNOT gates and up to 43.50% (7.61% on average) in the circuit depth compared with the state-of-the-art scheme, SABRE.

Juan Carlos García-Escartín, Pedro Chamorro‐Posada

Belal Ehsan Baaquie, L. C. Kwek

Hui Liu, Bingjie Zhang, Yu Zhu +2 more

Quantum computing has already demonstrated great computational potential across multiple domains and has received more and more attention. However, due to the connectivity limitations of Noisy Intermediate-Scale Quantum (NISQ) devices, most of the quantum algorithms cannot be directly executed without the help of inserting SWAP gates. Nevertheless, more SWAP gates lead to a longer execution time and, inevitably, lower fidelity of the algorithm. To this end, this paper proposes an optimized qubit mapping algorithm based on a dynamic look-ahead strategy to minimize the number of SWAP gates inserted. Firstly, a heuristic algorithm is proposed based on maximizing physical qubit connectivity to generate the optimal initial qubit mapping, which reduces the need for logical qubit shifts during subsequent SWAP gate insertion. Secondly, in the form of directed acyclic graphs, we identify quantum gates that violate the constraints of physical coupling and insert SWAP gates to remap qubits, thereby overcoming the limitations of qubit interactions. Finally, the optimal SWAP gate insertion strategy is built by comparing the cost of different SWAP gate insertion strategies through a multi-window look-ahead strategy to reduce the number of SWAP gates inserted. The experimental results show that the strategy in this paper decreases the number of SWAP gate insertions and significantly reduces the depth of quantum circuits when performing qubit mapping compared with state-of-the-art methods.