Technical reference for the complete system architecture. Covers every component from problem definition to experimental findings, with mathematical formulations, design rationale, and paper references.
- Problem Definition
- MDP Formulation
- Network Architecture — DuelingCNN
- Agent — D3QN + PER
- Training Pipeline
- Multi-Topology Support
- Supported Hardware Topologies
- Baseline: SABRE
- Key Experimental Findings
- Current Best Configuration
- References
A quantum algorithm is expressed as a quantum circuit: a sequence of quantum gates applied to logical qubits. Single-qubit gates (e.g., Hadamard, T, Rz) act on one qubit and can be executed on any physical qubit. Two-qubit gates (e.g., CNOT, CZ) require both operand qubits to be physically adjacent on the hardware — connected by a direct coupling link.
Real quantum processors have limited connectivity: not every pair of physical qubits is coupled. IBM's heavy-hex architecture, for example, connects each qubit to at most 3 neighbors. When a two-qubit gate requires qubits that are not adjacent, the compiler must insert SWAP gates to move qubit states along the coupling graph until the operands become neighbors.
This is the quantum circuit routing problem (also called qubit routing or transpilation): given a logical quantum circuit and a hardware coupling graph, find a sequence of SWAP insertions that makes every two-qubit gate executable, while minimizing the total number of SWAPs inserted.
In the current Noisy Intermediate-Scale Quantum (NISQ) era, quantum processors suffer from:
- Gate errors: every gate has a non-trivial error rate (~0.1-1% for two-qubit gates on current hardware). Each SWAP decomposes into 3 CNOT gates, so one SWAP triples the error contribution.
- Decoherence: qubit states decay over time. Longer circuits (more SWAPs) mean more time for decoherence to corrupt the computation.
- Limited qubit counts: NISQ devices have 50-1000+ qubits, but effective circuit depth is severely limited by noise.
Minimizing SWAP count directly improves the probability that a quantum computation produces a correct result. A routing solution that uses even one fewer SWAP can meaningfully impact output fidelity.
Given:
- A quantum circuit
$C$ with$n$ logical qubits and a set of two-qubit gates$G = {g_1, g_2, \ldots, g_m}$ , each$g_i = (q_a, q_b)$ specifying two logical qubits. - A hardware coupling graph
$H = (V, E)$ where$|V|$ is the number of physical qubits and$E$ are the bidirectional coupling edges. - A dependency DAG
$D$ over the gates, where$g_j$ depends on$g_i$ if they share a qubit and$g_i$ precedes$g_j$ .
Find:
- An initial mapping
$\pi: {0, \ldots, n-1} \rightarrow V$ assigning logical qubits to physical positions. - A sequence of SWAP operations on edges in
$E$ , interleaved with gate executions, such that every gate$g_i = (q_a, q_b)$ is executed when$(\pi(q_a), \pi(q_b)) \in E$ .
Minimize:
- The total number of SWAP operations inserted.
This problem is NP-hard in general (Cowtan et al., 2019; Siraichi et al., 2018). Heuristic approaches like SABRE (Li et al., 2019) achieve good practical performance but are not optimal. Our approach uses reinforcement learning to discover routing strategies that can match or beat these heuristics.
The routing problem is formulated as a Markov Decision Process (MDP)
src/environment.py — class QubitRoutingEnv).
The state is a 5-channel matrix_size
(default 27, large enough for the biggest topology). The observation space is
Box(0.0, 1.0, shape=(5, N, N), dtype=float32).
Each channel encodes a different aspect of the routing problem:
Binary, symmetric, constant within an episode. Encodes the hardware
topology. The CNN can learn which edges exist and use this to plan SWAP
sequences. For topologies smaller than
Rationale: Explicit adjacency lets the network distinguish between different topologies in multi-topology training without needing separate models.
Binary permutation matrix. Exactly one 1 per row (each logical qubit is somewhere) and one 1 per column (each position holds at most one qubit). Updated after every SWAP.
Rationale: A permutation matrix is a lossless encoding of the mapping. The CNN can cross-reference this with the adjacency and demand channels to determine which SWAPs would be useful.
For each remaining (unexecuted) gate
where
The channel is then normalized by dividing by
Rationale: This channel tells the network where gate demand exists in physical space, with exponential discounting by DAG depth. Front-layer gates (depth 0) contribute 1.0; gates at depth 1 contribute 0.5; depth 2 contributes 0.25; and so on. This guides the agent to prioritize near-term gates while remaining aware of future demand. Inspired by the "lookahead" in SABRE's cost function but encoded as a spatial feature map.
For each gate
where
Values: 1.0 when adjacent (distance 1, already executable), 0.5 at distance 2,
0.25 at distance 4, etc. The
Rationale: This channel focuses attention on the immediate routing bottleneck: which front-layer gate pairs are far apart and need SWAPs to bring them together. Higher values mean "closer to being executable." The inverse- distance encoding naturally prioritizes the most constrained gates.
A uniform scalar broadcast across the entire
Rationale: Without this signal, the network has no sense of how long it has
been "stuck" — making the same unproductive SWAPs without executing any gates.
The stagnation channel acts as a soft alarm: as the value grows, the network
learns to try alternative SWAP strategies. It also helps the network anticipate
the timeout penalty, which fires when step_count >= max_steps.
Each action index
After each SWAP, the environment automatically executes all newly-routable front-layer gates (gates whose operand qubits are now adjacent). This cascading execution continues until no more gates can fire, so a single well-chosen SWAP can trigger multiple gate executions.
Action masking: In multi-topology mode, max_edges is the maximum edge
count across all topologies. Actions beyond the current topology's edge count
are invalid and masked via get_action_mask(). The agent's select_action()
applies this mask: invalid actions get
The reward at each time step is a composite signal:
where:
Every SWAP costs
Rationale: A SWAP decomposes into 3 CNOT gates on real hardware, each with
non-trivial error. The
gate_execution_reward (default 1.0).
With
Rationale: This balances the SWAP penalty with a progress signal. Without gate execution reward, the agent only sees negative rewards until the completion bonus, making credit assignment over long episodes extremely difficult.
where distance_reward_coeff (default 0.1).
A SWAP that moves front-layer qubits closer together yields positive
Rationale: This is the Pozzi-style distance shaping reward (Pozzi et al., 2022). It provides dense, informative feedback every step — not just when gates execute. The coefficient 0.1 keeps shaping subordinate to the primary SWAP cost signal, preventing the agent from gaming the shaping reward at the expense of actual progress.
Rationale: Performing the same SWAP twice in a row undoes the first SWAP,
wasting 2 steps. This is a common failure mode in early training. The penalty
discourages swap-undo loops without completely forbidding the action (which
could be needed in rare edge cases). The
Rationale: The completion bonus (+5.0) incentivizes actually finishing the circuit, not just making local progress. The timeout penalty (-10.0) punishes failure to route within the budget, creating urgency. The asymmetry (penalty > bonus) reflects that timeout is a catastrophic failure — the circuit was not routed — while completion is the expected baseline.
-
Reset: Pick a topology (uniform or weighted random), generate a random circuit (
random_circuit(num_qubits, circuit_depth)), set initial mapping (random permutation, identity, SABRE, or mixed), auto-execute any initially-routable gates. -
Step loop: Agent selects action (SWAP), environment performs SWAP, auto- executes all newly-routable gates (cascading), computes reward.
-
Termination:
-
terminated = Truewhen all gates executed. -
truncated = Truewhenstep_count >= max_steps.
-
-
Bootstrap distinction: Truncated episodes still bootstrap
$Q(s')$ because the episode was cut short, not naturally ended. Onlyterminatedis stored as thedoneflag in the replay buffer.
Implemented in src/networks.py. The network takes the 5-channel
Input: (batch, 5, N, N)
-> Conv2d(5 -> C1, 3x3, padding=1) -> ReLU
-> Conv2d(C1 -> C2, 3x3, padding=1) -> ReLU
-> Conv2d(C2 -> C3, 3x3, padding=1) -> ReLU
-> Flatten -> (batch, C3 * N * N)
Default channel progression: [32, 64, 32]. All convolutions use padding=1
("same" padding), preserving spatial dimensions throughout. No pooling layers.
Why CNN: The state is fundamentally a 2D spatial structure. Physical qubits are arranged on a grid-like topology, and the channels encode spatial relationships (adjacency, mapping, demand). Convolutional filters naturally capture local patterns: which qubits are near each other, where demand concentrates, which edges are useful. The same-padding design preserves the full spatial resolution — every position matters for routing decisions.
Why no pooling: Pooling would lose positional information that is critical for routing. The agent needs to know exactly which edges to SWAP, not just that "there is demand somewhere in this region."
After the CNN extracts features (flattened to
Value stream — estimates the state value
Linear(C3*N*N -> 256) -> ReLU -> Linear(256 -> 1)
Advantage stream — estimates per-action advantages
Linear(C3*N*N -> 256) -> ReLU -> Linear(256 -> num_actions)
Q-value aggregation:
Subtracting the mean advantage ensures identifiability:
Rationale: In quantum circuit routing, many states have similar values (the
circuit is partially routed, and the remaining difficulty is similar across
nearby states). The dueling architecture lets the network learn
For
| Configuration | Conv Channels | Dueling Hidden | Total Parameters |
|---|---|---|---|
| Standard | [32, 64, 32] | 256 | ~6.1M |
| BigNet | [64, 128, 64] | 512 | ~24.0M |
The bulk of parameters are in the first linear layers of the dueling streams
(flattened CNN output to hidden). For standard config:
Experimental finding: The standard [32, 64, 32] network outperforms the bigger [64, 128, 64] network on single-topology tasks (see Section 9). The larger network takes longer to converge and plateaus at a worse swap ratio on heavy_hex_19. For multi-topology, the bigger network performs comparably but requires more training time.
The agent (src/dqn_agent.py — class D3QNAgent) combines four key
algorithmic innovations:
- Double DQN — reduces overestimation bias
- Dueling architecture — separates value and advantage estimation
- Prioritized Experience Replay (PER) — focuses learning on surprising transitions
- N-step returns — reduces bias in target computation
Together, these form D3QN+PER (Double Dueling Deep Q-Network with Prioritized Experience Replay).
Standard DQN computes targets as:
The
Double DQN decouples action selection from action evaluation:
- The online network
$Q_\theta$ selects the best action:$a^* = \arg\max_{a'} Q_\theta(s_{t+n}, a')$ - The target network
$Q_{\theta^-}$ evaluates that action:$Q_{\theta^-}(s_{t+n}, a^*)$
Because the two networks have different parameters (the target network lags behind), the selection and evaluation errors are decorrelated, eliminating the systematic upward bias.
When computing the best next action, invalid actions (from topology masking) are
set to
q_online_next[~next_masks] = -float("inf")
best_actions = q_online_next.argmax(dim=1)This ensures the target never references an invalid action, which is critical for multi-topology training where different episodes have different valid action sets.
Implemented in src/replay_buffer.py.
Uniform random sampling from the replay buffer treats all transitions equally. But some transitions are more "surprising" (larger TD error) and therefore more informative for learning. PER samples transitions proportionally to their priority, focusing gradient updates on the experiences the network has the most to learn from (Schaul et al., 2016).
The SumTree class implements an array-based binary tree enabling O(log n)
proportional sampling:
-
Leaf nodes (indices
$[C, 2C)$ where$C$ = capacity) store individual transition priorities. - Internal nodes store the sum of their children's priorities.
- Root (index 1) stores the total priority sum.
Sampling: To sample proportionally, draw a uniform random value
Update: When a priority changes, update the leaf and propagate the delta up
to the root. Also
When a transition is first added, it gets the current maximum priority (optimistic initialization):
After a training step, priorities are updated from TD errors:
where
Instead of drawing batch_size independent samples (which could cluster in
high-priority regions), PER uses stratified sampling: the total priority
range batch_size equal segments, and one
sample is drawn uniformly from each segment.
This ensures diversity in the sampled batch — even low-priority transitions get occasional representation.
Prioritized sampling introduces bias: high-priority transitions are overrepresented. To correct this, each sampled transition is weighted by an importance sampling (IS) weight:
where
The exponent per_beta_anneal_steps training steps:
Early in training,
States are stored as uint8 (0-255) rather than float32, achieving a ~4x
memory reduction. Conversion happens at storage time (multiply by 255, clip,
cast) and retrieval time (cast to float32, divide by 255). The quantization
error (
Standard 1-step TD target:
N-step target:
The n-step return uses
The _nstep_buf is a FIFO list that accumulates recent transitions. When it
reaches length
_pop_nstep():
R = sum(gamma^i * r_i for i in range(min(len(buf), n)))
store(s_0, a_0, R, s_n, done_n) into PER buffer
remove oldest from _nstep_buf
When an episode ends (end_episode() or done=True), all remaining transitions
in the buffer are flushed with truncated n-step returns. This handles both
natural termination and timeout truncation correctly.
Default: n_step = 1 (standard TD). Higher values (3-5) can be enabled
via config but have not shown consistent improvement in our experiments.
Instead of periodically copying the entire online network to the target network (hard update), we use soft Polyak averaging at every target update step:
with
The target network is updated every target_update_freq = 500 training steps
using this formula. When
Rationale: Soft updates create a smoother evolution of the target network,
reducing oscillations in Q-value targets. With hard updates every
The agent uses linear epsilon decay:
With defaults:
At each step:
- With probability
$\epsilon$ : sample a random valid action uniformly - With probability
$1 - \epsilon$ : select$\arg\max_a Q(s, a)$ over valid actions (greedy)
Why
The final epsilon determines the quality of transitions entering the replay
buffer during late training. At
Experimental result:
Two modes, controlled by lr_schedule:
LR stays at lr (default
where $\text{lr}{\max}$ is the initial LR, $\text{lr}{\min} = 10^{-5}$, and
total_episodes * 50 gradient steps.
Rationale: High LR early in training enables fast feature learning (the CNN needs to understand the state structure). Low LR late in training enables fine-tuning (small Q-value adjustments that improve swap ratios from 1.05 to 1.01). However, our experiments have not shown consistent benefit from cosine scheduling over constant LR, likely because the epsilon schedule already controls exploration/exploitation balance.
The loss combines Huber loss with IS weight correction:
where
Why Huber over MSE: TD errors can be very large, especially early in
training or after epsilon transitions to bad states. MSE (
Gradient clipping: After backpropagation, gradients are clipped to a maximum
norm of grad_clip_norm = 10.0:
torch.nn.utils.clip_grad_norm_(online_net.parameters(), 10.0)This provides a second line of defense against gradient explosions. The value 10.0 is permissive enough to allow fast learning while preventing catastrophic updates.
Implemented in src/train.py.
for episode in range(total_episodes):
obs, info = env.reset() # New random circuit + topology
action_mask = env.get_action_mask()
while not (terminated or truncated):
action = agent.select_action(obs, action_mask)
next_obs, reward, terminated, truncated, info = env.step(action)
next_mask = env.get_action_mask()
agent.store_transition(obs, action, reward, next_obs, terminated, next_mask)
if global_step % train_freq == 0:
metrics = agent.train_step()
if train_steps % target_update_freq == 0:
agent.update_target_network()
agent.update_epsilon()
obs = next_obs; action_mask = next_mask
agent.end_episode() # Flush n-step buffer
Key design decisions:
-
train_freq = 4for primary experiments: one gradient step per 4 environment steps. Reduces computational cost while maintaining sufficient update frequency. -
train_start = 1000: no training until 1000 transitions are in the buffer, ensuring sufficient diversity before first gradient step. -
terminatedvstruncated: onlyterminatedis stored asdonein the buffer. Truncated episodes still bootstrap$Q(s')$ , which is correct — truncation is an artificial time limit, not a true terminal state. - Circuit skipping: episodes where the random circuit has zero two-qubit gates are logged but skipped (no stepping needed).
Optional depth progression configured via curriculum_depths and
curriculum_milestones:
curriculum_depths = [5, 10, 20] # Circuit depths
curriculum_milestones = [0.15, 0.35] # At 15% and 35% of trainingAt episode
- Progress
$p = e / E$ - If
$p < 0.15$ : depth = 5 (easy circuits, ~2-5 two-qubit gates) - If
$0.15 \leq p < 0.35$ : depth = 10 (medium circuits, ~5-15 gates) - If
$p \geq 0.35$ : depth = 20 (full difficulty, ~15-40 gates)
Rationale: Easy circuits let the agent learn basic SWAP mechanics (bring qubits together, execute gates) before facing the combinatorial complexity of deep circuits. Without curriculum, the agent may spend thousands of episodes timing out on depth-20 circuits, receiving only timeout penalties and learning nothing useful.
Checkpoints are saved every checkpoint_every episodes (default 1000-2000):
outputs/run_NNN/checkpoints/
checkpoint_ep1000.pt
checkpoint_ep2000.pt
...
checkpoint_final.pt (or checkpoint_emergency.pt on Ctrl+C)
Each checkpoint contains: online/target network state dicts, optimizer state,
epsilon value, epsilon step counter, training step counter, global step count,
and elapsed time. Optionally includes the full replay buffer (.buf.npz).
Resume support: Training can resume from any checkpoint with full state restoration, including the replay buffer if saved. The run directory is reused, and logs are appended.
Every eval_every episodes (default 500-1000), the agent is evaluated:
- For each topology, run
eval_episodes(default 20-50) random circuits. - Agent uses deterministic greedy policy (no epsilon exploration).
- Both agent and SABRE route the same circuit with the same initial mapping (SABRE's layout).
- Compare: swap ratio = agent_swaps / sabre_swaps.
Results are logged to evaluations.jsonl and visualized in figures/.
Why SABRE initial mapping for eval: Using SABRE's own initial mapping gives a fair comparison — both methods start from the same state. If the agent used a random mapping, it might get lucky or unlucky, adding noise to the comparison.
outputs/run_NNN/
config.json # Complete hyperparameter snapshot
results_summary.json # Final training + eval metrics
logs/
episodes.jsonl # Per-episode: reward, swaps, gates, completion
train_steps.jsonl # Per-100 steps: loss, mean_q, TD error, epsilon
evaluations.jsonl # Per-eval: agent vs SABRE comparison
checkpoints/
checkpoint_ep1000.pt # Model + optimizer + buffer state
checkpoint_final.pt
figures/
training_curves.png # Reward, swaps, completion rate over episodes
eval_comparison_ep*.png
eval/
eval_ep1000.json # Detailed per-circuit results
- JSONL format: each log line is an independent JSON object, enabling streaming writes and fault-tolerant reads.
- Ctrl+C handler: saves an emergency checkpoint before exiting, so long runs are never fully lost.
- tqdm progress bar: shows real-time rolling averages of reward, SWAPs, gates routed, completion rate, loss, Q-value, and epsilon.
A key feature of this system is the ability to train a single agent across multiple hardware topologies simultaneously.
The QubitRoutingEnv accepts a topologies list:
env = QubitRoutingEnv(
topologies=["linear_5", "grid_3x3", "heavy_hex_19"],
matrix_size=27, # Must fit the largest topology
)At each reset(), one topology is randomly selected (uniform or weighted). The
environment pre-computes all static data per topology (adjacency matrix, edge
list, distance matrix) at initialization time, so reset() only needs to swap
the active topology pointer.
All topologies share the same observation shape (5, N, N). Smaller topologies
(e.g., linear_5 with 5 qubits) are zero-padded to fill the
Why fixed shape: The DuelingCNN requires a fixed input size (the flattened
dimension depends on
max_edges = max(num_edges for all topologies). For a topology with fewer
edges, actions beyond its edge count are masked to False:
# get_action_mask()
mask = np.zeros(max_edges, dtype=bool)
mask[:current_topo["num_edges"]] = TrueThe agent never selects masked actions (random exploration only draws from valid
actions; greedy sets masked Q-values to
Optional topology_weights controls sampling probability:
topology_weights=[0.2, 0.2, 0.6] # 20% linear, 20% grid, 60% heavy_hexRationale: Heavy-hex is the hardest topology (most qubits, most edges, most complex routing). Without weighted sampling, the agent sees each topology equally often, but spends most training time already-solved easy topologies. Weighting toward the harder topology improves heavy_hex performance at minimal cost to the easier topologies.
Key experimental finding: A multi-topology agent can match or beat SABRE across all topologies simultaneously (Run 018: overall ratio 0.999). However, a single-topology specialist on heavy_hex_19 converges faster and achieves comparable performance on that specific topology. The multi-topology agent benefits from transfer learning: strategies learned on smaller topologies (bring qubits together, avoid cycles) generalize to larger ones.
Defined in src/circuit_utils.py — function get_coupling_map().
pos0 — pos1 — pos2 — pos3 — pos4
- Qubits: 5
- Edges: 4 (bidirectional)
- Max distance: 4 hops
- Degree: 1 (endpoints) or 2 (interior)
- Construction:
CouplingMap.from_line(5)
The simplest topology, used for sanity checks and curriculum warm-up. Maximum distance of 4 means up to 3 SWAPs may be needed for a single gate. Despite its simplicity, it still requires non-trivial routing for circuits with many two-qubit gates involving distant qubits.
pos0 — pos1 — pos2
| | |
pos3 — pos4 — pos5
| | |
pos6 — pos7 — pos8
- Qubits: 9
- Edges: 12 (bidirectional)
- Max distance: 4 hops (corner to corner)
- Degree: 2 (corners), 3 (edges), 4 (center)
- Construction:
CouplingMap.from_grid(3, 3)
A moderate topology with richer connectivity than the linear chain. The 2D grid structure means the CNN's spatial convolutions are particularly natural — the 3x3 kernel directly captures local neighborhoods in the coupling graph.
- Qubits: 19
- Edges: 20 (bidirectional)
- Max distance: 8 hops
- Degree: 1, 2, or 3 (heavy-hex pattern)
- Construction:
CouplingMap.from_heavy_hex(3)
This is a simplified version of IBM's heavy-hex architecture used in Eagle and Heron processors. The "heavy-hex" pattern replaces each edge of a hexagonal lattice with a path of length 2, inserting degree-2 "bridge" qubits. This creates a topology with very sparse connectivity (average degree ~2.1), making routing challenging.
The heavy-hex topology is the primary benchmark because:
- It represents real IBM hardware.
- Its sparse connectivity (max degree 3) creates long routing paths.
- SABRE is specifically optimized for these topologies, making it a strong baseline.
The get_coupling_map() function also supports:
linear_N: N-qubit linear chain (any N).ring_N: N-qubit ring (chain with wraparound edge).grid_RxC: R-by-C rectangular grid (any R, C).heavy_hex_27: 27-qubit heavy-hex (from_heavy_hex(5)), matching IBM's Falcon processors.
SABRE (SWAP-based Bidirectional heuristic search algorithm for Reversible circuit transpilation) by Li et al. (2019) is the default routing algorithm in IBM's Qiskit compiler. It operates in two phases:
Forward pass:
- Maintain a front layer of ready-to-execute gates.
- For each front-layer gate, compute a heuristic cost based on the distance between its qubits in the current mapping.
- For each candidate SWAP (on edges incident to front-layer qubits), score the SWAP by how much it reduces the total heuristic cost, including a lookahead term for near-future gates.
- Apply the best SWAP. Execute any newly-routable gates. Repeat.
Backward pass: 5. Reverse the circuit and run the forward pass again, starting from the final mapping of the forward pass. This "backward" routing often finds improvements.
Best of both: Take the solution with fewer SWAPs.
The SABRE heuristic cost for a SWAP candidate considers:
where
- It is the industry standard — used by default in Qiskit at
optimization_level=1. - It uses problem-specific knowledge: the dependency DAG structure, the coupling graph distances, and a lookahead heuristic.
- Its bidirectional search effectively doubles the search effort.
- It has been extensively tuned by IBM engineers over years.
- On random circuits, it typically achieves near-optimal SWAP counts for moderate circuit depths.
In evaluation (src/evaluate.py):
- Generate a random circuit.
- Run SABRE on it (via
generate_preset_pass_manager(optimization_level=1)). - Extract SABRE's initial mapping and SWAP count.
- Reset the RL environment with the same circuit and SABRE's initial mapping.
- Run the RL agent greedily (no exploration).
- Compare:
swap_ratio = agent_swaps / sabre_swaps.
This gives SABRE a slight advantage: the agent uses SABRE's mapping (which SABRE optimized jointly with routing), but the agent must route from that mapping without SABRE's bidirectional search. A ratio < 1.0 means the agent beats SABRE; > 1.0 means SABRE wins.
We also support QASMBench evaluation (run_qasmbench_evaluation()) for testing
on standard quantum algorithm circuits rather than random ones.
Results from runs 014-019 on the experiment-v2 branch.
| Run | Topologies | Episodes | Network | Best Swap Ratio | Final Swap Ratio | Completion | |
|---|---|---|---|---|---|---|---|
| 014 | heavy_hex_19 | 40k | [64,128,64]/512 | 0.02 | 1.167 | 1.167 | 100% |
| 015 | heavy_hex_19 | 60k | [32,64,32]/256 | 0.02 | 1.014 | 1.028 | 100% |
| 016 | multi (3 topos) | 45k | [32,64,32]/256 | 0.02 | 0.939* | 1.018 | 100% |
| 017 | heavy_hex_19 | 40k | [32,64,32]/256 | 0.02 | 1.059 | 1.059 | 100% |
| 018 | multi (3 topos) | 60k | [64,128,64]/512 | 0.02 | 0.947* | 0.999 | 99.3% |
| 019 | heavy_hex_19 | 80k | [32,64,32]/256 | 0.02 | 0.991 | 1.024 | 100% |
| 023 | heavy_hex_19 | 60k | [32,64,32]/256 | 0.02 | 0.994 | 1.014 | 100% |
| 024 | heavy_hex_19 | 100k | [32,64,32]/256 | 0.02 | 0.987 | 1.015 | 100% |
| 026 | multi (3 topos) | 100k | [32,64,32]/256 | 0.02 | 0.996 | 1.020 | 100% |
| 029 | heavy_hex_19 | 20k (finetune) | [32,64,32]/256 | 0.01 | 0.969 | 0.980 | 100% |
* Low completion rate at best ratio (67%) — only completed episodes counted.
Run 029 fine-tunes from Run 019's best checkpoint (ep64k) with LR=1e-5 — our best result overall.
-
Fine-tuning from best checkpoint (NEW — V6): Run 029 loaded Run 019's best weights (ep64k, ratio 0.991) and trained 20k more at LR=1e-5, reaching 0.969 — our best result, beating SABRE by 3.1%. The most compute-efficient approach: only 4.5h wall time for a 2.2% improvement over the base run.
-
More episodes (60k+): The agent continues improving well past 20k episodes. Run 015 (60k): 1.014 → Run 019 (80k): 0.991 → Run 024 (100k): 0.987. Consistent but diminishing returns.
-
Low epsilon (
$\epsilon = 0.02$ ): All successful runs use$\epsilon_{\text{end}} = 0.02$ . This keeps the replay buffer clean in late training. -
Slow epsilon decay (5M+ steps): With 80k episodes averaging ~150 steps each, total environment steps reach ~12M. Epsilon decay over 5M steps means the agent reaches
$\epsilon_{\text{end}}$ around episode 40k, with 40k more episodes of near-greedy learning. -
Standard network [32,64,32] for single-topology: Run 015 ([32,64,32]) converged to 1.028 on heavy_hex while Run 014 ([64,128,64]) plateaued at 1.167 after the same wall-clock time. The smaller network has 4x fewer parameters, leading to faster, more stable learning.
-
Weighted topology sampling for multi-topo: Run 018 used the larger network ([64,128,64]) for multi-topology and achieved an overall ratio of 0.999, effectively matching SABRE across all three topologies simultaneously.
-
Large replay buffer (300k-400k): Larger buffers retain more diverse experiences, especially important for multi-topology training where the agent needs to remember strategies for all topologies.
-
Bigger network for single-topology (Run 014): [64,128,64] with 512 dueling hidden on single heavy_hex_19 plateaued at ratio 1.167 — substantially worse than the standard network's 1.028. The extra capacity likely led to overfitting to recent experiences or slower feature learning.
-
Higher gate execution reward (Run 022,
$r_{\text{gate}} = 2.0$ ): Doubling the gate reward distorted the reward landscape, making the agent focus on executing easy gates rather than minimizing total SWAPs. Final ratio 1.377 — strongly negative. -
N-step returns without stabilization (Runs 022, 025): N-step=3 alone caused 0% completion in Run 025 (60k episodes). The 3-step bootstrap creates too much variance during early exploration. Only viable when paired with curriculum learning to stabilize the early phase.
-
Higher learning rate (
$10^{-3}$ ): Caused unstable Q-values and poor convergence.$10^{-4}$ is the sweet spot for this problem. -
Short training (< 20k episodes): The agent reaches 100% completion rate around 10-15k episodes but the swap ratio continues improving for tens of thousands more episodes. Premature stopping leaves significant performance on the table.
Typical training progression on heavy_hex_19:
| Phase | Episodes | Completion Rate | Swap Ratio | Notes |
|---|---|---|---|---|
| Exploration | 0 - 5k | 0% - 5% | N/A | Random actions, learning state structure |
| Learning to complete | 5k - 15k | 5% - 100% | 1.5 - 2.0 | Agent learns to route, but inefficiently |
| Optimizing efficiency | 15k - 40k | ~100% | 1.2 - 1.05 | Swap ratio steadily decreasing |
| Approaching SABRE | 40k - 80k | 100% | 1.05 - 0.99 | Slow improvement, occasional sub-1.0 evals |
| Fine-tuning (Stage 2) | +20k @ LR=1e-5 | 100% | 0.99 - 0.97 | Low-LR refinement from best checkpoint |
The multi-topology agents follow a similar pattern but shifted: simpler topologies (linear_5, grid_3x3) reach 100% completion first, then heavy_hex catches up, then all three optimize simultaneously.
Stage 1: Full training run (80k episodes, ~16h):
Based on Run 019 (ratio 0.991 at ep63k):
TrainConfig(
# Environment
topologies=["heavy_hex_19"],
matrix_size=27,
circuit_depth=20,
max_steps=400,
gamma_decay=0.5,
distance_reward_coeff=0.1,
completion_bonus=5.0,
timeout_penalty=-10.0,
repetition_penalty=-0.5,
gate_execution_reward=1.0,
initial_mapping_strategy="random",
# Network
conv_channels=[32, 64, 32],
dueling_hidden=256,
# DQN
gamma=0.99,
lr=1e-4,
batch_size=128,
target_update_freq=500,
tau=0.005,
grad_clip_norm=10.0,
# Epsilon
epsilon_start=1.0,
epsilon_end=0.02,
epsilon_decay_steps=5_000_000,
# PER
buffer_capacity=400_000,
per_alpha=0.6,
per_beta_start=0.4,
per_beta_end=1.0,
per_beta_anneal_steps=500_000,
per_epsilon=1e-6,
# Training
total_episodes=80_000,
train_start=1_000,
train_freq=4,
# Eval
eval_every=500,
eval_episodes=50,
# Device
device="cuda",
seed=42,
)Stage 2: Fine-tune from best checkpoint (20k episodes, ~4.5h):
Based on Run 029 (ratio 0.969 — our best result, beats SABRE by 3.1%):
# Load best checkpoint weights only (fresh optimizer, fresh epsilon)
# python main.py train --config configs/run29_finetune_run019.json \
# --finetune outputs/run_019/checkpoints/checkpoint_ep64000.pt
TrainConfig(
topologies=["heavy_hex_19"],
lr=1e-5, # 10x lower than Stage 1
lr_schedule="constant", # No annealing needed
epsilon_start=0.05, # Start low — network already knows routing
epsilon_end=0.01,
epsilon_decay_steps=2_000_000,
buffer_capacity=300_000,
total_episodes=20_000,
train_start=500, # Start training sooner (network is warm)
# All other params same as Stage 1
)The --finetune flag loads only network weights from the checkpoint, keeping a fresh
optimizer at the new LR and fresh epsilon schedule. This avoids restoring the old
optimizer momentum which would fight the new learning rate.
Based on Run 023 (ratio 0.994 in only 60k episodes):
TrainConfig(
lr=1e-4,
lr_schedule="cosine",
lr_min=1e-5,
curriculum_depths=[5, 10, 20],
curriculum_milestones=[0.15, 0.35],
total_episodes=60_000,
epsilon_decay_steps=4_000_000,
# All other params same as Run 019
)Based on Run 026 (ratio 0.996, first multi-topo to beat SABRE):
TrainConfig(
topologies=["linear_5", "grid_3x3", "heavy_hex_19"],
matrix_size=27,
circuit_depth=20,
max_steps=300,
conv_channels=[64, 128, 64],
dueling_hidden=512,
lr=1e-4,
epsilon_end=0.02,
epsilon_decay_steps=5_000_000,
batch_size=128,
buffer_capacity=300_000,
total_episodes=60_000,
train_freq=4,
tau=0.005,
target_update_freq=500,
initial_mapping_strategy="random",
distance_reward_coeff=0.1,
repetition_penalty=-0.5,
)-
Cowtan, A., Dilkes, S., Duncan, R., Krajenbrink, A., Simmons, W., and Sivarajah, S. (2019). "On the Qubit Routing Problem." 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC).
-
Li, G., Ding, Y., and Xie, Y. (2019). "Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices." Proceedings of the 24th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS). Introduces the SABRE algorithm.
-
van Hasselt, H., Guez, A., and Silver, D. (2016). "Deep Reinforcement Learning with Double Q-learning." Proceedings of the 30th AAAI Conference on Artificial Intelligence. Introduces Double DQN.
-
Wang, Z., Schaul, T., Hessel, M., van Hasselt, H., Lanctot, M., and de Freitas, N. (2016). "Dueling Network Architectures for Deep Reinforcement Learning." Proceedings of the 33rd International Conference on Machine Learning (ICML).
-
Schaul, T., Quan, J., Antonoglou, I., and Silver, D. (2016). "Prioritized Experience Replay." Proceedings of the 4th International Conference on Learning Representations (ICLR).
-
Pozzi, M. G., Herbert, S. J., Sherrill, S. S., and Sherrill, A. (2022). "Using Reinforcement Learning to Perform Qubit Routing in Quantum Compilers." ACM Transactions on Quantum Computing. Introduces the distance-based shaping reward used in our reward function.
-
Sutton, R. S. and Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd edition). MIT Press. Chapter 7: n-step bootstrapping.
-
Siraichi, M. Y., Santos, V. F., Collange, S., and Pereira, F. M. Q. (2018). "Qubit Allocation." Proceedings of the IEEE/ACM International Symposium on Code Generation and Optimization (CGO).
-
Mnih, V., Kavukcuoglu, K., Silver, D., et al. (2015). "Human-level control through deep reinforcement learning." Nature, 518(7540), 529-533. Introduces DQN and experience replay.
| File | Purpose |
|---|---|
src/environment.py |
Gymnasium environment: state construction, SWAP execution, reward computation, multi-topology |
src/networks.py |
DuelingCNN: Conv2d feature extractor + dueling V/A streams |
src/dqn_agent.py |
D3QNAgent: action selection, training step, checkpointing, epsilon/LR scheduling |
src/replay_buffer.py |
PrioritizedReplayBuffer + SumTree: O(log n) proportional sampling, uint8 storage |
src/config.py |
TrainConfig dataclass, run directory setup, preset configs |
src/train.py |
Training loop: episode iteration, curriculum, logging, periodic eval, checkpoint saving |
src/evaluate.py |
Evaluation: agent vs SABRE on random + QASMBench circuits, trajectory recording |
src/circuit_utils.py |
Quantum circuit utilities: DAG construction, front layer, coupling maps, SABRE interface |
src/visualize.py |
Training curve and evaluation comparison plotting |
src/explore.py |
Data exploration script: demonstrates the full pipeline interactively |
For a heavy_hex_19 topology with
Channel 0 (Adjacency): Channel 1 (Mapping):
27x27 matrix 27x27 matrix
20 nonzero pairs (edges) 19 nonzero entries (permutation)
Symmetric, constant per episode One 1 per row/column, changes each SWAP
Channel 2 (Gate Demand): Channel 3 (Front-Layer Distance):
27x27 matrix 27x27 matrix
Continuous [0,1], dense Sparse, only front-layer positions
Depth-decayed, position-space 1/distance encoding, symmetric
Channel 4 (Stagnation):
27x27 matrix
Uniform value, increases without gate execution
Resets to 0 on gate execution
Consider a step where the agent SWAPs edge (3, 7) on heavy_hex_19:
| Component | Value | Explanation |
|---|---|---|
| SWAP cost | Always |
|
| Gates executed | Two front-layer gates became routable ( |
|
| Distance shaping |
|
|
| Repetition penalty | Different action from previous step | |
| Terminal bonus | Not done yet | |
| Total | Net positive: productive SWAP |
Compare with a wasted step (SWAP that helps nothing):
| Component | Value | Explanation |
|---|---|---|
| SWAP cost | Always |
|
| Gates executed | No gates became routable | |
| Distance shaping | Moved qubits slightly apart ( |
|
| Repetition penalty | Same SWAP as previous step (undo!) | |
| Total | Strongly negative: agent learns to avoid this |