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

arXiv:2210.01306 · ACM Transactions on Quantum Computing

Robust Qubit Mapping Algorithm via Double-Source Optimal Routing on Large Quantum Circuits

Chin-Yi Cheng, Chien-Yi Yang, Yi-Hsiang Kuo, Ren-Chu Wang, Hao–Chung Cheng, Chung-Yang Ric Huang

Published Aug 3, 2024• 19 citations
arXivHTMLPDF

Abstract

Qubit mapping is a critical aspect of implementing quantum circuits on real hardware devices. Currently, the existing algorithms for qubit mapping encounter difficulties when dealing with larger circuit sizes involving hundreds of qubits. In this article, we introduce an innovative qubit mapping algorithm, Duostra, tailored to address the challenge of implementing large-scale quantum circuits on real hardware devices with limited connectivity. Duostra operates by efficiently determining optimal paths for double-qubit gates and inserting SWAP gates accordingly to implement the double-qubit operations on real devices. Together with two heuristic scheduling algorithms, Limitedly Exhaustive Search and Shortest-Path Estimation, it yields results of good quality within a reasonable runtime, thereby striving toward achieving quantum advantage. Experimental results showcase our algorithm’s superiority, especially for large circuits beyond the NISQ era. For example, on large circuits with more than 50 qubits, we can reduce the mapping cost on an average 21.75% over the virtual best results among QMAP, t \(|ket\rangle\) , Qiskit, and SABRE. Besides, for mid-size circuits such as the SABRE-large benchmark, we improve the mapping costs by 4.5%, 5.2%, 16.3%, 20.7%, and 25.7%, when compared to QMAP, TOQM, t \(|ket\rangle\) , Qiskit, and SABRE, respectively.

DOI
10.1145/3680291

Related papers

Single-Qubit Gates Matter for Optimising Quantum Circuit Depth in Qubit Mapping

Sanjiang Li, Ky Dan Nguyen, Zachary Clare +1 more

Quantum circuit transformation (QCT, a.k.a. qubit mapping) is a critical step in quantum circuit compilation. Typically, QCT is achieved by finding an appropriate initial mapping and using SWAP gates to route the qubits such that all connectivity constraints are satisfied. The objective of QCT can be to minimise circuit size or depth. Most existing QCT algorithms prioritise minimising circuit size, potentially overlooking the impact of single-qubit gates on circuit depth. In this paper, we first point out that a single SWAP gate insertion can double the circuit depth, and then propose a simple and effective method that takes into account the impact of single-qubit gates on circuit depth. Our method can be combined with many existing QCT algorithms to optimise circuit depth. The Qiskit SABRE algorithm has been widely accepted as the state-of-the-art algorithm for optimising both circuit size and depth. We demonstrate the effectiveness of our method by embedding it in SABRE, showing that it can reduce circuit depth by up to 50% and 27% on average on, for instance, Google Sycamore and 117 real quantum circuits from MQTBench.

arXiv:2308.00876•Oct 28, 2023•10 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

Improving and benchmarking NISQ qubit routers

Vicente Pina-Canelles, Adrian Auer, Inés de Vega

Quantum computers with a limited qubit connectivity require inserting SWAP gates for qubit routing, which increases gate execution errors and the impact of environmental noise due to an overhead in circuit depth. In this work, we benchmark various routing techniques considering random quantum circuits on one-dimensional and square lattice connectivities, employing both analytical and numerical methods. We introduce circuit fidelity as a comprehensive metric that captures the effects of SWAP and circuit depth overheads. Leveraging a novel approach based on the SABRE algorithm, we achieve up to $84\%$ higher average circuit fidelity for large devices within the NISQ range, compared to previously existing methods. Additionally, our results highlight that the optimal routing choice critically depends on the qubit count and the hardware characteristics, including gate fidelities and coherence times.

arXiv:2502.03908•Feb 6, 2025•0 citations

Exhaustive K-SWAP-sequence search for qubit mapping

Waibel, Jakob

Quantum computing promises to solve certain problems more efficiently than classical computation. Realizing this potential on noisy, intermediate-scale quantum (NISQ) devices remains challenging. Among other things, hardware connectivity constraints necessitate additional routing operations that degrade circuit fidelity. The qubit mapping problem - assigning logical qubits to physical qubits while minimizing inserted SWAP gates - is thus critical in quantum circuit transpilation. Exact methods scale poorly, and heuristic approaches like the SABRE algorithm, though efficient, rely on local decisions that can miss globally optimal solutions. In this thesis, we propose K-SWAP SABRE that integrates bounded exhaustive search over sequences of up to k SWAPs into the SABRE algorithm. A modified heuristic ensures global progress while maintaining comparability between explored branches. Experiments on benchmark circuits show that increasing k reduces required SWAP gates, especially on highly connected devices, though at the cost of longer runtime. Our results demonstrate that K-SWAP SABRE can improve heuristic qubit mapping quality without sacrificing scalability, offering a practical approach for mapping circuits to near-term and emerging quantum architectures.

•Jan 1, 2025•0 citations

A co-optimization qubit mapping algorithm via two-stage search and bidirectional look

Kang Xu, Peian Chen, Yukun Wang +1 more

Abstract Current quantum devices typically lack full qubit connectivity, making it difficult to directly execute logical circuits on quantum devices. This limitation necessitates quantum circuit mapping algorithms to insert SWAP gates, dynamically remapping logical qubits to physical qubits, and transforming logical circuits into physical circuits that comply with device connectivity constraints. However, the insertion of SWAP gates increases both the gate count and circuit depth, ultimately reducing the fidelity of quantum algorithms. To achieve a balanced optimization of these two objectives, we propose the TANGO algorithm. The algorithm first formulates an evaluation function that balances the impact of qubit mapping on both mapped and unmapped nodes is introduced to enhance initial mapping quality, thereby reducing the number of SWAP gates inserted during routing. Next, we design an innovative two-stage routing algorithm that prioritizes the number of executable gates as the primary evaluation metric while also considering quantum gate distance, circuit depth, {and a novel bidirectional-look SWAP strategy}, which optimizes SWAP gate selection in conjunction with preceding gates, improving the effectiveness of the mapping algorithm. Finally, by integrating advanced quantum gate optimization techniques, the algorithm's overall performance is further enhanced. Experimental results demonstrate that, compared to state-of-the-art methods, the proposed algorithm achieves multi-objective co-optimization of gate count and circuit depth across various benchmarks and quantum devices, exhibiting significant performance advantages.

EPJ Quantum Technology•Aug 21, 2026•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
Qubit mapping is a critical aspect of implementing quantum circuits on real hardware devices. Currently, the existing algorithms for qubit mapping encounter difficulties when dealing with larger circuit sizes involving hundreds of qubits. In this article, we introduce an innovative qubit mapping algorithm, Duostra, tailored to address the challenge of implementing large-scale quantum circuits on real hardware devices with limited connectivity. Duostra operates by efficiently determining optimal paths for double-qubit gates and inserting SWAP gates accordingly to implement the double-qubit operations on real devices. Together with two heuristic scheduling algorithms, Limitedly Exhaustive Search and Shortest-Path Estimation, it yields results of good quality within a reasonable runtime, thereby striving toward achieving quantum advantage. Experimental results showcase our algorithm’s superiority, especially for large circuits beyond the NISQ era. For example, on large circuits with more than 50 qubits, we can reduce the mapping cost on an average 21.75% over the virtual best results among QMAP, t (|ket\rangle) , Qiskit, and SABRE. Besides, for mid-size circuits such as the SABRE-large benchmark, we improve the mapping costs by 4.5%, 5.2%, 16.3%, 20.7%, and 25.7%, when compared to QMAP, TOQM, t (|ket\rangle) , Qiskit, and SABRE, respectively.
Quantum circuit transformation (QCT, a.k.a. qubit mapping) is a critical step in quantum circuit compilation. Typically, QCT is achieved by finding an appropriate initial mapping and using SWAP gates to route the qubits such that all connectivity constraints are satisfied. The objective of QCT can be to minimise circuit size or depth. Most existing QCT algorithms prioritise minimising circuit size, potentially overlooking the impact of single-qubit gates on circuit depth. In this paper, we first point out that a single SWAP gate insertion can double the circuit depth, and then propose a simple and effective method that takes into account the impact of single-qubit gates on circuit depth. Our method can be combined with many existing QCT algorithms to optimise circuit depth. The Qiskit SABRE algorithm has been widely accepted as the state-of-the-art algorithm for optimising both circuit size and depth. We demonstrate the effectiveness of our method by embedding it in SABRE, showing that it can reduce circuit depth by up to 50% and 27% on average on, for instance, Google Sycamore and 117 real quantum circuits from MQTBench.
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 computers with a limited qubit connectivity require inserting SWAP gates for qubit routing, which increases gate execution errors and the impact of environmental noise due to an overhead in circuit depth. In this work, we benchmark various routing techniques considering random quantum circuits on one-dimensional and square lattice connectivities, employing both analytical and numerical methods. We introduce circuit fidelity as a comprehensive metric that captures the effects of SWAP and circuit depth overheads. Leveraging a novel approach based on the SABRE algorithm, we achieve up to 84%84\%84% higher average circuit fidelity for large devices within the NISQ range, compared to previously existing methods. Additionally, our results highlight that the optimal routing choice critically depends on the qubit count and the hardware characteristics, including gate fidelities and coherence times.
Quantum computing promises to solve certain problems more efficiently than classical computation. Realizing this potential on noisy, intermediate-scale quantum (NISQ) devices remains challenging. Among other things, hardware connectivity constraints necessitate additional routing operations that degrade circuit fidelity. The qubit mapping problem - assigning logical qubits to physical qubits while minimizing inserted SWAP gates - is thus critical in quantum circuit transpilation. Exact methods scale poorly, and heuristic approaches like the SABRE algorithm, though efficient, rely on local decisions that can miss globally optimal solutions. In this thesis, we propose K-SWAP SABRE that integrates bounded exhaustive search over sequences of up to k SWAPs into the SABRE algorithm. A modified heuristic ensures global progress while maintaining comparability between explored branches. Experiments on benchmark circuits show that increasing k reduces required SWAP gates, especially on highly connected devices, though at the cost of longer runtime. Our results demonstrate that K-SWAP SABRE can improve heuristic qubit mapping quality without sacrificing scalability, offering a practical approach for mapping circuits to near-term and emerging quantum architectures.
Abstract Current quantum devices typically lack full qubit connectivity, making it difficult to directly execute logical circuits on quantum devices. This limitation necessitates quantum circuit mapping algorithms to insert SWAP gates, dynamically remapping logical qubits to physical qubits, and transforming logical circuits into physical circuits that comply with device connectivity constraints. However, the insertion of SWAP gates increases both the gate count and circuit depth, ultimately reducing the fidelity of quantum algorithms. To achieve a balanced optimization of these two objectives, we propose the TANGO algorithm. The algorithm first formulates an evaluation function that balances the impact of qubit mapping on both mapped and unmapped nodes is introduced to enhance initial mapping quality, thereby reducing the number of SWAP gates inserted during routing. Next, we design an innovative two-stage routing algorithm that prioritizes the number of executable gates as the primary evaluation metric while also considering quantum gate distance, circuit depth, {and a novel bidirectional-look SWAP strategy}, which optimizes SWAP gate selection in conjunction with preceding gates, improving the effectiveness of the mapping algorithm. Finally, by integrating advanced quantum gate optimization techniques, the algorithm's overall performance is further enhanced. Experimental results demonstrate that, compared to state-of-the-art methods, the proposed algorithm achieves multi-objective co-optimization of gate count and circuit depth across various benchmarks and quantum devices, exhibiting significant performance advantages.
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.