Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

International Journal of Advanced Computer Science and Applications

SWAP Optimization for Qubit Mapping Based on the Centric-Shortest Quantum Gate Set in NISQ Devices

Shujuan Liu, Hui Li, Yingsong Ji, Jiepeng Wang

Published Jan 1, 2025• 0 citations
Publisher

Abstract

In the Quantum computing era of Noisy Intermediate-Scale Quantum (NISQ) devices, conventional qubit mapping strategies typically rely on specific heuristic rules to solve the mapping problem, overlooking the impact of other factors on the mapping, which leads to increased overhead from extra SWAP gates. To address this issue, we propose a SWAP optimization strategy based on the Centric-Shortest Quantum Gate Set (C-SQGS) and applies it to qubit mapping. In this approach, the centric qubit is determined by analyzing the maximum flexibility qubit set and the physical distances between the associated CNOT gates, leading to the identification of the Centric-Shortest Quantum Gate Set. To overcome the limitations of traditional cost functions that consider only single factors, a multi-factor cost function is introduced to evaluate the overall overhead of candidate SWAP operations and determine pending SWAP gate Set. Based on qubit flexibility analysis, executable SWAP gate is identified and inserted into the circuit. Experimental results demonstrate that the C-SQGS strategy effectively reduces both SWAP gate and two-qubit gate overhead. Specifically, it achieves an average SWAP gate reduction of 36.9% and 47.7%, and a two-qubit gate reduction of 13.8% and 13.5% on the t|ket⟩ and Qiskit compilers, respectively. These results highlight the potential of the C-SQGS strategy in enhancing the efficiency of qubit mapping for NISQ devices.

DOI
10.14569/ijacsa.2025.0161284

Related papers

Research on Qubit Mapping Technique Based on Batch SWAP Optimization

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.

International Journal of Advanced Computer Science and Applications•Jan 1, 2023•3 citations

QM-DLA: an efficient qubit mapping method based on dynamic look-ahead strategy

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.

Scientific Reports•Jun 7, 2024•4 citations

Not All SWAPs Have the Same Cost: A Case for Optimization-Aware Qubit Routing

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.

arXiv:2205.10596•IEEE International Symposium on High-Performance Computer Architecture (HPCA)•Apr 1, 2022•32 citations

An optimized sparrow search algorithm for quantum circuit mapping

Hui Li, Shujuan Liu, Jiepeng Wang +3 more

Abstract In the Noisy Intermediate-Scale Quantum (NISQ) era, owing to the limitation of quantum hardware coupling constraints, only physically directly connected qubits can realize interaction. For CNOT gates that do not satisfy the coupling conditions, extra SWAP gates need to be inserted to adjust the qubit positions to ensure the executability of the quantum circuit. To reduce the extra overhead due to SWAP gates, this paper proposes a Leveraging Strategy-Driven Quantum Sparrow Search Algorithm (LS-QSSA) and applies it to quantum circuit mapping. LS-QSSA introduces the concept of qubit coupling count, and combines it with the SWAP gate overhead to jointly construct the fitness function. In the individual selection stage, the top 20% of individuals in terms of fitness value are set as “discoverers,” which are able to explore multiple solution space locations at the same time through the introduction of quantum representations, thus expanding the search space. To enhance the capability of escaping local optima, LS-QSSA introduces a Gaussian noise mechanism to perturb the follower positions. Experimental results demonstrate that LS-QSSA achieves an approximate reduction of 36.4% and 47.5% in the quantity of SWAP gates, and around 13.1% and 13.2% in hardware gate count overhead, when compared with the $t\ket{ket}$ and Qiskit compilers, respectively.

The Computer Journal•Jul 24, 2025•0 citations

Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices

Gushu Li, Yufei Ding, Yuan Xie

Due to little considerations in the hardware constraints, e.g., limited connections between physical qubits to enable two-qubit gates, most quantum algorithms cannot be directly executed on the Noisy Intermediate-Scale Quantum (NISQ) devices. Dynamically remapping logical qubits to physical qubits in the compiler is needed to enable the two-qubit gates in the algorithm, which introduces additional operations and inevitably reduces the fidelity of the algorithm. Previous solutions in finding such remapping suffer from high complexity, poor initial mapping quality, and limited flexibility and control. To address these drawbacks mentioned above, this paper proposes a SWAP-based Bidirectional heuristic search algorithm (SABRE), which is applicable to NISQ devices with arbitrary connections between qubits. By optimizing every search attempt, globally optimizing the initial mapping using a novel reverse traversal technique, introducing the decay effect to enable the trade-off between the depth and the number of gates of the entire algorithm, SABRE outperforms the best known algorithm with exponential speedup and comparable or better results on various benchmarks.

arXiv:1809.02573•International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS)•Apr 4, 2019•593 citations

Pre-processing of quantum circuit mapping based on circuit partitioning and unitary matrix decomposition

Kexin Cao, Xueyun Cheng, Xinyu Chen +1 more

Quantum computing is currently in the era of Noisy-Intermediate-Scale Quantum (NISQ), where superconducting quantum chips can only support two-qubit gates between adjacent physical qubits. This constraint necessitates the insertion of SWAP gates during circuit mapping to ensure that the nearest neighbor requirements are met on actual quantum computing devices. In this work, based on the circuit partitioning and unitary matrix decomposition mechanism, an equivalent transformation form of quantum circuit is given to reduce the number of two-qubit gates in the target quantum circuit. Experimental results demonstrate that the decomposed equivalent circuits have a shorter depth, with an average optimization rate of 18.41%. Our proposed optimization method effectively reduces the number of two-qubit gates in quantum circuits, enhancing the efficiency of mapping on NISQ devices.

International Conference on Electronics, Circuits and Information Engineering (ECIE)•May 24, 2024•0 citations
In the Quantum computing era of Noisy Intermediate-Scale Quantum (NISQ) devices, conventional qubit mapping strategies typically rely on specific heuristic rules to solve the mapping problem, overlooking the impact of other factors on the mapping, which leads to increased overhead from extra SWAP gates. To address this issue, we propose a SWAP optimization strategy based on the Centric-Shortest Quantum Gate Set (C-SQGS) and applies it to qubit mapping. In this approach, the centric qubit is determined by analyzing the maximum flexibility qubit set and the physical distances between the associated CNOT gates, leading to the identification of the Centric-Shortest Quantum Gate Set. To overcome the limitations of traditional cost functions that consider only single factors, a multi-factor cost function is introduced to evaluate the overall overhead of candidate SWAP operations and determine pending SWAP gate Set. Based on qubit flexibility analysis, executable SWAP gate is identified and inserted into the circuit. Experimental results demonstrate that the C-SQGS strategy effectively reduces both SWAP gate and two-qubit gate overhead. Specifically, it achieves an average SWAP gate reduction of 36.9% and 47.7%, and a two-qubit gate reduction of 13.8% and 13.5% on the t|ket⟩ and Qiskit compilers, respectively. These results highlight the potential of the C-SQGS strategy in enhancing the efficiency of qubit mapping for NISQ devices.
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.
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.
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.
Abstract In the Noisy Intermediate-Scale Quantum (NISQ) era, owing to the limitation of quantum hardware coupling constraints, only physically directly connected qubits can realize interaction. For CNOT gates that do not satisfy the coupling conditions, extra SWAP gates need to be inserted to adjust the qubit positions to ensure the executability of the quantum circuit. To reduce the extra overhead due to SWAP gates, this paper proposes a Leveraging Strategy-Driven Quantum Sparrow Search Algorithm (LS-QSSA) and applies it to quantum circuit mapping. LS-QSSA introduces the concept of qubit coupling count, and combines it with the SWAP gate overhead to jointly construct the fitness function. In the individual selection stage, the top 20% of individuals in terms of fitness value are set as “discoverers,” which are able to explore multiple solution space locations at the same time through the introduction of quantum representations, thus expanding the search space. To enhance the capability of escaping local optima, LS-QSSA introduces a Gaussian noise mechanism to perturb the follower positions. Experimental results demonstrate that LS-QSSA achieves an approximate reduction of 36.4% and 47.5% in the quantity of SWAP gates, and around 13.1% and 13.2% in hardware gate count overhead, when compared with the t∣ket⟩t\ket{ket}t∣ket⟩ and Qiskit compilers, respectively.
Due to little considerations in the hardware constraints, e.g., limited connections between physical qubits to enable two-qubit gates, most quantum algorithms cannot be directly executed on the Noisy Intermediate-Scale Quantum (NISQ) devices. Dynamically remapping logical qubits to physical qubits in the compiler is needed to enable the two-qubit gates in the algorithm, which introduces additional operations and inevitably reduces the fidelity of the algorithm. Previous solutions in finding such remapping suffer from high complexity, poor initial mapping quality, and limited flexibility and control. To address these drawbacks mentioned above, this paper proposes a SWAP-based Bidirectional heuristic search algorithm (SABRE), which is applicable to NISQ devices with arbitrary connections between qubits. By optimizing every search attempt, globally optimizing the initial mapping using a novel reverse traversal technique, introducing the decay effect to enable the trade-off between the depth and the number of gates of the entire algorithm, SABRE outperforms the best known algorithm with exponential speedup and comparable or better results on various benchmarks.
Quantum computing is currently in the era of Noisy-Intermediate-Scale Quantum (NISQ), where superconducting quantum chips can only support two-qubit gates between adjacent physical qubits. This constraint necessitates the insertion of SWAP gates during circuit mapping to ensure that the nearest neighbor requirements are met on actual quantum computing devices. In this work, based on the circuit partitioning and unitary matrix decomposition mechanism, an equivalent transformation form of quantum circuit is given to reduce the number of two-qubit gates in the target quantum circuit. Experimental results demonstrate that the decomposed equivalent circuits have a shorter depth, with an average optimization rate of 18.41%. Our proposed optimization method effectively reduces the number of two-qubit gates in quantum circuits, enhancing the efficiency of mapping on NISQ devices.