QAP-Router: Tackling Qubit Routing as Dynamic Quadratic Assignment with Reinforcement Learning
arXiv:2605.12365v1 [quant-ph] 12 May 2026
1
Kien X. Nguyen1,2 , Ankit Kulshrestha2 , Ilya Safro1 , Xiaoyuan Liu2 Department of Computer and Information Sciences, University of Delaware, USA 2 Quantum Lab, Fujitsu Research of America, USA {kxnguyen,isafro}@udel.edu, {akulshrestha,xliu}@fujitsu.com
Abstract Qubit routing is a fundamental problem in quantum compilation, known to be NPhard. 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.
1
Introduction
Quantum computing has seen tremendous progress over the past decade due to its vast potential applications, such as security [51, 37], optimization [16, 1], network science [58], machine learning [8, 11, 73, 74], and finance [21]. These advances have enabled the execution of small- to medium-scale quantum circuits on real quantum hardware, which is now referred to as noisy intermediate-scale quantum (NISQ) systems. For instance, in 2023, IBM demonstrated that its 127-qubit Eagle processor can execute quantum circuits beyond the reach of classical exact simulation, marking a milestone towards quantum utility [32, 33]. In 2025, Fujitsu and RIKEN developed a 256-qubit superconducting quantum computer, marking a significant step towards large-scale quantum systems [38]. Despite this progress, the current NISQ hardware, containing tens to a few hundred qubits, remains highly constrained. They often support only a restricted set of native gates and have limited qubit connectivity, so arbitrary qubit pairs cannot directly interact. Therefore, quantum algorithms must be transformed into equivalent circuits that comply with device constraints through a process known as quantum compilation [42, 71]. This process contains two phases: (i) circuit synthesis and optimization, and (ii) qubit mapping and routing (Figure 1). In the first phase, a high-level quantum algorithm is translated into a gate-level circuit over the native instruction set of the target hardware, while compiler optimizations reduce depth and gate count [76, 36, 61, 31]. In the second phase, the logical circuit is compiled to the device constraints; qubit mapping creates an initial logical-to-physical Preprint.
Logical Circuit Synthesis Logical Circuit Optimization
Quantum Algorithm
Logical Circuit single-qubit quantum gate
Qubit Mapping Qubit Routing
two-qubit quantum gate physical qubit
Executable Program
Physical Quantum Device
SWAP gate
Figure 1: Overview of the quantum compilation pipeline. A quantum algorithm, expressed as a sequence of unitary transformations, is first translated into a logical circuit via circuit synthesis and optimization. Then, to execute the logical circuit on a target quantum device, qubit mapping determines an initial assignment of logical to physical qubits, followed by qubit routing that inserts SWAP operators to enable the execution of all two-qubit gates under the connectivity constraints.
assignment, and qubit routing inserts additional operations, such as SWAP gates, to make all twoqubit gates executable under the device connectivity [13, 47, 67]. Moreover, quantum operations are inherently noisy due to hardware imperfections and environmental disturbances that cause gate errors, decoherence, and readout noise. Therefore, it is crucial to keep circuits as shallow as possible by minimizing the number of inserted SWAP operations, which increase depth and accumulated errors. In this paper, we focus on qubit routing on superconducting quantum devices, an NP-hard problem [28], with the assumption that an initial mapping is given. Recent work includes classical optimization methods and machine learning based approaches. Classical methods include exact solutions [60], heuristics [76, 13, 36, 75, 4], and reduction [46, 45] to construct efficient mapping and routing strategies. In contrast, machine learning approaches aim to learn a general routing policy that can be generalized across circuits and device topologies, typically by means of reinforcement learning and learned heuristics [20, 23, 52, 59, 66, 33]. However, existing approaches to qubit routing remain limited in their ability to produce globally efficient compilations. In practice, routing decisions are often guided by heuristic objectives with limited lookahead, which can improve executability at the current stage of the circuit but may still introduce overhead. As a result, qubit routing is rarely performed as an isolated step; instead, it is commonly interleaved with further compilation procedures that refine the circuit, adjust the mapping, or reduce the overhead introduced during routing [76, 36, 33]. To this end, we exploit the inherent structure of the qubit routing problem by framing it as a dynamic global assignment task, where the logical circuit induces structured interactions, and the device topology defines communication costs. Specifically, we propose a formulation of qubit routing based on the Quadratic Assignment Problem (QAP) [34, 35] and use its objective to define the reward function in our reinforcement learning framework. By representing logical qubit interactions as a flow matrix and hardware connectivity as a distance matrix, our approach directly optimizes the alignment between circuit structure and device topology, which we incorporate into the learning objective. Furthermore, our policy network captures this interaction–distance coupling through a solution-aware Transformer encoder that jointly encodes flow-based interactions and topology-aware distances within the attention mechanism. [65]. This provides a principled foundation that strikes a good balance between optimization and learning, facilitating globally informed routing strategies. Finally, we evaluate our approach on realistic quantum circuits against state-of-the-art qubit compilers and show that it achieves up to 15.7% reduction on the MQTBench dataset [53], 30.4% reduction on AgentQ dataset [30], and 12.1% reduction on QUEKO dataset [64] in CNOT gate count, in comparison to existing approaches. In summary, our contributions are threefold: 2
1. We introduce QAP-Router, framing qubit routing as a dynamic QAP and incorporating its objective into the reward function of our reinforcement learning framework. 2. We design a solution-aware state encoder based on a Transformer backbone, which integrates the interaction between the flow matrix and the distance matrix into the attention mechanism. 3. We train our method on randomly generated circuits and evaluate it on realistic benchmark circuits against existing commercial quantum compilers, showing that it achieves improved routing performance on three different datasets.
2
Background and Motivation
2.1
Quadratic Assignment Problem
The Quadratic Assignment Problem (QAP) involves N facilities and M locations [34, 35]. A distance is specified for each pair of locations, and a weight (or flow) is specified for each pair of facilities. The goal is to assign all facilities to locations so that the sum of distances multiplied by the corresponding flow is minimized. Let X ∈ RN ×M be the permutation matrix, F ∈ RN ×N be the flow matrix, and D ∈ RM ×M be the distance matrix. The objective function of QAP is min Tr(F · X · D · X ⊤ ), X X X s.t. X ij = 1, ∀j, X ij = 1, i
(1) ∀i,
X ij ∈ {0, 1},
(2)
j
where Tr(·) denotes the trace of a matrix. QAP has been studied extensively in the High-Performance Computing (HPC) field [22, 63, 57]. In this work, we draw inspiration from the topology-aware process mapping in HPC, where the goal is to assign communicating processes (facilities) to physical processors (locations) so that frequently communicating processes are placed close to each other in the machine topology. This is analogous to our qubit routing setting, where logical qubits play the role of communicating processes and physical qubits are the physical processors. The main distinction is that HPC process mapping is often static, whereas qubit routing is dynamic, as the mapping changes over time through SWAP actions, and the interaction matrix evolves as gates are executed and cleared. This motivates framing our problem to a dynamic QAP framework.
Before SWAP: After SWAP:
Logical circuit divided into multiple time slices
Before SWAP: After SWAP:
Current assignment on the physical device before time slice
Figure 2: Motivation for integration of QAP objective to the reward function. At time slice t = 2, we aim to schedule gate (q2 , q3 ) by making q2 and q3 adjacent on the device. We compare two actions SWAP(q2 , q6 ) (green) and SWAP(q2 , q4 ) (red) that result in two reward values. In the former case, the action minimizes the distance between q2 and q3 , yielding a positive reward, while the latter case does not change the distance remains unchanged.
3
2.2
Qubit Routing as a Dynamic QAP Framework
We adapt the qubit routing problem to the dynamic QAP framework, which can be defined as min
X 1 ,...,X T
s.t.
X i
T X
Tr(F t · X t · D · X ⊤ t ),
(3)
t
X t,ij = 1,
∀j, t,
X
X t,ij = 1,
∀i, t
X t,ij ∈ {0, 1},
(4)
j
where X t denotes the assignment of logical qubits to physical qubits at the time step t, F t is the flow matrix encoding logical qubit interactions at time t, and D is the distance matrix derived from the hardware coupling graph. A quantum circuit Ξ can be modeled by a Directed Acyclic Graph (DAG), where the nodes correspond to two-qubit gates and the edges represent dependencies between gates. By partitioning the DAG depthwise according to qubit interaction dependencies, we obtain a sequence of time slices {ξt }Tt=1 , where each depth level corresponds to a slice ξt , consisting of parallel two-qubit gates acting on disjoint qubits (single-qubit gates are omitted). Formally, we denote the circuit as Ξ = {ξt }Tt=1 . Each slice can be formulated as an individual QAP problem. At each time step t, the permutation X t determines the physical placement of the logical qubits, and the objective encourages frequently interacting qubits to be mapped to nearby physical nodes (Figure 2). Unlike static QAP, the assignments evolve over time, starting from X 0 , and updated through a sequence of routing operations (e.g. SWAP gates), which transition X t to X t+1 . As a result, the sequential decision process naturally facilitates a reinforcement learning framework, where each action corresponds to a SWAP operation that updates the permutation matrix.
3
Method
In this section, we present our reinforcement learning framework for qubit routing. We first define the environment, including the observation space, action space, and reward function. We then describe the state space encoding procedure within the policy network. 3.1
Reinforcement Learning Environment
Framing the qubit routing problem as reinforcement learning involves defining an observation space and an action space, and designing a proper reward function. Observation space. The observation space encapsulates the following information: 1. The current mapping of logical qubits to physical nodes, or X τ ∈ {0, 1}NQ ×NP . 2. The current logical interaction graph representing the current time slice t, or F τ ∈ RNQ ×NQ . H×NQ ×NQ 3. A series of future time slices of H look-ahead horizon, or {F τ +h }H . h=1 ∈ R P ×NP 4. The distance matrix of the device graph, or D ∈ RN . ≥0
Action space. We partition the circuit Ξ into T time slices and define a maximum J number of steps for each slice t during the rollout. In other words, we index the environment time step as a tuple τ = (t, j), where t ∈ {1, . . . , T } denotes the current circuit slice and j ∈ {1, . . . , J} denotes the routing step within that slice. The action space A is defined as the set of edges in the physical device, and |A| is the number of actions. At any timestep τ , an action aτ = (u, v) ∈ A indicates a SWAP on the physical device edge (u, v), with u ̸= v; u, v ∈ {1, . . . , NP }. As a result, the observation is updated by applying the selected SWAP action, X τ +1 = X τ S uv , where S uv denotes the permutation matrix for the transposition (u, v), i.e., the identity matrix with columns u and v exchanged. Furthermore, the environment immediately schedules any two-qubit gates whose qubits become adjacent on the device, immediately removing them from the circuit. In particular, at each routing step j in slice t, given the current state sτ = (X τ , F τ , F τ +1:τ +H ; D), we take an action aτ = (u, v) and update the current permutation X τ as X t,j+1 = X t,j S uv and the 4
interaction graph F τ as follows. Let Gτ ⊂ {(qu , qv ) : 1 ≤ qu < qv ≤ NQ } be the set of executable two-qubit gates after taking action aτ . We then define a symmetric gate clearing mask X ⊤ NQ ×NQ Mτ = (equ e⊤ , diag(M τ ) = 0, (5) qv + eqv equ ) ∈ {0, 1} (qi ,qj )∈Gτ
where ei ∈ RNQ is the i-th standard basis vector, and update the interaction graph F τ as F t,j+1 = F k,j if Gt,j = ∅, F t,j+1 = F t,j ⊙ (1 − M t,j ) otherwise, where ⊙ denotes the element-wise multiplication (or Hadamard product). Reward function. Given the current permutation X t,j , the current interaction graph F t,j and the new permutation X t,j+1 and the new interaction graph F t,j+1 after taking action at,j , we shape the reward signal based on the QAP objective OQAP (X, F , D) = Tr(F · X · D · X ⊤ ), and define the QAP reward term as follows: rQAP = OQAP (X t,j , F t,j , D) − OQAP (X t,j+1 , F t,j+1 , D)
(6)
The intuition for the subtraction in the QAP term is that OQAP is a minimization objective, so if the flow F t,j+1 after taking the action at,j yields a lower (better) objective value than F t,j , then the term results in a positive reward. Since the ultimate objective is to minimize the number of SWAP operations inserted into the circuit, we include a negative constant β that encourages the policy to take as few actions as possible. Lastly, we include a reward for actions that successfully schedule any two-qubit gates proportional to |G|. The final reward function at time step τ = (t, j) is rτ = λQAP · rQAP + λswap · β + λgate · |Gτ |,
(7)
where λQAP , λswap and λgate are the balancing coefficients. To balance the immediate benefit of reducing SWAP overhead in the current time slice against the need to preserve favorable qubit placements for upcoming interactions, we further incorporate a look-ahead mechanism by aggregating future time slices into a decay-weighted effective flow for the QAP term, so that near-term interactions are prioritized while upcoming constraints remain visible. The combined effective flow matrix is: F̂ t,j =
H X
γ h F t+h ,
0<γ<1
(8)
h=0
This formulation enables the assignment at timestep τ to be optimized primarily for the current slice t, while remaining aware of imminent interactions in future slices. As a result, the routing strategy favors placements that are immediately effective but do not incur unnecessary overhead when executing upcoming gates, thus balancing short-term optimality with forward-looking consistency. 3.2
State Space Encoding
The observation space exposes the information required for near-optimal swap decisions while preserving the Markov property of the underlying decision process. It provides (i) the current logical to physical assignment, (ii) the current and look-ahead interaction graphs, and (iii) the hardware topology, as mentioned above. In this section, we describe how the components in the state space are encoded in the policy network. There are three modules: a logical qubit encoder and a physical node encoder, both of which are followed by a QAP-aware mixed attention Transformer layer [68] that fuses the logical qubit and physical node embeddings, and projects it to the logical space. 3.2.1
Logical Qubit Encoder
We begin by describing the logical qubit encoder, which extracts representations of logical qubits based on their interaction structure in the circuit. To encode individual qubits, we assign each qubit a unique identifier via a one-hot encoding. Each logical qubit i ∈ {1, . . . , NQ } is assigned a one–hot vector E i ∈ RNQ ; stacking {E i } yields E = I NQ . The initial qubit features are obtained by a learned projection W E ∈ RNQ ×d , Z (0) = E W E ∈ RNQ ×d , where d is the hidden dimension. 5
a) Logical circuit to flow matrices conversion
...
...
Convert to flow matrices
Look-ahead horizon of logical qubit interactions
b) State space encoding pipeline
Initial qubit embedding
Encoder
Combine
Concat
Logical Qubit Encoder Decay-weighted
Solution Aware Transformer
flow matrix Device distance matrix
Decoder
Policy Head
Value Head
Physical Device Encoder
Current assignment ...
Figure 3: Logical circuit to flow matrices conversion procedure and state space encoding pipeline. (a) A circuit is first divided into a sequence of time slices {ξt }Tt=1 , where each slice contain parallelized two-qubit gates (single-qubit gates are omitted). Each slice is then converted to a flow matrix that encode the qubit interactions, yielding {F t }Tt=1 . (b) The encoding procedure contains a logical qubit encoder that extracts the logical qubit features Z logical via an attention mechanism scaled by a decay-weighted effective flow matrix F̂ t . A physical device encoder extracts the physical node features Z physical governed by the distance matrix D and the current assignment X t . Z logical and Z physical are then concatenated and fed into a solution-aware transformer whose attention matrix is scaled by the QAP objective F̂ t · D. The resulting context vector Z fuse is passed to the policy head πθ and value head Vϕ . N ×N
Flow–aware multi–head attention. Let F ∈ R≥0Q Q denote the symmetric zero–diagonal flow matrix of an arbitrary time slice. We perform message passing using a mixed-attention Transformer block whose attention is scaled by F τ , so that qubits with pending interactions attend to each other. For layer ℓ with h heads and head width dk , we define the query, key and value as Qh = Z (ℓ) W Q,h ,
K h = Z (ℓ) W K,h ,
V h = Z (ℓ) W V,h ,
W (·),h ∈ RH×dk . (9) The head outputs are calculated using the standard Transformer attention Attnh Z (ℓ) , B , where B is the scaling matrix and B := F τ . The multi–head aggregation follows the standard concatenation and then projection procedure. We then apply a residual connection and a position–wise feed–forward network (FFN): (ℓ) (ℓ) (ℓ) Z̃ = Z (ℓ) + MHA LN Z (ℓ) ; F τ , Z (ℓ+1) = Z̃ + FFN LN Z̃ , (10) where MHA denotes multi-head attention and LN denotes layer normalization [3]. The final logical embedding is Z logical = LN Z (L) ∈ RNQ ×d . (11) Look–ahead integration. With look–ahead enabled, F τ is replaced by a decay–weighted aggregate F̂ τ similar to Eq. (8), which preserves the same formulation and places greater emphasis on near-term interactions while retaining awareness of future ones. 3.2.2
Physical Qubit Encoder
The hardware’s physical qubits, referred to as nodes, are specified by the set of physical coordinates φ ∈ RNP ×2 , φi ∈ [0, 1] and the current logical-to-physical assignment X τ ∈ {0, 1}NQ ×NP . The physical qubit encoder first projects the physical coordinates in logical order, Πτ = X τ φ ∈ RNQ ×2 , so that the row i contains the (x, y) location of the logical qubit i on the device at an arbitrary time step. From Πτ and the device coupling graph G, we construct a distance matrix based on the 6
shortest-path distances over G: ∆τ ij = D Πτ i , Πτ j ,
N ×NQ
∆τ ∈ R≥0Q
,
(12)
¯ τ ∈ RNQ ×NQ . ∆ ≥0
(13)
with a symmetric row-sum normalization employed, 1
1
¯ τ = diag(∆τ 1)− 2 ∆τ diag(∆τ 1)− 2 , ∆
The initial node features are obtained by projecting coordinates to the hidden vector Z (0) = NQ ×d Π W proj + 1 b⊤ , followed by a small stack of kernel-weighted residual layers: proj ∈ R ¯ τ Z (ℓ) W ℓ + 1b⊤ Z (ℓ+1) = Z (ℓ) + σ ∆ , (14) ℓ where W ℓ ∈ Rd×d , bℓ ∈ Rd are learned, and σ is an activation function, e.g. ReLU [2]. After L layers, the final physical node embedding is Z physical = Z (L) ∈ RNQ ×d . 3.2.3
QAP-aware Fusion Layer
After getting the final logical qubit, Z logical , and physical embedding, Z physical , we concatenate them and fuse the resulting representation using a feed-forward layer. Z fuse = FFN([Z logical , Z physical ]) ∈ RNQ ×d
(15)
We then apply a mixed-attention Transformer layer, where the attention Attnh Z (ℓ) , B is scaled by the QAP objective matrix formed by the flow matrix F τ and the distance matrix D , with B := F τ · D. The fused representation Z fuse is then fed into separate policy and value heads, which parameterize a stochastic policy πθ (a|s) and a value function Vϕ (s), respectively.
4
Experimental Results
4.1
Experiment Setting
Evaluation metrics. In this paper, we focus purely on the qubit routing task by inserting SWAPs into the quantum circuit to make the logical circuit executable on physical hardware. In the reinforcement learning setting, this corresponds to the number of steps taken in the environment before all gates in the circuit are successfully scheduled. However, the quantum compilation baselines we compare against may incorporate additional transformations prior to or during routing, such as the use of BRIDGE operations. For example, circuit synthesis techniques may introduce additional CNOT gates to effectively relabel qubits or restructure the circuit, thereby reducing routing difficulty at the cost of modifying the original computation [33] . Similarly, BRIDGE operations can replace SWAP sequences with alternative gate constructions that exploit intermediate qubits, trading off gate count and depth in different ways [13]. Although these techniques can improve overall compilation performance, the distinction between qubit routing and circuit synthesis can become ambiguous. To ensure a fair and consistent comparison focused on routing efficiency, we evaluate all methods based on the number of additional two-qubit gates introduced during compilation. In particular, we use the number of added CNOT gates as our primary metric, as it captures both SWAP and BRIDGE overhead, as well as any auxiliary two-qubit operations introduced by alternative compilation strategies. In brevity, a SWAP gate can be decomposed into 3 consecutive CNOT gates, and a BRIDGE equals 4 CNOT gates. Datasets. To evaluate our method, we adopt two realistic benchmarks: (i) MQTBench dataset [53], or the Munich Quantum Toolkit Benchmark Library, a widely used collection of quantum circuits for quantum compilation. The dataset includes circuits from a diverse range of algorithms, such as the quantum Fourier transform and the quantum approximate optimization algorithm. The number of qubits ranges from 2 to 50, with circuit sizes reaching up to 1640 gates. (ii) AgentQ dataset [30], a collection of 14000 optimized quantum circuits for 12 different combinatorial optimization problems. (iii) QUEKO dataset [64], a dataset designed for the qubit mapping task; we focus on the QAOAMaxCut instances. We select circuits with 12, 16 and 20 qubits. To focus exclusively on the routing 7
Table 1: The average number of inserted CNOT gates on MQTBench, AgentQ, and QUEKO datasets with 12, 16 and 20 qubits. The experiments use the trivial initial mapping on both 2D Grid and IBM Tokyo device topology. Best results are highlighted in bold, and second best in underline. SabreSwap (lookahead)
Pytket
AIRouting
QAP-Router (Ours)
140.17 273.67 543.32
112.97 222.41 421.45
119.47 226.96 427.82
108.09 216.30 432.50
91.10 199.84 428.58
221.22 358.53
171.26 248.91
109.68 170.71
102.05 162.77
100.83 175.88
70.20 133.42
220.16 418.96
117.26 221.20
85.32 158.16
63.52 117.28
92.30 125.38
68.88 130.36
54.02 103.08
152 138 112
148.87 399.43 871.93
156.49 323.02 671.73
97.28 203.63 393.08
79.09 157.00 300.08
83.40 153.63 308.46
77.41 162.32 338.28
77.26 166.95 323.43
12 16
860 269
172.72 363.50
106.41 214.51
104.96 171.95
89.30 129.71
78.22 122.42
67.46 134.93
58.05 110.19
16 20
150 150
144.10 273.60
75.52 145.10
60.46 111.56
45.90 85.20
47.58 86.30
50.38 96.24
42.84 75.24
Num. of qubits
Num. of circuits
Greedy
BasicSwap
MQTBench [53]
12 16 20
152 138 112
292.32 722.50 1480.45
238.48 510.93 1086.83
AgentQ [30]
12 16
860 269
360.75 632.40
QUEKO [64]
16 20
150 150
MQTBench [53]
12 16 20
AgentQ [30] QUEKO [64]
Dataset
SabreSwap (basic)
2D Grid
IBM Tokyo
problem, we represent all two-qubit interactions using CNOT gates and remove single-qubit gates, as they do not affect qubit connectivity or routing requirements. Baselines. We compare our methods against the following baselines: (i) Greedy method, (ii) Qiskit BasicSwap, (iii) Qiskit SabreSwap with its built-in “basic” and “look-ahead” heuristics [36, 75], (iv) Pytket LexiRouting [13], and (v) Qiskit AIRouting [33]. More details in Appendix C. Physical devices. We validate our methods with circuits on the 2D grid and IBM Tokyo-like device topology, with 12, 16, and 20 physical qubits. More details in Appendix B. Evaluation setup. We conduct our experiments in the most challenging setting where NQ = NP . We fix an initial mapping for all circuits to ensure a fair comparison. We adopt the “trivial” mapping where logical qubit i is mapped to physical node i. Starting from this mapping, we execute the routing procedure and report the number of inserted CNOT gates. We further include the results and analyses on individual circuit types and circuit sizes, and on random initial mappings in Appendix E. Implementation Details We use OpenAI gymnasium [10] to implement the RL environment, with PyTorch [49] as the deep learning framework. We train our policy network on randomly generated circuits to encourage generalization across diverse interaction patterns. During training, each circuit is treated as an independent episode in the RL environment, where the agent sequentially selects SWAP operators until all gates in the circuit are scheduled or until a certain number of steps Tmax is reached. We employ a random initial mapping for each episode and train the RL agent with Proximal Policy Optimization [56] using stable-baselines3 [54] implementation. To generate training data, we construct random circuits by sampling two-qubit gates over a set of NQ logical qubits. Each gate is then created by uniformly sampling a pair of distinct qubits (qu , qv ). This process produces random circuits with varying gate counts and interaction patterns. During inference, we set Tmax = 1000. More details in Appendix D. 4.2
Results on Qubit Routing
In this section, we report the results on 12-, 16-, and 20-qubit circuits on three datasets: MQTBench [53], AgentQ [30] and QUEKO [64]. We note that comparisons with state-of-the-art routing methods, such as SabreSwap and AIRouting, are not strictly budget-matched, since we can only configure the options exposed through their public APIs. Consequently, their internal search and post-processing budgets may differ from ours. For instance, even at a lower optimization setting, AIRouting performs 32 routing passes, which is more than an order of magnitude larger than the 3 forward–backward passes used in our method. Thus, we treat these methods as strong off-the-shelf baselines rather than budget-matched comparisons. 8
As shown in Table 1, QAP-Router outperforms the state-of-the-art baselines in 11 out of 14 settings on the three datasets across two device topologies. On the 2D Grid topology with 16 qubits, it reduces the number of inserted CNOT gates by 7.61% on MQTBench and 18.4% on AgentQ. our method achieves an 11.7% reduction in inserted CNOT gates compared with SabreSwap and a substantial 21.8% reduction compared with AIRouting. We also observe that QAP-Router is less effective in some settings, particularly on 20-qubit MQTBench circuits across both topologies. Nevertheless, even in these more challenging cases, QAP-Router remains competitive with the AI-based baseline, Qiskit AIRouting. This suggests that while the proposed QAP-guided policy provides strong overall routing performance, further improvements are needed to enhance its robustness on larger and more diverse circuit instances. The strong performance of QAP-Router, especially on medium-sized circuits, suggests that the proposed QAP-based formulation and solution-aware policy are able to capture globally useful routing structures. We include more discussion and analysis in Appendix E. 4.3
Ablation Study on Look-ahead Horizon
In this ablation study, we examine the effect of the look-ahead horizon length. We consider five different look-ahead horizons, H ∈ {2, 4, 6, 8, 10}, on the MQTBench and AgentQ datasets in the 16-qubit setting. As shown in Figure 4, the performance exhibits a downward trend as H increases, indicating that incorporating a longer look-ahead horizon generally improves routing quality. This suggests that exposing the policy to a broader view of upcoming interactions helps it make more globally informed routing decisions, thereby reducing the CNOT overhead in the compiled circuits. 155
Number of inserted CNOTs
217.5 215.0
150
212.5 210.0
145
207.5 140
205.0 202.5
135
200.0 2
4
6
8
Look-ahead Horizon
10
2
4
6
8
Look-ahead Horizon
10
Figure 4: Comparison on the number of inserted CNOT gates across different look-ahead horizons on the 16-qubit 2D Grid device for MQTBench (left) and AgentQ (right) datasets.
5
Conclusion and Future Work
In this paper, we study the qubit routing problem by proposing a dynamic QAP-based formulation that explicitly captures the interaction-distance coupling between logical circuits and hardware topology. By integrating this structure into both the reward function and the policy network’s encoder, our approach enables efficient routing decisions that balance near-term execution with awareness of future interactions. Experimental results on realistic circuits demonstrate that our method produces efficient routing strategies with reduced CNOT gate overhead while generalizing across diverse circuit structures. Such results highlight the benefit of incorporating problem structure into learning-based approaches for quantum compilation. Future Work. We acknowledge several limitations of the proposed method. One limitation is that our current framework trains a separate RL policy for each target circuit size, i.e., for each number of qubits. While this setting allows the policy to specialize in a fixed action space and device topology, it limits the scalability and reusability of the learned router across circuits of different sizes. As future work, we aim to develop a more general routing policy that can handle circuits with varying numbers of logical and physical qubits. A promising direction is to design size-invariant architectures that operate directly on the circuit interaction graph and hardware coupling graph rather than relying on fixed-size representations.
9
References [1] Amira Abbas, Andris Ambainis, Brandon Augustino, Andreas Bärtschi, Harry Buhrman, Carleton Coffrin, Giorgio Cortiana, Vedran Dunjko, Daniel J Egger, Bruce G Elmegreen, et al. Challenges and opportunities in quantum optimization. Nature Reviews Physics, pages 1–18, 2024. [2] Abien Fred Agarap. Deep learning using rectified linear units (relu). arXiv:1803.08375, 2018.
arXiv preprint
[3] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint arXiv:1607.06450, 2016. [4] Bao Bach, Ilya Safro, and Ed Younis. Efficient compilation for shuttling trapped-ion machines via the position graph architectural abstraction. arXiv preprint arXiv:2501.12470, 2025. [5] Puneet S Bagga and Arthur Delarue. Solving the quadratic assignment problem using deep reinforcement learning. arXiv preprint arXiv:2310.01604, 2023. [6] Marcello Benedetti, Erika Lloyd, Stefan Sack, and Mattia Fiorentini. Parameterized quantum circuits as machine learning models. Quantum Science and Technology, 4(4):043001, 2019. [7] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour d’horizon, 2020. [8] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. Quantum machine learning. Nature, 549(7671):195, 2017. [9] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. In Quantum Computation and Information, volume 305 of Contemporary Mathematics, pages 53–74. American Mathematical Society, 2002. [10] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym, 2016. [11] Marco Cerezo, Guillaume Verdon, Hsin-Yuan Huang, Lukasz Cincio, and Patrick J Coles. Challenges and opportunities in quantum machine learning. Nature computational science, 2(9):567–576, 2022. [12] Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca. Quantum algorithms revisited. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 454(1969):339–354, 1998. [13] Alexander Cowtan, Silas Dilkes, Ross Duncan, Alexandre Krajenbrink, Will Simmons, and Seyon Sivarajah. On the qubit routing problem. arXiv preprint arXiv:1902.08091, 2019. [14] David Deutsch and Richard Jozsa. Rapid solution of problems by quantum computation. Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences, 439(1907):553–558, 1992. [15] Wolfgang Dür, Guifré Vidal, and J. Ignacio Cirac. Three qubits can be entangled in two inequivalent ways. Physical Review A, 62(6):062314, 2000. [16] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028, 2014. [17] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. 2014. [18] Daniel M. Greenberger, Michael A. Horne, and Anton Zeilinger. Going beyond Bell’s theorem. In Menas Kafatos, editor, Bell’s Theorem, Quantum Theory and Conceptions of the Universe, pages 69–72. Kluwer Academic Publishers, Dordrecht, 1989. 10
[19] Marc Hein, Wolfgang Dür, Jens Eisert, Robert Raussendorf, Maarten Van den Nest, and Hans J. Briegel. Entanglement in graph states and its applications. In Giulio Casati, Dima L. Shepelyansky, Peter Zoller, and Giuliano Benenti, editors, Quantum Computers, Algorithms and Chaos, volume 162 of Proceedings of the International School of Physics “Enrico Fermi”, pages 115–218. IOS Press, 2006. [20] Steven Herbert and Akash Sengupta. Using reinforcement learning to find efficient qubit routing policies for deployment in near-term quantum computers. arXiv preprint arXiv:1812.11619, 2018. [21] Dylan Herman, Cody Googin, Xiaoyuan Liu, Yue Sun, Alexey Galda, Ilya Safro, Marco Pistoia, and Yuri Alexeev. Quantum computing for finance. Nature Reviews Physics, 5(8):450–465, 2023. [22] Torsten Hoefler and Marc Snir. Generic topology mapping strategies for large-scale parallel architectures. In Proceedings of the international conference on Supercomputing, pages 75–84, 2011. [23] Ching-Yao Huang, Chi-Hsiang Lien, and Wai-Kei Mak. Reinforcement learning and dear framework for solving the qubit mapping problem. In Proceedings of the 41st IEEE/ACM international conference on computer-aided design, pages 1–9, 2022. [24] IBM Quantum. BasicSwap: Qiskit transpiler pass documentation. https://quantum.cloud. ibm.com/docs/api/qiskit/qiskit.transpiler.passes.BasicSwap, 2026. Accessed: 2026-05-05. [25] IBM Quantum. EfficientSU2: Qiskit circuit library documentation. https://quantum.cloud. ibm.com/docs/api/qiskit/qiskit.circuit.library.EfficientSU2, 2026. Accessed: 2026-05-05. [26] IBM Quantum. RealAmplitudes: Qiskit circuit library documentation. https://quantum. cloud.ibm.com/docs/api/qiskit/qiskit.circuit.library.RealAmplitudes, 2026. Accessed: 2026-05-05. [27] IBM Quantum. TwoLocal: Qiskit circuit library documentation. https://quantum. cloud.ibm.com/docs/api/qiskit/qiskit.circuit.library.TwoLocal, 2026. Accessed: 2026-05-05. [28] Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto. Algorithmic theory of qubit routing. In Algorithms and Data Structures Symposium, pages 533–546. Springer, 2023. [29] Ali Javadi-Abhari, Matthew Treinish, Kevin Krsulich, Christopher J Wood, Jake Lishman, Julien Gacon, Simon Martiel, Paul D Nation, Lev S Bishop, Andrew W Cross, et al. Quantum computing with qiskit. arXiv preprint arXiv:2405.08810, 2024. [30] Linus Jern, Valter Uotila, Cong Yu, and Bo Zhao. Agent-q: fine-tuning large language models for quantum circuit generation and optimization. In 2025 IEEE International Conference on Quantum Computing and Engineering (QCE), volume 1, pages 1621–1632. IEEE, 2025. [31] Krishnageetha Karuppasamy, Varun Puram, Stevens Johnson, and Johnson P Thomas. A comprehensive review of quantum circuit optimization: Current trends and future directions. Quantum Reports, 7(1):2, 2025. [32] Youngseok Kim, Andrew Eddins, Sajant Anand, Ken Xuan Wei, Ewout Van Den Berg, Sami Rosenblatt, Hasan Nayfeh, Yantao Wu, Michael Zaletel, Kristan Temme, et al. Evidence for the utility of quantum computing before fault tolerance. Nature, 618(7965):500–505, 2023. [33] David Kremer, Victor Villar, Hanhee Paik, Ivan Duran, Ismael Faro, and Juan Cruz-Benito. Practical and efficient quantum circuit synthesis and transpiling with reinforcement learning. arXiv preprint arXiv:2405.13196, 2024. [34] Eugene L Lawler. The quadratic assignment problem. Management science, 9(4):586–599, 1963. 11
[35] Chi-Guhn Lee and Zhong Ma. The generalized quadratic assignment problem. Research Rep., Dept., Mechanical Industrial Eng., Univ. Toronto, Canada, page M5S, 2004. [36] Gushu Li, Yufei Ding, and Yuan Xie. Tackling the qubit mapping problem for nisq-era quantum devices. In Proceedings of the twenty-fourth international conference on architectural support for programming languages and operating systems, pages 1001–1014, 2019. [37] Silong Li, Yuxiang Chen, Lin Chen, Jing Liao, Chanchan Kuang, Kuanching Li, Wei Liang, and Naixue Xiong. Post-quantum security: Opportunities and challenges. Sensors, 23(21):8744, 2023. [38] Fujitsu Limited. Fujitsu and riken develop world-leading 256-qubit superconducting quantum computer, 2025. Date accessed: May 03, 2026. https://info.archives.global. fujitsu/global/about/resources/news/press-releases/2025/0422-01.html. [39] Chang Liu, Zetian Jiang, Runzhong Wang, Junchi Yan, Lingxiao Huang, and Pinyan Lu. Revocable deep reinforcement learning with affinity regularization for outlier-robust graph matching. arXiv preprint arXiv:2012.08950, 2020. [40] Xiaoyuan Liu, Hayato Ushijima-Mwesigwa, Avradip Mandal, Sarvagya Upadhyay, Ilya Safro, and Arnab Roy. Leveraging special-purpose hardware for local search heuristics. Computational Optimization and Applications, 82(1):1–29, 2022. [41] Andrew Lucas. Ising formulations of many np problems. Frontiers in physics, 2:74887, 2014. [42] Marco Maronese, Lorenzo Moro, Lorenzo Rocutto, and Enrico Prati. Quantum compiling. In Quantum Computing Environments, pages 39–74. Springer, 2022. [43] K. Mitarai, M. Negoro, M. Kitagawa, and K. Fujii. Quantum circuit learning. Phys. Rev. A, 98(3):032309, 2018. [44] Abtin Molavi, Amanda Xu, Ethan Cecchetti, Swamit Tannu, and Aws Albarghouthi. Generating compilers for qubit mapping and routing. Proceedings of the ACM on Programming Languages, 10(POPL):2265–2294, 2026. [45] Abtin Molavi, Amanda Xu, Martin Diges, Lauren Pick, Swamit Tannu, and Aws Albarghouthi. Qubit mapping and routing via maxsat. In 2022 55th IEEE/ACM international symposium on Microarchitecture (MICRO), pages 1078–1091. IEEE, 2022. [46] Prakash Murali, Jonathan M Baker, Ali Javadi-Abhari, Frederic T Chong, and Margaret Martonosi. Noise-adaptive compiler mappings for noisy intermediate-scale quantum computers. In Proceedings of the twenty-fourth international conference on architectural support for programming languages and operating systems, pages 1015–1029, 2019. [47] Siyuan Niu, Adrien Suau, Gabriel Staffelbach, and Aida Todri-Sanial. A hardware-aware heuristic for the qubit mapping problem in the nisq era. IEEE Transactions on Quantum Engineering, 1:1–14, 2020. [48] Alex Nowak, Soledad Villar, Afonso S Bandeira, and Joan Bruna. Revised note on learning quadratic assignment with graph neural networks. In 2018 IEEE Data Science Workshop (DSW), pages 1–5. IEEE, 2018. [49] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019. [50] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J Love, Alán Aspuru-Guzik, and Jeremy L O’brien. A variational eigenvalue solver on a photonic quantum processor. Nature communications, 5:4213, 2014. [51] Christopher Portmann and Renato Renner. Security in quantum cryptography. Reviews of Modern Physics, 94(2):025008, 2022. 12
[52] Matteo G Pozzi, Steven J Herbert, Akash Sengupta, and Robert D Mullins. Using reinforcement learning to perform qubit routing in quantum compilers. ACM Transactions on Quantum Computing, 3(2):1–25, 2022. [53] Nils Quetschlich, Lukas Burgholzer, and Robert Wille. MQT Bench: Benchmarking software and design automation tools for quantum computing. Quantum, 2023. MQT Bench is available at https://www.cda.cit.tum.de/mqtbench/. [54] Antonin Raffin, Ashley Hill, Adam Gleave, Anssi Kanervisto, Maximilian Ernestus, and Noah Dormann. Stable-baselines3: Reliable reinforcement learning implementations. Journal of machine learning research, 22(268):1–8, 2021. [55] Robert Raussendorf and Hans J. Briegel. A one-way quantum computer. Physical Review Letters, 86(22):5188–5191, 2001. [56] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017. [57] Christian Schulz and Jesper Larsson Träff. Better process mapping and sparse quadradic assignment, 2017. [58] Ruslan Shaydulin, Hayato Ushijima-Mwesigwa, Ilya Safro, Susan Mniszewski, and Yuri Alexeev. Network community detection on small quantum computers. Advanced Quantum Technologies, 2(9):1900029, 2019. [59] Animesh Sinha, Utkarsh Azad, and Harjinder Singh. Qubit routing using graph neural network aided monte carlo tree search. In Proceedings of the AAAI conference on artificial intelligence, volume 36, pages 9935–9943, 2022. [60] Marcos Siraichi, Vinicius Fernandes Dos Santos, Sylv ain Collange, and Fernando Magno Quintão Pereira. Qubit allocation. In CGO 2018-IEEE/ACM International Symposium on Code Generation and Op timization, pages 1–12, 2018. [61] Seyon Sivarajah, Silas Dilkes, Alexander Cowtan, Will Simmons, Alec Edgington, and Ross Duncan. t| ket>: a retargetable compiler for nisq devices. Quantum Science & Technology, 6(1):014003, 2021. [62] Robert S Smith, Eric C Peterson, Mark G Skilbeck, and Erik J Davis. An open-source, industrial-strength optimizing compiler for quantum programs. Quantum Science & Technology, 5(4):044001, 2020. [63] C Devi Sudheer and Ashok Srinivasan. Optimization of the hop-byte metric for effective topology aware mapping. In 2012 19th International Conference on High Performance Computing, pages 1–9. IEEE, 2012. [64] Bochen Tan and Jason Cong. Optimality study of existing quantum computing layout synthesis tools. IEEE Transactions on Computers, 70(9):1363–1373, 2020. [65] Zhentao Tan and Yadong Mu. Learning solution-aware transformers for efficiently solving quadratic assignment problem. arXiv preprint arXiv:2406.09899, 2024. [66] Wei Tang, Yiheng Duan, Yaroslav Kharkov, Rasool Fakoor, Eric Kessler, and Yunong Shi. Alpharouter: Quantum circuit routing with reinforcement learning and tree search. In 2024 IEEE International Conference on Quantum Computing and Engineering (QCE), volume 1, pages 930–940. IEEE, 2024. [67] Hayato Ushijima Mwesigwa and Xiaoyuan Liu. An ising-based model for qubit mapping. In Proceedings of the SC’23 Workshops of the International Conference on High Performance Computing, Network, Storage, and Analysis, pages 1492–1498, 2023. [68] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pages 5998–6008, 2017. 13
[69] Runzhong Wang, Junchi Yan, and Xiaokang Yang. Neural graph matching network: Learning lawler’s quadratic assignment problem with extension to hypergraph and multiple-graph matching. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(9):5261–5279, 2021. [70] Yaakov S Weinstein, MA Pravia, EM Fortunato, Seth Lloyd, and David G Cory. Implementation of the quantum fourier transform. Physical review letters, 86(9):1889, 2001. [71] Ge Yan, Wenjie Wu, Yuheng Chen, Kaisen Pan, Xudong Lu, Zixiang Zhou, Yuhan Wang, Ruocheng Wang, and Junchi Yan. Quantum circuit synthesis and compilation optimization: Overview and prospects. arXiv preprint arXiv:2407.00736, 2024. [72] Emre Yolcu and Barnabás Póczos. Learning local search heuristics for boolean satisfiability. Advances in Neural Information Processing Systems, 32, 2019. [73] Amine Zeguendry, Zahi Jarir, and Mohamed Quafafou. Quantum machine learning: A review and case studies. Entropy, 25(2):287, 2023. [74] Haimeng Zhao, Alexander Zlokapa, Hartmut Neven, Ryan Babbush, John Preskill, Jarrod R McClean, and Hsin-Yuan Huang. Exponential quantum advantage in processing massive classical data. arXiv preprint arXiv:2604.07639, 2026. [75] Henry Zou, Matthew Treinish, Kevin Hartman, Alexander Ivrii, and Jake Lishman. Lightsabre: A lightweight and enhanced sabre algorithm. arXiv preprint arXiv:2409.08368, 2024. [76] Alwin Zulehner, Alexandru Paler, and Robert Wille. An efficient methodology for mapping quantum circuits to the ibm qx architectures. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2018.
A
Related Work
Qubit mapping and routing are of central importance in quantum compilation. These problems are often defined in terms of boolean satisfiability and often require circuit transformations to achieve a good enough mapping/routing [60]. Different quantum compilers use different types of qubit mapping and routing algorithms to achieve a low overhead. Some examples include heuristic search [72, 29], graph guided search algorithms [62], quadratic binary unconstrained optimization (QUBO) [40] and template matching [44]. Recently, some approaches have explored applying RL to this class of problems by either reducing it to sequential decision making [33] or by modeling it as sequence-to-sequence task [23]. Our method is inspired by several works in the domain of RL algorithms applied to CO problems [7]. In this work, we leverage graph neural networks to solve QAP problem. The use of Graph Neural Networks is similar to existing work [69, 48, 39] which use these networks to solve QAP by graph matching. However, our approach does not incur the expensive O(n4 ) graph matching cost. Similarly, RL based QAP solvers [5, 65] focus on solving a static QAP problem. In contrast, in this work we tackle the harder problem of a dynamic QAP. Taken in context of qubit routing, our method is novel in itself. However, we believe that the algorithm presented here has the potential to be a general dynamic QAP solver as well.
B
Physical Device Topology
2D Grid. We consider a regular 2D grid topology in which qubits are arranged on a lattice (Figure 5), and each qubit is connected to its nearest neighbors (up to four). This corresponds to rectangular subgrids that provide uniform connectivity and serve as a simplified abstraction of hardware constraints. IBM Tokyo. We also evaluate our method on hardware-inspired topologies based on IBM devices, specifically 12- and 16-qubit subgraphs extracted from larger architectures such as IBM Tokyo (originally with 20 qubits). These topologies feature irregular connectivity with varying node degrees (Figure 6), reflecting the realistic constraints of superconducting quantum processors and posing more challenging routing scenarios compared to regular grids. 14
a) 12 qubits
b) 16 qubits
c) 20 qubits
Figure 5: 2D Grid device topology for 12, 16 and 20 qubits.
a) 12 qubits
b) 16 qubits
c) 20 qubits
Figure 6: IBM Tokyo-like device topology for 12, 16 and 20 qubits.
15
• 12-qubit additional edges Eextra = {(1, 6), (2, 5), (4, 9), (5, 8), (6, 11), (7, 10)}. • 16-qubit additional edges Eextra = {(1, 6), (2, 5), (4, 9), (5, 8), (6, 11), (7, 10), (9, 14), (10, 13)}. • 20-qubit additional edges Eextra ={(1, 7), (2, 6), (3, 9), (4, 8), (5, 11), (6, 10), (7, 13), (8, 12), (11, 17), (12, 16), (13, 19), (14, 18)}.
C
Baseline Descriptions
In this appendix section, we briefly describe the baselines used in the empirical study. Let π be the current logical-to-physical qubit mapping, Ffront be the current front layer of executable two-qubit gates, and Gfuture be a set of future gates used for look-ahead scoring. Pytket LexiRouting. The LexiRouting baseline uses the routing procedure implemented in TKET /Pytket. In our experiments, this corresponds to applying Pytket’s routing framework with
LexiRouteRoutingMethod. The method updates the mapping by inserting SWAP operations and may also use architecture-aware replacements such as BRIDGE operations when applicable. It includes a look-ahead parameter that controls how many upcoming two-qubit gates are considered when selecting routing modifications [13]. We set the look-ahead horizon to 10. Greedy. The greedy baseline is Pytket LexiRouting with the look-ahead horizon set to 0. Qiskit BasicSwap. BasicSwap is Qiskit’s minimum-effort SWAP insertion pass. It traverses the circuit and checks whether each two-qubit operation is compatible with the target coupling map under the current layout. When a two-qubit operation acts on non-adjacent physical qubits, BasicSwap inserts one or more SWAP gates before the operation to make it executable. In Qiskit’s implementation, these SWAPs are inserted along a shortest undirected path between the two physical qubits involved in the operation. Since this method does not perform a global search or look-ahead optimization, it is typically simple and deterministic, but may introduce more SWAPs than more sophisticated routing methods [24]. Qiskit SabreSwap with “basic” heuristic. SabreSwap is Qiskit’s implementation of the SABRE routing algorithm. SABRE maintains a front layer of two-qubit gates and searches over candidate SWAPs in the neighborhood of qubits involved in the front layer. With the “basic” heuristic, each candidate SWAP is scored by the sum of physical distances between the qubits of the front-layer gates after applying that SWAP: X SabreSwapbasic = D π(qi ), π(qj ) . (16) (qi ,qj )∈Ffront
The SWAP with the lowest score is selected, the layout is updated, and the process repeats until all gates are routed. This heuristic focuses only on the current front layer and therefore provides a direct comparison against methods that incorporate future interactions [36]. Qiskit SabreSwap with “look-ahead” heuristic. The “look-ahead” variant of SabreSwap extends the basic SABRE cost by incorporating an additional set of upcoming gates. Specifically, it combines the front-layer cost with a weighted cost over an extended set Gfuture of future gates: X 1 SabreSwaplookahead = D π(qi ), π(qj ) (17) |Ffront | (qi ,qj )∈Ffront
+ω·
1 |Gfuture |
X
D π(qi ), π(qj ) ,
(18)
(qi ,qj )∈Gfuture
where ω is a weighting coefficient that gives lower priority to future gates than to immediately executable gates. Compared with the “basic” heuristic, this variant is less myopic because it attempts to choose SWAPs that are beneficial for both the current front layer and near-future interactions [36]. We set the number of trials to 1, which is equivalent to 3 passes. 16
Qiskit AIRouting. AIRouting is an AI-powered routing pass from the qiskit-ibm-transpiler package. Unlike purely hand-designed heuristics such as BasicSwap and SabreSwap, AIRouting uses reinforcement-learning-based models for layout selection and circuit routing. The pass acts as both a layout stage and a routing stage: depending on the selected layout mode, it may keep, improve, or optimize the initial layout before routing the circuit. We use AIRouting as an off-the-shelf learned routing baseline and compare its routed circuits against heuristic baselines and our proposed method [33]. We set its optimization level to 1, which is equivalent to doing 32 passes.
D
Additional Implementation Details
We use OpenAI gymnasium [10] to implement the RL environment, with the integration of PyTorch [49] as the deep learning framework. We train our policy network on randomly generated circuits to encourage generalization across diverse interaction patterns. During training, each circuit is treated as an independent episode in the RL environment, where the agent sequentially selects SWAP operators until all gates in the circuit are scheduled. We employ a random initial mapping for each episode to enhance robustness and encourage the policy to generalize across arbitrary mappings. We train the RL policy network with Proximal Policy Optimization (PPO) [56] using stable-baselines3 [54] implementation. We adopt the default decoder architecture from stable-baselines3, a two-layer feed forward network, and set the hidden dimension to 256. We use a learning rate of 0.0003, a batch size of 1024, and a total number of training timesteps of 10M on 12 qubits, 20M on 16, and 50M on 20. Although these budgets define the maximum number of environment interactions, we empirically observe that the learned policy generally converges after approximately one third of the allocated timesteps. The remaining hyper-parameters for PPO follow by the library default settings. To choose the best set of hyper-parameters (λQAP , λswap , λgate ), we perform a grid search over the values {0.5, 1.0, 2.0}, yielding a total of 27 runs per setting. Empirically, we observe the best combination to be (λQAP , λswap , λgate ) = (1.0, 2.0, 2.0). All experiments were conducted on a single 141GB NVIDIA H200 GPU. Training Data Generation. To generate training data, we construct random circuits by sampling two-qubit gates over a set of NQ logical qubits. Specifically, we first sample the total number of two-qubit gates uniformly at random between κlow · NQ and κhigh · NQ , where κlow , κhigh denote low and high thresholds. Empirically, we set (κlow , κhigh ) = (8, 16). Each gate is then created by uniformly sampling a pair of distinct qubits (qu , qv ). This process produces random circuits with varying gate counts and interaction patterns. Post-processing. During evaluation, we employ a lightweight post-processing step following the conventional bidirectional routing strategy used in SABRE [36]. The purpose of this step is to refine the final routed circuit without introducing an expensive search procedure. Specifically, for each circuit, we perform three routing passes in a forward–backward–forward order. In the first forward pass, the circuit is routed from the initial mapping X 0 order to obtain an initial feasible layout X ′0 and routed circuit. The second pass routes the circuit in the reversed order of gates using the final layout from the first pass X ′0 as its initial layout, which helps propagate information from later circuit interactions back toward the beginning of the circuit. We also record the final layout of the backward pass as X ′′0 . Finally, a third forward pass routes the original circuit again using the layout information obtained from the backward pass X ′′0 . This bidirectional procedure allows the router to account for both early and late two-qubit interactions. Compared with applying a single forward pass, the forward–backward–forward refinement can reduce unnecessary SWAP insertions caused by myopic layout choices, while adding only a small constant-factor overhead during evaluation. All reported results use the routed circuit produced by the final forward pass.
E
More Results on Random Initial Mappings
To further evaluate the robustness of our method, we test QAP-Router under random initial mappings. Specifically, we generate a fixed set of 10 random initial mappings and report the averaged results 17
Table 2: The average number of inserted CNOT gates on MQTBench, AgentQ, and QUEKO datasets with 12, 16 and 20 qubits. The experiments use a fixed set of 10 random initial mappings on 2D Grid device topology. Best results are highlighted in bold, and second best in underline. Num. of qubits
Num. of circuits
BasicSwap
SabreSwap (basic)
SabreSwap (lookahead)
Pytket
AIRouting
QAP-Router (Ours)
MQTBench
12 16 20
152 138 112
226.48 ± 8.92 519.00 ± 27.51 1046.47 ± 45.18
145.61 ± 1.95 301.88 ± 4.17 572.98 ± 11.27
113.33 ± 3.12 227.00 ± 3.93 424.33 ± 9.58
110.87 ± 5.38 233.88 ± 6.50 441.70 ± 10.14
109.74 ± 2.08 234.41 ± 3.87 450.46 ± 10.45
101.64 ± 3.54 215.40 ± 4.53 436.29 ± 7.22
QUEKO
16 20
150 112
122.07 ± 1.91 227.66 ± 7.75
89.52 ± 2.21 168.01 ± 5.33
65.93 ± 1.50 122.15 ± 3.34
68.79 ± 1.46 128.81 ± 3.87
71.72 ± 1.66 135.05 ± 3.66
51.72 ± 0.78 104.70 ± 1.02
Dataset
in Table 2 on two datasets, MQTBench and QUEKO, using the more challenging 2D Grid device topology. As shown in Table 2, QAP-Router is robust to variations in the initial mapping, achieving the best performance in 4 out of 5 settings. Although our method struggles on 20-qubit MQTBench circuits under the trivial initial mapping, as reported in Table 1, it achieves the second-best result under random initial mappings, trailing SabreSwap by only about 12 CNOT gates, equivalent to approximately 4 SWAP gates. These results suggest that QAP-Router is not overly dependent on a favorable initial layout and can generalize effectively across different starting mappings.
F
Circuit Definitions
In this appendix section, we briefly describe the types of circuits included in the datasets used for the empirical study. Amplitude Estimation (ae). Amplitude estimation circuits estimate an unknown amplitude encoded in a quantum state using amplitude amplification and phase-estimation-like subroutines [9]. In routing benchmarks, these circuits are useful because their controlled amplification and estimation structure induces repeated long-range two-qubit interactions, making them a challenging case for evaluating whether a router can preserve favorable logical-to-physical qubit placements across multiple time slices. Deutsch–Jozsa (dj). Deutsch–Jozsa circuits solve the oracle problem of determining whether a Boolean function is constant or balanced [14]. It is a well known textbook algorithm that falls under umbrella of the hidden subgroup problem for commutative group. Greenberger–Horne–Zeilinger (ghz). GHZ circuits [18] prepare highly entangled multipartite states, commonly written as 1 √ (|0⟩⊗n + |1⟩⊗n ). 2 Their preparation requires propagating entanglement across many qubits through a sequence of twoqubit gates, making them useful benchmarks for evaluating how routing methods handle structured, non-local entangling patterns under limited hardware connectivity. Graph State (graphstate). Graph-state circuits prepare entangled states associated with an underlying graph, where vertices correspond to qubits and edges indicate entangling operations [19, 55]. This is a much broader extension of the previous case. Quantum Approximate Optimization Algorithm (qaoa). QAOA circuits are variational circuits for approximate combinatorial optimization, alternating between problem-dependent cost operators and mixing operators [16]. This is arguably most frequently used algorithm for combinatorial optimization problems. Their cost Hamiltonian layers induce two-qubit interactions determined by the problem graph, making them useful benchmarks for evaluating whether a routing can align logical interaction structure with the hardware topology. Quantum Fourier Transform (qft). QFT circuits [70] implement the quantum analogue of the discrete Fourier transform and are central subroutines in algorithms such as phase estimation, Shor’s factoring and many other versions of the hidden subgroup problem. Quantum Neural Network (qnn). QNN circuits are parameterized quantum circuits used as trainable models in quantum machine learning [43, 6]. 18
Quantum Phase Estimation (qpe). QPE circuits estimate the eigenphase of a unitary operator and serve as a fundamental primitive in many quantum algorithms [12]. Their structure can induce repeated interactions between phase and system registers, making them useful for evaluating whether routing methods preserve favorable placements across successive time slices. Real Amplitudes (realamp). Real-amplitudes circuits are hardware-efficient variational ansatz circuits composed of alternating rotation and entangling layers that prepare states with real-valued amplitudes [26]. SU(2) (su2). The SU(2) circuits are parameterized ansatz circuits based on layers of single-qubit operations spanning SU(2) together with entangling gates [25]. Variational Quantum Eigensolver (vqe). VQE circuits prepare parameterized trial states whose parameters are optimized classically to minimize the expectation value of a Hamiltonian [50]. The idea is very similar to that of QAOA but with only one Hamiltonian. These circuits have many applications in such domains as quantum chemistry, materials science, and condensed matter. Two-local (twolocal). Two-local circuits are parameterized ansatz circuits consisting of alternating single-qubit rotation layers and two-qubit entangling layers [27]. Traveling Salesperson Problem (tsp). TSP circuits encode instances of the traveling salesperson problem, often through Ising/QUBO formulations or QAOA-style optimization circuits [41, 17]. W State (wstate). W-state circuits prepare multipartite entangled states corresponding to an equal superposition over computational basis states with Hamming weight one [15].
G
Routing Performance on Different Types and Sizes of Quantum Circuits
G.1
Across Circuit Types
In Figures 7, 8 and 9, we report the performance of each method across up to 19 circuit types from different quantum applications, such as quantum neural network, quantum approximate optimization algorithm, quantum variational eigensolver, etc. We conduct the experiment on 2D Grid devices on the MQTBench dataset for 12-, 16-, and 20-qubit circuits. Here, we take a closer look at the 20-qubit circuits where our method seems to struggle, as suggested by Table 1. Circuits in the domains of Amplitude Estimation (ae), Quantum Fourier Transform (qft), and Quantum Phase Estimation (qpe) are where our method trails the strongest baselines most noticeably. These circuit families often contain highly structured long-range and repeated controlled interactions. Although the QAP objective provides a global topology-aware signal by jointly modeling logical interactions and physical distances, the current policy still makes sequential routing decisions over an evolving circuit state. Thus, for qft-, qpe-, and ae-like circuits, performance may depend not only on global spatial awareness, but also on accurately modeling long-horizon temporal structure across the circuit. This indicates that the decay-weighted aggregation used to construct the effective flow matrix F̂ may be insufficient for larger-scale circuits, motivating more exploration in future work. In contrast, methods such as SabreSwap may perform well on these regular circuit families due to their explicit bidirectional refinement. G.2
Across Circuit Sizes
In Figures 10, 11 and 12, we report the performance of each method across several gate ranges. On 16 qubits, QAP-Router achieves the best results on all circuit sizes, reducing the average CNOT count by 16 relative to the second-best method, AIRouting, on medium-sized circuits. On larger circuits, QAP-Router ranks second, incurring an average overhead of 27 additional CNOT gates compared to SabreSwap with the lookahead heuristic.
19
Number of inserted CNOTs Number of inserted CNOTs Number of inserted CNOTs Number of inserted CNOTs
600
552
500 417
400
366
345
300 210
200
158 153 150 144
100 0
179 102 93
48 35 24 34 21
ae
27 18 29 18 18 17 12
dj
ghz
500 400
54 42 31 23 24 22 12
graphstate
403
366
142 123
417
395
363
180
portfolioqaoa
456
417
156
366
300 200
183
159
180
204 145
100
69 60
0
176
198
123
portfoliovqe
42 38 39 36
qaoa
12
208 157
138
qft
194
156 165 168 156
qftentangled
160
180
138 123
qnn
600 501
500 400
419
300
366 297
286
286 204
200
417
407
241
223 176 165 170
156 148 166 149
153
188 185 198
180 165 180
168
153
100 0
qpeexact
qpeinexact
random
417
366
300 200
181
156
180
100 0
149
183 123
162
180
150
Pytket AIRouting QAP-Router (Ours)
123 27
su2random
routing
Greedy BasicSwap SabreSwap (Basic) SabreSwap (Lookahead)
417 366
27 27 31 18 18 19 12
realamprandom
500 400
123
twolocalrandom
27
Circuit Types
31
18
vqe
18
17
12
48
56
39
28
34
wstate
22
4
Figure 7: Comparison on the number of inserted CNOT gates between QAP-Router and state-of-theart routers for 12-qubit circuits on 2D grid device. The results are shown across 19 circuit types in the MQTBench dataset.
20
Number of inserted CNOTs Number of inserted CNOTs Number of inserted CNOTs
1000 800
1038
1023
825
780
600 400
369
177 183 74 50
0 1600 1400 1200 1000 800 600 400 200 0 1000 800
340
287 282 277 303
200
ae
33 46 39
96
33 48 27 27 28 12
dj
111 80
ghz
298 312 289 273 99 87
52 39 42 40 18
graphstate
portfolioqaoa
55 44 45 47 24
qaoa
1449 1118
1041
1023 897
885
786
1041 868
780 532
388
334 350 321
398
276
qft 1023
358
312 339 314 321
qftentangled
301 312 290 273
qnn
532 334 338 342 310
qpeexact
1023
780
449
337 338 348 310
qpeinexact
780
464 486 494 437
random
Greedy BasicSwap SabreSwap (Basic) SabreSwap (Lookahead)
1023
780
612 428
Pytket AIRouting QAP-Router (Ours)
600 400
353
300 312 293 273
352
0
356
293 312 282 273
200
299 312 291 273
141
realamprandom
su2random
45 46 27 27 28 12
tsp
96
twolocalrandom
Circuit Types
48 51 27 27 27 12
vqe
130
64 66 43 51 37
wstate
22
Figure 8: Comparison on the number of inserted CNOT gates between QAP-Router and state-of-theart routers for 16-qubit circuits on 2D grid device. The results are shown across 18 circuit types in the MQTBench dataset.
21
Number of inserted CNOTs Number of inserted CNOTs Number of inserted CNOTs
2500 2000
2143
1500
1827 1583
1448
1000
701
500 0
518 484 496 555
669 294 258
ae
194
129 48 70 36 36 42 24
108 72 57 68 51
dj
101 82 61 68 62 28
ghz
graphstate
qft 2564
2500 2000 1500
1953
1831 1602
1879
1879
1608
1532
704
500 0
660
618 514 602 576
qftentangled
734
531 495 526 519
qnn
740
596 611 579 634
qpeexact
1953 1608
1500
627
638
515 495 518 519
Pytket AIRouting QAP-Router (Ours)
686
525 495 513 519
532 495 533 519 174 129 94
0
realamprandom
746
1608
1000 500
894 916
random
Greedy BasicSwap SabreSwap (Basic) SabreSwap (Lookahead)
1953 1608
799
576 611 602 634
qpeinexact
2500 1953
1097
1044
1040
1000
2000
573 564 565 599
su2random
twolocalrandom
60
83
wstate
Circuit Types
59
34
Number of inserted CNOTs
Figure 9: Comparison on the number of inserted CNOT gates between QAP-Router and state-of-theart routers for 20-qubit circuits on 2D grid device. The results are shown across 14 circuit types in the MQTBench dataset.
400
Greedy BasicSwap SabreSwap (Basic) SabreSwap (Lookahead)
Pytket AIRouting QAP-Router (Ours)
433 351
300 199
200
164
175
157
137
100 51
0
46
36
26
0-50
25
24
12
Number of Gates
50-100
Figure 10: Comparison on the number of inserted CNOT gates between QAP-Router and state-ofthe-art routers for 12 qubits. The results are shown across 2 ranges of gate numbers: 0-50 and 50-100, in the MQTBench dataset.
22
Number of inserted CNOTs
1600 1400 1200
Greedy BasicSwap SabreSwap (Basic) SabreSwap (Lookahead)
Pytket AIRouting QAP-Router (Ours)
1449
1025
1000
868
800
746 612
600 379
400 200 0
112 78
464 486 494 437 310 321 305 289
56 37 36 35 20
0-50 (n=50)
100-150 (n=80)
Number of Gates
150-200 (n=8)
Number of inserted CNOTs
Figure 11: Comparison on the number of inserted CNOT gates between QAP-Router and state-ofthe-art routers for 16 qubits. The results are shown across 3 gate ranges: 0-50, 100-150 and 150-200, in the MQTBench dataset.
2500
Greedy BasicSwap SabreSwap (Basic) SabreSwap (Lookahead)
2000
Pytket AIRouting QAP-Router (Ours)
2586
1939
1500
1927 1605
1434
1095
1000 673
500 0
1549
198 134
533 532 534 573
731
559 605 582 626
809
903 894
749
84 57 61 56 36
0-50
150-200
200-250
Number of Gates
250-300
Figure 12: Comparison on the number of inserted CNOT gates between QAP-Router and state-ofthe-art routers for 20 qubits. The results are shown across 4 gate ranges: 0-50, 150-200, 200-250, and 250-300, in the MQTBench dataset.
23