# Algorithmic Theory of Qubit Routing

arXiv: https://arxiv.org/abs/2305.02059 · HTML: https://mlsanity.com/paper/2305.02059/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 May 2023.

## Built on by (most cited first, 4 of 4)

- [Quantum computing and artificial intelligence: status and perspectives](https://mlsanity.com/paper/2505.23860/) (2025)
- [qgym: A Gym for Training and Benchmarking RL-Based Quantum Compilation](https://mlsanity.com/paper/2308.02536/) (2023)
- [QAP-Router: Tackling Qubit Routing as Dynamic Quadratic Assignment with Reinforcement Learning](https://mlsanity.com/paper/2605.12365/) (2026)
- [Position: Quantum Program Generation Must Prioritize Validity Over Probabilistic Scaling](https://mlsanity.com/paper/2607.15313/) (2026)

## Abstract (arXiv)

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 give a fixed-parameter algorithm when the number of two-qubit gates is a parameter. (3) We give a polynomial-time algorithm when each qubit is involved in at most one two-qubit gate.