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

Lecture notes in computer science

Qubit Routing via swap Network: A Minimum Dominating Path Approach

Riccardo Romanello, Daniele Lizzio Bosco, Giuseppe Serra, Carla Piazza

Published Jan 1, 2026• 0 citations
Publisher
DOI
10.1007/978-3-032-29921-5_5

Related papers

Parallel token swapping for qubit routing

Ishan Bansal, Oktay Günlük, Richard Shapley

arXiv:2411.18581•Discrete Applied Mathematics•Aug 18, 2025•2 citations

A Neutral-Atom Quantum Compiler with Application-Specific Layout and Hub-Assisted Shuttling

Takahiko Satoh, Takaharu Yoshida

Compiling arbitrary-connectivity NISQ circuits onto monolithic single-zone neutral-atom devices is constrained by a finite interaction range and a minimum separation between simultaneously addressable sites. Under the minimum-separation constraint, the SWAP-only configuration of our pipeline does not return a schedule within a practical time budget on a range of circuits, including circuits as small as nine qubits. We address this with hub traps, a small number of dynamically placed empty traps that serve as transit waypoints, together with a per-gate rule that chooses between SWAP-based routing and hub-mediated shuttling. We evaluate the compiler on seventeen benchmarks using analytic estimates of execution time and a per-layer fidelity proxy, comparing against a placement-matched baseline and against ablations of our own pipeline. Hub traps make these otherwise-unsolved circuits compile in seconds to minutes and remove SWAP gates entirely on every completed circuit, so their role is to enable routing rather than only to optimize fidelity. The benefit is concentrated on routing-dominated circuits and is absent on routing-free ones, which we separate by the structure of the interaction graph. On the most routing-dominated circuit the fidelity proxy improves by up to three orders of magnitude over the placement-matched baseline. The gain comes primarily from eliminating SWAP overhead, as the absolute fidelities there remain low.

quant-pharXiv:2605.29964•May 29, 2026•0 citations

Algorithmic Theory of Qubit Routing

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama +2 more

arXiv:2305.02059•Lecture notes in computer science•Jan 1, 2023•18 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•42 citations

Routing in a quantum network

William J. Munro, Nicoló Lo Piparo, Michael Hanks +1 more

Bulletin of the American Physical Society•Mar 5, 2020•0 citations

Nested Qubit Routing

Harshit Dhankhar, Tristan Cazenave

Communications in computer and information science•Jan 1, 2026•1 citation
Compiling arbitrary-connectivity NISQ circuits onto monolithic single-zone neutral-atom devices is constrained by a finite interaction range and a minimum separation between simultaneously addressable sites. Under the minimum-separation constraint, the SWAP-only configuration of our pipeline does not return a schedule within a practical time budget on a range of circuits, including circuits as small as nine qubits. We address this with hub traps, a small number of dynamically placed empty traps that serve as transit waypoints, together with a per-gate rule that chooses between SWAP-based routing and hub-mediated shuttling. We evaluate the compiler on seventeen benchmarks using analytic estimates of execution time and a per-layer fidelity proxy, comparing against a placement-matched baseline and against ablations of our own pipeline. Hub traps make these otherwise-unsolved circuits compile in seconds to minutes and remove SWAP gates entirely on every completed circuit, so their role is to enable routing rather than only to optimize fidelity. The benefit is concentrated on routing-dominated circuits and is absent on routing-free ones, which we separate by the structure of the interaction graph. On the most routing-dominated circuit the fidelity proxy improves by up to three orders of magnitude over the placement-matched baseline. The gain comes primarily from eliminating SWAP overhead, as the absolute fidelities there remain low.
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.