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

Research on Qubit Mapping Technique Based on Batch SWAP Optimization

Hui Li, Kai Lü, Ziao Han, Huiping Qin, Mingmei Ju, Shujuan Liu

Published Jan 1, 2023• 3 citations
Publisher

Abstract

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.

DOI
10.14569/ijacsa.2023.0141217

Related papers

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

Shujuan Liu, Hui Li, Yingsong Ji +1 more

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.

International Journal of Advanced Computer Science and Applications•Jan 1, 2025•0 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

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

A Beam Search Framework for Quantum Circuit Mapping

Cheng Qiu, Pengcheng Zhu, Lihua Wei

In the era of noisy intermediate-scale quantum (NISQ) computing, the limited connectivity between qubits is one of the common physical limitations faced by current quantum computing devices. Quantum circuit mapping methods transform quantum circuits into equivalent circuits that satisfy physical connectivity constraints by remapping logical qubits, making them executable. The optimization problem of quantum circuit mapping has NP-hard computational complexity, and existing heuristic mapping algorithms still have significant potential for optimization in terms of the number of quantum gates generated. To reduce the number of SWAP gates inserted during mapping, the solution space of the mapping problem is represented as a tree structure, and the mapping process is equivalent to traversing this tree structure. To effectively and efficiently complete the search process, a beam search framework (BSF) is proposed for solving quantum circuit mapping. By iteratively selecting, expanding, and making decisions, high-quality target circuits are generated. Experimental results show that this method can significantly reduce the number of inserted SWAP gates on medium to large circuits, achieving an average reduction of 44% compared to baseline methods, and is applicable to circuits of various sizes and complexities.

Entropy•Feb 24, 2025•1 citation

Towards Fidelity-Optimal Qubit Mapping on NISQ Computers

Sri Khandavilli, Indu Palanisamy, Manh V. Nguyen +3 more

Quantum computing is gaining momentum in revolutionizing the way we approach complex problem-solving. However, the practical implementation of quantum algorithms remains a significant challenge due to the error-prone and hardware limits of near-term quantum devices. For instance, physical qubit connections are limited, which necessitates the use of quantum SWAP gates to dynamically transform the logical topology during execution. In addition, to optimize fidelity, it is essential to ensure that 1) the allocated hardware has a low error rate and 2) the number of SWAP gates injected into the circuit is minimized. To address these challenges, we propose a suite of algorithms: the Fidelity-aware Graph Extraction Algorithm (FGEA) is used to identify the hardware region with the lowest probability of error, the Frequency-based Mapping Algorithm (FMA) allocates logical-physical qubits that reduce the potential distance of topological transformation, and the Heuristic Routing Algorithm (HRA) searches for an optimal swapping injection strategy. We evaluate the proposed algorithms on the IBM-provided Noisy Intermediate-Scale Quantum (NISQ) computer, using a dataset consisting of 17 different quantum circuits of various sizes. The circuits are executed on the IBM Toronto Falcon processor. The three proposed algorithms outperform the existing SABRE algorithm in reducing the number of SWAP gates required. Therefore, our proposed algorithms hold significant promise in enhancing the fidelity and reducing the number of SWAP gates required in implementing Quantum algorithms.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•8 citations

A SAT Approach to the Initial Mapping Problem in SWAP Gate Insertion for Commuting Gates

Atsushi Matsuo, Shigeru Yamashita, Daniel J. Egger

Most quantum circuits require SWAP gate insertion to run on quantum hardware with limited qubit connectivity. A promising SWAP gate insertion method for blocks of commuting two-qubit gates is a predetermined swap strategy which applies layers of SWAP gates simultaneously executable on the coupling map. A good initial mapping for the swap strategy reduces the number of required swap gates. However, even when a circuit consists of commuting gates, e.g., as in the Quantum Approximate Optimization Algorithm (QAOA) or trotterized simulations of Ising Hamiltonians, finding a good initial mapping is a hard problem. We present a SAT-based approach to find good initial mappings for circuits with commuting gates transpiled to the hardware with swap strategies. Our method achieves a 65% reduction in gate count for random three-regular graphs with 500 nodes. In addition, we present a heuristic approach that combines the SAT formulation with a clustering algorithm to reduce large problems to a manageable size. This approach reduces the number of swap layers by 25% compared to both a trivial and random initial mapping for a random three-regular graph with 1000 nodes. Good initial mappings will therefore enable the study of quantum algorithms, such as QAOA and Ising Hamiltonian simulation applied to sparse problems, on noisy quantum hardware with several hundreds of qubits.

arXiv:2212.05666•IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•May 16, 2023•17 citations
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.
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.
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.
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.
In the era of noisy intermediate-scale quantum (NISQ) computing, the limited connectivity between qubits is one of the common physical limitations faced by current quantum computing devices. Quantum circuit mapping methods transform quantum circuits into equivalent circuits that satisfy physical connectivity constraints by remapping logical qubits, making them executable. The optimization problem of quantum circuit mapping has NP-hard computational complexity, and existing heuristic mapping algorithms still have significant potential for optimization in terms of the number of quantum gates generated. To reduce the number of SWAP gates inserted during mapping, the solution space of the mapping problem is represented as a tree structure, and the mapping process is equivalent to traversing this tree structure. To effectively and efficiently complete the search process, a beam search framework (BSF) is proposed for solving quantum circuit mapping. By iteratively selecting, expanding, and making decisions, high-quality target circuits are generated. Experimental results show that this method can significantly reduce the number of inserted SWAP gates on medium to large circuits, achieving an average reduction of 44% compared to baseline methods, and is applicable to circuits of various sizes and complexities.
Quantum computing is gaining momentum in revolutionizing the way we approach complex problem-solving. However, the practical implementation of quantum algorithms remains a significant challenge due to the error-prone and hardware limits of near-term quantum devices. For instance, physical qubit connections are limited, which necessitates the use of quantum SWAP gates to dynamically transform the logical topology during execution. In addition, to optimize fidelity, it is essential to ensure that 1) the allocated hardware has a low error rate and 2) the number of SWAP gates injected into the circuit is minimized. To address these challenges, we propose a suite of algorithms: the Fidelity-aware Graph Extraction Algorithm (FGEA) is used to identify the hardware region with the lowest probability of error, the Frequency-based Mapping Algorithm (FMA) allocates logical-physical qubits that reduce the potential distance of topological transformation, and the Heuristic Routing Algorithm (HRA) searches for an optimal swapping injection strategy. We evaluate the proposed algorithms on the IBM-provided Noisy Intermediate-Scale Quantum (NISQ) computer, using a dataset consisting of 17 different quantum circuits of various sizes. The circuits are executed on the IBM Toronto Falcon processor. The three proposed algorithms outperform the existing SABRE algorithm in reducing the number of SWAP gates required. Therefore, our proposed algorithms hold significant promise in enhancing the fidelity and reducing the number of SWAP gates required in implementing Quantum algorithms.
Most quantum circuits require SWAP gate insertion to run on quantum hardware with limited qubit connectivity. A promising SWAP gate insertion method for blocks of commuting two-qubit gates is a predetermined swap strategy which applies layers of SWAP gates simultaneously executable on the coupling map. A good initial mapping for the swap strategy reduces the number of required swap gates. However, even when a circuit consists of commuting gates, e.g., as in the Quantum Approximate Optimization Algorithm (QAOA) or trotterized simulations of Ising Hamiltonians, finding a good initial mapping is a hard problem. We present a SAT-based approach to find good initial mappings for circuits with commuting gates transpiled to the hardware with swap strategies. Our method achieves a 65% reduction in gate count for random three-regular graphs with 500 nodes. In addition, we present a heuristic approach that combines the SAT formulation with a clustering algorithm to reduce large problems to a manageable size. This approach reduces the number of swap layers by 25% compared to both a trivial and random initial mapping for a random three-regular graph with 1000 nodes. Good initial mappings will therefore enable the study of quantum algorithms, such as QAOA and Ising Hamiltonian simulation applied to sparse problems, on noisy quantum hardware with several hundreds of qubits.