Qubit Routing

A quantum processor can run a two-qubit gate only between physically adjacent qubits, so a compiler's router inserts SWAP operations to walk logical qubits along hardware edges until each pending gate's operands sit next to each other. Every SWAP costs time and occupies an edge, so routing is a combinatorial scheduling problem: pick which SWAPs to run in parallel each timestep so the whole circuit finishes as early as possible.

The task's environment models real hardware coupling graphs (grid topologies plus the connectivity of IBM Q 16 and Q 20, Rigetti Acorn, and Google Sycamore) and four timing models in which SWAPs and CNOTs lock edges for different durations. Circuits come from synthetic generator families and from real OpenQASM benchmark suites, and the routing engine ships with no router in it: the algorithm is written from scratch.

Implement route_instance(instance) -> list[list[int]] in /app/router.py: the outer list is timesteps, each inner list the indices into instance["edges"] to SWAP in parallel that step. After each timestep the simulator runs any gate whose operands are adjacent on an unlocked edge.

• The initial logical-to-physical layout is fixed, and every gate must finish within instance["max_steps"]; a schedule that leaves a gate unfinished, or that the simulator rejects, counts for nothing.
• Four timing models must be handled: uniform, instant_cnot, slow_cnot_3x, and slow_swap_2x.
• Completing every circuit is the entry ticket; past that, fewer timesteps is strictly better on a smooth curve.
• Each route_instance call gets 10 seconds (an overrun abandons that circuit), and the whole scored run shares a 5400-second budget.
• The router must be ordinary, self-contained Python: the standard library plus the provided package, everything inside /app.

The routing engine at /app/qubit_routing/ (the timestep/edge-lock simulator, the device set, circuit generators, and the instance format, but no router), plus a training split of normalized OpenQASM benchmark circuits at /app/qubit_routing/qasm_training/. Running python3 -m qubit_routing.run (with --limit 50for a quick pass) routes the local circuits with the agent's router.py and writes routing_results.json with circuits finished, timesteps used, and per-call time. /app/README.md documents the contract in full. The machine is offline, and the environment is deliberately dependency-light: Python 3.13 with the standard library only.

A clean-room verifier, separate from the agent's environment, rebuilds the scored package from a pristine baked copy of the engine plus only the agent's own .py files (anything shadowing the engine is dropped), then generates a hidden, deterministically seeded instance pool spanning the same devices, timing models, and circuit families, but on held-out OpenQASM circuits and fresh synthetic seeds. The candidate driver runs de-rooted with the 10-second per-call cap, and every returned schedule is independently re-simulated on the pristine engine before it can score.

• Per instance: zero unless the re-simulated schedule is valid and completes every gate; then zero at a trusted greedy baseline, full credit at a precomputed CP-SAT reference target, with 2**u - 1 in speedup space between the two.
• The aggregate is a weighted mean in which synthetic and OpenQASM instances contribute 50/50; unrouted instances contribute zero.
• The greedy baseline and CP-SAT targets live root-only in the verifier image, the scorer never imports code from /app, the reward directory is locked before any agent code runs, and stray agent processes are killed before scoring.
• A missing router.py or a package-boundary violation zeroes the result.