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

Beam search over SWAP sequences on the SABRE benchmark: 82% fewer added gates than SABRE and 29% fewer than the best published routings for IBM Q20 Tokyo, found by an autonomous agent

Harish Santhanalakshmi Ganesan

Published Oct 25, 2026• 0 citations
Publisher

Abstract

Preprint with the routed circuits, verifier and search code. We revisit the qubit-routing benchmark of Li, Ding and Xie (SABRE, ASPLOS 2019): 26 circuits routed onto the 43-edge IBM Q20 Tokyo coupling graph, scored by the number of added gates (three per inserted SWAP). With the same circuits, graph and metric and an exact replay verifier, our routings need 12,087 added gates in total against SABRE's published 68,559 (82% fewer). On identical inputs, Qiskit 2.4.1 SABRE gives 64,137 (default) and 53,418 (heavy trials), and pytket 2.18.5 gives 35,685. On the 15 circuits reported in common by later routing papers on this device, the best published counts (HAIL, 2025) total 13,044 against our 9,312. Our count is lower on every circuit than every method we found (SAHS, MCTS, FiDLS, ILS, TWP, HAIL), with one tie. The routings come from a level-synchronous beam search over SWAP sequences, combined with SABRE-style forward-reverse passes to refine the initial mapping. The search code was written by a language-model agent inside an autonomous discovery loop (about three hours, about 21 USD of model usage). Beam search for routing is not new. The contribution is the measured gap on this widely cited suite, the exactly verifiable routed circuits, and an account of the discovery process. Caveats: far more compute per circuit than the baselines, a metric that ignores depth and fidelity, two regenerated QFT circuits, and the design graph rather than the physical device. Files: the preprint (PDF + LaTeX source, figures, bibliography); the 26 OpenQASM benchmark circuits with the QFT generator; qmap.py (QASM parser, coupling graph, exact replay verifier, SABRE reimplementation); routings/best_combined.json (initial mapping and full operation sequence per circuit) with a per-circuit source map; the baseline script and its output; every proposer run's router code, drivers and notes; SHA-256 sums. Reproduce: python qmap.py verify routings/best_combined.json (prints total_g_add 12087).

DOI
10.5281/zenodo.23651579

Related papers

Graph Reinforcement Learning for Calibration-Aware Quantum Circuit Routing

Yash Vardhan Tomar, Dheeraj Peddireddy

Quantum circuit routing is a key step in compiling programs for noisy intermediate-scale quantum processors, particularly superconducting devices whose sparse fixed coupling makes routing a central compilation cost. Routes that appear efficient by standard overhead metrics such as SWAP count, routed two-qubit count, and depth can still lose fidelity when they pass through poorly calibrated couplers. We study a calibration-aware graph reinforcement-learning router that uses same-day calibration data from superconducting IBM Heron r2 processors to choose hardware-edge SWAPs. We train the policy with proximal policy optimization and evaluate it with exact simulated fidelity across nine Munich Quantum Toolkit (MQT) Bench circuits and three calibration snapshots. Across these evaluations, pooled mean exact fidelity is 0.727, compared with 0.440 for SWAP-based bidirectional heuristic search (SABRE)-best20 and 0.481 for target-aware SABRE. We observe that fidelity gains come with higher routed two-qubit counts and are concentrated in 5 qubit and 8 qubit circuit families; under the fixed tree action graph, all 10 qubit families favor SABRE-best20. Overall, our results show that calibration-aware learned routing can improve fidelity beyond gate-count-driven compilation, by roughly 0.25 to 0.29 in absolute mean fidelity over the SABRE-family baselines.

quant-pharXiv:2606.12816•Jun 12, 2026•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

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

Efficient Qubit Routing Using a Dynamically Extract-and-Route Framework

Ching-Yao Huang, Wai-Kei Mak

In current quantum devices, physical qubits are not fully connected so that two-qubit interaction can only be performed between specific pairs of physical qubits. To execute a quantum circuit, it is necessary to transform it into a functionally equivalent one that respects the constraints imposed by the target architecture. Quantum circuit transformation inevitably introduces additional gates which reduces the fidelity of the circuit. Therefore, it is important that the transformation method completes the transformation with minimal overheads. Quantum circuit transformation consists of two steps, initial mapping and qubit routing, and here we propose a DEAR (Dynamically-Extract-and-Route) framework to solve the qubit routing problem. A key insight of DEAR is that by maintaining a sufficient lookahead ability all the time, we can make much better routing decisions while effectively controlling the runtime. In our DEAR framework, we periodically extract a subcircuit by identifying a set of remaining gates that should be executed earlier than the others, and then applies A* search to determine how to insert a sequence of additional SWAP and BRIDGE operations into the subcircuit to obtain a high quality routing solution with minimum number of additional gates. In this work, we consider the insertion of both SWAP and BRIDGE operations while most previous works deal with SWAP insertion only. We evaluate our approach with four benchmark sets with different characterization on IBM Tokyo. The experimental results show that our approach outperforms the state-of-the-art work utilizing SWAP and BRIDGE insertion with 19.1% and 77.5% average reduction in the number of additional gates and runtime, respectively, starting from the same initial mapping. We also performed experiments on larger quantum devices such as Google Sycamore and IBM Rochester both with 53 physical qubits that have largely different architectures from one another and from IBM Tokyo. Again, DEAR was much faster and required significantly less amount of additional gates.

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Apr 10, 2024•12 citations

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

Chin-Yi Cheng, Chien-Yi Yang, Yi-Hsiang Kuo +3 more

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.

arXiv:2210.01306•ACM Transactions on Quantum Computing•Aug 3, 2024•19 citations

dSABRE: A SABRE-Style Router for Multi-Core Distributed Quantum Computers

Sanjiang Li

Minimising EPR consumption is the dominant objective when routing a quantum circuit on a distributed quantum computer (DQC). We present dSABRE, a SABRE-style router for multi-core processors that, on each iteration of a lookahead-driven loop, first resolves any intra-core front-layer gates by SWAP scoring and only falls back to scoring inter-core teleportation candidates when the intra-core front is empty. Three mechanisms drive the improvement over the state of the art: a five-term gate-centric teleportation score that generalises the local SWAP heuristic to the inter-core setting, whose explicit capacity-penalty term keeps the scorer from teleporting into saturated cores; a proactive congestion-relief pass that redistributes idle qubits out of high-demand cores before deadlock; and a BFS-layer construction of the inter-core extended set that respects DAG dependencies layer by layer rather than mixing wires in topological order. Across 18 MQT-Bench circuits at 25, 36, and 64 logical qubits, dSABRE reduces geometric-mean EPR consumption by 41-44% over TeleSABRE and by 16-68% over the gate-teleportation-based pytket-dqc, using standard Qiskit SabreLayout for the initial layout. A large-circuit QFT sweep at 100-360 qubits confirms scalability. Code and online appendices are available at https://github.com/ebony72/dsabre.

quant-pharXiv:2605.21960•May 22, 2026•0 citations
Preprint with the routed circuits, verifier and search code. We revisit the qubit-routing benchmark of Li, Ding and Xie (SABRE, ASPLOS 2019): 26 circuits routed onto the 43-edge IBM Q20 Tokyo coupling graph, scored by the number of added gates (three per inserted SWAP). With the same circuits, graph and metric and an exact replay verifier, our routings need 12,087 added gates in total against SABRE's published 68,559 (82% fewer). On identical inputs, Qiskit 2.4.1 SABRE gives 64,137 (default) and 53,418 (heavy trials), and pytket 2.18.5 gives 35,685. On the 15 circuits reported in common by later routing papers on this device, the best published counts (HAIL, 2025) total 13,044 against our 9,312. Our count is lower on every circuit than every method we found (SAHS, MCTS, FiDLS, ILS, TWP, HAIL), with one tie. The routings come from a level-synchronous beam search over SWAP sequences, combined with SABRE-style forward-reverse passes to refine the initial mapping. The search code was written by a language-model agent inside an autonomous discovery loop (about three hours, about 21 USD of model usage). Beam search for routing is not new. The contribution is the measured gap on this widely cited suite, the exactly verifiable routed circuits, and an account of the discovery process. Caveats: far more compute per circuit than the baselines, a metric that ignores depth and fidelity, two regenerated QFT circuits, and the design graph rather than the physical device. Files: the preprint (PDF + LaTeX source, figures, bibliography); the 26 OpenQASM benchmark circuits with the QFT generator; qmap.py (QASM parser, coupling graph, exact replay verifier, SABRE reimplementation); routings/best_combined.json (initial mapping and full operation sequence per circuit) with a per-circuit source map; the baseline script and its output; every proposer run's router code, drivers and notes; SHA-256 sums. Reproduce: python qmap.py verify routings/best_combined.json (prints total_g_add 12087).
Quantum circuit routing is a key step in compiling programs for noisy intermediate-scale quantum processors, particularly superconducting devices whose sparse fixed coupling makes routing a central compilation cost. Routes that appear efficient by standard overhead metrics such as SWAP count, routed two-qubit count, and depth can still lose fidelity when they pass through poorly calibrated couplers. We study a calibration-aware graph reinforcement-learning router that uses same-day calibration data from superconducting IBM Heron r2 processors to choose hardware-edge SWAPs. We train the policy with proximal policy optimization and evaluate it with exact simulated fidelity across nine Munich Quantum Toolkit (MQT) Bench circuits and three calibration snapshots. Across these evaluations, pooled mean exact fidelity is 0.727, compared with 0.440 for SWAP-based bidirectional heuristic search (SABRE)-best20 and 0.481 for target-aware SABRE. We observe that fidelity gains come with higher routed two-qubit counts and are concentrated in 5 qubit and 8 qubit circuit families; under the fixed tree action graph, all 10 qubit families favor SABRE-best20. Overall, our results show that calibration-aware learned routing can improve fidelity beyond gate-count-driven compilation, by roughly 0.25 to 0.29 in absolute mean fidelity over the SABRE-family baselines.
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.
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.
In current quantum devices, physical qubits are not fully connected so that two-qubit interaction can only be performed between specific pairs of physical qubits. To execute a quantum circuit, it is necessary to transform it into a functionally equivalent one that respects the constraints imposed by the target architecture. Quantum circuit transformation inevitably introduces additional gates which reduces the fidelity of the circuit. Therefore, it is important that the transformation method completes the transformation with minimal overheads. Quantum circuit transformation consists of two steps, initial mapping and qubit routing, and here we propose a DEAR (Dynamically-Extract-and-Route) framework to solve the qubit routing problem. A key insight of DEAR is that by maintaining a sufficient lookahead ability all the time, we can make much better routing decisions while effectively controlling the runtime. In our DEAR framework, we periodically extract a subcircuit by identifying a set of remaining gates that should be executed earlier than the others, and then applies A* search to determine how to insert a sequence of additional SWAP and BRIDGE operations into the subcircuit to obtain a high quality routing solution with minimum number of additional gates. In this work, we consider the insertion of both SWAP and BRIDGE operations while most previous works deal with SWAP insertion only. We evaluate our approach with four benchmark sets with different characterization on IBM Tokyo. The experimental results show that our approach outperforms the state-of-the-art work utilizing SWAP and BRIDGE insertion with 19.1% and 77.5% average reduction in the number of additional gates and runtime, respectively, starting from the same initial mapping. We also performed experiments on larger quantum devices such as Google Sycamore and IBM Rochester both with 53 physical qubits that have largely different architectures from one another and from IBM Tokyo. Again, DEAR was much faster and required significantly less amount of additional gates.
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⟩|ket\rangle∣ket⟩ , 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⟩|ket\rangle∣ket⟩ , Qiskit, and SABRE, respectively.
Minimising EPR consumption is the dominant objective when routing a quantum circuit on a distributed quantum computer (DQC). We present dSABRE, a SABRE-style router for multi-core processors that, on each iteration of a lookahead-driven loop, first resolves any intra-core front-layer gates by SWAP scoring and only falls back to scoring inter-core teleportation candidates when the intra-core front is empty. Three mechanisms drive the improvement over the state of the art: a five-term gate-centric teleportation score that generalises the local SWAP heuristic to the inter-core setting, whose explicit capacity-penalty term keeps the scorer from teleporting into saturated cores; a proactive congestion-relief pass that redistributes idle qubits out of high-demand cores before deadlock; and a BFS-layer construction of the inter-core extended set that respects DAG dependencies layer by layer rather than mixing wires in topological order. Across 18 MQT-Bench circuits at 25, 36, and 64 logical qubits, dSABRE reduces geometric-mean EPR consumption by 41-44% over TeleSABRE and by 16-68% over the gate-teleportation-based pytket-dqc, using standard Qiskit SabreLayout for the initial layout. A large-circuit QFT sweep at 100-360 qubits confirms scalability. Code and online appendices are available at https://github.com/ebony72/dsabre.