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

Communications in computer and information science

Nested Qubit Routing

Harshit Dhankhar, Tristan Cazenave

Published Jan 1, 2026• 1 citation
Publisher
DOI
10.1007/978-3-032-15931-1_6

Related papers

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

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

Qubit Routing via swap Network: A Minimum Dominating Path Approach

Riccardo Romanello, Daniele Lizzio Bosco, Giuseppe Serra +1 more

Lecture notes in computer science•Jan 1, 2026•0 citations

A doubly stochastic matrices-based approach to optimal qubit routing

Nicola Mariella, Sergiy M. Zhuk

arXiv:2211.07222•Quantum Information Processing•Jun 29, 2023•4 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

Algorithmic Theory of Qubit Routing in the Linear Nearest Neighbor Architectures

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama +2 more

The qubit routing problem, also known as the swap minimization problem, is a (classical) combinatorial optimization problem that arises in the design of compilers of quantum programs. We study the qubit routing problem from the viewpoint of theoretical computer science, while most of the existing studies investigated the practical aspects. We concentrate on the linear nearest neighbor (LNN) architectures of quantum computers, in which the graph topology is a path. Our results are three-fold. (1) We prove that the qubit routing problem is NP-hard. (2) We show that the qubit routing problem on a path can be solved in a fixed-parameter time where the number of two-qubit gates is a parameter. (3) We show that the qubit routing problem on a path can be solved in polynomial time if each qubit is involved in at most one two-qubit gate.

ACM Transactions on Quantum Computing•Mar 8, 2025•2 citations
The qubit routing problem, also known as the swap minimization problem, is a (classical) combinatorial optimization problem that arises in the design of compilers of quantum programs. We study the qubit routing problem from the viewpoint of theoretical computer science, while most of the existing studies investigated the practical aspects. We concentrate on the linear nearest neighbor (LNN) architectures of quantum computers, in which the graph topology is a path. Our results are three-fold. (1) We prove that the qubit routing problem is NP-hard. (2) We show that the qubit routing problem on a path can be solved in a fixed-parameter time where the number of two-qubit gates is a parameter. (3) We show that the qubit routing problem on a path can be solved in polynomial time if each qubit is involved in at most one two-qubit gate.