# QAP-Router: Tackling Qubit Routing as Dynamic Quadratic Assignment with Reinforcement Learning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Quantum reinforcement learning, one of 15 directions in Deep reinforcement learning methods.
- Builds on 28 of its 71 references that are in the map.
- First posted on arXiv 12 May 2026.

## Placed in

- Deep reinforcement learning methods / [Quantum reinforcement learning](https://mlsanity.com/deeprl/quantum-reinforcement-learning/)

## Builds on (most cited first, 28 of 28)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Parameterized quantum circuits as machine learning models](https://mlsanity.com/paper/1906.07682/) (2019)
- [Ising formulations of many NP problems](https://mlsanity.com/paper/1302.5843/) (2013)
- [Challenges and Opportunities in Quantum Machine Learning](https://mlsanity.com/paper/2303.09491/) (2023)
- [Neural Graph Matching Network: Learning Lawler's Quadratic Assignment Problem with Extension to Hypergraph and Multiple-graph Matching](https://mlsanity.com/paper/1911.11308/) (2019)
- [Challenges and Opportunities in Quantum Optimization](https://mlsanity.com/paper/2312.02279/) (2023)
- [Noise-Adaptive Compiler Mappings for Noisy Intermediate-Scale Quantum Computers](https://mlsanity.com/paper/1901.11054/) (2019)
- [Practical and efficient quantum circuit synthesis and transpiling with Reinforcement Learning](https://mlsanity.com/paper/2405.13196/) (2024)
- [Agent-Q: Fine-Tuning Large Language Models for Quantum Circuit Generation and Optimization](https://mlsanity.com/paper/2504.11109/) (2025)
- [On the qubit routing problem](https://mlsanity.com/paper/1902.08091/) (2019)
- [Revocable Deep Reinforcement Learning with Affinity Regularization for Outlier-Robust Graph Matching](https://mlsanity.com/paper/2012.08950/) (2020)
- [Exponential quantum advantage in processing massive classical data](https://mlsanity.com/paper/2604.07639/) (2026)
- [Qubit Routing using Graph Neural Network aided Monte Carlo Tree Search](https://mlsanity.com/paper/2104.01992/) (2021)
- [Qubit Mapping and Routing via MaxSAT](https://mlsanity.com/paper/2208.13679/) (2022)
- [Quantum Circuit Synthesis and Compilation Optimization: Overview and Prospects](https://mlsanity.com/paper/2407.00736/) (2024)
- [AlphaRouter: Quantum Circuit Routing with Reinforcement Learning and Tree Search](https://mlsanity.com/paper/2410.05115/) (2024)
- [Optimality Study of Existing Quantum Computing Layout Synthesis Tools](https://mlsanity.com/paper/2002.09783/) (2020)
- [A Hardware-Aware Heuristic for the Qubit Mapping Problem in the NISQ Era](https://mlsanity.com/paper/2010.03397/) (2020)
- [Algorithmic Theory of Qubit Routing](https://mlsanity.com/paper/2305.02059/) (2023)
- [Learning Solution-Aware Transformers for Efficiently Solving Quadratic Assignment Problem](https://mlsanity.com/paper/2406.09899/) (2024)
- [Better Process Mapping and Sparse Quadratic Assignment](https://mlsanity.com/paper/1702.04164/) (2017)
- [An Open-Source, Industrial-Strength Optimizing Compiler for Quantum Programs](https://mlsanity.com/paper/2003.13961/) (2020)
- [Generating Compilers for Qubit Mapping and Routing](https://mlsanity.com/paper/2508.10781/) (2025)
- [Solving the Quadratic Assignment Problem using Deep Reinforcement Learning](https://mlsanity.com/paper/2310.01604/) (2023)

## Abstract (arXiv)

Qubit routing is a fundamental problem in quantum compilation, known to be NP-hard. Its dynamic nature makes local routing decisions propagate and compound over time, making global efficient solutions challenging. Existing heuristic methods rely on local rules with limited lookahead, while recent learning-based approaches often treat routing as a generic sequential decision problem without fully exploiting its underlying structure. In this paper, we introduce QAP-Router, framing qubit routing based on a dynamic Quadratic Assignment Problem (QAP) formulation. By modeling logical interactions, or quantum gates, as flow matrices and hardware topology as a distance matrix, our approach captures the interaction-distance coupling in a unified objective, which defines the reward in the reinforcement learning environment. To further exploit this structure, the policy network employs a solution-aware Transformer backbone that encodes the interaction between the flow matrix and the distance matrix into the attention mechanism. We also integrate a lookahead mechanism that blends naturally into the QAP framework, preventing myopic decisions. Extensive experiments on 1,831 real-world quantum circuits from the MQTBench, AgentQ and QUEKO datasets show that our method substantially reduces the CNOT gate count of routed circuits by 15.7%, 30.4% and 12.1%, respectively, relative to existing industry compilers.