Paper deep dive
Efficient LLM-Generated Shuttling Compilers for Complex Trapped-Ion Architectures
Fabian Kreppel, Reza Salkhordeh, Ferdinand Schmidt-Kaler, André Brinkmann
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Trapped-ion quantum computers rely on shuttling compilers, which cast an input algorithm into a sequence of ion-qubit movements within a given architecture. We present the first study in which a single frontier large language model (LLM), Claude Opus 4.7, generates and iteratively refines the full Python code of shuttling compilers from written specifications. We start with a compiler for (i) a linear segmented trap, extend it to (ii) a trap with junctions, and finally achieve efficient compilation for (iii) a broad class of connected trap graphs. The compilers for the more general cases are seeded with code from the previous ones. We benchmark the LLM-generated compilers against state-of-the-art hand-crafted ones using a common suite of quantum circuits. The number of shuttling timesteps is reduced by up to 76% for (i) and up to 39% for (ii). For the broad case (iii) of freely connected architectures, we find large variations in the required number of shuttling timesteps, depending on the connectivity. A densely connected, junction-rich architecture yields an order-of-magnitude reduction in shuttling timesteps compared to a corridor-like one. Repeating the complete generation and evaluation with a second frontier LLM, Claude Fable 5, reproduces these findings, with the Fable 5 compilers surpassing the hand-crafted ones more often on the largest circuits. Our results show that an unmodified frontier LLM can produce working, correct, and competitive shuttling compilers without additional manual algorithmic engineering, thus reducing the development time for new architectures from several months to a few days.
Tags
Links
- Source: https://arxiv.org/abs/2607.24714v1
- Canonical: https://arxiv.org/abs/2607.24714v1
Trouble viewing inline? Open PDF directly →
Full Text
318,819 characters extracted from source content.
Expand or collapse full text
Efficient LLM-Generated Shuttling Compilers for Complex Trapped-Ion Architectures Fabian Kreppel, 1, a) Reza Salkhordeh, 1, b) Ferdinand Schmidt-Kaler, 2, c) and André Brinkmann 3, d) 1) Institute of Computer Science, Johannes Gutenberg University, Mainz, Germany 2) Institute of Physics, Johannes Gutenberg University, Mainz, Germany 3) Department of Computer Science, Saarland University, Saarbrücken, Germany Trapped-ion quantum computers rely on shuttling compilers, which cast an input algorithm into a sequence of ion-qubit movements within a given architecture. We present the first study in which a single frontier large language model (LLM), Claude Opus 4.7, generates and iteratively refines the full Python code of shuttling compilers from written specifications. We start with a compiler for (i) a linear segmented trap, extend it to (i) a trap with junctions, and finally achieve efficient compilation for (i) a broad class of connected trap graphs. The compilers for the more general cases are seeded with code from the previous ones. We benchmark the LLM-generated compilers against state-of-the-art hand-crafted ones using a common suite of quantum circuits. The number of shuttling timesteps is reduced by up to 76 % for (i) and up to 39 % for (i). For the broad case (i) of freely connected architectures, we find large variations in the required number of shuttling timesteps, depending on the connectivity. A densely connected, junction-rich architecture yields an order-of-magnitude reduction in shuttling timesteps compared to a corridor-like one. Repeating the complete generation and evaluation with a second frontier LLM, Claude Fable 5, reproduces these findings, with the Fable 5 compilers surpassing the hand-crafted ones more often on the largest circuits. Our results show that an unmodified frontier LLM can produce working, correct, and competitive shuttling compilers without additional manual algorithmic engineering, thus reducing the development time for new architectures from several months to a few days. I. INTRODUCTION Trapped-ion quantum computing (QC) comes with the advantage that ion qubits are moved between different sections of a scalable architecture 1–10 to execute an algo- rithm efficiently. Such QC architectures are based on linear segmented traps with qubit storage and opera- tion zones 4,6–8 , racetrack loops 9 , or multiple junctions 10 . Shuttling compilers 11–23 require substantial engineering effort by domain experts for each specific architecture as the QC hardware grows in complexity and connectivity. Here, we investigate whether this per-layout effort can be replaced by code generation. Rather than having an expert engineer each compiler, a state-of-the-art general- purpose large language model (LLM), Claude Opus 4.7 24 , writes the compiler’s full Python code from a specifica- tion given in a single prompt. We demonstrate our novel approach on multiple architectures of strictly increasing generality, shown in Fig. 1: (i) a linear segmented shut- tling architecture with a central qubit operation zone, (i) an architecture with multiple junctions, and (i) a broad class of connected trap graphs, including dense ar- chitectures with multiple ion transport options. Follow- up prompts then refine each emitted compiler to lower the total number of shuttling timesteps for a given al- gorithm, thus improving its QC runtime. Generating a compiler this way is far more time-efficient than writing a) Electronic mail: f.kreppel@uni-mainz.de b) Electronic mail: rsalkhor@uni-mainz.de c) Electronic mail: fsk@uni-mainz.de d) Electronic mail: andre.brinkmann@uni-saarland.de one by hand. A hand-crafted shuttling compiler takes several months to develop, whereas writing the specifica- tion and generating the compiler with LLM support cuts this effort to a few days per architecture. A QC encodes each qubit in a single ion, so we will use “qubit” and “ion” interchangeably. The ions are confined in a segmented microchip trap 25 , where electrodes can be fed with control voltages to define localized potential wells. Changing these control voltages reshapes the wells and shuttles ions from one segment to the next. In a similar way, ions can be passed through junctions. We represent the trap as a graph whose vertices are its seg- ments and whose edges connect segments between which an ion can shuttle. A segment is either a qubit segment or a gate segment, at which single- and two-qubit oper- ations are executed. Each segment holds at most two qubits in an ordered chain, and a gate is applied by laser or microwave pulses once a gate segment holds exactly the qubits the gate acts on. In this work, we deliberately choose a single gate segment for architectures (i) to (i) in order to focus on the shuttling challenge alone, set- ting aside the problem of scheduling simultaneous gates across several gate segments. That task couples routing with parallel gate scheduling, and we leave it to future work. A single gate segment is also the hardest shut- tling regime, since every gate must be routed to it, with no second gate segment to share the load. This restric- tion reflects current hardware, on which the number of gate segments is still very limited 6,23 , though multi-gate- segment devices have recently been realized 9,10 . The different layouts are distinguished by their connec- tivity. In a linear array 4,6–8 or a racetrack loop 9 , every segment has just two neighbors, so the qubit count rises arXiv:2607.24714v1 [quant-ph] 27 Jul 2026 2 empty seed Linear ar- chitecture Sec. IV Branched ar- chitecture with junctions and stacks Sec. V General archi- tecture graph Sec. VI general compiler prompt final code + new prompt final code + new prompt follow-up optimizations follow-up optimizations follow-up optimizations 01234568910111213147 01346810111314259127 15 16 17 18 19 20 21 22 stack height junction distancejunction distance 1 2 3 4 56 7 8 9 10 0 0 1 2 3 4 5 6 7 891001 234 567 8910 0 12 3 45 6 7 8 9 10 11 cycletwo_cycles_bridged theta figure8 1 3 4 58 9 10 12 0 2 67 11 01 23 456 9 10 11 12 1516 7 8 13 14 01 23 45 67 8910 11 12 13 14 15 1617 18 1920 2122 0 1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 121314 15 18 19 22 23 26 16 1720 21 24 25 cycle_with_two_chordscomplete_graphhypercubebutterfly Fig. 1. Overview of the approach. The three shuttling compilers are generated in a chained sequence of increasing architectural generality: from top to bottom, a linear architecture (Sec. IV), a branched architecture with junctions and stacks (Sec. V), and a general architecture (Sec. VI). Each subsequent compiler is seeded with the previous one’s optimized code together with a written specification of what must change, while the linear-architecture compiler starts from scratch. Each emitted compiler is then refined through follow-up optimization prompts that target timesteps, compile time, and memory use. Beside each stage, we draw the corresponding architecture, in which qubit segments (yellow) connect to gate segments (red) and junction segments (green). In the butterfly architecture, vertices 0 to 3 appear on both sides and denote the same four vertices. only with the physical length of the chip. Junctions 26–29 raise this limit by allowing a segment to connect to sev- eral others 30–33 . For example, the most advanced QC processor, Quantinuum Helios, realizes a singleX junc- tion connecting a ring-shaped storage region to two lin- ear segmented sections 10 . Adding multiple junctions drives the architecture toward two-dimensional quantum charge-coupled device (QCCD) designs 34 . Our choice of architectures follows this increase in connectivity. The compilation can be separated into two steps: First, a circuit compiler 35 expresses the quantum circuit in the QC’s native gate set, fixing a gate order (the program or- der) along with other transpilation optimizations. In the following step, a shuttling compiler identifies which ions should encode which qubits 11–13,19,36,37 and how to move and rearrange the ions in the trap architecture to execute the sequence as efficiently as possible. Thus, this com- piler derives a shuttling schedule, an ordered sequence of ion movements consistent with the trap’s connectiv- ity. The schedule is assembled from four reconfiguration primitives: • Translate moves the qubits in a segment to an adjacent segment. • Separate splits the two qubits in a segment, send- ing one to each of its neighbors. • Merge brings one qubit into a segment from each of its neighbors. • Swap reverses the order of the two qubits in a seg- ment. 3 Separation, merge, and swap can be performed only at the gate segment, as they require precise calibration of the trap potentials. Gate and shuttling operations are never executed in parallel. At every step of compilation, the next gate to schedule is chosen from the set of ready gates: gates for which every predecessor on each of their qubits, if any, has already been executed. Choosing the gate order at this stage, rather than adopting the pro- gram order fixed upstream by the circuit compiler 35 , lets the shuttling compiler exploit the current ion placement, which is unavailable earlier. It thereby relaxes the other- wise strict compilation boundary. Shuttling compilers have so far been written by hand for linear segmented traps 11,12,14,15 , for architec- tures with junctions 16 , and for other layouts 17–22 . Re- cent approaches pursue architecture independence either through a hand-designed graph abstraction paired with a generic routing heuristic 38–40 or through an attempt to teach the LLM itself to output a shuttling schedule 41 , though in the latter case complete schedules were ob- tained only for circuits with few qubits. Here, we employ an unmodified frontier LLM and let it write Python code from prompt inputs that define the specifications. The LLM is consulted only at build time, but the generated Python shuttling compiler compiles any quantum circuit. This allows us to verify the cor- rectness of the LLM-generated compiler code as a whole, as we would for any other source code. It needs no fine-tuning data, compiles every benchmark circuit in full, with the largest reaching 50 qubits and no inher- ent circuit-size limit, and extends beyond the linear and branched architectures to a general class of connected trap graphs. These properties make the proposed ap- proach well-suited for shuttling compilation. Whether they depend on the particular LLM is then checked against a second frontier model, Claude Fable 5 42 . The paper is organized as follows. Sec. I reviews prior work on shuttling compilation and learning-based rout- ing. Sec. I describes the prompting protocol and the benchmark setup. Sec. IV, Sec. V, and Sec. VI then present the linear-, branched-, and general-architecture compilers, each from its prompt and emitted compiler through optimization to its benchmark results, with the last also comparing the trap architectures. The Opus 4.7 generation run is then compared with its Fable 5 replica- tion in Sec. VII. Sec. VIII concludes the paper. I. RELATED WORK In a quantum circuit, any qubit may eventually inter- act with any other. No platform can achieve this di- rectly, and a general all-to-all coupling would in any case lead to increased gate and memory errors. Shuttling- based trapped-ion and optical-tweezer architectures can adapt the connectivity between qubits as the circuit runs, by physically moving the qubits between operation sites. For such architectures, the circuit is first expressed and possibly optimized in software such as Qiskit 43 , t|ket⟩ 44 , Cirq 45 , or PennyLane 46 , and this output is then passed to the shuttling compiler, which assigns qubits to ions and produces the schedule of ion movements. A single gate then generally requires an entire sequence of oper- ations drawn from the four distinct shuttling primitives, and these operations are further constrained by the lim- ited capacity of each segment. Due to the large search space, heuristic approaches have been developed to min- imize the number of shuttling operations. Typically, such compilers work with one specific architecture 7,9–23 . One of our compilers instead targets general architectures, a goal shared by several recent approaches. SHAW and SHAPER 38 aim for a single compiler that handles many architectures. Their gen- erality is based on a position graph, a unified abstrac- tion of a trap’s operation sites and movement paths, to- gether with the constraints on routing ions between them. Onto this graph they transfer the SWAP-based SABRE heuristic 47 from superconducting-qubit routing, extend- ing it from fixed qubits on a coupling graph to dynam- ically shuttled ions, with SHAW performing a heuristic search and SHAPER a permutative one. A later variant scales the search to larger circuits by caching repeated computations, which speeds up the SABRE-based meth- ods without changing their routing decisions 39 . Simi- larly, S-SYNC 40 casts the whole QCCD device as a static connectivity graph and reformulates shuttling as generic SWAP-gate insertion, so that a heuristic scheduler jointly minimizes shuttling and swapping. A different hardware model is addressed by the MQT IonShuttler, which schedules shuttling on a two- dimensional QCCD grid with one or more dedicated pro- cessing zones. It solves small single-zone instances ex- actly via Boolean satisfiability 48 and larger or multi-zone ones heuristically 21,22 . It moves ions by rotating them around grid loops through empty sites and executes gates in the processing zones. Each memory site holds a single ion, and two-qubit gates are executed by shuttling both ions into a processing zone, with any reordering handled by rotation around the loops. Separation, merge, and swap operations are therefore not required. A separate direction targets the parallelism of grouped ion transport, with the FluxTrap framework 49 aggregat- ing SIMD-style intra-trap shifts and junction transfers to parallelize ion movement on two-dimensional trapped- ion machines. Compilation has also been pushed to multi-SIMD platforms, where regions communicate by teleportation 50 , and to distributed architectures, whose traps exchange qubits over photonic links 51 . Routing on fixed-connectivity platforms such as super- conducting processors takes a different form, where the qubits remain fixed on a coupling graph and routing re- duces to inserting SWAP gates. Learning-based methods have been explored extensively for this setting 52–63 . Un- like these platforms, shuttling architectures change their connectivity as the ions move. 4 parse_input() reads and parses the input Input: circuit file, architecture, gate vertex Output: TrapGraph, list of QuantumGate initial_mapping() assigns qubits to vertices Input: TrapGraph, qubits, list of QuantumGate Output: initial mapping compile() routes gates, groups moves into timesteps Input: initial mapping, TrapGraph, qubits, list of QuantumGate Output: shuttling schedule validate_and_output() checks the shuttling schedule and writes it out Input: shuttling schedule, initial map- ping, TrapGraph, qubits, list of QuantumGate Output: output file compilation pipeline TrapGraph vertices adjacency of vertices distances between vertices shortest paths between vertices qubit vertices gate vertices junction vertices . . . QuantumGate operation qubits gate acts on parameters gate id list of QuantumGate in program order data classes builds used by Fig. 2. Structure of the single-file compiler ion_trap_compiler.py. Boxes in green are the provided, fixed components that the LLM may not change: the outer functions parse_input and validate_and_output and the data classes TrapGraph and QuantumGate. Boxes in blue are the two functions written by the LLM: initial_mapping and compile. The shaded frame groups the QuantumGate objects into the list the pipeline passes along. Solid arrows follow the compilation pipeline, and dashed lines show which data-class objects each function builds or uses. Of TrapGraph’s query methods, the figure shows only those shared by all three compilers. I. SETUP This section sets out the prompting protocol and benchmark setup shared by the three compilers. The compilers themselves are then presented in turn in Sec. IV, Sec. V, and Sec. VI. A. Prompting protocol The compilers in this paper are generated using Claude Code, Anthropic’s command-line agent, running Claude Opus 4.7 24 as the underlying LLM. The LLM is used unmodified, without fine-tuning or retrieval augmenta- tion, and the only in-context tools available to it are the file-reading and file-editing primitives exposed by Claude Code. Each compiler is generated through a single con- versation. The first prompt gives the LLM a written specification together with the circuit and architecture files used by the acceptance tests and asks for a com- plete Python implementation in a single file. None of the prompts leaves the algorithmic design to the LLM. Each sets out a complete algorithm, based on the hand-crafted compilers 11,16 , as the required default that the LLM im- plements and later refines. The linear- and branched- architecture prompts additionally invite further strate- gies to be layered on top, provided they perform no worse than the default. Fixing the algorithm this way is neces- sary, since Opus 4.7 did not produce a working compiler in preliminary tests without one. For an unbiased com- parison, the Fable 5 replication run of Sec. VII keeps the same prompts, although Fable 5 might not share this lim- itation, and prompts leaving more of the design open to it could yield better results. The full prompt for each compiler appears in Appendices A, B, and C. This first prompt is always issued at medium reasoning effort. In every follow-up prompt we ask the LLM to identify code- level optimizations that reduce shuttling timesteps, com- pile time, and memory use, then apply them in place. These follow-up prompts use medium or extra-high rea- soning effort to expose the trade-off between optimization depth and the LLM’s own runtime. Every prompt builds on a Python file named ion_trap_compiler.py, which the LLM adapts and ex- tends. Its structure is illustrated in Fig. 2. The compila- tion pipeline runs through four functions, from the input files to the shuttling schedule. parse_input reads and parses the input, constructing the objects that every later step uses: a single TrapGraph for the whole architecture and a list holding one QuantumGate per circuit gate in program order. initial_mapping assigns the qubits to 5 vertices, and compile then routes the gates and groups the resulting moves into timesteps (the parallelized shut- tling steps a circuit takes to run) to produce the shut- tling schedule. Finally, validate_and_output checks this schedule and writes it out. The two outer func- tions parse_input and validate_and_output, together with the two data classes TrapGraph and QuantumGate, are provided and may not be changed by the LLM. TrapGraph also exposes many query methods that the compilers use. The LLM writes only the two functions in between, initial_mapping and compile, whose in- terfaces and full specification are fixed in every prompt. When one compiler is seeded from the previous one, these two function bodies are the only parts it adapts and ex- tends. The three compilers are generated in a chain, each building on its predecessor. Starting from scratch, the LLM produces the linear-architecture compiler from the first prompt and the provided helper functions alone. Each later compiler is then seeded with the previous one’s optimized Python file, in which the provided helper functions and data classes are swapped for their new- architecture versions while the LLM’s initial_mapping and compile are carried over unchanged. Because this file sits in the working directory, Claude Code reads and edits it directly, and the prompt asks the LLM to adapt and extend only those two functions in place. Each adap- tation prompt treats the seed as the source of truth for everything that stays unchanged and describes only what must change. Because it names the unchanged features from the earlier specification rather than from the seed’s code, it can list a feature the seed lacks as one to keep, and the LLM then carries that gap forward rather than filling it. Every first prompt also contains a working example and an acceptance-test matrix, both built from given in- put files in the working directory. The working exam- ple specifies one circuit, one architecture, and the gate vertex, together with the exact bound the schedule must meet. The matrix itself is a list of circuit-and-graph pairs that the compiler must run successfully, drawn from the benchmark circuits and a few small hand-written checks. Some carry a tight bound, such as zero swaps for a chain- like circuit. The full matrix for the linear- and branched- architecture compilers is given in Tab. I and Tab. IV. For the general-architecture compiler, whose evaluation spans many layouts, the matrix graphs are not the eval- uation instances themselves but are built from the same construction rules, as described in Sec. VI A. Each sched- ule is then checked by validator functions the LLM is not allowed to modify. The LLM therefore debugs its own code against the tests during generation, and ev- ery reported result is a schedule it both produced and validated. Sec. IV, Sec. V, and Sec. VI present the three compil- ers in a common structure. Each section opens with a specification that summarizes the corresponding prompt and states the task we set for the LLM, with the full prompt reproduced in the appendix. The section then reports the emitted compiler, noting where it follows or departs from that specification, and then presents its op- timizations. These come from the follow-up prompts we issue, which ask only for code-level improvements. The LLM itself decides which changes to make, and we then describe them. Each section closes with the compiler’s evaluation. B. Evaluation setup We benchmark every generated compiler on two cir- cuit sets. The first is a library of 153 quantum circuits 64 with 3 to 16 qubits. The second comprises five fami- lies of scalable circuits with up to 50 qubits: Quantum Approximate Optimization Algorithm (QAOA) 65 , Quan- tum Fourier Transform (QFT) 66 , Cross-Entropy Bench- marking (XEB) 67 , a Sycamore-specialized XEB variant (XEB_Sy) 68 , and Quantum Volume (QV) 69 . Of these, the QAOA, QFT, XEB, and XEB_Sy circuits are gen- erated with a circuit generator 70 , the QV circuits with Qiskit 43 , and every circuit is transpiled into a trapped- ion native gate set by a circuit compiler 35 . Each circuit of n qubits is compiled on an architec- ture with 2n + 1 non-junction segments. The linear and branched architectures follow a previously published construction 16 . In the linear architecture, the gate seg- ment sits at the center. The branched architectures are mirror-symmetric about that single central gate segment and are parameterized by a stack height h, the number of segments in each side-stack, and a junction distance d, the spacing between consecutive junctions along the main axis. Both parameters are shown in Fig. 1. Each is built outward from the gate segment on both sides: first a qubit segment for separation and merge, then a stack, then a further stack after every d segments of the main axis, with the qubit segments split equally between the two sides. Segments beyond a side’s share extend the main axis instead, and the construction stops once no qubit segment is left. We vary h up to 10 and d up to 4 on the circuit library, and h up to 45 and d up to 50 on the scalable families. Once d > n− 2−h, only one stack fits per side, so all larger distances yield the same archi- tecture and are evaluated once. A stack of more than n− 2 segments does not fit, so such heights are skipped. The general-architecture compiler of Sec. VI is evalu- ated on ten layouts: the eight cyclic families of Fig. 1 together with the linear and branched architectures. Three of the cyclic families are built from classical in- terconnection networks, though not in their original form: a complete graph on four vertices, the three- dimensional hypercube 71 , and the two-dimensional but- terfly network 71 . The vertices of these networks are pre- dominantly junctions, which cannot store qubits persis- tently for technical reasons 28 , so edges are subdivided by paths of non-junction segments, as shown in Fig. 1. This subdivision also lets the otherwise fixed networks scale, 6 q 0 q 1 q 2 q 3 g 1 g 2 g 3 g 4 g 5 (a) example circuit g 1 g 2 g 3 g 4 g 5 (b) circuit-DAG q 0 q 1 q 2 q 3 4 3 1 2 1 1 4 (c) qubit-interaction graph Fig. 3. Construction of the circuit-DAG (b) and the qubit-interaction graph (c) from an example circuit (a). since the number of inserted segments grows to give each instance the 2n + 1 non-junction segments required for an n-qubit circuit. Two state-of-the-art hand-crafted compilers serve as references, one for the linear architecture 11 and one for the branched one 16 . Each is a heavily optimized heuris- tic for exactly the layout its LLM-generated counterpart targets, and operates under the same hardware limits as our compilers, namely a single gate segment, two qubits per segment, and the confinement of separation, merge, and swap to the gate segment. Both were evaluated on the same benchmark circuits, so the comparison is di- rect. In contrast to the generated compilers, which pick a gate from the ready set at each step, the baselines ex- ecute a circuit’s gates in the input order. The branched- architecture baseline further uses its junctions to push translation, separation, and merge counts below the lin- ear figures and to eliminate physical ion swaps outright on its targets, which makes it an especially stringent ref- erence. It is also limited to a single stack per junction, whereas the generated compiler handles junctions that carry several stacks. For every schedule we record the number of timesteps, our primary objective, with the translation, separation, merge, and swap counts. The timestep reduction factor is the timestep count of the reference divided by that of the optimized compiler, where the reference is either a hand-crafted baseline or the emitted compiler. A value above 1 therefore means the optimized LLM-based com- piler outputs fewer timesteps. In the text we summarize a circuit set by the median of its per-circuit reduction factors rather than by their average or by the ratio of summed timesteps over the suite, since both alternatives are dominated by the few largest circuits, whose timestep counts outweigh the rest. IV. LINEAR SHUTTLING ARCHITECTURE A. Specification This specification summarizes the prompt, which is re- produced in full in Appendix A. The prompt defines the architecture as a linear chain of vertices, each either a qubit vertex or a gate vertex, and provides the four shut- tling operations of Sec. I, together with a gate-execution operation that runs the corresponding one- or two-qubit gate when a gate vertex holds exactly the required qubits. The architecture files place a single gate vertex at the center of the chain, as drawn in Fig. 1. Building on these definitions, the prompt describes the compiler in three parts. The initial mapping maps each of the n qubits to a vertex subject to three rules inherited from the linear baseline 11 . At most two qubits sit on a vertex, exactly ⌈ n 2 ⌉ vertices hold qubits, and every other vertex is left empty. To compute the mapping, two distinct graphs are derived from the circuit, both shown in Fig. 3 for an example circuit. The first is a directed acyclic graph (DAG), the circuit-DAG, whose nodes are the gates of the circuit and whose edges encode the program-order dependency between two consecutive gates that share a qubit. A gate’s depth in the circuit-DAG is the length of the longest directed path from any source node to it. The second is the qubit-interaction graph, an undirected graph whose nodes are the qubits. Its edge weight be- tween two qubits q and q ′ is the sum, over every two- qubit gate that acts on q and q ′ , of a depth-based weight 1 1+δ/τ , where δ is the gate’s circuit-DAG depth. Here τ ≈ total_dag_depth 3 , and total_dag_depth is the largest gate depth in the circuit-DAG. This depth-weighting bi- ases the mapping toward interactions that occur early in the circuit, where the initial mapping has the largest ef- fect on schedule length. The matching is then computed greedily on the qubit-interaction graph. The heaviest edge whose two qubits are both still unmatched is picked, those two qubits are matched into a pair, and the proce- dure repeats until no such edge remains. In the example of Fig. 3, gates g 1 and g 2 have depth 0, g 3 has depth 1, g 4 has depth 2, and g 5 has depth 3, so with τ = 1 their depth-based weights are 1, 1, 1 2 , 1 3 , and 1 4 . Summing the gate weights for each pair gives q 0 -q 1 a weight of 1 + 1 3 = 4 3 from g 1 and g 4 , q 2 -q 3 a weight of 1 from g 2 , q 1 -q 2 a weight of 1 2 from g 3 , and the pair q 0 -q 2 a weight of 1 4 from g 5 . The greedy matching therefore pairs (q 0 ,q 1 ) and (q 2 ,q 3 ), leaving the lighter q 1 -q 2 and q 0 -q 2 edges unused. 7 When the number of qubits is odd, one qubit cannot be matched and is left as a singleton. The prompt spec- ifies that the singleton is the qubit with the lowest total interaction weight across all its edges. A chain extraction then orders these pairs and the singleton by greedily ap- pending the matched pair with the heaviest connecting weight to the running chain, and the chain is placed on consecutive vertices in that order. The one exception is the first gate to execute. If it is a two-qubit gate, its two qubits are placed directly on the gate vertex, so that this gate runs with no preceding shuttling, and the gate ver- tex’s two neighbors are left empty so that a subsequent Separate has room to split the pair. Once the initial mapping has placed every qubit on its starting vertex, the routing begins, which iteratively brings each gate’s qubits together at the gate vertex. At every scheduling step the next gate is chosen from the set of ready gates. Among them, the compiler prefers a gate that acts on the same qubit set as the one just executed, so a run of gates on one pair completes without re-shuttling. Otherwise it takes the gate whose qubits lie closest to a gate vertex, with ties broken in favor of the gate that appears earliest in the input circuit. For a single-qubit gate, the routine is simple. If the tar- get qubit shares its vertex with another qubit, the pair is first moved to the gate vertex and split with a Sep- arate, which sends each qubit to a neighboring vertex. The target qubit then moves back onto the gate vertex, where the gate executes. For a two-qubit gate, the qubits sitting strictly be- tween its two endpoints on the current layout form an ordered set of intermediates that must be cleared before the gate can execute. The intermediates are removed one at a time by a Merge-Swap-Separate cycle on the gate vertex. Each cycle advances whichever endpoint the prompt estimates to be cheaper, a choice it allows to be re-evaluated every round. Before each cycle, that end- point and its adjacent intermediate must each sit alone at its current vertex. If either of them shares its ver- tex with another qubit, the pair is first moved to the gate vertex and split with a Separate. The cycle then proceeds in three steps. A Merge combines the end- point and the intermediate at the gate vertex, a Swap reverses that chain, and a Separate sends them back out with their positions exchanged. Each cycle moves the endpoint one position closer to its partner and the intermediate one position farther away, so the interme- diate set shrinks by one. In the special case where the endpoint already shares its vertex with its adjacent in- termediate, the Merge is skipped: moving the pair to the gate vertex and applying only the Swap and Sepa- rate accomplishes one cycle iteration on its own, so the intermediate set shrinks by one without a full Merge- Swap-Separate cycle. After at most k cycles, where k is the initial size of the intermediate set, a final Merge brings the two endpoints together at the gate vertex, and the gate executes. Once the gate has run, the prompt asks the compiler Tab. I. Acceptance-test matrix for the linear-architecture compiler. Each architecture is a linear path with the listed number of vertices whose central vertex is the gate vertex, and n is the circuit’s qubit count. The generated compiler must pass all eight tests. T1–T3 additionally carry the tight schedule bounds shown. The rest need only run to a valid schedule, apart from the compile-time and swap conditions given for T4 and T5. Test Circuitn Gates Vertices Expected T1 working example 337 ≤ 16 ops, ≤ 12 steps T2 same_pair2105 no shuttling T3 qaoa_553511 no swaps T4 rd32-v0_664429 runs, < 1 s T5 4mod5-v1_23510211 runs, swaps > 0 T6 4mod5-bdd_287710615 runs T7 alu-v2_31564011 runs T8 cnt3-5_1791623033 runs to consider a one-step post-execution lookahead Swap at the gate vertex. While the chain order is irrelevant for gate execution, it influences the routing cost of the next gate touching either qubit. For each of the two qubits, the prompt defines its preferred side of the gate vertex as the side that currently holds its next two-qubit-gate partner, with no preferred side when there is no such partner. The compiler inserts a Swap when this flip places more qubits on their preferred side than the no-Swap arrangement does. The post-processing exists because the routing emits a plain sequential stream of operations. The hand-crafted compilers 11,16 determine directly during routing which operations run in parallel within each translation phase between two non-translation operations. Splitting rout- ing and grouping into two steps keeps the prompt simpler for the LLM, and once the full stream is known, unnec- essary operations can be eliminated as well. The post- processing therefore applies two reduction passes followed by a grouping pass. Roundtrip elimination removes a Translate A → B immediately followed by B → A whenever no operation between them touches A or B. Consecutive cancellation removes an adjacent Separate and Merge in either order and a double Swap at the gate vertex. These two passes are alternated until nei- ther removes any further operation, at which point a final grouping pass assembles the operations into timesteps. To fill a timestep the grouper may pull a later operation forward past operations it does not touch, as long as that operation does not conflict with the timestep being built or with any operation skipped over on the way. Transla- tions may chain: a Translate A→B and a Translate B→C fit in one timestep, since B is vacated in the same step it is filled. In effect, this combines independent and chained Translate moves into one translation timestep, while non-translation operations each occupy their own timestep, since any two of them share the single gate vertex. The prompt closes with the acceptance-test matrix of eight benchmark circuits listed in Tab. I. Three carry tight bounds. The first is a working example that must hit fixed operation and timestep counts, the second a 8 same-pair circuit with all gates on one qubit pair that must produce zero shuttling, and the third a QAOA cir- cuit with chain-like qubit interactions that must produce zero swaps. Each of the remaining five, of varying qubit and gate counts, only needs to execute successfully, with a compile-time guard on one and a swap-count check on another. B. Emitted compiler The emitted compiler structurally implements every block of the prompt, passes all acceptance tests on the first attempt with their bounds preserved, and produces a deterministic schedule. Its initial mapping makes two choices the prompt’s placement rule leaves open, both to shorten routing. Within each pair it orients the qubit that interacts more strongly with the neighboring pairs toward those pairs, and it centers the chain on the gate vertex. The only deviation from the prompt is the spe- cial case described above, where the endpoint already shares its vertex with its adjacent intermediate and the Merge can be skipped. Rather than take that short- cut, the emitted compiler isolates the two and runs a full Merge-Swap-Separate cycle. It reaches the same end state with more operations. C. Optimized compiler We initiate every optimization round, here and in the later compiler sections, with a follow-up prompt that asks the LLM to identify code-level improvements reducing timesteps, compile time, and memory use. Two opti- mizations change the emitted schedule. The larger is a Tab. I. Linear architecture, circuit library: metrics summed over all 153 library circuits, for the linear-architecture com- piler, the general-architecture compiler, and the hand-crafted baseline 11 . The lowest value per column is in bold. All values are rounded to thousands. CompilerTimesteps Translate Separate Merge Swap Linear, emitted14,768k7,242k 1,796k 1,796k 1,072k Linear, optimized 12,475k 4,977k 1,783k 1,782k 1,071k General, emitted17,513k8,413k 2,364k 2,364k 1,509k General, optimized 20,243k9,727k 2,836k 2,835k 1,984k Baseline 11 16,737k8,574k 2,056k 2,056k 1,189k Tab. I. Linear architecture, scalable families: suite-total timesteps per family, summed over all circuits of each family, for the linear-architecture compiler, the general-architecture compiler, and the hand-crafted baseline 11 . The lowest value per family is in bold. All values are rounded to thousands. CompilerQAOA QFTQVXEB XEB_Sy Linear, emitted6k 111k 1,076k 2,196k4,066k Linear, optimized4k 80k 806k 1,480k2,734k General, emitted18k 237k 1,096k 3,151k6,185k General, optimized18k 254k 1,150k 3,907k6,651k Baseline 11 6k 317k930k 2,144k4,544k mirror-mapping trial-compile on the initial mapping. A placement and its left-right mirror can compile to dif- ferent lengths even though the architecture is symmet- ric. The router’s tie-breaks favor the lower-numbered vertices rather than resolving by a reflection-invariant rule, so the two orientations are not routed identically. One is often shorter, with no way to tell which without compiling. The LLM therefore compiles both the default mapping and its mirror and returns the shorter sched- ule. It is the only strategy the LLM layers on top of the required default, an addition of the kind the prompt in- vites without naming. The second, smaller change adopts the prompt’s dedicated routine for the special case where an endpoint shares a vertex with its adjacent intermedi- ate, replacing the emitted compiler’s isolate-then-cycle handling. The remaining changes are lower-level perfor- mance and memory optimizations that leave the emitted schedule unchanged. D. Evaluation The suite totals for the linear-architecture compiler as emitted and as optimized, for the general-architecture compiler, and for the hand-crafted baseline appear in Tab. I for the circuit library and in Tab. I for the scalable families. We include the general-architecture compiler here, ahead of its own presentation in Sec. VI, so that it can be compared directly with its specialized counterpart. a. Emitted versus optimized compiler. The follow- up optimizations shorten the library circuits by a median factor of about 1.16, with the reduction almost entirely in translations. It comes from the mirror-mapping trial- compile of Sec. IV C. Per family, the median emitted-to- optimized factor is about 1.3 for QAOA, QFT, and QV, and 1.4 for XEB and XEB_Sy. The mirror trial roughly doubles the per-circuit compilation work, partly offset by the accompanying performance optimizations, so the optimized compiler is usually slower to compile than the emitted one. b. Optimized LLM-based compiler versus the hand- crafted baseline. The optimized linear-architecture com- piler outperforms the baseline on the vast majority of circuits, by a median factor of about 1.2 on the circuit library and, per scalable family, about 1.2 for QAOA and QV, 1.4 for XEB, 1.5 for XEB_Sy, and 3.6 for the all-to-all QFT. Across the circuit library, the per-circuit reduction factors, plotted in Fig. 4, run from about 0.8 to about 1.9, with values below 1.0 only on the few cir- cuits where the baseline still comes out shorter, and the least-squares fit rises with the qubit count. Most of the saving comes from translations, with smaller reductions in separations, merges, and swaps. This advantage comes from where the gate order is decided: rather than rout- ing an order fixed by the circuit compiler, as the baseline does, the generated compiler chooses the next gate it- self, from the ready set, while it routes, ordering gates 9 345678910111213141516 number of qubits 0.8 1.0 1.2 1.4 1.6 1.8 timestep reduction factor mean = 1.20 median = 1.19 least-squares fit Fig. 4. Linear architecture, optimized LLM-based compiler versus the hand-crafted baseline 11 on the 153 library circuits. Each circuit’s reduction factor is plotted against its qubit count. The dashed line marks factor 1, and the red, pur- ple, and green lines mark the mean, the median, and a least- squares fit. to suit the current ion placement. The QFT, with its many long-range interactions, is where that fixed order- ing costs the baseline most. Its reduction factor climbs from near 1.1 at the smallest sizes to about 4.2, or 76 % fewer timesteps, at 40 to 50 qubits. QAOA rises more gently, QV and XEB stay between about 1.0 and 1.6 re- gardless of size, and XEB_Sy grows from just below 1.0 at its smallest instance to about 1.7 at the largest sizes. Compile times are comparable to the baseline’s or shorter on most circuits, but several times longer on the larger QV, XEB, and XEB_Sy circuits. V. BRANCHED SHUTTLING ARCHITECTURE WITH JUNCTIONS A. Specification The prompt for the branched-architecture compiler, which appears in Appendix B, gives the LLM its opti- mized linear predecessor as a starting point and speci- fies what must change for a tree-structured architecture with junctions, as shown in Fig. 1. The architecture consists of a single main axis, a linear chain of vertices indexed contiguously as in the linear architecture, with stacks branching off it. A gate vertex lies on the main axis and has two non-junction neighbors. A junction is a main-axis vertex of degree ≥ 3. In addition to its two axis neighbors, it is the root of one or more stacks, each a linear chain of qubit vertices extending away from the axis. A stack is accessed only through its junction- adjacent end, the first slot, and behaves as a last-in-first- out buffer. Because junctions cannot store qubits persistently for technical reasons 28 , they are subject to three additional rules. The in-transit rule allows a junction to hold qubits only between two consecutive translations of the same chain, so it is necessarily empty whenever a non- translation operation runs. The no-roundtrip rule re- quires a chain that enters a junction via one edge to leave via a different one, which obliges the routing to plan ahead. Together they give the exit-availability rule: Before a chain is translated onto a junction, at least one neighbor other than the chain’s entry neighbor must be empty, or be made empty by a chained translation in the same timestep. Only then can the chain move off the junction on the next step. Stack buffers shift as a unit. A push translates the chain at the junction into the first slot, while every already-occupied slot shifts one slot deeper in the same timestep. A pop translates the chain at the first slot out through the junction, while every occupied deeper slot shifts one slot toward the first slot. Both push and pop fit in a single timestep regardless of stack height, because the cascading shift of every occupied slot is a chained trans- lation, permitted under the translation grouping rule of the linear architecture. Building on these rules, the prompt describes three changes to the compiler. The initial mapping reuses the matching and chain extraction of the linear procedure but places the resulting pairs differently, in three ways. First, qubits are placed only on non-junction vertices, which the prompt adds as a fourth placement rule. Second, instead of forming a contiguous run centered on the gate vertex, the chain is assigned to those vertices in order of increasing graph distance to the nearest gate vertex, filling outward along the main axis in both directions and into the stacks. Because chain extraction orders the pairs from most to least strongly interacting, the most strongly interacting pairs still lie closest to the gate vertex. Third, the intra-pair orientation generalizes, since the pairs no longer lie in a spatial chain with a definite neighbor on each side. Within each pair, the qubit with the larger total interaction weight to all the other pairs is placed at the chain position that faces the rest of the architecture, where most of the other pairs lie, keeping it close to the qubits it interacts with most. The routing again brings each gate’s qubits together at the gate vertex, now on a tree with junctions and stacks. Single-qubit routing follows the linear routine unchanged. The only structural difference is in how a chain moves. Every walk now uses a move primitive that follows the unique tree path between source and destination, evacu- ating any obstacle on its path. For a two-qubit gate, the intermediates are the qubits sitting on the tree path between the two endpoints’ cur- rent vertices and their target gate-vertex neighbors. How many intermediates an iteration removes depends on the method used and, for some methods, on whether two intermediates are co-located on a vertex. The compiler picks whichever of the swap, stack, and park-the-endpoint methods has the lowest estimated timestep cost. The swap method always applies, so, besides competing on 10 cost, it is the unconditional fallback when neither of the others does, with the rotor-conveyor as the guaranteed terminal routine: • The swap method is the Merge-Swap-Separate cycle of the linear architecture, with the endpoint and its adjacent intermediate now routed to the gate vertex’s two neighbors along their tree paths rather than along a line. It always removes exactly one intermediate, since a Swap exchanges only a single pair. • The stack method applies when a junction on the path has a stack that is not full. It routes a nearby intermediate to that junction and pushes it onto the stack instead of displacing it past the gate vertex. This removes one intermediate from the path, or two when a co-located pair is pushed together. • The park-the-endpoint method parks one endpoint out of the way, on a non-full stack or at an empty end of the main axis. This frees the corridor the endpoint occupied, so the intermediates can be moved through it and off the path. The parked endpoint is then retrieved and delivered to its gate-vertex neighbor. Several intermediates can be cleared in one iteration this way. • The rotor-conveyor is used only when none of the other methods applies, and is the most costly. It first separates every co-located pair in the trap, carrying each to the gate vertex and splitting it there. This reshuffles much of the trap but leaves one qubit per vertex, so that each later Merge- Swap-Separate cycle acts on exactly two qubits. It then moves one endpoint, the anchor, to the gate- vertex neighbor on the far side from the other end- point, and carries the qubits between the other end- point and its target neighbor across the gate vertex one at a time. Each cycle brings the intermediate nearest the target neighbor onto that neighbor and merges it with the anchor at the gate vertex, where a Swap reverses the pair and a Separate sends the two back out exchanged, leaving the interme- diate on the anchor’s side and the anchor on the endpoint’s side. The intermediate is then moved off that neighbor and deep into the anchor’s side of the trap, and the anchor is translated back across the gate vertex to its own neighbor. This repeats until the other endpoint reaches its target neighbor and the gate executes. In the branched architec- ture, it always succeeds, because the gate vertex can swap the order of two qubits, which a tree’s corridors cannot otherwise do. The prompt also specifies two supporting mechanisms. First, an endpoint may begin deep within a stack, with other qubits between it and the first slot. Because the stack is last-in-first-out, that endpoint cannot leave un- til those qubits are removed, so a three-phase protocol extracts it before the gate is routed. The protocol first clears the junction’s main-axis neighbors, reserving one as the endpoint’s destination. The intervening qubits are then popped off the stack and parked on the cleared vertices. Once the endpoint reaches the first slot, it is popped out onto the reserved vertex. Second, the stack method needs a stack with a free slot, but on a densely occupied architecture every reachable stack may be full. An eviction routine then frees a slot by popping out a stack qubit whose own next gate lies far ahead. Inde- pendently of these mechanisms, every routing attempt is wrapped in a snapshot-and-restore transaction, so a failed attempt is rolled back in full before the next is tried. The post-processing of the linear architecture is ex- tended with a junction-soundness rule. Removing a roundtrip can leave a chain entering and leaving a junc- tion by the same edge, so each candidate removal is checked by replaying the resulting schedule against the simulated state, and is accepted only if no such violation appears. When a single removal fails this check, the pass retries it together with the smallest enclosing roundtrip pair, since dropping both can clear the junction traver- sal altogether. Roundtrip elimination and consecutive cancellation then alternate to fixpoint as in the linear architecture. The prompt also offers a conservative al- ternative for when the replay is not implemented: refuse any removal in which either vertex of the roundtrip is a junction. This preserves correctness with less imple- mentation effort, but rejects every candidate that might expose a violation, including those the replay would ac- cept. The acceptance-test matrix consists of the fourteen tests listed in Tab. IV, spanning height-1 to height-10 stacks, main-axis sizes up to 81, and architectures of up to 93 vertices in total. Four carry tight bounds. Three are inherited from the linear architecture: a same-pair test that must produce zero shuttling, a working exam- ple that must hit a fixed operation and timestep bound, and a chain-structured QAOA test that must produce zero swaps. The fourth extends the same zero-swap re- quirement to 25- and 40-qubit QAOA circuits. Each of the remaining ten, of varying configurations, only needs to execute successfully, with a compile-time guard on one. B. Emitted compiler The LLM rewrites the linear-architecture seed in full, and the resulting compiler passes all acceptance tests on the first attempt. Its routing, however, departs from the specification. Where the prompt describes a per-iteration choice among the swap, stack, and park-the-endpoint methods backed by the rotor-conveyor as a guaranteed fallback, the emitted compiler keeps none of that selec- tion. Instead, a fast attempt moves each endpoint along its tree path to one of the gate vertex’s two neighbors, pushing any obstacle off the path to a nearby free ver- 11 Tab. IV. Acceptance-test matrix for the branched-architecture compiler. The Main-axis vertices column lists each architecture’s main-axis size, with any special structure noted in parentheses, and the Variants column gives the number of architecture variants each test runs, which differ in stack height and junction distance. Tests T1–T8 reuse the circuits of Tab. I on branched architectures, T9 adds larger circuits, and T10–T14 stress two-qubit delivery on progressively denser architectures. Four tests carry tight schedule bounds, three of them inherited from the linear architecture. The rest need only run to a complete, valid schedule, apart from the compile-time guard on T4. TestCircuit(s)Main-axis verticesVariantsFocus / expected T1 same_pair5 (no junctions)1no shuttling T2working example71≤ 20 ops, ≤ 12 steps T3 qaoa_5114no swaps T4 rd32-v0_6692runs, < 1 s T5 4mod5-v1_23114runs T6 4mod5-bdd_287154runs T7 alu-v2_31114runs T8 cnt3-5_179334runs T9 qaoa_25, qaoa_40, qv_25, qft_25, xeb_sy_2551, 815runs, no swaps for QAOA T10 4gt12, 4gt4, alu-v2_3013 (depth-1 stacks)5tight single corridors T11 4gt4, mod8, rd53, hwb713, 15, 175occupied stacks, stacked endpoints T12 xeb_9, xeb_sy_919 (4–6 junctions)5rotor-conveyor required T13 qft_15318congested endpoint corridor T14 xeb_16, xeb_sy_16, qv_20, qv_2533, 41, 517rotor placement, packed corridors tex, and hands off to the rotor-conveyor when it fails. Swap, stack, and park-the-endpoint are thus all omitted as methods in their own right, with intermediates reach- ing a stack only incidentally as obstacles pushed off the path, and the Merge-Swap-Separate cycle appearing only inside the rotor-conveyor. This is an outright sub- stitution rather than a re-encoding of the prompt’s meth- ods. The fast attempt is not cost-driven either. It tries each combination of which endpoint goes to which neigh- bor and which one to route first, four in all, accepting the first that succeeds rather than keeping the plan with the fewest operations, as the prompt asks. Post-processing is adapted in two ways. First, the timestep grouper is tightened for the branched archi- tecture so that it never moves an operation across the boundary between a translation and a non-translation timestep. Otherwise a non-translation operation could fall between two translations of the same chain, violating the in-transit rule. Second, the junction-soundness rule is implemented in the conservative form the prompt offers as a fallback. Rather than replaying the schedule after a candidate removal and accepting it whenever no junction violation appears, the emitted compiler never removes a roundtrip that touches a junction. This is sound and within the specification, but it misses the nested removals that the replay-based rule, which the prompt marks as preferred, would license. C. Optimized compiler The optimizations change two stages of the pipeline. One change is to the initial mapping, where the sin- gle deterministic placement of the prompt is replaced by a search that compiles a few candidate placements and keeps the one with the shortest schedule. To avoid com- piling every candidate, each is first scored by an inexpen- sive proxy for routing effort. The proxy multiplies each edge weight of the qubit-interaction graph by the graph distance between the vertices holding its two qubits, and sums the products. It thus combines a circuit property, how strongly and how early a pair interacts, with a place- ment property, how far apart the placement puts that pair. The score is low when strongly or early-interacting qubits start close together and so need little routing, which usually yields a short schedule. Candidates are generated inexpensively in two ways, by flipping choices in the placement, such as the orientation of the chain, and by a local search that repeatedly swaps qubits to lower the proxy. Only the few candidates with the low- est proxy are then actually compiled, and the shortest schedule among them is kept. A deterministic budget caps how many are compiled, keeping the search time- bounded and reproducible. None of this initial-mapping search appears in the prompt, which invites such addi- tions without naming them. The routing gains two changes. The fast attempt now scores all candidate plans and keeps the least costly, in- stead of accepting the first that succeeds. Separately, the park-the-endpoint method is added as a standalone routine, inserted into the fallback chain between the fast attempt and the rotor-conveyor. The routing thus re- covers one of the prompt’s three methods, but keeps the substituted structure: methods are tried in a fixed or- der rather than chosen per iteration by estimated cost. The remaining changes are lower-level performance and memory optimizations that leave the emitted schedule unchanged. D. Evaluation The suite totals for the branched-architecture compiler as emitted and as optimized, for the general-architecture compiler, and for the hand-crafted baseline, summed over all tested configurations, appear in Tab. V for the circuit library and in Tab. VI for the scalable families. The general-architecture compiler is included here for a direct 12 Tab. V. Branched architecture, circuit library: metrics summed over all 153 library circuits and all tested (stack height, junction distance) configurations, for the branched- architecture compiler, the general-architecture compiler, and the hand-crafted baseline 16 , which emits no swaps by con- struction. The lowest value per column is in bold. All values are rounded to thousands. CompilerTimesteps Translate Separate Merge Swap Branched, emitted209,179k 104,308k 21,745k 21,736k 4,316k Branched, optimized 196,614k 100,629k 18,803k 18,793k 1,315k General, emitted199,299k 98,115k 20,530k 20,521k 3,060k General, optimized 199,940k 98,497k 20,616k 20,607k 3,146k Baseline 16 223,853k 131,802k 17,494k 17,484k0 Tab. VI. Branched architecture, scalable families: suite-total timesteps per family, summed over all circuits of each fam- ily and all tested (stack height, junction distance) configu- rations, for the branched-architecture compiler, the general- architecture compiler, and the hand-crafted baseline 16 . The lowest value per family is in bold. All values are rounded to thousands. CompilerQAOAQFTQVXEB XEB_Sy Branched, emitted 4,664k 49,937k 73,630k 282,932k 512,872k Branched, optimized 1,199k 25,130k 50,524k 184,273k 328,129k General, emitted1,516k 28,053k 55,106k 194,079k 375,006k General, optimized 1,553k 31,257k 57,738k 201,135k 385,556k Baseline 16 723k 27,057k 49,324k 143,729k 302,262k comparison with its specialized counterpart. a. Emitted versus optimized compiler. Together, the three schedule-affecting changes of Sec. V C remove most of the branched-architecture compiler’s swaps, about 70 % of them, and shorten the circuit-library schedules by a median factor of about 1.05, with the park-the-endpoint method contributing the largest share. Per scalable fam- ily, the median emitted-to-optimized factor is about 3.1 for QAOA, 1.7 for QFT, 1.4 for XEB and XEB_Sy, and 1.3 for QV. QAOA improves the most because the park method removes its swaps almost entirely. Its median grows with circuit size, from about 1.0 at 5 qubits to 4.6 at 50 qubits, and the factor of a single configuration peaks at 9.8 on a large architecture with deep stacks and long corridors. The heavier search the park method requires raises the compile time by tens to hundreds of times. b. Optimized LLM-based compiler versus the hand- crafted baseline. Across the tested architectures, the generated branched-architecture compiler outperforms the hand-crafted baseline by a median factor of about 1.2 on the circuit library, and per scalable family, the median is about 1.2 for QFT, QV, and XEB_Sy, 1.1 for XEB, and 0.7 for the chain-structured QAOA, the only family with a median below 1. The largest advan- tage of a single configuration is a factor of 1.64, or 39 % fewer timesteps, on QFT at 40 qubits, stack height 15, and junction distance 9. The per-family totals in Tab. VI sum the timesteps of every circuit, so the largest circuits, with by far the most timesteps, dominate them, and on the total only QFT remains ahead of the baseline. By construction, the baseline emits no swaps. At stack height 1 and junction distance 1 the generated compiler 345678910111213141516 number of qubits 0.85 0.90 0.95 1.00 1.05 1.10 1.15 1.20 timestep reduction factor mean = 1.05 median = 1.07 least-squares fit Fig. 5. Branched architecture, optimized LLM-based com- piler versus the hand-crafted baseline 16 on the circuit library at stack height 1 and junction distance 1. Each circuit’s re- duction factor is plotted against its qubit count. The dashed line marks factor 1, and the red, purple, and green lines mark the mean, the median, and a least-squares fit. emits none either, and on all but one library circuit both emit identical separation and merge counts, so the factor is decided by translations alone. Its advantage on the cir- cuit library is then slight, a mean of 1.05 and a median of 1.07, and it falls with circuit size, as Fig. 5 shows: the least-squares fit drops below the baseline at about 11 qubits. It needs about 29 % fewer translations than the baseline at 3 qubits but about 25 % more at 15 and 16 qubits. This advantage comes from choosing the gate order from the ready set, which saves a roughly fixed fraction of the shuttling at any size, whereas the base- line follows a fixed upstream order. Its shuttling cost, however, grows with size, since a larger circuit means a longer architecture and more occupied vertices per de- livery, and the generated compiler’s evacuation traffic per delivery grows faster than the baseline’s junction- aware routing. Small circuits have little evacuation traf- fic, so the ordering benefit dominates. The largest library circuits have much, so the baseline’s per-move economy wins. Across all tested architectures, the median margin instead widens to about 1.2, even as the compiler begins emitting swaps. Because the library circuits reach only 16 qubits, deeper stacks and longer corridors add little further evacuation traffic, so the ordering benefit keeps the upper hand. On the scalable families, which reach much deeper stacks and longer corridors, the five diverge. All lie above the baseline at stack height 1 and junction distance 1, at factors of about 1.2 to 1.3. The chain-structured QAOA declines most steeply, falling below the baseline as soon as the stacks deepen or the corridors lengthen, to about 0.3 at the deepest stacks and longest corridors, since the baseline routes its chains more compactly. QFT and QV hold their advantage through moderate stacks and corri- dors, falling below the baseline only at their deepest and 13 longest, QFT to about 0.5 and QV, with its larger swap count, to about 0.4. The grid-based XEB and XEB_Sy emit by far the most swaps, nearly 94,000 and 155,000 at 49 qubits. They even rise with stack height, to peaks near 1.5 and 1.6, before dropping to about 0.2 and 0.3 at the tallest stacks, and they weaken with junction dis- tance too. The generated compiler searches up to 150 candidate placements per compilation against the base- line’s single deterministic one, so it is slower by hundreds to thousands of times. VI. GENERAL SHUTTLING ARCHITECTURE A. Specification The prompt for the general-architecture compiler, which appears in Appendix C, gives the LLM the opti- mized branched-architecture compiler and describes only the differences for an arbitrary connected architecture, no longer a tree. The no-roundtrip rule still applies at every junction, forbidding a chain from leaving by the edge it arrived on. On a tree the chain has no way back, but on a cycle it can return to the side it came from along the cycle’s other arc, so the rule relaxes wherever a junction lies on a cycle. The initial mapping is unchanged from the branched architecture. Matching and the chain-extraction proce- dure make no assumption about the architecture, using only the graph distance and the set of non-junction ver- tices, so both carry over verbatim. The routing pipeline structure of the branched ar- chitecture carries over to the general graph. Here the prompt describes three changes. First, the tree-specific code is removed: the park slots selected from the main- axis-and-stacks layout, whose only options were stack heads or the ends of the main axis, and the stack method itself, since a general graph has neither. Second, in its place, the park-the-endpoint method is generalized to park an endpoint on any empty non-junction vertex that lies off the routing paths, with candidates ranked by the total distance the endpoint must walk, out to the park vertex and then on to its gate-vertex neighbor. Third, a cycle-detour method is added. For an intermediate on the direct path from an endpoint to its target gate- vertex neighbor, the router seeks the shortest alternative path to that neighbor that avoids the intermediate. If such a path exists and its extra length, measured against the direct path, costs less than evicting the intermedi- ate, the endpoint takes that alternative arc. Since the arc leaves the direct path entirely, it also bypasses any other intermediates on it, so a single detour handles sev- eral at once with no Separate, Merge, or Swap. In the per-iteration cost comparison, the cycle-detour takes the stack method’s place against the park-the-endpoint and swap methods. The prompt keeps both of the swap method’s earlier roles, competing on cost and serving as the unconditional fallback when neither of the others ap- plies, with the rotor-conveyor as the guaranteed terminal routine. Because the branched-architecture seed routes by the fast attempt described in Sec. V and has no swap method, the prompt here names a feature the seed never implemented, which Sec. I A notes can happen. One change is made to the post-processing. The con- servative roundtrip-elimination guard inherited from the branched architecture is replaced with the replay-based junction-soundness check that its prompt marked as pre- ferred but its compiler did not implement. A roundtrip at a junction normally cannot be deleted, since deleting it would make the chain enter and leave the junction by the same edge, which the no-roundtrip rule forbids. On a cycle, though, the chain can get back to its entry side along the cycle’s other arc, rather than reversing at the junction, so the roundtrip there is redundant and safe to delete. These junction deletions are the extra removals the replay gains over the conservative guard. The acceptance-test matrix has two parts. One re- tains the fourteen-test suite of Sec. V, which the general- architecture compiler, seeded from its predecessor, must still pass. The other adds an architecture matrix of fifteen graph families, each specified parametrically at 2n + 1 non-junction vertices for an n-qubit circuit and chosen to test particular routing capabilities. They carry no bounds and only need to execute successfully. Three are trees, including the linear and branched architectures, and the remaining twelve add cycles. Of those twelve, the eight drawn in Fig. 1 and carried into the evaluation are: • cycle: a single cycle. • two_cycles_bridged: two cycles connected by a path. • theta: two junctions linked by three internally dis- joint paths. • figure8: two cycles sharing a single vertex. • cycle_with_two_chords: a cycle with two non- crossing chords. • complete_graph: a complete graph on four ver- tices, with edges subdivided by non-junction ver- tices. • hypercube: the three-dimensional hypercube 71 , subdivided in the same way. • butterfly:the two-dimensional butterfly network 71 , subdivided in the same way. As Sec. I B explains, the subdivision of the last three families provides the qubit and gate vertices that the orig- inal networks, consisting predominantly of junctions, do not offer. On every graph the gate vertex meets the con- straint of degree two with two non-junction neighbors. The matrix specifies each family by a construction rule rather than as a fixed graph, and only specific instances drawn from these rules are tested. Passing the acceptance tests thus shows the compiler handles those instances, not every graph the rules admit. 14 B. Emitted compiler The emitted compiler implements every described change and, on the first attempt, passes both the in- herited branched-architecture suite and the architecture matrix. In one respect it goes beyond the prompt, which, unlike those for the linear and branched architectures, in- vites no additions. Although the prompt leaves the rotor- conveyor unchanged, the LLM adds a two-arc delivery for a gate vertex lying on a cycle. Rather than send both endpoints through the single corridor a tree would force, it routes them to the gate vertex’s two neighbors along the cycle’s two arcs, so that neither has to pass the other through the gate vertex. This is the general-architecture compiler’s only feature that its prompt does not require. The rotor-conveyor nonetheless remains where general- ity is lost. The branched-architecture prompt requires it to make routing total, and in the branched architec- ture it does. That guarantee does not carry to general graphs. Reached only when no cheaper method succeeds, the emitted rotor is a bounded heuristic rather than a complete search, so on some architectures it reports fail- ure even though free qubit vertices remain, and the com- piler does not produce a schedule for every connected graph. C. Optimized compiler The optimizations for this compiler are entirely engineering-focused. The prompts ask for reductions in timesteps, compile time, and memory use alike, and here the LLM finds no further way to shorten the schedule, so its changes target compile time and memory use in- stead. Most are lower-level optimizations that leave the emitted schedule unchanged. The exception is a compile- time budget, which trades schedule length for compilation speed. Routing is slow on a dense circuit, so the search caps how many candidates it routes. It estimates how many routings fit in a fixed time budget from the operation count of the first routed candidate, a proxy for one rout- ing’s cost, and stops there. Deriving the cap from this count rather than from measured compile time keeps it deterministic and the output reproducible. Small cir- cuits never reach the cap and are unchanged. Larger ones reach it, accepting a longer schedule in return for a much shorter compile time. A user can raise the budget to compile more candidates, up to the search’s fixed trial limit. None of these optimizations changes how the search picks among compiled candidates, only which candidates get compiled. Where the budget compiles the same can- didates as the emitted compiler, the output is identical to it. Where it compiles fewer, the search stops after the first several candidates in its routing order and re- turns a longer schedule. The rewrites also shifted that order, so the optimized compiler compiles a different set of candidates, which can shorten the schedule as well. D. Evaluation The general-architecture compiler handles all ten ar- chitectures from a single code base. a. Emitted versus optimized compiler. The general- architecture compiler’s follow-up optimizations trade schedule length for compilation speed. Its schedules are rarely shorter after optimization than as emitted, and on the largest QAOA circuits it emits up to 75 % more timesteps, so we use the emitted compiler, which gives its shortest schedules, as the baseline here. On the few configurations where it is shorter, the gain is almost al- ways a few percent, though one reaches 62 %. In return, the optimized compiler is up to about 200 times faster on the largest circuits. b. General-architecture compiler versus the special- ized compilers. Each factor here divides the general- architecture compiler’s timestep count by the specialized compiler’s, so a value above 1 means the specialist emits fewer timesteps. We take the general-architecture com- piler as emitted, since that gives its shortest schedules, and each specialist after optimization. On the branched architecture, from which it was generalized, the general- architecture compiler nearly matches the specialized one, with a median factor of about 1.0 on the circuit li- brary and, per scalable family, about 1.1 for QAOA and XEB_Sy and 1.0 for QFT, QV, and XEB, though the gap reaches up to 2.6 on QFT. For the linear architec- ture, for which it is not tuned, the gap is wider, at a median factor of about 1.1 on the circuit library and, per scalable family, about 2.7 for QAOA, 2.3 for QFT, 1.6 for XEB, 1.5 for XEB_Sy, and 1.2 for QV, reaching 6.8 on the largest QAOA circuits. Yet on about 8 % of the li- brary circuits the general-architecture compiler is shorter than the specialized one, by up to 22 %. As emitted, the general-architecture compiler is the slowest of the three to compile, since its candidate search runs uncapped. After optimization the compile-time budget caps that search, bringing the compiler level with the specialists or ahead. The supporting totals are in Tab. I, Tab. I, Tab. V, and Tab. VI. Specializing a compiler for a fixed archi- tecture thus still yields a substantial performance gain, while the general-architecture one trades it for covering every layout from a single code base. c. Architecture suitability. We compare the general- architecture compiler across all ten, the eight cyclic fami- lies plus the linear and branched layouts, taking the latter at stack height 1 and junction distance 1, the one config- uration that scales across both the circuit library and the scalable families. All ten have the same number of qubit vertices, 2n, and a single gate vertex for an n-qubit cir- cuit, differing only in how those vertices are connected, so the comparison isolates the effect of connectivity. The heatmap in Fig. 6 reports the timesteps per architecture, summed over each circuit class and normalized by the 15 butterfly complete_graph hypercube cycle_with_two_chords branched (height 1, distance 1) theta figure8 two_cycles_bridged cycle linear Library QAOA QFT QV XEB_Sy XEB 1.01.01.01.21.31.41.51.41.92.0 1.01.11.11.21.51.92.32.32.82.8 1.01.01.11.21.22.53.22.42.62.7 1.01.11.11.11.22.02.42.75.96.1 1.01.11.21.31.62.93.94.47.57.8 1.01.11.21.31.53.14.14.77.77.8 1 2 3 4 5 6 7 timesteps relative to best architecture for that class Fig. 6. Architecture suitability per circuit class. Each row is one scalable family or the circuit library, and each column one of the ten architectures, the eight cyclic families plus the linear and branched architectures. Cell values are the class’s total timesteps normalized by the row minimum, so 1.0 marks the best architecture for that class. Rows and columns are ordered by the sums of these values. best architecture. Summing rather than taking medians weights the largest circuits, where shuttling is heaviest, which is where the choice of architecture matters most. The densely connected architectures with high-degree junctions and short pairwise distances, butterfly, complete_graph, and hypercube, lead in every circuit class, with butterfly the best throughout. Their many alternative arcs let the cycle-detour bypass an intermedi- ate entirely, and their short distances put an empty non- junction vertex within easy reach of park-the-endpoint. Both spare the costly Merge-Swap-Separate routine. What the two worst architectures, the linear architecture and the plain cycle, lack most is junctions. Without them, the only vertices off a routing path lie beyond its endpoints, so parking means long walks along the cor- ridor itself, and the cycle’s single alternative arc spans most of the architecture and rarely wins on cost. Ac- cordingly, the extra arc gives the cycle only a small advantage over the linear architecture, 0 to 4 % at the class medians. A single junction pair changes this. The theta family, a cycle with one additional path between two junctions, needs about 10 % fewer timesteps than the plain cycle at the class medians on the least shuttling- intensive classes, and less than half on the most demand- ing ones. How much the architecture matters scales with a cir- cuit’s shuttling demand, which the scalable families vary through their interaction patterns. QAOA is chain-like, QFT and QV are effectively all-to-all, and the two XEB families couple only nearest neighbors on a square lat- tice but are run to a large depth. The spread between the best and worst architecture is accordingly smallest for QAOA, a factor of 2.8, and largest for the two XEB families, both at 7.8, with QFT and QV in between at 3.2 and 6.1. On the smaller library circuits it reaches at most 2.0. The trend is not strict, however: on the two largest QFT circuits the plain cycle and theta es- sentially tie. On single configurations the spread widens further, up to a factor of 10, or 90 % fewer timesteps on the best than on the worst architecture, for the largest XEB_Sy circuits. The effect is large enough that on the three densest lay- outs the general-architecture compiler produces shorter schedules than the two specialists do on the architec- tures they target, by a factor of about 2.9 to 3.5 for the linear one and 1.2 to 1.5 for the branched one. It surpasses the hand-crafted baselines too, by 1.4 to 1.9 on all five families of the branched architecture and by 3.2 to 5.7 on every family of the linear one, except the chain-like QAOA, which the linear layout fits so well that the general-architecture compiler emits 13 to 25 % more timesteps there. On single configurations the advantage peaks at 83 % and 40 % over the two specialists, and at 85 % and 50 % over their hand-crafted baselines. The connectivity of the architecture thus has a first-order ef- fect on shuttling overhead and is worth optimizing along- side the compiler. d. Comparison with related approaches. SHAW and SHAPER 38,39 cover many architectures through a hand- designed position-graph abstraction and an adapted SABRE heuristic 47 , and the SWAP-based S-SYNC 40 likewise abstracts the device as a static graph. Our general-architecture compiler covers a broad class of con- nected architectures as well, but is itself generated by the LLM rather than hand-designed. Their elementary op- erations are nevertheless defined differently from ours, acting on single ions where ours act on a segment’s whole chain. The MQT IonShuttler 21,22,48 assumes a different hardware model, a two-dimensional QCCD grid with dedicated processing zones and reordering by rota- tion around grid loops, and so does without separations, merges, and swaps altogether. In neither case do the 16 schedule lengths lie on a scale comparable to ours. VII. LLM COMPARISON To test whether more recent models can substantially improve the results, we repeat the complete generation and evaluation with Claude Fable 5 42 under the protocol of Sec. I A. The prompts are identical to those of the Opus 4.7 run for all three compilers. For the linear- and branched-architecture compilers, every input file is iden- tical as well, so their results compare directly. Each run seeds each compiler from its own predecessor’s optimized code, so the two chains stay independent. The general- architecture compiler differs in two respects. First, its prompt builds on the branched-architecture compiler and therefore contains function names that Opus 4.7 chose. Since the prompt is kept identical for an unbiased com- parison, these names are absent from the Fable 5 seed. Second, its acceptance-matrix graphs were drawn inde- pendently from the same construction rules, so the two runs did not necessarily test against identical instances during generation. The evaluation itself uses the same graphs for both runs. Neither difference favors Fable 5, which matched the prompt’s descriptions to its own func- tions by their role. a. Emitted compilers. All emitted compilers pass every acceptance test of all three stages on the first at- tempt, though their quality differs. Opus 4.7’s emit- ted compilers produce fewer timesteps on most circuits. The contrast is clearest for the linear-architecture com- piler, where Fable 5’s emitted compiler needs 16 % more timesteps at the median on the circuit library, and more on every scalable family, by median factors from 1.33 on QV up to 3.5 on QFT. Both emitted branched- architecture compilers omit the same part of the spec- ification, the per-iteration choice among the swap, stack, and park-the-endpoint methods, and substitute a simpler fast attempt backed by the rotor-conveyor. In both, in- termediates reach a stack only incidentally, as evacuation landings, and never through the prompt’s stack method. b. Follow-up refinement. Fable 5 gains the most un- der the follow-up prompts. On the linear architecture it gains median factors of 1.8 to 3.8 across the scalable families and 1.25 on the circuit library, against Opus 4.7’s 1.3 to 1.4 and 1.16, closing most of its emitted- compiler gap. Both LLMs introduce the omitted park- the-endpoint method during the follow-up prompts, and in both runs it becomes the largest single improvement of the branched-architecture compiler. The two general- architecture compilers diverge most. Opus 4.7’s opti- mizations trade schedule length for compilation speed, whereas Fable 5’s optimized compiler emits the fewest timesteps of all its versions. c. Optimized compilers. On the linear- and branched-architecture suites, the two optimized compil- ers split along circuit size. Opus 4.7 emits the shorter schedule on 82 % of the linear and 86 % of the branched Tab. VII. Optimized compilers of both LLMs against the hand-crafted baselines 11,16 on identical inputs: the median timestep reduction factor and the share of the n circuit and architecture configurations on which the factor exceeds 1, sep- arated into the circuit library and the individual scalable fam- ilies. The better value per row and metric is in bold. Opus 4.7Fable 5 Suiten Median>1 Median>1 Linear, library1531.19 93.5 %1.12 79.7 % Linear, QAOA101.24 100.0 %1.16 100.0 % Linear, QFT103.59 100.0 %2.86 100.0 % Linear, QV101.16 100.0 %1.63 100.0 % Linear, XEB61.40 100.0 %1.50 100.0 % Linear, XEB_Sy61.48 83.3 %1.54 83.3 % Branched, library1,9061.18 92.5 %1.13 95.1 % Branched, QAOA1,0450.660.9 %0.48 1.2 % Branched, QFT1,0421.23 84.1 %1.27 98.4 % Branched, QV1,0451.17 76.1 %1.21 89.6 % Branched, XEB5121.07 58.8 %1.26 90.6 % Branched, XEB_Sy5121.23 72.7 %1.41 93.9 % circuit-library configurations, at median margins of 6 and 5 %. Across the scalable families the picture shifts toward Fable 5, which emits the shorter schedule on the majority of configurations of every family on the branched architecture except QAOA, and of QV, XEB, and XEB_Sy on the linear one. Fable 5 is stronger where the hand-crafted baselines are most difficult to outperform, as Tab. VII shows. On the branched architecture’s scalable families other than QAOA, where the baseline dominates both LLMs, its share of configurations above the baseline lies between 89 and 98 % against Opus 4.7’s 59 to 84 %. Within each family, both LLMs’ shares fall with qubit count, Opus 4.7’s far more steeply. At the largest sizes Fable 5 still outperforms the baseline on 80 to 98 % of each family’s configurations except QAOA, whereas Opus 4.7’s shares drop to between 42 and 72 %. d. Architecture matrix. The qualitative findings of Sec. VI reproduce in the Fable 5 run. For both LLMs the subdivided butterfly is the best in every circuit class, and the plain cycle and the linear architecture are the worst overall, with best-to-worst spreads of up to 7.8 for Opus 4.7 and 6.0 for Fable 5, so the first-order effect of the architecture’s connectivity is not an artifact of one LLM. For each run we take the general-architecture compiler in the version that produces the shortest schedules: the optimized one for Fable 5 and the emitted one for Opus 4.7, since its optimizations trade schedule length for com- pilation speed. Head-to-head, the two split along con- nectivity. Fable 5’s needs fewer timesteps on the sparse architectures, throughout on two_cycles_bridged and on most circuit classes of the linear architecture and the cycle, whereas Opus 4.7’s is ahead on every class of the two densest, the complete_graph and the hypercube. Against the hand-crafted baseline on the branched archi- tecture’s scalable families, Fable 5’s general-architecture compiler still beats it, with median factors of 1.2 to 1.3 against Opus 4.7’s 1.0 to 1.2. QAOA is the exception, 17 where both remain below. Fable 5’s compiler is thus the stronger of the two on the sparse architectures, which are each run’s worst case, and the weaker on the dense ones, which are each run’s best case, so its best-to-worst spread comes out smaller than Opus 4.7’s. In sum, the two frontier LLMs show distinct capabil- ity profiles under an identical protocol. Opus 4.7 writes the stronger emitted compilers and retains a small ad- vantage on small circuits, whereas Fable 5 starts weaker, optimizes more aggressively, and ends more competitive against the hand-crafted baselines on the large circuits where shuttling costs dominate. The qualitative claims of the preceding sections hold in both runs, and the two chains deviate from the branched-architecture specifica- tion in the same place and recover from it at the same point. This indicates that the methodology, rather than one particular LLM, carries the result. VIII. CONCLUSION AND OUTLOOK We have shown that frontier LLMs can generate the complete Python source code of three shuttling compilers for trapped-ion quantum computers from written specifi- cations. The first compiler targets a linear segmented ar- chitecture, the second one an architecture with junctions and stack-shaped side branches, and the third one gen- eral connected architectures. All three are benchmarked against the published hand-crafted references 11,16 on cir- cuits with up to 50 qubits. For the linear architecture, the compiler generated by Claude Opus 4.7 24 emits up to 76 % fewer timesteps than the hand-crafted baseline, and for the branched architec- ture up to 39 % fewer, with a median reduction factor of about 1.2 on the circuit library in both cases. This advantage over the hand-crafted baselines comes largely from where gate ordering is decided: the generated com- pilers select each gate from the ready set during shut- tling and can therefore exploit the current ion place- ment, whereas the baselines route a gate order fixed by the circuit compiler 35 , which never sees that placement. This relaxes the otherwise strict boundary between cir- cuit compilation and shuttling compilation. Covering a broad class of architectures instead costs the general- architecture compiler more timesteps than the special- ists need, up to 6.8 times as many on the linear archi- tecture and 2.6 times on the branched one. Run across ten architectures, it exposes a first-order effect of con- nectivity, needing up to 90 % fewer timesteps on a dense, junction-rich layout than on a sparse one. The densest layouts are the subdivided butterfly, complete_graph, and hypercube, and the sparsest are the plain cycle and the linear architecture. On such dense layouts the general-architecture compiler emits fewer timesteps than each specialist does on its own architecture, by up to 83 % for the linear one and 40 % for the branched one, with similar margins over the hand-crafted baselines. These results indicate that an unmodified frontier LLM, given a detailed specification, can produce working, correct, and competitive shuttling compilers for distinct trapped-ion architectures without any additional manual algorithmic engineering. Repeating the complete genera- tion and evaluation with a second frontier LLM, Claude Fable 5 42 , reproduces the qualitative findings, showing they follow from the methodology rather than a single model, with the Fable 5 compilers surpassing the hand- crafted baselines more often on the largest circuits. Gen- erating and testing a compiler this way takes just a few days, about an order of magnitude faster than hand- crafting one. That low cost makes it worthwhile to build a dedicated compiler for each new target architecture, since on its own architecture a specialist compiler out- performs the general one. We see several directions for future work. (i) We plan to extend the architecture to several gate segments, and thereby enable parallel gate execution. (i) We want to allow separation, merge, and swap at any segment rather than only at a single central gate segment. (i) We in- tend to combine the shuttling of single ions with that of entire ion crystals so that a segment can hold more than one or two ions, together with the addressing-based gate operations needed to act on individual ions within such a crystal. (iv) Finally, we aim to make the routing com- plete on every connected architecture. This last direction remains an open problem: the general-architecture com- piler covers a broad class of connected architectures but not all of them, and closing the gap would require the prohibitive cost of a complete search such as A* 72 . ACKNOWLEDGMENTS We thank the data center (ZDV) of Johannes Guten- berg University Mainz for the use of their Mogon NHR cluster for evaluating our generated compilers. We ac- knowledge funding by the German Federal Ministry of Research, Technology and Space (BMFTR) within the projects IQuAn, ATIQ, and SYNQ, and by the DFG Pri- ority Programme SPP2514. AUTHOR DECLARATIONS Conflict of Interest The authors have no conflicts to disclose. Author Contributions Fabian Kreppel: Conceptualization (equal); Data curation (lead); Formal analysis (lead); Investigation (lead); Methodology (equal); Software (lead); Valida- tion (lead); Writing – original draft (lead); Writing – review & editing (equal). Reza Salkhordeh: Investi- gation (supporting); Software (supporting). Ferdinand 18 Schmidt-Kaler: Funding acquisition (equal); Supervi- sion (supporting); Writing – review & editing (equal). André Brinkmann: Conceptualization (equal); Fund- ing acquisition (equal); Methodology (equal); Project ad- ministration (lead); Supervision (lead); Writing – review & editing (equal). DATA AVAILABILITY The data that support the findings of this study are available from the corresponding author upon reasonable request. REFERENCES 1 D. Kielpinski, C. Monroe, and D. J. Wineland, “Architecture for a large-scale ion-trap quantum computer,” Nature 417, 709–711 (2002). 2 S. Seidelin et al., “Microfabricated Surface-Electrode Ion Trap for Scalable Quantum Information Processing,” Phys. Rev. Lett. 96, 253003 (2006). 3 D. R. Leibrandt et al., “Demonstration of a scalable, multiplexed ion trap for quantum information processing,” Quantum Info. Comput. 9, 901—-919 (2009). 4 R. Bowler, J. Gaebler, Y. Lin, T. R. Tan, D. Hanneke, J. D. Jost, J. P. Home, D. Leibfried, and D. J. Wineland, “Coherent Diabatic Ion Transport and Separation in a Multizone Trap Array,” Phys. Rev. Lett. 109, 080502 (2012). 5 P. Murali, D. M. Debroy, K. R. Brown, and M. Martonosi, “Ar- chitecting Noisy Intermediate-Scale Trapped Ion Quantum Com- puters,” in ACM/IEEE 47th Annu. Int. Symp. Comput. Archit. (ISCA) (Virtual Event, May 30–Jun. 3, 2020) p. 529–542. 6 V. Kaushal, B. Lekitsch, A. Stahl, J. Hilder, D. Pijn, C. Schmiegelow, A. Bermudez, M. Müller, F. Schmidt-Kaler, and U. Poschinger, “Shuttling-based trapped-ion quantum informa- tion processing,” AVS Quantum Sci. 2, 014101 (2020). 7 J. M. Pino, J. M. Dreiling, C. Figgatt, J. P. Gaebler, S. A. Moses, M. S. Allman, C. H. Baldwin, M. Foss-Feig, D. Hayes, K. Mayer, C. Ryan-Anderson, and B. Neyenhuis, “Demonstra- tion of the trapped-ion quantum CCD computer architecture,” Nature 592, 209–213 (2021). 8 M. Lee, J. Jeong, Y. Park, C. Jung, T. Kim, and D. Cho, “Ion shuttling method for long-range shuttling of trapped ions in MEMS-fabricated ion traps,” Jpn. J. Appl. Phys. 60, 027004 (2021). 9 S. A. Moses, C. H. Baldwin, et al., “A Race-Track Trapped-Ion Quantum Processor,” Phys. Rev. X 13, 041052 (2023). 10 A. Ransford et al., “Helios: A 98-qubit trapped-ion quantum computer,” (2025), arXiv:2511.05465. 11 J. Wagner, Automated generation of shuttling schedules for a scalable trapped-ion quantum processor, M.sc. thesis, Institute of Computer Science, Johannes Gutenberg Univ., Mainz, Germany (2022). 12 J. Durandau, J. Wagner, F. Mailhot, C. Brunet, F. Schmidt- Kaler, U. Poschinger, and Y. Bérubé-Lauzière, “Automated Gen- eration of Shuttling Sequences for a Linear Segmented Ion Trap Quantum Computer,” Quantum 7, 1175 (2023). 13 J. Durandau, C. Brunet, F. Schmidt-Kaler, U. Poschinger, F. Mailhot, and Y. Bérubé-Lauzière, “Heuristics for Shuttling Se- quence Optimization for a Linear Segmented Trapped-Ion Quan- tum Computer,” (2026), arXiv:2603.05464. 14 A. Ash-Saki, R. O. Topaloglu, and S. Ghosh, “Muzzle the Shut- tle: Efficient Compilation for Multi-Trap Trapped-Ion Quan- tum Computers,” in Des. Automat. Test Europe Conf. Exhib. (DATE) (Antwerp, Belgium, Mar. 14–23, 2022) p. 322–327. 15 T. Wu and T. Wang, “An Improved Ion-Shuttling Approach for QCCD Architectures,” in Int. Symp. Phys. Des. (ISPD) (Bonn, Germany, Mar. 15–18, 2026) p. 173–181. 16 F. Kreppel, C. Melzer, J. Wagner, J. Hilder, U. Poschinger, F. Schmidt-Kaler, and A. Brinkmann, “Shuttling Compiler for a Trapped-Ion Quantum Computer Architecture with Junctions,” in IEEE Int. Conf. Quantum Comput. Eng. (QCE), Vol. 1 (Mon- treal, Canada, Sep. 15–20, 2024) p. 1065–1076. 17 M. Webber, S. Herbert, S. Weidt, and W. K. Hensinger, “Efficient Qubit Routing for a Globally Connected Trapped Ion Quantum Computer,” Adv. Quantum Technol. 3, 2000027 (2020). 18 W. Dai, K. A. Brown, and T. G. Robertazzi, “Advanced Shuttle Strategies for Parallel QCCD Architectures,” IEEE Trans. Quan- tum Eng. (TQE) 5, 1–18 (2024). 19 C. Chang, J. R. Jiang, D. Chiou, T. Hsu, and G.-D. Lin, “Quantum Circuit Compilation for Trapped-Ion Processors With the Drive-Through Architecture,” IEEE Trans. Quantum Eng. (TQE) 6, 1–14 (2025). 20 D. Schoenberger, J. Hilder, F. Schmidt-Kaler, and R. Wille, “Shuttling for Trapped-Ion Quantum Computers with Embedded Processing Zones,” in IEEE Int. Conf. Quantum Softw. (QSW) (Helsinki, Finland, Jul. 7–12, 2025) p. 123–129. 21 D. Schoenberger, S. Hillmich, M. Brandl, and R. Wille, “Shut- tling for Scalable Trapped-Ion Quantum Computers,” IEEE Trans. Comp.-Aided Des. Integ. Cir. Sys. 44, 2144–2155 (2025). 22 D. Schoenberger and R. Wille, “Orchestrating Multi-Zone Shut- tling in Trapped-Ion Quantum Computers,” in IEEE Int. Conf. Quantum Comput. Eng. (QCE), Vol. 1 (Albuquerque, NM, USA, Aug. 31–Sep. 5, 2025) p. 1069–1075. 23 T. Schmale, B. Temesi, A. Baishya, N. Pulido-Mateo, L. Krin- ner, T. Dubielzig, C. Ospelkaus, H. Weimer, and D. Borcherding, “Backend compiler phases for trapped-ion quantum computers,” in IEEE Int. Conf. Quantum Softw. (QSW) (Barcelona, Spain, Jul. 10–16, 2022) p. 32–37. 24 Anthropic, “System Card: Claude Opus 4.7,” Tech. Rep. (An- thropic, 2026). 25 S. Schulz, U. Poschinger, K. Singer, and F. Schmidt-Kaler, “Op- timization of segmented linear Paul traps and transport of stored particles,” Fortschr. Phys. 54, 648–665 (2006). 26 W. K. Hensinger, S. Olmschenk, D. Stick, D. Hucul, M. Yeo, M. Acton, L. Deslauriers, J. Rabchuk, and C. Monroe, “T- junction ion trap array for two-dimensional ion shuttling, storage, and manipulation,” Appl. Phys. Lett. 88, 034101 (2006). 27 R. B. Blakestad, C. Ospelkaus, A. P. VanDevender, J. M. Amini, J. Britton, D. Leibfried, and D. J. Wineland, “High-Fidelity Transport of Trapped-Ion Qubits through anX-Junction Trap Array,” Phys. Rev. Lett. 102, 153002 (2009). 28 R. B. Blakestad, C. Ospelkaus, A. P. VanDevender, J. H. We- senberg, M. J. Biercuk, D. Leibfried, and D. J. Wineland, “Near- ground-state transport of trapped-ion qubits through a multidi- mensional array,” Phys. Rev. A 84, 032314 (2011). 29 W. C. Burton, B. Estey, I. M. Hoffman, A. R. Perry, C. Volin, and G. Price, “Transport of Multispecies Ion Crystals through a Junction in a Radio-Frequency Paul Trap,” Phys. Rev. Lett. 130, 173202 (2023). 30 J. M. Amini, H. Uys, J. H. Wesenberg, S. Seidelin, J. Britton, J. J. Bollinger, D. Leibfried, C. Ospelkaus, A. P. VanDevender, and D. J. Wineland, “Toward scalable ion traps for quantum information processing,” New J. Phys. 12, 033031 (2010). 31 D. L. Moehring, C. Highstrete, D. Stick, K. M. Fortier, R. Haltli, C. Tigges, and M. G. Blain, “Design, fabrication and experimen- tal demonstration of junction surface ion traps,” New J. Phys. 13, 075018 (2011). 32 K. Wright, J. M. Amini, D. L. Faircloth, C. Volin, S. C. Doret, H. Hayden, C. Pai, D. W. Landgren, D. Denison, T. Killian, R. E. Slusher, and A. W. Harter, “Reliable transport through a microfabricated X-junction surface-electrode ion trap,” New J. Phys. 15, 033004 (2013). 33 G. Shu, G. Vittorini, A. Buikema, C. S. Nichols, C. Volin, D. Stick, and K. R. Brown, “Heating rates and ion-motion control 19 in aY-junction surface-electrode trap,” Phys. Rev. A 89, 062308 (2014). 34 B. Lekitsch, S. Weidt, A. G. Fowler, K. Mølmer, S. J. Devitt, C. Wunderlich, and W. K. Hensinger, “Blueprint for a microwave trapped ion quantum computer,” Sci. Adv. 3, e1601540 (2017). 35 F. Kreppel, C. Melzer, D. O. Millán, J. Wagner, J. Hilder, U. Poschinger, F. Schmidt-Kaler, and A. Brinkmann, “Quantum Circuit Compiler for a Shuttling-Based Trapped-Ion Quantum Computer,” Quantum 7, 1176 (2023). 36 S. Upadhyay, A. Ash-Saki, R. O. Topaloglu, and S. Ghosh, “A Shuttle-Efficient Qubit Mapper for Trapped-Ion Quantum Com- puters,” in Great Lakes Symp. VLSI (GLSVLSI) (Irvine, CA, USA, June 6–8, 2022) p. 305–308. 37 A. Ovide, D. Cuomo, and C. G. Almudever, “Scaling and As- signing Resources on Ion Trap QCCD Architectures,” in IEEE Int. Conf. Quantum Comput. Eng. (QCE), Vol. 1 (Montreal, Canada, Sep. 15–20, 2024) p. 959–970. 38 B. G. Bach, I. Safro, and E. Younis, “Efficient Compilation for Shuttling Trapped-Ion Machines via the Position Graph Archi- tectural Abstraction,” (2025), arXiv:2501.12470. 39 B. Russon, B. G. Bach, E. Younis, and I. Safro, “Scaling Qubit Mapping and Routing With Position Graph Abstraction and Memoization,” (2026), arXiv:2605.09237. 40 C. Zhu, X. Wu, J. Wang, and X. Wang, “S-SYNC: Shuttle and Swap Co-Optimization in Quantum Charge-Coupled Devices,” in 52nd Annu. Int. Symp. Comput. Archit. (ISCA) (Tokyo, Japan, June 21–25, 2025) p. 271–284. 41 F. Kreppel, R. Salkhordeh, F. Schmidt-Kaler, and A. Brinkmann, “Shuttling Compiler for Trapped-Ion Quantum Computers Based on Large Language Models,” (2025), arXiv:2512.18021. 42 Anthropic, “System Card: Claude Fable 5 & Claude Mythos 5,” Tech. Rep. (Anthropic, 2026). 43 R. Wille, R. V. Meter, and Y. Naveh, “IBM’s Qiskit Tool Chain: Working with and Developing for Real Quantum Computers,” in Des. Automat. Test Europe Conf. Exhib. (DATE) (Florence, Italy, Mar. 25–29, 2019) p. 1234–1240. 44 S. Sivarajah, S. Dilkes, A. Cowtan, W. Simmons, A. Edging- ton, and R. Duncan, “t|ket⟩: a retargetable compiler for NISQ devices,” Quantum Sci. Technol. 6, 014003 (2020). 45 Cirq Developers, Cirq (Zenodo, 2025). 46 V. Bergholm et al., “PennyLane: Automatic differentia- tion of hybrid quantum-classical computations,” (2022), arXiv:1811.04968. 47 G. Li, Y. Ding, and Y. Xie, “Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices,” in 24th ACM Int. Conf. Archit. Support Program. Lang. Operating Syst. (ASP- LOS) (Providence, RI, USA, Apr. 13–17, 2019) p. 1001–1014. 48 D. Schoenberger, S. Hillmich, M. Brandl, and R. Wille, “Us- ing Boolean Satisfiability for Exact Shuttling in Trapped-Ion Quantum Computers,” in 29th Asia South Pacific Des. Automat. Conf. (ASP-DAC) (Incheon, Republic of Korea, Jan. 22–25, 2024) p. 127–133. 49 J. Ruan, H. Zhang, X. Fang, A. Li, W. C. Campbell, E. Hud- son, D. Hayes, H. Haeffner, T. Humble, J. Palsberg, and Y. Ding, “TrapSIMD: SIMD-Aware Compiler Optimization for 2D Trapped-Ion Quantum Machines,” (2025), arXiv:2504.17886. 50 J. Heckey, S. Patil, A. Javadi-Abhari, A. Holmes, D. Kudrow, K. R. Brown, D. Franklin, F. T. Chong, and M. Martonosi, “Com- piler Management of Communication and Parallelism for Quan- tum Computation,” in 20th ACM Int. Conf. Archit. Support Pro- gram. Lang. Operating Syst. (ASPLOS) (Istanbul, Turkey, Mar. 14–18, 2015) p. 445–456. 51 X. Wu, C. Zhu, J. Wang, and X. Wang, “MUSS-TI: Multi-level Shuttle Scheduling for Large-Scale Entanglement Module Linked Trapped-Ion,” in 58th IEEE/ACM Int. Symp. Microarchit. (MI- CRO) (Seoul, Republic of Korea, Oct. 18–22, 2025) p. 749–763. 52 A. Paler, L. Sasu, A. Florea, and R. Andonie, “Machine Learning Optimization of Quantum Circuit Layouts,” ACM Trans. Quan- tum Comput. (TQC) 4, 12:1–12:25 (2023). 53 M. G. Pozzi, S. J. Herbert, A. Sengupta, and R. D. Mullins, “Using Reinforcement Learning to Perform Qubit Routing in Quantum Compilers,” ACM Trans. Quantum Comput. (TQC) 3, 10:1–10:25 (2022). 54 H. Fan, C. Guo, and W. Luk, “Optimizing quantum circuit place- ment via machine learning,” in 59th ACM/IEEE Des. Automat. Conf. (DAC) (San Francisco, CA, USA, Jul. 10–14, 2022) p. 19–24. 55 G. Pascoal, J. P. Fernandes, and R. Abreu, “Deep Reinforcement Learning Strategies for Noise-Adaptive Qubit Routing,” in IEEE Int. Conf. Quantum Softw. (QSW) (Shenzhen, China, Jul. 7–13, 2024) p. 146–156. 56 W. Tang, Y. Duan, Y. Kharkov, R. Fakoor, E. Kessler, and Y. Shi, “AlphaRouter: Quantum Circuit Routing with Reinforce- ment Learning and Tree Search,” in IEEE Int. Conf. Quantum Comput. Eng. (QCE), Vol. 1 (Montreal, Canada, Sep. 15–20, 2024) p. 930–940. 57 A. Sinha, U. Azad, and H. Singh, “Qubit Routing Using Graph Neural Network Aided Monte Carlo Tree Search,” in 36th AAAI Conf. Artif. Intell. (Virtual Event, Feb. 22–Mar. 1, 2022) p. 9935–9943. 58 E. Russo, M. Palesi, D. Patti, G. Ascia, and V. Catania, “Op- timizing Qubit Assignment in Modular Quantum Systems via Attention-Based Deep Reinforcement Learning,” in Des. Au- tomat. Test Europe Conf. (DATE) (Lyon, France, Mar. 31–Apr. 2, 2025) p. 1–7. 59 S. Sang, L. Hour, and Y. Han, “Learning-Optimized Qubit Map- ping and Reuse to Minimize Inter-Core Communication in Mod- ular Quantum Architectures,” (2025), arXiv:2506.09323. 60 A. Zeynali and Z. Bakhshi, “Noise-Adaptive Quantum Circuit Mapping for Multi-Chip NISQ Systems via Deep Reinforcement Learning,” (2025), arXiv:2511.18079. 61 D. Cuomo, M. Caleffi, K. Krsulich, F. Tramonto, G. Agliardi, E. Prati, and A. S. Cacciapuoti, “Optimized Compiler for Dis- tributed Quantum Computing,” ACM Trans. Quantum Comput. (TQC) 4, 15:1–15:29 (2023). 62 P. Escofet, A. Ovide, M. Bandic, L. Prielinger, H. van Someren, S. Feld, E. Alarcon, S. Abadal, and C. Almudever, “Revisiting the Mapping of Quantum Circuits: Entering the Multi-core Era,” ACM Trans. Quantum Comput. (TQC) 6, 4:1–4:26 (2025). 63 R. Sundaram, H. Gupta, and C. Ramakrishnan, “DQC-QR: Dis- tributing and Routing Quantum Circuits with Minimum Execu- tion Time,” ACM Trans. Quantum Comput. (TQC) 6, 30:1–30:26 (2025). 64 X.Zhou, https://github.com/BensonZhou1991/ circuittransform/tree/master/inputs/QASM%20example (2019), GitHub repository, commit: 8e6e5b1. 65 N. Moll et al., “Quantum optimization using variational algo- rithms on near-term quantum devices,” Quantum Sci. Technol. 3, 030503 (2018). 66 M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information: 10th Anniversary Edition (Cambridge University Press, Cambridge, UK, 2010). 67 S. Boixo, S. V. Isakov, V. N. Smelyanskiy, R. Babbush, N. Ding, Z. Jiang, M. J. Bremner, J. M. Martinis, and H. Neven, “Charac- terizing quantum supremacy in near-term devices,” Nature Phys. 14, 595–600 (2018). 68 F. Arute et al., “Quantum supremacy using a programmable su- perconducting processor,” Nature 574, 505–510 (2019). 69 A. W. Cross, L. S. Bishop, S. Sheldon, P. D. Nation, and J. M. Gambetta, “Validating quantum computers using randomized model circuits,” Phys. Rev. A 100, 032328 (2019). 70 T. Tomesh and G. Contreras, https://github.com/ teaguetomesh/quantum_circuit_generator (2021), GitHub repository, commit: 0225dc5. 71 F. T. Leighton, “Introduction to Parallel Algorithms and Ar- chitectures: Arrays, Trees, Hypercubes,” (Morgan Kaufmann Publishers, Inc, San Francisco, CA, United States, 1991) Chap. 3.1–3.2, p. 392–472. 20 72 P. E. Hart, N. J. Nilsson, and B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths,” IEEE Trans. Syst. Sci. Cybern. 4, 100–107 (1968). 21 Appendix A: Prompt for the linear compiler The full prompt used to generate the linear-architecture compiler is reproduced below. The prompt refers to input files by name, concrete files placed in the working directory and not reproduced here. The circuit files, in .qasm or .json form, are the benchmark circuits of Sec. I B together with a few small hand-written checks. Each linear trap is a path whose central vertex is the gate vertex, of the length listed in Tab. I. Implement a complete Ion-Trap Shuttling Compiler in a single Python file. The compiler translates a quantum circuit into a sequence of physical shuttling operations for a linear ion-trap quantum computer, minimizing the total number of timesteps needed to execute the circuit. For the implementation, extend the existing ion_trap_compiler.py file. The file already contains some functions described below, which can be called directly. Do not re-implement these functions; only their interfaces, as described below, are relevant. SECTION 1 - HARDWARE MODEL (TrapGraph) The hardware is represented by the TrapGraph class, whose implementation is already provided in ion_trap_compiler.py. class TrapGraph: @property def num_vertices(self) -> int # Returns the number of vertices in the graph @property def vertices(self) -> List[int] # Returns all vertices of the graph def degree(self, v: int) -> int # Returns the degree of vertex v def neighbors(self, v: int) -> List[int] # Returns the adjacent vertices of vertex v @property def qubit_vertices(self) -> List[int] # Returns all qubit vertices @property def gate_vertices(self) -> List[int] # Returns all gate vertices @property def junctions(self) -> List[int] # Returns all vertices with degree > 2 def bfs_path(self, src: int, dst: int) -> Optional[List[int]] # Returns the shortest path from src to dst, including both endpoints def distance(self, src: int, dst: int) -> int # Returns the shortest distance from src to dst The TrapGraph is a linear graph of trap segments (vertices) numbered 0 to TrapGraph.num_vertices - 1, connected as a path: 0 - 1 - 2 - ... - (TrapGraph.num_vertices - 1). Each vertex can hold at most 2 ions, arranged as an ordered linear chain. Each vertex is either a qubit vertex or a gate vertex. At a gate vertex, the operations SEPARATE, MERGE, SWAP, and GATE can be executed; a qubit vertex can only store up to 2 ions. During gate execution, the gate vertex must contain exactly the number of ions required by the gate (no more, no fewer). During the execution of translations, the gate vertices can always be used for transfer. SECTION 2 - CIRCUIT INPUT The quantum circuit is represented by two lists: - qubits: List[str] # All qubits in the circuit - gates: List[QuantumGate] # All quantum gates in the circuit The quantum gates are represented by the QuantumGate class, whose implementation is already provided in ion_trap_compiler.py. @dataclass class QuantumGate: name: str # Name of the unitary operation qubits: List[str] # Qubits on which the gate acts params: List[Tuple[str, float]] # Parameters of the unitary operation gate_id: int # Sequential index in program order Every gate acts on exactly one or two qubits. Gates acting on the same qubit must be executed in the order in which they appear in the gates list. Gates acting on disjoint qubits may be executed in any order. SECTION 3 - PHYSICAL OPERATIONS There are five elementary operations. Each consumes one timestep unless grouped (see Sec. 6.3). TRANSLATE(src: int, dst: int) Move the entire contents of vertex src to adjacent vertex dst. Preconditions: src and dst are adjacent; dst is empty. After: src is empty, dst holds what src held. SEPARATE(vertex: int) Split the qubit chain at vertex into two halves. Since each vertex holds at most two qubits, the left qubit goes to the left neighbor and the right qubit to the right neighbor. Preconditions: vertex ∈ TrapGraph.gate_vertices; vertex contains 2 qubits; both neighbors are empty; left neighbor has a smaller index than right neighbor. After: vertex is empty. MERGE(vertex: int) Combine the chains from the two neighbors of vertex into vertex, in the order [left_chain, right_chain]. Preconditions: vertex ∈ TrapGraph.gate_vertices; each neighbor contains exactly one qubit; left neighbor has a smaller index than 22 right neighbor. After: both neighbors are empty. SWAP(vertex: int) Reverse the order of the qubit chain at vertex. Not permitted on a single-qubit chain. Preconditions: vertex ∈ TrapGraph.gate_vertices; vertex contains exactly two qubits. GATE(vertex: int, gate: QuantumGate) Execute gate at vertex. Preconditions: vertex ∈ TrapGraph.gate_vertices; the vertex contains exactly the qubits required by the gate (no more, no fewer); all per-qubit program-order dependencies of this gate are satisfied. Note: The qubit order within the vertex chain need not match the order in QuantumGate.qubits; only the sets of qubits must be identical. Implementation requirement: Record operations as compact tuples: - ("T", src: int, dst: int) for TRANSLATE - ("S", v: int, left_neighbor: int, right_neighbor: int) for SEPARATE - ("M", v: int, left_neighbor: int, right_neighbor: int) for MERGE - ("W", v: int) for SWAP - ("G", v: int, gate: QuantumGate) for GATE SECTION 4 - INPUT PARSING At program start, call the following function to parse all inputs. Its implementation is already provided in ion_trap_compiler.py. def parse_input() -> Tuple[TrapGraph, List[str], List[QuantumGate], float, Optional[str], Optional[str]] # Return values (positional): # 1. TrapGraph: hardware graph (see Sec. 1) # 2. List[str]: qubits (see Sec. 2) # 3. List[QuantumGate]: gates (see Sec. 2) # 4. float: time_begin (pass through to validate_and_output, Sec. 7) # 5. Optional[str]: output_json (pass through to validate_and_output, Sec. 7) # 6. Optional[str]: stats_file (pass through to validate_and_output, Sec. 7) SECTION 5 - INITIAL PLACEMENT Before shuttling begins, assign each qubit to exactly one vertex such that: - exactly ⌈len(qubits) / 2⌉ vertices hold qubits; - no vertex holds more than 2 qubits; - all remaining vertices are empty. Implement the function: def initial_mapping(trap_graph: TrapGraph, qubits: List[str], gates: List[QuantumGate] ) -> Dict[int, List[str]] # Return value: # Dict[int, List[str]]: initial_state # Keys are vertex indices; values are the qubit chains at those vertices (at most two qubits per vertex). Vertices with empty chains # may be omitted or represented with an empty list. The function can be implemented as follows: The circuit-DAG (Directed Acyclic Graph) represents the quantum circuit as a dependency graph. Each gate is a node. A directed edge from gate A to gate B exists if and only if gate B acts on at least one qubit that gate A also acts on, and gate B appears after gate A in program order with no intervening gate on that qubit -- meaning gate B depends on gate A and cannot execute before A completes. The depth of a node is the length of the longest directed path from any source node (a gate with no predecessors) to that node. The total DAG depth is the length of the longest such path in the entire graph, i.e., the minimum number of sequential layers required if all independent gates ran in parallel. Weight every gate g at circuit-DAG depth δ by w = 1 / (1 + δ / τ), where τ ≈ total_dag_depth / 3 (all float divisions), so that gates executed early carry more influence on placement decisions than gates deeper in the circuit. If total_dag_depth == 0, treat all gates as equally weighted. Use this weighted interaction matrix to build a weighted interaction graph whose nodes are qubits and whose edge weight between two qubits is the sum of weights of all gates acting on that pair. Default pairing rule: Compute a maximum-weight matching on the weighted interaction graph using a greedy procedure: repeatedly pick the heaviest unpaired edge and pair its two endpoint qubits; if len(qubits) is odd, the qubit with the lowest total interaction weight across all its edges is left unpaired as the singleton. Then perform greedy chain extraction over the matched-vertex interaction graph -- starting from the matched pair with the highest combined edge weight, repeatedly extend the chain by appending the adjacent matched pair with the highest connecting weight -- to produce an ordered sequence of pairs (and the singleton, if any). Place pairs and the singleton on consecutive trap vertices in this order. The resulting initial arrangement co-locates frequently interacting qubits at the same vertex and orders vertices so that the qubit layout along the trap minimizes required timesteps. For circuits with a chain-like qubit-interaction structure (as in qaoa_5.json), this placement should yield a mapping that requires zero swaps. Additionally, the initial mapping can reduce shuttling before the first gate. Notwithstanding the above rule, if the first applicable gate is a two-qubit gate, placing its qubits at a shared gate vertex eliminates any shuttling needed to make that gate executable. 23 Whenever qubits are placed at a gate vertex, the two neighbors of that gate vertex must be left empty in the initial mapping if a separation is required before moving these qubits (see Sec. 9). This greedy matching and chain-extraction procedure is the required default. Additional strategies (e.g., graph-coloring or other heuristics) may be layered on top to further reduce timesteps, but must not perform worse than the default on the provided benchmark circuits. An explicit nx.DiGraph circuit-DAG object is not required; any equivalent per-qubit dependency tracking is acceptable. SECTION 6 - COMPILER PIPELINE Implement the function: def compile(trap_graph: TrapGraph, qubits: List[str], gates: List[QuantumGate], initial_state: Dict[int, List[str]] ) -> List[List[Tuple]] # Return value: # List[List[Tuple]]: all_timesteps # The outer list is ordered by execution time. Each inner list contains all shuttling operations for that timestep, represented as # tuples (see Sec. 3). The compilation pipeline consists of the following steps: 6.1 GATE SCHEDULING Maintain a ready-queue of gates whose per-qubit dependencies are fully satisfied -- i.e., all earlier gates on the same qubits have already executed. At each scheduling step, select the next gate using the following priority heuristic, whose core principle is to minimize unnecessary qubit movement by batching gates that can run without re-shuttling: - If multiple ready gates share the same qubit set (one or two qubits), execute all of them consecutively before moving those qubits away from the gate vertex. - Among the remaining ready gates, prefer gates whose qubits are already at or closest to a gate vertex, minimizing shuttling needed to begin execution. Additional scheduling strategies are encouraged; this is an open-ended optimization target. 6.2 ROUTING Emit the TRANSLATE / SEPARATE / MERGE / SWAP operations needed to bring the required qubits to a gate vertex before each gate execution. Note: at any routing step, additional qubits may need to be translated to free vertices required for SEPARATE, MERGE, SWAP, or GATE operations. Intermediate qubits blocking a path may also need to be moved. Single-qubit gate case: Given: - current_state: Dict[int, List[str]] (same structure as initial_state) - QuantumGate with len(QuantumGate.qubits) == 1; qa = QuantumGate.qubits[0] 1. If qa shares its vertex with another qubit in current_state: - Move qa’s vertex to a gate vertex. - Execute SEPARATE to isolate qa. 2. Move qa to the gate vertex. 3. Execute the gate. Two-qubit gate case -- distance reduction via iterative merge-swap-separate: Given: - current_state: Dict[int, List[str]] - QuantumGate with len(QuantumGate.qubits) == 2; call the qubits qa and qb. 1. Trivial case: - If qa and qb are at the same vertex: move that vertex to a gate vertex and execute the gate. - Otherwise go to step 2. 2. Initialization: - Build a linear ordering of all qubits by iterating over current_state in ascending key order and concatenating the values: · linear_ordering: List[str], len == len(qubits) - Let intermediate_qubits = [i1, i2, ..., ik] be the qubits between qa and qb in linear_ordering. - By definition: · qa is directly left of i1 in linear_ordering. · qb is directly right of ik in linear_ordering. 3. Iterative Reduction: Repeat until intermediate_qubits == []: a) Choose direction: Select the side (qa or qb) that minimizes the approximate number of future timesteps: - qa will be merged with i1, or - qb will be merged with ik. b) Prepare for merge: - If the chosen qubit (qa or qb) shares its vertex with another qubit: · If qa is chosen: ♦ If qa is the right qubit in its chain: ■ Move qa’s vertex to a gate vertex and execute SEPARATE. ♦ If qa is the left qubit in its chain (i.e., qa shares with i1): 24 ■ Move that vertex to a gate vertex. ■ Execute SWAP, then SEPARATE. ■ Update: intermediate_qubits = [i2, i3, ..., ik]. · If qb is chosen: ♦ If qb is the left qubit in its chain: ■ Move qb’s vertex to a gate vertex and execute SEPARATE. ♦ If qb is the right qubit in its chain (i.e., qb shares with ik): ■ Move that vertex to a gate vertex. ■ Execute SWAP, then SEPARATE. ■ Update: intermediate_qubits = [i1, i2, ..., i(k-1)]. - If i1 (when qa is chosen) or ik (when qb is chosen) shares its vertex with another qubit: · Move that vertex to a gate vertex and execute SEPARATE. After this step, the chosen qubit and its neighbor (i1 or ik) are each alone at some vertex. c) Merge and propagate: - If qa is chosen: · Move qa to the left neighbor of the gate vertex. · Move i1 to the right neighbor of the gate vertex. - If qb is chosen: · Move qb to the right neighbor of the gate vertex. · Move ik to the left neighbor of the gate vertex. - Execute MERGE. Chain at gate vertex: [qa, i1] or [ik, qb]. - Execute SWAP. Chain becomes: [i1, qa] or [qb, ik]. - Execute SEPARATE. - Update intermediate_qubits: remove i1 (if qa chosen) or ik (if qb chosen). The intermediate chain is reduced by exactly one qubit. d) Dynamic reassignment (optional): - Different gate vertices may be used each round. - The choice of qa or qb in step a) may be re-evaluated each round. 4. Finalization: When intermediate_qubits == []: - If qa shares its vertex with another qubit: · Move qa’s vertex to a gate vertex and execute SEPARATE. - If qb shares its vertex with another qubit: · Move qb’s vertex to a gate vertex and execute SEPARATE. - Move qa to the left neighbor of the gate vertex. - Move qb to the right neighbor of the gate vertex. - Execute MERGE. - Execute the gate. Notes for both cases: - Not all gate vertices may be usable at every point in time. Always choose a gate vertex that approximately minimizes the number of timesteps. Chain-order optimization after two-qubit gate execution: After routing, the two target qubits are co-located in the gate vertex. Since QuantumGate.qubits order does not affect gate correctness, the qubit order within the vertex chain is irrelevant for the current gate but does affect routing efficiency for subsequent gates. Use a one-step lookahead over the next gate of each qubit: immediately after gate execution, consider inserting a post-execution SWAP if doing so would reduce the routing cost of the next gate touching either qubit. The preferred side of each qubit is the side of the gate vertex where its next 2-qubit-gate partner is currently on (None if the qubit has only single-qubit gates in the future or there is no next gate for the qubit). Insert the SWAP only when the post-SWAP arrangement matches more qubits on the preferred side than the no-SWAP arrangement. When in doubt, do not insert, as an unnecessary SWAP can cascade into extra separations downstream. 6.3 TIMESTEP GROUPING AND POST-PROCESSING A timestep is a set of operations executed simultaneously. After the routing emits the raw operation stream, apply the following passes in order: 1. Roundtrip elimination -- remove a TRANSLATE A→B immediately followed by TRANSLATE B→A when no intervening operation references A or B (as src, dst, or operand vertex). Removing the pair must leave A’s and B’s contents identical to the no-removal trace at every intermediate step. 2. Consecutive cancellation -- remove: - a SEPARATE immediately followed by a MERGE on the same vertex, - a MERGE immediately followed by a SEPARATE on the same vertex, - a SWAP immediately followed by another SWAP on the same vertex, in each case only when the qubits are not involved in any intervening operation. Apply passes 1 and 2 alternately to fixpoint. Use always the current, post-removal operation stream. When no further reductions are possible, proceed to pass 3. 3. Grouping -- pack independent operations into the same timestep: Translation timesteps: may contain only TRANSLATE operations. All translations on pairwise disjoint source/destination vertex pairs may be freely grouped. A "chain of translations" along consecutive vertices is also permitted: if TRANSLATE B→C and TRANSLATE A→B are both needed, they may share a timestep, provided each chained vertex except the rightmost (here C) actually holds a qubit at the start of the timestep. This is because B→C vacates B in the same timestep that A→B fills it. This chain rule extends to arbitrarily long consecutive sequences, where each qubit appears in at most one TRANSLATE. Non-translation timesteps: may contain only non-TRANSLATE operations (SEPARATE, MERGE, SWAP, GATE). Two such operations may share a timestep only if the vertex sets they involve are pairwise disjoint. The vertex set of an operation is: - SWAP(v): v 25 - GATE(v, ...): v - SEPARATE(v): v, v-1, v+1 - MERGE(v): v, v-1, v+1 In particular, a SEPARATE at v1 and a MERGE at v2 cannot share a timestep when v1, v1±1 ∩ v2, v2±1 ̸= ∅, even if v1 ̸= v2. SECTION 7 - VALIDATION AND OUTPUT At the end of the program, call the following function to validate the results and emit all output. Its implementation is already provided in ion_trap_compiler.py. def validate_and_output(trap_graph: TrapGraph, qubits: List[str], gates: List[QuantumGate], initial_state: Dict[int, List[str]], all_timesteps: List[List[Tuple]], time_begin: float, output_json: Optional[str] = None, stats_file: Optional[str] = None) # All parameters are the unchanged return values of parse_input (Sec. 4), initial_mapping (Sec. 5), and compile (Sec. 6). SECTION 8 - PERFORMANCE REQUIREMENTS The compiler must minimize runtime and peak RAM usage. Complexity should scale roughly linearly in all parameters: number of vertices, qubits, and gates. The compiler must handle large circuits (200 qubits, several hundred thousand gates, 400+ vertices) within an acceptable runtime and memory budget. Prefer greedy/heuristic approaches over exact optimization. SECTION 9 - WORKING EXAMPLE (VERIFICATION) The following example must produce a valid (not necessarily identical) shuttling sequence of at most 16 individual operations, completable in 12 timesteps or fewer. Command: python ion_trap_compiler.py --circ example.qasm --graph graph_7.json --gate 3 Trap graph: vertices 0-6 in a path; vertex 3 is the only gate vertex. Initial mapping: Map q[0],q[1] → Vertex 3 Map q[2] → Vertex 5 Reference 16-step sequence with 12 timesteps: Timestep 1: 1. GATE cx q[0],q[1] at Vertex 3 Timestep 2: 2. SEPARATE Vertex 3 → q[0]→V2, q[1]→V4 Timestep 3: 3. TRANSLATE q[0]: V2→V1 4. TRANSLATE q[1]: V4→V3 5. TRANSLATE q[2]: V5→V4 Timestep 4: 6. TRANSLATE q[1]: V3→V2 Timestep 5: 7. MERGE V2+V4 → Vertex 3 (contains q[1],q[2]) Timestep 6: 8. GATE cx q[1],q[2] at Vertex 3 Timestep 7: 9. SWAP Vertex 3 (chain becomes q[2],q[1]) Timestep 8: 10. SEPARATE Vertex 3 → q[2]→V2, q[1]→V4 Timestep 9: 11. TRANSLATE q[1]: V4→V5 12. TRANSLATE q[2]: V2→V3 13. TRANSLATE q[0]: V1→V2 Timestep 10: 14. TRANSLATE q[2]: V3→V4 Timestep 11: 15. MERGE V2+V4 → Vertex 3 (contains q[0],q[2]) Timestep 12: 16. GATE cx q[0],q[2] at Vertex 3 SECTION 10 - CODE QUALITY - Single file, Python 3.12+. All Python libraries are permitted; however, only libraries needed to compute the requested output may be installed. 26 - Determinism: the compiler must produce byte-identical output for identical inputs across runs, independent of PYTHONHASHSEED or any other process-level entropy. Iterations over sets, dicts, or any other unordered containers whose order can affect the emitted operation stream must be explicitly sorted (e.g., by qubit name, vertex index, or gate id). The random module must not be used without a fixed, in-source seed. - All graph traversals (DAG depth, routing reductions, cycle detection in timestep grouping, etc.) must be iterative -- using an explicit stack or queue -- never recursive. Recursive traversal exceeds Python’s default recursion limit on 200-qubit / 100k-gate inputs and is forbidden. SECTION 11 - ACCEPTANCE TEST MATRIX The implementation must pass every test below; otherwise it must be automatically debugged until all tests pass. Each test fixes the input, invocation, and expected bound; the schedule itself need not match any reference. T1. Sec. 9 cx-triangle. Input/invocation: as in Sec. 9. Expected: ≤ 16 individual operations, ≤ 12 timesteps. T2. Same-pair batching. Input: 10 gates, each on the same qubit pair (q0, q1). Invocation: python ion_trap_compiler.py --circ same_pair.qasm --graph graph_5.json --gate 2 Expected: q0 and q1 are mapped to vertex 2 in the initial state; the 10 GATE operations execute back-to-back on that vertex; SEPARATE, MERGE, SWAP, and TRANSLATE counts are all 0. T3-T8 exercise the .json benchmark circuits. T3. qaoa_5.json -- chain-structured zero-SWAP target. Input: 5 qubits, 35 gates, two-qubit interaction graph is the path q0-q1-q2-q3-q4 (only 4 RZZ gates, all on adjacent pairs). Invocation: python ion_trap_compiler.py --circ qaoa_5.json --graph graph_11.json --gate 5 Expected: 0 SWAP operations. This is the canonical regression target for the initial-placement heuristic described in Sec. 5. T4. rd32-v0_66.json -- small reversible circuit, 4 qubits, 42 gates. Invocation: python ion_trap_compiler.py --circ rd32-v0_66.json --graph graph_9.json --gate 4 Expected: schedule verifies; runtime under one second on commodity hardware. The smallest non-trivial benchmark; serves as a fast smoke test. T5. 4mod5-v1_23.json -- 5 qubits, 102 gates, two-qubit interaction graph is non-chain. Invocation: python ion_trap_compiler.py --circ 4mod5-v1_23.json --graph graph_11.json --gate 5 Expected: schedule verifies; SWAP count > 0 (this circuit cannot be routed without swaps, testing that the routing emits them when needed). T6. 4mod5-bdd_287.json -- 7 qubits, 106 gates. Invocation: python ion_trap_compiler.py --circ 4mod5-bdd_287.json --graph graph_15.json --gate 7 Expected: schedule verifies. T7. alu-v2_31.json -- 5 qubits, 640 gates (largest gate count in the set). Invocation: python ion_trap_compiler.py --circ alu-v2_31.json --graph graph_11.json --gate 5 Expected: schedule verifies. T8. cnt3-5_179.json -- 16 qubits, 230 gates (largest qubit count in the set). Invocation: python ion_trap_compiler.py --circ cnt3-5_179.json --graph graph_33.json --gate 16 Expected: schedule verifies. Cross-cutting requirements over T3-T8: - For each circuit, the operation stream is byte-identical across two runs with different PYTHONHASHSEED values. - Total wall-clock time and peak RSS scale roughly linearly with number of vertices, qubits, and gates; no individual circuit takes more than a small multiple of the time predicted by linear extrapolation from the smallest circuit. 27 Appendix B: Prompt for the branched compiler The prompt for the branched-architecture compiler is reproduced below. It is issued with the optimized linear- architecture compiler as its seed and specifies the changes needed for a branched, tree-structured trap with junctions and stacks. Its circuit files are as in Appendix A. The trap-graph files encode branched traps as a JSON edge list of segment pairs. A file named graph_n_h_d has an n-segment main axis, side-stacks of height h, and junction distance d. Implement a complete Ion-Trap Shuttling Compiler in a single Python file. The compiler translates a quantum circuit into a sequence of physical shuttling operations for a linear ion-trap quantum computer with junctions, minimizing the total number of timesteps needed to execute the circuit. For the implementation, extend the existing ion_trap_compiler.py file. The file already contains a working compiler for a junction-free linear trap and exposes the helpers described below, which can be called directly. Do not re-implement these helpers; only their interfaces, as described below, are relevant. Every other function in the file (initial_mapping, compile, and the internal routing/grouping helpers) must be adapted to the junction topology described in this document. SECTION 1 - HARDWARE MODEL (TrapGraph) The hardware is represented by the TrapGraph class, whose implementation is already provided in ion_trap_compiler.py. The class is junction-aware and exposes structural helpers for the main axis and stacks; routing code should prefer these helpers over any reasoning based on vertex indices. class TrapGraph: # Basics @property def num_vertices(self) -> int # Number of vertices @property def vertices(self) -> List[int] # All vertices, sorted def degree(self, v: int) -> int # Degree of v def neighbors(self, v: int) -> Tuple[int, ...] # Adjacent vertices, sorted (immutable tuple) @property def qubit_vertices(self) -> List[int] # All qubit vertices, sorted @property def gate_vertices(self) -> List[int] # Gate vertices (order from CLI) @property def junctions(self) -> List[int] # All vertices with degree > 2, sorted # Topology helpers def is_junction(self, v: int) -> bool # O(1) def is_on_main_axis(self, v: int) -> bool # O(1) @property def main_axis(self) -> List[int] # Ordered [0, 1, ..., M] def stacks_at(self, j: int) -> List[List[int]] # For junction j: list of stacks; each stack is # [slot 0, slot 1, ..., bottom] def stack_of(self, v: int) -> Optional[Tuple[int, int, int]] # (junction, stack_index, slot_index) for stack vertices, None for # main-axis vertices # Distances and paths (precomputed; O(1) distance, paths are cached) def bfs_path(self, src: int, dst: int) -> Optional[List[int]] # Shortest path from src to dst, including both endpoints def distance(self, src: int, dst: int) -> int # Shortest distance from src to dst def next_hop(self, src: int, dst: int) -> Optional[int] # First vertex after src on the unique src->dst path def path_passes_through(self, src, dst, v: int) -> bool # True iff v is a strict interior vertex of the src->dst path def junctions_on_path(self, src, dst) -> List[int] # Junctions visited along the src->dst path def subtree_through(self, j: int, via: int) -> Set[int] # All vertices reachable from j by first stepping to via, excluding # j Topology: The TrapGraph is a tree consisting of one main linear axis (the contiguous index range 0, 1, ..., M, available as TrapGraph.main_axis) with zero or more side branches ("stacks") attached to it. A junction has degree ≥ 3 and connects one or more linear stacks of qubit-only vertices that extend away from the main axis. Each stack is enumerated by stacks_at(j) in slot order (slot 0 is junction-adjacent); for a stack vertex v, stack_of(v) returns its (junction, stack_index, slot_index). A graph with no junctions reduces to the plain linear case; stacks_at returns [] there and stack_of returns None for every vertex. Example (M = 6, junctions at vertices 1 and 5, two stacks of height 3, gate vertex at 3): 9 12 | | 8 11 | | 7 10 | | 0 - 1 - 2 - 3 - 4 - 5 - 6 TrapGraph.num_vertices == 13 TrapGraph.qubit_vertices == [0, 2, 4, 6, 7, 8, 9, 10, 11, 12] TrapGraph.gate_vertices == [3] TrapGraph.junctions == [1, 5] TrapGraph.main_axis == [0, 1, 2, 3, 4, 5, 6] TrapGraph.stacks_at(1) == [[7, 8, 9]] # 7 is slot 0 TrapGraph.stacks_at(5) == [[10, 11, 12]] TrapGraph.stack_of(8) == (1, 0, 1) # junction 1, stack 0, slot 1 TrapGraph.stack_of(3) == None # main-axis vertex All benchmark JSON files in this directory follow this convention. Stacks may have different heights and junctions may sit anywhere on the main axis. 28 Each vertex can hold at most 2 ions, arranged as an ordered linear chain. Vertex types and their constraints: - Gate vertex (∈ TrapGraph.gate_vertices): · The operations SEPARATE, MERGE, SWAP, and GATE may be executed there. · During gate execution, the gate vertex must contain exactly the qubits required by the gate (no more, no fewer). · A gate vertex always lies on the main axis. Its two neighbors are never junctions; both have degree ≤ 2. This means SEPARATE and MERGE well-define a left and right neighbor. · A gate vertex may always be used as a transit vertex during translations. - Junction vertex (∈ TrapGraph.junctions): · May hold ions only while they are in transit (i.e., between two consecutive TRANSLATEs of the same chain). During every SEPARATE, MERGE, SWAP, and GATE all junctions must be empty. · No-roundtrip rule: if TRANSLATE(a, j) moves a chain into junction j, the next TRANSLATE involving that junction must be TRANSLATE(j, b) with b ̸= a. The chain must leave the junction through a different edge than the one it entered through. · Exit-availability rule (planning consequence of the no-roundtrip rule and of the "transit only" restriction above): before emitting TRANSLATE(a, j) that lands a chain on junction j, the routing must guarantee that, at the moment the chain arrives, at least one neighbor of j other than the entry edge ‘a‘ is empty (or will be made empty in the same translation timestep by a chained translation), so that the chain can be drained on the next translation step. If no such exit can be secured -- e.g. because every other neighbor holds an ion and is itself a dead-end or full stack -- the routing must pick a different plan (a different path, a stack push elsewhere, or a different gate vertex). Translating onto a junction whose every non-entry exit is occupied by chains that cannot themselves be displaced is a permanent deadlock and is forbidden. - Qubit vertex: · Any other vertex. May hold up to 2 ions; never executes SEPARATE / MERGE / SWAP / GATE. Stack mechanics (LIFO): Each stack attached to a junction j is a Last-In, First-Out buffer. The stack vertex adjacent to j is called slot 0; the next deeper vertex is slot 1; and so on. The slot-0 vertex is the only access port -- qubits enter and leave the stack only through that vertex, via the junction. Pushes and pops have constant timestep cost regardless of stack depth: - Push: a qubit chain at the junction j is translated to slot 0. If slot 0 already holds a chain, every occupied slot shifts one slot deeper simultaneously (slot k → slot k+1 for every occupied k, plus j → slot 0). All of these translations share a single timestep under the chain-of-translations rule (Sec. 6.3), so a push costs exactly one translation timestep as long as the deepest occupied slot is not already the bottom of the stack. Empty slots between occupied slots do not block the cascade -- only occupied slots emit a shift; the chain-rule requirement (each chained source initially occupied) is satisfied for every emitted shift. - Pop: the qubit chain at slot 0 is translated through the junction. Simultaneously, every deeper occupant shifts one slot shallower (slot k+1 → slot k for every occupied k+1) within the same timestep. A pop therefore also costs exactly one translation timestep as long as slot 0 is occupied. As with push, empty slots between occupied slots are no obstacle; only occupied slots emit a shift. Qubits inside a stack cannot pass each other. The order in which qubits exit a stack is the reverse of the order in which they entered. To reach a qubit deeper than another, every shallower qubit must be extracted first; in-place permutation of stack contents is impossible. Reordering is only achievable by evacuating qubits out of the stack along its edges (through the junction onto the main axis or another stack), holding them at other vertices, and re-pushing in the desired order. SECTION 2 - CIRCUIT INPUT The quantum circuit is represented by two lists: - qubits: List[str] # All qubits in the circuit - gates: List[QuantumGate] # All quantum gates in the circuit The QuantumGate class is provided in ion_trap_compiler.py. @dataclass class QuantumGate: name: str # Name of the unitary operation qubits: List[str] # Qubits on which the gate acts params: List[Tuple[str, float]] # Parameters of the unitary operation gate_id: int # Sequential index in program order Every gate acts on exactly one or two qubits. Gates acting on the same qubit must be executed in the order in which they appear in the gates list. Gates acting on disjoint qubits may be executed in any order. SECTION 3 - PHYSICAL OPERATIONS There are five elementary operations. Each consumes one timestep unless grouped (see Sec. 6.3). TRANSLATE(src: int, dst: int) Move the entire contents of vertex src to adjacent vertex dst. Preconditions: src and dst are adjacent in TrapGraph; dst is empty; src is non-empty; if src is a junction, dst is not the vertex from which the chain currently at src entered (no-roundtrip rule). After: src is empty, dst holds what src held. SEPARATE(vertex: int) Split the qubit chain at vertex into its two halves. Since each vertex holds at most two qubits, the left qubit goes to the left neighbor and the right qubit to the right neighbor. Preconditions: vertex ∈ TrapGraph.gate_vertices; vertex contains 2 qubits; both neighbors are empty; left neighbor has a smaller index than right neighbor; all junctions are empty. After: vertex is empty. 29 MERGE(vertex: int) Combine the chains from the two neighbors of vertex into vertex, in the order [left_chain, right_chain]. Preconditions: vertex ∈ TrapGraph.gate_vertices; each neighbor contains exactly one qubit; left neighbor has a smaller index than right neighbor; all junctions are empty. After: both neighbors are empty. SWAP(vertex: int) Reverse the order of the qubit chain at vertex. Not permitted on a single-qubit chain. Preconditions: vertex ∈ TrapGraph.gate_vertices; vertex contains exactly two qubits; all junctions are empty. GATE(vertex: int, gate: QuantumGate) Execute gate at vertex. Preconditions: vertex ∈ TrapGraph.gate_vertices; the vertex contains exactly the qubits required by the gate (no more, no fewer); all per-qubit program-order dependencies of this gate are satisfied; all junctions are empty. Note: The qubit order within the vertex chain need not match the order in QuantumGate.qubits; only the sets of qubits must be identical. Implementation requirement: Record operations as compact tuples: - ("T", src: int, dst: int) for TRANSLATE - ("S", v: int, left_neighbor: int, right_neighbor: int) for SEPARATE - ("M", v: int, left_neighbor: int, right_neighbor: int) for MERGE - ("W", v: int) for SWAP - ("G", v: int, gate: QuantumGate) for GATE SECTION 4 - INPUT PARSING At program start, call the following function to parse all inputs. Its implementation is already provided in ion_trap_compiler.py. def parse_input() -> Tuple[TrapGraph, List[str], List[QuantumGate], float, Optional[str], Optional[str]] # Return values (positional): # 1. TrapGraph: hardware graph (see Sec. 1) # 2. List[str]: qubits (see Sec. 2) # 3. List[QuantumGate]: gates (see Sec. 2) # 4. float: time_begin (pass through to validate_and_output, Sec. 7) # 5. Optional[str]: output_json (pass through to validate_and_output, Sec. 7) # 6. Optional[str]: stats_file (pass through to validate_and_output, Sec. 7) SECTION 5 - INITIAL PLACEMENT Before shuttling begins, assign each qubit to exactly one vertex such that: - exactly ⌈len(qubits) / 2⌉ vertices hold qubits; - no vertex holds more than 2 qubits; - no junction vertex holds any qubit; - all remaining vertices are empty. Implement the function: def initial_mapping(trap_graph: TrapGraph, qubits: List[str], gates: List[QuantumGate] ) -> Dict[int, List[str]] # Return value: # Dict[int, List[str]]: initial_state # Keys are vertex indices; values are the qubit chains at those vertices (at most two qubits per vertex). Vertices with empty chains # may be omitted or represented with an empty list. The function can be implemented as follows: The circuit-DAG (Directed Acyclic Graph) represents the quantum circuit as a dependency graph. Each gate is a node. A directed edge from gate A to gate B exists if and only if gate B acts on at least one qubit that gate A also acts on, and gate B appears after gate A in program order with no intervening gate on that qubit -- meaning gate B depends on gate A. The depth of a node is the length of the longest directed path from any source node to it. The total DAG depth is the maximum such path in the graph. Weight every gate g at circuit-DAG depth δ by w = 1 / (1 + δ / τ), where τ ≈ total_dag_depth / 3 (all float divisions), so that gates executed early carry more influence on placement decisions than gates deeper in the circuit. If total_dag_depth == 0, treat all gates as equally weighted. Build a weighted interaction graph whose nodes are qubits and whose edge weights are summed gate weights over all 2-qubit gates acting on each pair. Default pairing rule: Compute a maximum-weight matching on the weighted interaction graph using a greedy procedure: repeatedly pick the heaviest unpaired edge and pair its two endpoint qubits. Tie-breaker among edges of equal weight: sort by the lexicographic order of the qubit-name tuple (smaller name first within each edge, then smaller edge first). If len(qubits) is odd, the qubit with the lowest total interaction weight is left unpaired as the singleton; ties broken by qubit name (string sort). Then perform greedy chain extraction over the matched-vertex interaction graph: starting from the matched pair with the highest internal weight (the weight of the edge between the two qubits of the pair; ties broken by the qubit-name tuple of the pair), repeatedly extend the chain by appending the adjacent unused matched pair connected by the heaviest cross-pair edge to the current chain’s last pair (ties 30 broken by the qubit-name tuple of the candidate pair). The chain extends only at the most recently appended end. The result is an ordered sequence of pairs (and the singleton, if any), called the items list below. Intra-pair qubit orientation (the order in which the two qubits of a pair sit within the vertex chain at placement time): for each pair, compute for each of its two qubits the sum of edge weights from that qubit to every qubit in other items (other pairs and the singleton, if any). Place the qubit with the greater such total at chain index 0; the other at chain index 1. Ties broken by qubit name lexicographically (smaller-name qubit at chain index 0). This rule deterministically orients the qubit with stronger downstream interactions so it ends up on the side of the pair that the candidate-vertex order (sorted by distance to the nearest gate vertex, then by vertex index) will fill next -- i.e. closer to the later-placed items, reducing routing distance for the gates that act between this pair and those later items. Place pairs and the singleton on a sequence of trap vertices chosen as follows: 1. Compute the candidate vertex list: candidates = sorted( [v for v in trap_graph.vertices if not trap_graph.is_junction(v)], key=lambda v: (min(trap_graph.distance(v, gv) for gv in trap_graph.gate_vertices), v) ) This places vertices closest to any gate vertex first, with vertex index as a deterministic tie-breaker. Main-axis and stack vertices that are equidistant from a gate vertex are interleaved naturally. 2. Walk candidates in order and assign each ordered item (pair or singleton) to the next available candidate vertex. Junction vertices are never used. Override: if the first applicable gate is a two-qubit gate whose qubit set equals items[0], place items[0] at the gate vertex that minimizes the sum of distances to every non-junction vertex (i.e. the union of trap_graph.qubit_vertices and trap_graph.gate_vertices -- a centrality measure that spreads remaining items evenly; ties broken by gate vertex index). Reserve both neighbors of that gate vertex as empty for the SEPARATE that follows the first MERGE. Subsequent items continue to fill candidates from the front of the list, skipping the gate vertex itself and the reserved neighbors. Note: this gate-vertex-selection rule is distinct from the per-gate "best gv" rule used in Sec. 6.2 Step 1 (which ranks by combined distance from the two endpoints). The placement rule above is used only at compile-time initial-state setup; the routing rule of Sec. 6.2 is recomputed for every two-qubit gate during scheduling. This greedy matching and graph-distance-based placement is the required default. Additional strategies (e.g., graph-coloring, simulated annealing) may be layered on top, but must not perform worse than the default on the acceptance tests. For circuits with a chain-like qubit-interaction structure (as in qaoa_5.json, qaoa_25.json, qaoa_40.json), this placement should yield a mapping that requires zero swaps independently of the underlying graph topology. An explicit graph object for the circuit-DAG is not required; any equivalent per-qubit dependency tracking is acceptable. SECTION 6 - COMPILER PIPELINE Implement the function: def compile(trap_graph: TrapGraph, qubits: List[str], gates: List[QuantumGate], initial_state: Dict[int, List[str]] ) -> List[List[Tuple]] # Return value: # List[List[Tuple]]: all_timesteps # The outer list is ordered by execution time. Each inner list contains all shuttling operations for that timestep, represented as # tuples (see Sec. 3). compile must compile the circuit completely: the returned all_timesteps must execute every gate in gates. Partial compilation is forbidden -- if any gate cannot be routed, compile must raise an exception instead of returning a schedule that omits gates (see the no-partial-schedule rule in Sec. 11). The compilation pipeline consists of the following steps: 6.1 GATE SCHEDULING Maintain a ready-queue of gates whose per-qubit dependencies are fully satisfied -- i.e., all earlier gates on the same qubits have already executed. At each scheduling step, select the next gate using the following priority heuristic, whose core principle is to minimize unnecessary qubit movement by batching gates that can run without re-shuttling: - If multiple ready gates share the same qubit set (one or two qubits), execute all of them consecutively before moving those qubits away from the gate vertex. - Among the remaining ready gates, prefer gates whose qubits are currently closest (by trap_graph.distance) to a gate vertex. Additional scheduling strategies are encouraged; this is an open-ended optimization target. 6.2 ROUTING Routing is graph-aware: every primitive that walks along the trap must consult trap_graph.next_hop / trap_graph.bfs_path / trap_graph.distance instead of integer index arithmetic, since the topology is no longer a single linear path. Use is_on_main_axis / is_junction / stack_of / stacks_at to discriminate vertex roles; never infer them from index ranges. Internal compiler state (in addition to current_state and qubit→vertex maps): - For each junction j currently holding ions, the entry vertex from which those ions arrived. This entry record must be updated on every TRANSLATE: writing the entry on TRANSLATE(*, j) and clearing it on TRANSLATE(j, *). It is consulted to enforce the no-roundtrip rule during routing decisions and during timestep grouping (Sec. 6.3). 31 Terminology used below: - "next_gate_id(q)" -- the gate_id (Sec. 2) of the next gate involving qubit q that has not yet been scheduled, in program order. If q has no remaining gates, treat next_gate_id(q) as +∞. - "keep qubit" / "keep set" -- the qubit(s) currently being routed for the gate under consideration. For a single-qubit gate routing of q, the keep set is q; for a two-qubit gate of qa, qb, the keep set is qa, qb. Routing helpers must never displace a keep qubit except via the controlled displacements permitted by the Endpoint-protection rule (snapshot-wrapped, with guaranteed return before MERGE). Movement primitives (graph-aware, replace any linear-index versions): Endpoint protection (binding across the entire routing of a single gate): Once a routing pass has placed an endpoint qubit (qa or qb of the gate currently being routed) on a gv-neighbor, the vertex holding that qubit becomes a "placed" vertex. The placed qubit is protected only in the sense that, by the time MERGE is emitted, qa and qb must both sit on the two gv-neighbors. Subsequent routing of other qubits (evacuate / clear_junctions / move / push, and any of the Swap-, Stack-, Park-the-endpoint methods invoked while still routing the same gate) may temporarily displace a placed endpoint -- including routing other qubits through the placed vertex via the Swap-Method, or temporarily moving the placed endpoint aside -- provided the displacement is followed by a guaranteed re-delivery of that endpoint back to a gv-neighbor before MERGE. In particular: - A placed endpoint may be used as a swap partner in a Swap-Method step that routes another qubit past it; after the SEPARATE the endpoint may end up at a vertex adjacent to gv (possibly the opposite neighbor), and that is acceptable as long as it ends up at *one* of the two gv-neighbors when MERGE fires. - A placed endpoint may be temporarily relocated by any other method (Stack-Method push onto a free stack, Park-the-endpoint, a plain move) when doing so is the cheapest way to clear an obstruction, again provided the routing guarantees a return to a gv-neighbor before MERGE. - Endpoint chains must never be split: an endpoint must remain on its own (or paired with the other endpoint) -- it must not be merged with a non-endpoint qubit and left there. Merging with a non-endpoint is only temporarily allowed, e.g. to execute a MERGE+SWAP+SEPARATE for the Swap-Method, after which SEPARATE returns the endpoint to its own vertex within the same routing pass. To enforce "guaranteed return", the routing should plan the relocation and its reversal as a single transaction wrapped in snapshot/restore (see Sec. 12.1 for the canonical pattern), rolling back on failure. If, after the displacement, the placed endpoint cannot be routed back to either gv-neighbor without mutual exclusion, the routing must restart with a different gate vertex; on restart, the placed endpoint is fully unprotected and free to participate from scratch. Strict-blocking of placed vertices (i.e., adding every placed vertex unconditionally to the blocked / protect set of every helper call) remains an acceptable conservative strategy and is what the simplest finalize implementation should use first. The relaxations above are optimizations that the compiler may apply when a strict-blocked attempt would otherwise force a costly restart or an unnecessarily long detour. They are not preconditions for correctness. move(src, dst, blocked): Step along the unique src→dst tree path using trap_graph.next_hop (or iterate over trap_graph.bfs_path). At each hop: - If the next vertex is occupied, open it iteratively via push (see below) using a work-stack (Sec. 12.4), passing blocked ∪ src. - Emit TRANSLATE(cur, next). Returns False if no obstruction can be cleared. The path passes through junctions naturally; because bfs_path returns a simple path, each junction is entered and exited through different edges, so the no-roundtrip rule is respected automatically as long as the chain is flushed off the junction before any non-translation operation runs (see Sec. 6.3 grouping). move() must not terminate with the chain resting on a junction: if dst happens to be a junction, that is a caller bug (the spec only valid dst for move is a non-junction); if a junction is the last reachable vertex due to an obstacle, the routine returns False and the caller picks a different strategy. push(v, away_from, blocked): Move the chain at v one hop, away from away_from. Among neighbors of v not in blocked and not equal to away_from, prefer non-junction neighbors over junction neighbors (junctions are last resort, since they impose the no-roundtrip constraint). Break ties by vertex index for determinism. If the chosen neighbor is occupied, cascade-push it first via the iterative work-stack routine of Sec. 12.4 -- never use Python recursion (Sec. 10). The push() primitive here is the convenient short name used by move(); its work-stack implementation is documented in Sec. 12.4 (CASCADE PUSH FOR EVACUATE). Do not confuse it with Sec. 12.11 (STACK PUSH (LIFO CASCADE)), which is a different routine that inserts a chain into a stack column. No-roundtrip skip rule: if v itself is a junction, skip any candidate neighbor that equals v’s recorded entry edge -- translating back through the same edge the chain arrived on is forbidden by the no-roundtrip rule (Sec. 1). Pushing into a candidate neighbor that already holds a chain is separately forbidden by the dst-empty precondition of TRANSLATE (Sec. 3) and is handled by the cascade branch above. evacuate(v, blocked, keep=None, extra_avoid=None, force=False): Move the chain at v to the closest free non-junction vertex. Implement via BFS from v over the trap graph, applying the transit/destination rules of Sec. 12.2 to blocked and extra_avoid. Move the chain along that BFS path with move(). - blocked: vertices treated according to Sec. 12.2 (occupied non-junc in blocked = off-limits; empty non-junc in blocked = transit-only; junction in blocked = transit-only; nothing else affected). - keep: optional set of qubit names. If keep is given and the chain at v contains any keep qubit, refuse and return False unless force=True (relaxed endpoint-protection rule, see Sec. 6.2). The caller is then expected to wrap the call in snapshot/restore and re-deliver. - extra_avoid: optional set of vertices that are off-limits as both target and transit (typically the junctions on the outer walk_path’s path; see Sec. 12.3). Note: this parameter has the same semantics as hard_blocked introduced in Sec. 12.10; an implementation may merge them into a single parameter (recommended name: hard_blocked) and treat extra_avoid as an alias for backward compatibility. - force: when True, allow displacement of keep qubits encountered mid-walk. force=True is propagated through all recursive calls of evacuate / walk_path / find_empty_targets (see Sec. 12.10); callers must still pass hard_blocked to protect outer-walk source chains from being transited through. Returns True on success (chain moved to an empty non-junction target), False otherwise. clear_junction(j, blocked): If j holds ions, evacuate them off the junction so that the next non-translation operation can run. 32 All routing helpers must take blocked as an explicit Set[int] of forbidden vertices and must honor it strictly on their *primary* invocation. A helper must not silently re-try itself with a weaker blocked set; if the primary attempt fails it returns False. A *caller* may, inside its own snapshot/restore transaction, re-invoke the helper with progressively weaker constraints (e.g. drop the path-junction extra_avoid, or fall back to a minimal pblocked containing only the source and final destination of the outer walk). Sec. 12.3 documents the canonical three-step relaxation used inside walk_path’s obstacle evac, and Sec. 12.5 lays out the outer fallback chain (declutter, decongest, last-resort case (b)). Every level of relaxation must be wrapped in its own snapshot/restore so a wrong choice rolls back cleanly. evacuate is allowed to return False; the caller, not the helper, decides whether to relax and retry or to abandon and try a different strategy entirely. Single-qubit gate routing: Given current_state and a QuantumGate with qubits = [qa]: 1. If qa shares its vertex with another qubit, move the whole pair to a chosen gate vertex, evacuate the gate vertex’s two neighbors, emit SEPARATE. 2. Move qa to a gate vertex via move(). 3. Emit GATE(gv, gate). Stack-extraction prefix: if qa currently sits at slot k > 0 of some stack column (precisely: trap_graph.stack_of(qpos[qa]) is not None and stack_of(qpos[qa])[2] > 0), run the Sec. 6.2 Stack-reordering protocol before step 1, so qa (and any vertex-mate) ends up walked out to a main-axis non-junction before any SEPARATE is attempted. This matches the two-qubit pre-extract step in Sec. 12.5 step 1 and keeps the single-qubit fast path deterministic. The target hint t to pass to the extraction routine is the gate vertex about to be used (Sec. 6.2 Phase 3 tie-breaker). When qa’s chain at qpos[qa] has size ≥ 2 and qa sits at slot k > 0 (the "buried 2-chain" case), the stack-reordering protocol must separate the chain at qpos[qa] before any pop, parking qa’s partner one slot deeper (or popping the partner outward first if no deeper slot exists) -- see the [step-1-strengthening] "Buried-2-chain stack extraction" block at the end of Sec. 12.5 for the detailed protocol. Without this separation step, a 2-chain cannot pop into a shallower single-slot vertex and extraction silently returns False. Fallback when isolation fails: if the standard isolation flow above cannot land qa alone at a gate vertex (e.g. because aggressive displacement during a force-walk left qa parked in a deep stack), the routing must take a snapshot and run a decongest pass: for every non-qa qubit, if it sits in a stack at slot > 0, run stack extraction on it; otherwise walk it toward any empty non-junction that is not on the qa-to-gate-vertex corridor. Re-run stack extraction on qa one more time (in case the decongest displaced it deeper), then retry the standard isolation flow. If that still fails, restore the snapshot and raise an exception per the no-partial-schedule rule (Sec. 11): the compiler must never emit a partially compiled circuit. Every gate of the circuit must be routed and emitted; if any gate cannot be routed by any available strategy, the compiler must raise an exception rather than return a schedule that omits that gate. Returning a partial schedule (one that the validator would reject for unexecuted gates) is forbidden -- the only two permitted outcomes are a complete, valid schedule or a raised exception. Without the second re-extract step, a force-walk that pushes qa one slot deeper into a stack leaves the chain unreachable on retry. Two-qubit gate routing -- iterative distance reduction: Given current_state and a QuantumGate with qubits = [qa, qb]: Step 0 -- trivial same-vertex case: If qa and qb are at the same vertex: move that vertex to a gate vertex (if not already there) and emit GATE. Step 1 -- initialization: Choose a gate vertex gv (ranked by the sum of distances from qpos[qa] and qpos[qb] to gv; ties broken by gv index). Let l and r be gv’s two non-junction main-axis neighbors (l < r), and choose the assignment qa → l, qb → r that minimizes total movement -- concretely distance(qpos[qa], l) + distance(qpos[qb], r) versus distance(qpos[qa], r) + distance(qpos[qb], l), swapping roles when the alternative is lower; see Sec. 12.9 for the tie-break. Define the "intermediate qubits" as those qubits q’ /∈ qa, qb whose current vertex v’ lies on trap_graph.bfs_path(qpos[qa], l) or trap_graph.bfs_path(qpos[qb], r), excluding the endpoint vertices qpos[qa] and qpos[qb] but including l and r themselves whenever they are occupied by a non-endpoint chain. If the gate vertex does not lie on a BFS path, any chain at gv is handled separately by Step 3 case (b). This definition is the routing-intermediate set: it is exactly the set of qubits that obstruct the delivery of qa to l and qb to r, so clearing it is both necessary and sufficient for Step 3 to proceed. Edge cases: - If qpos[qa] coincides with l (likewise qpos[qb] with r), the corresponding BFS path is empty and contributes no intermediates from that side. - If qpos[qa] = qpos[qb] (Step 0 handled it already), skip Step 1 entirely. - The two BFS paths may share vertices (in particular when gv lies on a shared trunk). Take the set union; do not double-count. Step 2 -- iterative reduction. Repeat until no intermediate qubit remains. Each iteration shrinks the intermediate set, choosing one of the methods below. The Swap-Method removes one intermediate per iteration; the Stack-Method removes one or two; the Park-the-endpoint variant clears the entire intermediate set in a single iteration. Different iterations may pick different methods. The loop is driven by the routing-intermediate set defined in Step 1, so the loop is allowed to operate on qubits sitting at l or r or anywhere on a routing path from an endpoint to its target neighbor. Iteration count is bounded at trap_graph.num_vertices · 6 + 30 (same bound as Sec. 12.5 step 3); if the bound is reached without emptying the intermediate set, the inner attempt fails and falls through to the outer retries of Sec. 12.5. Swap-Method (analog of the linear-trap merge-swap-separate step): Choose direction: i1 = intermediate qubit closest (graph distance) to qa; ik = intermediate qubit closest to qb. Pick whichever side minimizes the number of timesteps to set up the merge. Prepare: If the chosen mover qubit (qa or qb) shares a vertex, isolate it via the same SWAP-then-SEPARATE recipe as in the linear case (the qubit’s order in the chain dictates whether SWAP is required before SEPARATE; the chosen partner i1 / ik is isolated likewise). Merge and propagate: Move the mover to one neighbor of the chosen gate vertex and the partner to the other neighbor (assignment chosen so that the final chain order after MERGE matches the linear-case recipe). Emit MERGE, SWAP, SEPARATE. The intermediate set shrinks by one. Universal-fallback usage of the Swap-Method: 33 The Swap-Method can always be applied when the Stack-Method and the Park-the-endpoint variant are unavailable or fail. The Step 1 routing-intermediate set covers obstructors on both bfs_path(qa, l) and bfs_path(qb, r); when the Swap-Method is the only feasible reducer, walk those paths from each endpoint toward its target gv-neighbor, one intermediate per merge-swap-separate step. Equivalently, the consecutive intermediates encountered while shrinking the set are exactly the qubits on trap_graph.bfs_path(qpos[qa], qpos[qb]) extended through gv to l/r, consumed one at a time as qa and qb move toward their targets. Each step removes one qubit from the intermediate set, so a finite number of iterations clears the entire BFS path. Free placement of displaced intermediates: once a qubit has been removed from the intermediate set by a Swap-Method step, it is no longer constrained to lie on the qa↔qb BFS path. It may therefore be moved anywhere in the graph during or after the displacement translation. In particular, when the Swap-Method’s SEPARATE deposits the displaced qubit at a gate-vertex neighbor, the qubit can subsequently be routed off the BFS path entirely -- across a junction onto a side branch, into a free stack slot, or onto any empty qubit vertex anywhere in the trap, before the next Swap-Method iteration begins. The only requirements are: - the displaced qubit must end up at a location that is not on the (updated) BFS path between qa and qb at the start of the next iteration, so that it does not re-enter the intermediate set; - the routing of the displaced qubit honors the no-roundtrip rule for every junction it traverses, and respects every other active blocked / protect set (endpoint protection, endpoint-stack protection, etc.). This gives the Swap-Method the flexibility to "park" a displaced intermediate at a junction by translating it onto one of the junction’s stacks or onto any branch that is not on the qa↔qb path. The combination of repeated Swap-Method iterations plus free off-path placement of each displaced intermediate guarantees that the Swap-Method alone can always clear the intermediate set, regardless of the topology -- making it the unconditional fallback strategy when Stack-Method, Park-the-endpoint, and stack-slot eviction do not apply. Stack-Method: Iterate j over the junctions on the routing-intermediate paths -- i.e. trap_graph.junctions_on_path(qpos[qa], l) ∪ trap_graph.junctions_on_path(qpos[qb], r). For each such j, inspect trap_graph.stacks_at(j); if any of those stacks has at least one free slot (its deepest occupied slot is shallower than the stack length), an intermediate qubit q_inter near j can be pushed onto that stack instead of being shuffled past via merge-swap-separate. Pre-condition: q_inter’s current vertex contains only intermediate qubits -- i.e., neither qa nor qb shares that vertex. If q_inter is alone, only it is pushed. If q_inter shares its vertex with another intermediate qubit, both qubits in that chain are pushed together as a single chain (TRANSLATE moves whole chains), removing two intermediates at once. If q_inter shares a vertex with qa or qb, the Stack-Method does not apply directly -- isolate q_inter first via SEPARATE, or fall back to the Swap-Method this iteration. Action: route q_inter (or its 2-qubit chain) to the junction j with move(), then push it onto the stack via a single TRANSLATE of j → slot 0. By the LIFO mechanics in Sec. 1, any qubits already in the stack shift one slot deeper in the same timestep automatically; no extra cost. After the push, q_inter no longer lies on either of the routing-intermediate paths bfs_path(qa, l) or bfs_path(qb, r), so the intermediate set shrinks by one or two. Refinements: - LIFO ordering preference: q_inter will sit at slot 0 after the push and must therefore be popped before every qubit currently deeper in the stack. The ideal case is therefore that next_gate_id(q_inter) is ≤ the next_gate_id of every existing occupant; when this holds, no evacuation is forced later. In practice this preference is often unattainable -- the trap rarely has enough free non-junction qubit to keep order strictly. The rule is therefore a tie-breaker, not a hard precondition: prefer stacks that satisfy the LIFO order; otherwise still push, and account for the eventual cost of having to pop and re-park occupants when their gates come due. Pushing onto an order-violating stack is acceptable as long as the cost estimator (see "Method choice each iteration" below) accounts for the future evacuation overhead and the chosen method still beats the alternatives. - Look-ahead skip: do not push q_inter when its next gate is scheduled to fire within fewer timesteps than one push + one pop (≈ 2 translation timesteps plus the junction-traversal hops to and from the stack). The retrieval would land before any saving materializes and would block the main-axis path during a later gate’s routing. - Multi-stack parallelism: if several intermediates lie near distinct junctions, push them onto different stacks. Translations into disjoint stacks involve pairwise disjoint vertex pairs and therefore share a single translation timestep (Sec. 6.3). - Pre-stacking before scheduling reaches the gate: when the scheduler is idle on some main-axis stretch (no ready gate currently uses those qubits), opportunistically push qubits whose next gate is far in the future onto nearby stacks. This is equivalent to advancing future Stack-Method steps and frees the main axis for in-between gates. - Co-routing with SEPARATE: when an intermediate pair must first be isolated via SEPARATE on a gate vertex, route one of the resulting qubits toward the stack entry while the other is moved toward the opposite side of the gate vertex; this overlaps the stacking move with the routing of the partner qubit. Park-the-endpoint variant: Instead of pushing an intermediate aside, an entire path can be cleared by pushing qa or qb itself onto a "park slot" -- either (a) a stack s connected to a junction j, or (b) a far non-junction main-axis vertex that is not on the routing-intermediate paths. Once qa (or qb) is at the park slot, the intermediate qubits can be translated freely past the previously blocking endpoint; afterward qa is popped from s (or walked back from the main-axis park) and moved to its target gv-neighbor (l for qa, r for qb). For stack parking the LIFO mechanics guarantee constant-time push/pop; for main-axis parking the cost is simply distance(qpos[endpoint], park_vertex). During this routing episode no intermediate qubit may be pushed onto a stack that holds a parked endpoint (that would land the intermediate above qa and force qa to be popped before it -- LIFO order). Refinements: - Park slots include both stack slots and far main-axis non-junction vertices. For "very linear" traps -- a long main axis with one or two long stacks branching off, plus main-axis ends that extend past the junctions (graph_33_10_1 is the canonical example: V0-V4 to the left of junction V5 and V10-V14 to the right of junction V9 are "linear arms" five hops deep, equivalent in capacity to the 10-deep stacks at V15+ and V25+) -- every non-junction vertex on the main axis at distance ≥ 3 from gv is also a valid park slot. The implementation must enumerate both stack-slot candidates and far-main-axis candidates when scheduling Park-the-endpoint. When all stack slot 0s are already occupied with non-keep chains (Stack slot eviction would be required otherwise), main-axis-end parking is often the cheaper recovery. - Endpoint parking is flexible. qa and qb can be parked independently in any combination, and the choice of which stacks (or which main-axis vertices) are used is irrelevant for correctness -- only for cost. The compiler may: · Park only qa (or only qb), in any stack with a free slot or at any far main-axis non-junction vertex. · Park qa and qb in the same stack: push qa first, then push qb on top (the roles of qa and qb are exchangeable). After the second push, qb sits at slot 0 and qa at slot 1. Since both will be popped and routed to gv-neighbors afterward, the LIFO order is fine -- pop qb, route it to one neighbor of gv, pop qa, route it to the other neighbor, MERGE, GATE. While both endpoints share the stack, no intermediate may be pushed onto it (that would separate qa from qb in LIFO order). 34 Retrieval costs two consecutive pop timesteps instead of one. · Park qa and qb in different stacks, attached to the same junction or to different junctions -- the routing is identical in either case. Pushing qa and qb onto stacks at different junctions can also be done in parallel within a single translation timestep when the two routes are disjoint, which is often cheaper than serial pushes onto one junction’s stacks. · Park qa at a main-axis end, qb in a stack (or vice versa), or park both at opposite main-axis ends -- whichever combination clears the most of the routing-intermediate paths at lowest cost. In all variants, once the endpoints are parked the intermediates can be translated freely along the cleared stretch of the main axis, often collapsing several Swap-Method iterations into a single translation timestep batch. - Endpoint choice by post-gate consumer: when only one of qa, qb is parked, prefer to park whichever has the more distant next gate (the parked qubit must be popped again; if its next gate is far, the extra hop is usually amortized by other movement). - Linger across multiple gates: if the parked endpoint’s next gate is also reachable via the same junction, the qubit may remain in the stack across several gates rather than being popped immediately. Track per-qubit "extraction deadline" against next_gate_id and only pop when the deadline forces it. - Combine with Stack-Method: park one endpoint in a stack at one junction and push one or more intermediates onto another stack (different junction) in parallel; the two stacking translations can share the same translation timestep. Method choice each iteration: estimate cost using actual graph distances and the constant-time stack push/pop mechanic: - Swap-Method ≈ 4 + max(0, distance(qa, gv) + distance(i1, gv) - 2) (MERGE + SWAP + SEPARATE plus loading the two neighbors of gv). - Stack-Method ≈ distance(qpos[q_inter], j) + 1 per push (the +1 is the j → slot 0 translation; existing stack contents shift in the same timestep at no extra cost). A second intermediate co-pushed as part of the same chain costs nothing extra. Eventual extraction adds 1 + distance(j, target) per popped chain. - Park-the-endpoint (stack park) ≈ distance(qpos[qa or qb], j) + 1 for the push, plus 1 + distance(j, gv-neighbor) for the eventual pop and delivery to the gate vertex. - Park-the-endpoint (main-axis-end park) ≈ 2·distance(qpos[qa or qb], park_vertex), i.e. one walk to the park vertex plus one walk back to the gv-neighbor when MERGE is due. Main-axis parking has no LIFO constraint and never blocks future stack pushes; prefer it over stack parking when the cost is equal or smaller, and always when the candidate stack already holds chains whose next gates are sooner than the parked endpoint’s next gate. Pick the cheapest method. Different iterations may pick different methods; gate-vertex choice may also vary between iterations. Tie-break order when two methods yield equal estimated cost: (1) Stack-Method, (2) Park-the-endpoint, (3) Swap-Method (Stack first because it has no SEPARATE/SWAP/MERGE overhead). When two candidate vertices within the same method tie, break by the vertex that the method’s cost formula refers to -- the intermediate vertex’s index for Stack-Method and Swap-Method, the junction’s index for Park-the-endpoint -- ascending. Other strategies are possible (e.g., mixing swap and stack steps within one reduction; opportunistically using any free junction-adjacent slot for a cheap detour; allowing intermediates to overshoot through the junction onto the far side of the main axis when both endpoints have already cleared it). Two-qubit routing is therefore an open-ended optimization target; the Swap-Method, Stack-Method, and park-the-endpoint variant above are the required baselines. Swap-Method same-side handling: when both the chosen mover and its intermediate partner currently sit on the same side of gv (so the mover’s path to its target gv-neighbor passes through the other gv-neighbor, which holds the partner), the naive sequence "move target_l to l with blocked = gv, r", then "move target_r to r with blocked = gv, l" deadlocks: the first move’s strict-blocked invocation refuses to displace the partner sitting at r. The Swap-Method must handle this by temporarily relocating the blocking partner to a safe holding vertex (an empty non-stack, non-junction main-axis vertex not on the mover’s path), completing the mover’s move, then restoring the blocking partner to its destination. With this two-step relocation, the Swap-Method always succeeds for a single intermediate regardless of same-side / different-side configuration -- making it the unconditional backup whenever Stack-Method, Park-the-endpoint, or stack-slot eviction do not apply (see Universal-fallback usage of the Swap-Method above for the off-path displacement rule). Stack-Method atomicity: each Stack-Method candidate push is a multi-step procedure (route the intermediate to the junction, then translate to slot 0). The traversal itself may displace blockers via cascading evacuations. If the final push step then fails (slot 0 became occupied during the traversal, or no-roundtrip blocks the push, or move couldn’t reach the junction), the partial state changes from that candidate must be rolled back via snapshot/restore before the next candidate is tried. A partial push that left an endpoint or a non-keep qubit displaced and then declared "failure" without rollback leaves the trap in a worse configuration than it started: e.g. an endpoint shoved into a stack while the original target slot 0 becomes blocked, parking the endpoint where it cannot subsequently be routed. Snapshot before each candidate; restore on any failure. Preferred displacement target for routing-intermediates: when an iteration relocates a qubit out of the routing-intermediate set (Step 1), the preferred destination is a free stack slot (slot 0 of a stack whose slot 0 and junction are both empty), not a one-hop vacate to an adjacent main-axis vertex. A single-hop shift often leaves the chain on an adjacent junction or on another vertex still on the qa→l or qb→r path, immediately reintroducing it as an intermediate. A stack push terminates the displacement in one translation timestep regardless of how many other stacks are populated. Use Stack-Method first; if no free stack is reachable, fall back to Swap-Method or generic evacuate. Endpoint-stack protection (cascade-push avoidance): if an endpoint qa or qb currently sits in a stack column (slot k of some stack S, k ≥ 0), the routing must never push another qubit onto slot 0 of S while that endpoint is still parked there. Doing so triggers the LIFO cascade and shoves the endpoint one slot deeper (slot k → slot k+1), after which retrieving the endpoint requires first popping the new arrival back out. Therefore: at every point during the routing of the gate (qa, qb) -- Step 2 iterations and Step 3 finalization alike -- every slot of S other than the endpoint’s own slot must be added to the blocked set of every evacuate / move / Stack-Method / Park-the-Endpoint call. Free-stack searches must skip S entirely. The endpoint’s own slot remains unblocked so the endpoint can pop out itself. Endpoint chain protection (implementation note): evacuate naturally moves the chain at its target vertex one hop forward as part of its reverse-shift. If the chain at that vertex contains qa or qb, this displaces an endpoint, which can cascade the endpoint into an arbitrary far vertex. To keep this controlled, evacuate should by default refuse when the chain at its target contains a keep qubit, returning False so the caller can pick a different strategy. The relaxed Endpoint-protection rule (Sec. 6.2 movement primitives) lists which displacements are nonetheless permitted -- always paired with snapshot/restore so the trap state is recoverable on failure. Endpoint-on-junction at MERGE/SEPARATE/SWAP/GATE: see Sec. 12.7’s hard invariant -- between non-translation ops every junction must be empty, and primitives are responsible for draining any transiting chain off a junction before returning. Stack-slot eviction (cascading stack rearrangement): on densely-packed traps (graph_33_*, graph_15_5_1, graph_11_2_1, graph_11_3_1) 35 every slot 0 of every stack may be occupied at the time Stack-Method tries to park an intermediate. Strict Stack-Method ("only push when slot 0 is empty") then has no candidate and returns False, leaving the intermediate to block the merge path. In that case the routing must attempt **stack-slot eviction**: pick a stack whose slot 0 occupant is not a keep qubit and whose next gate is far in the future, pop that occupant onto a free non-stack vertex (or another free stack), then push the intermediate onto the freed slot 0. The pop must respect the no-roundtrip rule for the junction; the destination of the evicted qubit must not lie on either routing-intermediate path (bfs_path(qa, l) or bfs_path(qb, r)) nor be a gv-neighbor. Without stack-slot eviction, fully-loaded traps remain unsolvable. This is the extension of the Stack-Method baseline that Sec. 6.2’s "Stack reordering" prose alludes to: "pop the relevant prefix of the stack out through the junction onto temporary holding vertices ... and re-push". Implement that explicitly, not just as a future tweak. Stack-reordering for trapped endpoints (Sec. 1 mechanics applied to endpoints): if at the start of routing an endpoint qa or qb sits at slot k > 0 of some stack column -- i.e. one or more other qubits occupy slots 0...k-1 above it -- the endpoint cannot be popped directly. The routing must first extract the trapping qubits, then walk the endpoint out to the main axis. The extraction routine has three phases and must run before iterative reduction begins (the Swap-Method cannot pull an endpoint up through a stack): Phase 1 -- pre-clear the junction-adjacent main-axis vertices, and reserve at least one of them as a Phase-3 landing pad. Each popped occupant has to land somewhere; the natural landing pad is a main-axis neighbor of the junction. For each main-axis neighbor nb of the junction j that is currently non-empty, evacuate nb with blocked equal to the entire stack we are about to drain. Blocking the whole stack is essential: it prevents the displaced main-axis chain from being pushed back into the very stack we want to empty. Reserve-one-landing rule: pick one main-axis neighbor of j (the first one already empty, or -- if all are non-empty -- the first one that successfully evacuates) and treat it as the dedicated Phase 3 landing vertex. During Phase 2, that vertex must be added to the per-slot blocked set so that displaced shallower-slot chains do not re-occupy it. Without this rule, the natural displacement order in Phase 2 fills both main-axis neighbors of j with the displaced shallower-slot occupants, and Phase 3 then has nowhere to land (both gv-junction-neighbors blocked, both forbidden by no-roundtrip for some routings, etc.). The reserved landing vertex must remain empty until Phase 3 emits TRANSLATE(j → landing). Phase 2 -- pop each shallower slot top-down. For each occupied slot k in 0...slot-1, evacuate the slot vertex to anywhere outside the stack, using blocked equal to all other slots of the same stack ∪ the reserved Phase-3 landing vertex from Phase 1. If that fails, retry with the relaxed blocked set containing only the endpoint’s own slot vertex. The cascade-shift translations described in Sec. 1 (every occupied k+1 shifts to k within the same timestep) are emitted as discrete TRANSLATE operations one per slot; the chain-of-translations grouping rule of Sec. 6.3 will pack them into a single timestep when the grouping pass runs. Phase 3 -- walk the endpoint out. The caller passes a "target vertex" hint t to this phase (the gate vertex about to be used for the single-qubit gate, or the best gate vertex by combined-distance order for a two-qubit pre-extract -- see Sec. 12.5 step 1). Starting from the endpoint’s current slot, while the endpoint is not yet on the main axis: if it is in the stack at slot > 0, translate it one slot shallower (the previous slot is empty because Phase 2 emptied it); if it is at slot 0, translate it onto the junction; if it is on the junction, translate it onto an empty main-axis neighbor (evacuating that neighbor first if still occupied, which Phase 1 should already have ensured). The choice of main-axis neighbor is governed by the Non-junction landing rule and the forced-junction tie-breaker below -- both consult t. Non-junction landing rule: when picking which main-axis neighbor of the stack’s junction j to land the chain on after the j → main-axis translation, prefer a neighbor that is NOT itself a junction. If a chain lands on a junction-on-the-main-axis (j2), then j2 records its entry from j, and the next translation involving j2 cannot exit back to j (no-roundtrip). Almost any subsequent walk toward a gate vertex starts by attempting precisely that "back through j" translation, so landing on a junction routinely creates an unrecoverable no-roundtrip stall. Only fall back to a junction main-axis neighbor when no non-junction neighbor is available. Tie-breaker for the forced-junction fallback: when both of j’s main-axis neighbors are themselves junctions (j sits in a run of back-to-back junctions on the trunk), the extraction caller must pass a "target vertex" hint t. For a single-qubit gate this is the gate vertex about to be used; for a two-qubit gate’s pre-extract this is the gate vertex of the gate (not the partner endpoint), because the chain must ultimately reach a gv-neighbor regardless of where the partner sits -- landing toward the partner instead biases the chain away from gv and creates a no-roundtrip stall the moment the routing tries to walk to gv. With the hint t, filter the candidates as follows. For each candidate landing neighbor n of j, compute trap_graph.bfs_path(n, t): if that path passes through j itself, n is "unsafe" -- landing there forces the very next translation to attempt T(n, j), which is forbidden by no-roundtrip at n (n just received the chain from j). Prefer "safe" candidates (path to t does not revisit j) over unsafe ones, then break ties within each class by trap_graph.distance(n, t), then by vertex index. Only when every candidate is unsafe does the fallback land on an unsafe neighbor; in that case the subsequent routing is likely to fail and must unwind to an outer fallback level. This hint and filter matter only in the all-junctions-fallback branch -- when at least one non-junction main-axis neighbor exists, the primary rule already gives a no-roundtrip-safe landing. The two non-obvious points are: (a) the Phase 1 pre-clear pass blocks the entire stack so the evacuee never returns to it via a different slot, and (b) Phase 1 runs before Phase 2 so each pop has a reachable empty destination near the junction. Without both, routing fails on traps with depth-5+ stacks fully packed at one end. Slot-0 special case: when the endpoint is at slot 0 of a stack (no shallower-slot occupants), Phase 2 is a no-op; Phase 1 and Phase 3 still apply (pre-clear the junction-adjacent main-axis neighbor, then walk slot 0 → junction → main axis). Step 3 -- finalization: After Step 2’s iterative reduction, the routing-intermediate set is empty. By construction this means qpos[qa] = l and qpos[qb] = r (or vice versa) -- both endpoints sit at the chosen gv-neighbors. The only remaining obstruction can be the gate vertex gv itself, if it still holds a non-endpoint chain. Finalization runs as follows: (a) If gv is empty: clear_junctions(blocked = gv, l, r), emit MERGE(gv), emit GATE(gv, gate). Done. (b) If gv holds a chain (necessarily non-endpoint, since qa and qb are at l and r), the chain at gv is a 1- or 2-qubit obstacle sandwiched directly between qa at l and qb at r. Apply one Swap-Method step with qa and qb as the two endpoints and the gv-occupants as the (single) intermediate: MERGE qa with the gv-chain at l (or r, whichever side the SWAP-then-SEPARATE recipe dictates), SWAP, SEPARATE -- the gv-occupant now lands on one of gv’s neighbors opposite to where it came from, and qa moves through. Because gv’s two neighbors are both non-junction and lie on the main axis, this Swap-Method step is always 36 feasible. After the gv-occupant is displaced, evacuate it off l/r via Stack-Method (push onto a free stack at a nearby junction) or via Swap-Method’s free-placement rule (move it anywhere off the qa↔qb path). Re-deliver qa to l and qb to r, then run case (a). Explicit case (b) protocol -- try every (anchor, anchor_target, other, other_target) combination in turn, wrapping each attempt in snapshot/restore. The four combinations are: (qa at l, qb to r), (qa at r, qb to l), (qb at l, qa to r), (qb at r, qa to l). For each combination, perform the following steps in order; on any failure restore the per-attempt snapshot and continue with the next combination. Step 1. Move the anchor qubit to its anchor_target (the gv-neighbor we want it on going into the M-W-S), with blocked = other_target. Step 2. If other_target is currently non-empty, evacuate it somewhere off the (anchor_target, gv, other_target) triangle -- use blocked = anchor_target, gv. Step 3. Translate the chain currently at gv into other_target. Special case: if gv is already empty by this point (which means the gv-chain was the anchor itself, an endpoint that we just moved out in step 1), skip the M-W-S entirely; instead, deliver other to anchor_target (rotation-through-gv may apply, see step 6), clear junctions, emit MERGE and GATE, return success. Step 4. Clear junctions with blocked = l, r, gv, verify that l and r each hold exactly one qubit, then emit MERGE at gv. The chain at gv after MERGE is in (l-side, r-side) order; emit SWAP at gv to reverse it; emit SEPARATE at gv. After SEPARATE, the anchor qubit sits at other_target and the displaced gv-chain sits at anchor_target. Step 5. Evacuate the displaced gv-chain off anchor_target, with blocked = other_target, gv. Step 6. Deliver the other qubit to anchor_target. Compute its tree-path to anchor_target via bfs_path. If that path passes through other_target (which now holds the anchor), use the rotation-through-gv subroutine: translate from other_target to gv, then from gv to anchor_target -- this walks the anchor across gv to anchor_target and frees other_target -- then move the other qubit into the freed other_target with blocked = anchor_target, gv. Otherwise just move the other qubit to anchor_target with blocked = other_target, gv. Step 7. Clear junctions and emit MERGE, then GATE. Why all four anchor combinations: depending on which endpoint occupies which gv-neighbor at entry and which way the gv-chain should be displaced for the cleanest subsequent evac, exactly one of the four attempts is usually feasible. Trying them in turn is required to handle dense traps. Why the rotation-through-gv in step 6: when other is on the opposite side of gv from anchor_target, the tree-unique path passes through other_target (where anchor sits). On a tree there is no alternate route, so the only way to deliver other to anchor_target without ejecting anchor permanently is to swap their positions via gv’s two-step T relay. Endpoint relocation during finalization: by default, once qa is at l and qb is at r, no further relocation should be needed except the controlled Swap-Method of case (b) (which itself uses qa or qb as a swap-partner -- a controlled displacement allowed by the relaxed Endpoint protection rule). If for any other reason an already-placed endpoint must move (e.g. an intermediate that cannot be cleared without routing through l or r), the routing must either: - plan the displacement and its reversal as a snapshot/restore transaction (see Endpoint chain protection), or - restart finalization with a different gate vertex, in which case both endpoints are unprotected again. An endpoint must never be left at a vertex other than l or r when MERGE is emitted (see the "Endpoint-on-junction is forbidden at MERGE" rule above for the junction-empty part). Stack choice priority: Slot depth is fully determined by insertion order (Sec. 1), so the compiler chooses only which stack a qubit is pushed onto, not where in the stack it lands. Enumerate candidate stacks via trap_graph.stacks_at(j) for each junction of interest; rank as follows, with ties broken by junction vertex index, then by stack_index returned by stacks_at: 1. Free space. The stack must have at least one free slot (i.e., its deepest occupied slot is shallower than the bottom; equivalently, the number of currently occupied slots is strictly less than len(trap_graph.stacks_at(j)[stack_index])). This is the only hard requirement. 2. LIFO compatibility (preference, not requirement). The new arrival becomes the next qubit to be popped. Prefer stacks where the new arrival’s next_gate_id is ≤ the next_gate_id of every qubit already in that stack, so existing occupants are not blocked when their gates come due. When no such stack exists, pushing onto an order-violating stack is still allowed; the cost estimator must account for the eventual pop-and-re-park overhead. This relaxation is necessary because the trap rarely has enough free non-junction vertices to enforce strict LIFO order. 3. Distance to next consumer. Among eligible stacks, prefer the one whose junction minimizes trap_graph.distance from the new arrival’s likely future location (gate vertex of its next gate). 4. Distance to current location. As a secondary tie-breaker, prefer the stack whose junction is closest to the qubit’s current vertex, to minimize the cost of the push itself. Stack reordering is possible but only by full-or-partial evacuation, never in place: qubits inside a stack cannot pass each other. To change the order, pop the relevant prefix of the stack out through the junction onto temporary holding vertices (main axis or another stack), realize the desired ordering, and re-push. The pop and re-push must each respect the junction no-roundtrip rule. Reordering only pays off when its translation cost is less than the extraction cost it saves; estimate before emitting. The chosen ordering must remain consistent with the deterministic-ordering requirement of Sec. 10. This pop-and-re-push mechanic is the same machinery used by the Stack-slot eviction rule and by Stack-reordering for trapped endpoints (both above) -- three different applications of the same primitive. Notes for both single- and two-qubit cases: - When several gate vertices are available, rank candidates by trap_graph.distance to the qubit’s current location, not by index difference, and honor any "avoid" set imposed by the routing context. Chain-order optimization after two-qubit gate execution: After routing, the two target qubits are co-located at the gate vertex. Since QuantumGate.qubits order does not affect gate 37 correctness, but qubit order within the chain affects routing of subsequent gates, use a one-step lookahead over the next gate of each qubit and insert a post-execution SWAP only when doing so brings more qubits to their preferred side. Use trap_graph.distance to determine the preferred side. When in doubt, do not insert the SWAP -- an unnecessary SWAP can cascade into extra separations downstream. 6.3 TIMESTEP GROUPING AND POST-PROCESSING A timestep is a set of operations executed simultaneously. After the routing emits the raw operation stream, apply the following passes in order: 1. Roundtrip elimination -- remove a TRANSLATE A→B immediately followed by TRANSLATE B→A when no intervening operation references A or B (as src, dst, or operand vertex). Removing the pair must leave A’s and B’s contents identical to the no-removal trace at every intermediate step. General junction soundness rule: let the candidate removal be a set R of (possibly nested) (X_i→Y_i, Y_i→X_i) pairs. R is legal iff replaying the trace with all pairs in R deleted yields, for every junction j, a sequence of entries and exits at j in which no exit reuses the immediately preceding entry edge. The pair (X→Y, Y→X) by itself is never the junction violation (it is a normal back-and-forth on Y); a violation can only appear in what the removal exposes around it. The rewriter therefore replays the trace after each candidate removal, tracks each junction’s current entry vertex per chain, and accepts only when the residual is legal. When a singleton R fails the check, try a combined R that also drops the smallest enclosing roundtrip -- a combined removal can be legal even when no proper subset is. The basic non-junction case is recovered by |R| = 1. Six illustrative consequences of the general rule (B is a junction in all): Example 1 -- fully nested roundtrip, smallest legal R is the pair: TRANSLATE(A→B) TRANSLATE(B→C) TRANSLATE(C→B) TRANSLATE(B→A) Removing only the inner pair (B→C, C→B) leaves A→B, B→A, which is a junction roundtrip violation at B (entered from A, exits back to A). Removing only the outer pair (A→B, B→A) leaves B→C, C→B with no source for the chain at B and is therefore unsound for chain contents as well. Removing both pairs together leaves an empty residual, which is trivially legal. Apply this combined removal recursively: arbitrary nested roundtrips around a junction collapse simultaneously when every layer pairs up. Example 2 -- outer translation continues to a different exit: TRANSLATE(A→B) TRANSLATE(B→C) TRANSLATE(C→B) TRANSLATE(B→D) with (D ̸= A) Removing only the inner pair (B→C, C→B) leaves A→B, B→D. The chain enters B from A and exits to D ̸= A -- legal. The outer translations stay. Recursively, sequences of multiple inner detours through B can be peeled off one at a time as long as each successive exit from B remains different from the chain’s most recent entry into B. Example 3 -- multiple stacked detours, all-or-none: TRANSLATE(A→B) TRANSLATE(B→C) TRANSLATE(C→B) TRANSLATE(B→D) TRANSLATE(D→B) TRANSLATE(B→A) with (D ̸= A, D ̸= C) The chain enters B from A, makes two detours (to C and to D), and leaves back to A. Each individual exit in the original trace alternates entry edges (legal). Removing only one inner pair, e.g. (B→C, C→B), yields A→B, B→D, D→B, B→A -- still legal, since each exit from B continues to alternate. But removing both inner pairs alone yields A→B, B→A -- a junction violation. The minimal R that collapses everything is therefore the pair (A→B, B→A) together with every inner detour pair simultaneously; or, equivalently, peel off the inner pairs one at a time first and stop before exposing the A→B, B→A roundtrip. The general rule subsumes both choices. Example 4 -- recursive Pattern 2: TRANSLATE(A→B) TRANSLATE(B→C) TRANSLATE(C→B) TRANSLATE(B→D) TRANSLATE(D→B) TRANSLATE(B→E) with (E ̸= A, D ̸= C, E ̸= D) Apply Example-2 reasoning to (B→C, C→B): residual A→B, B→D, D→B, B→E is legal (D ̸= A, E ̸= D). Apply Example-2 again to (B→D, D→B): residual A→B, B→E with E ̸= A -- legal. Inner pairs peel off one at a time as long as each successive exit avoids the chain’s current entry edge. Example 5 -- non-adjacent inner pair through unrelated ops: TRANSLATE(A→B) TRANSLATE(B→C) [ops on vertices disjoint from A, B, C] TRANSLATE(C→B) TRANSLATE(B→D) with (D ̸= A) The inner pair (B→C, C→B) is not adjacent in the trace, but the baseline "no intervening operation references A or B" condition for the basic rule still applies (here: also no intervening reference to C, since C is the intermediate vertex of the inner pair). Removing the inner pair leaves A→B, [ops], B→D -- the junction entry record at B remains "from A" across the unrelated ops, and B→D with D ̸= A is legal. Example 6 -- nested non-junction roundtrip inside a junction detour: TRANSLATE(A→B) TRANSLATE(B→C) 38 TRANSLATE(C→D) TRANSLATE(D→C) TRANSLATE(C→B) TRANSLATE(B→A) The basic (non-junction) rule first eliminates (C→D, D→C) -- that pair is sound on its own because C is being used as an ordinary vertex there. After that elimination the trace becomes Example 1 (A→B, B→C, C→B, B→A), which then collapses entirely under the combined-removal rule. Passes 1 and 2 alternated to fixpoint must find both reductions. 2. Consecutive cancellation -- remove: - a SEPARATE immediately followed by a MERGE on the same vertex, - a MERGE immediately followed by a SEPARATE on the same vertex, - a SWAP immediately followed by another SWAP on the same vertex, in each case only when the qubits involved do not appear in any intervening operation. Apply passes 1 and 2 alternately to fixpoint, always working on the current post-removal stream. When no further reductions are possible, proceed to pass 3. 3. Grouping -- pack independent operations into the same timestep: Translation timesteps: may contain only TRANSLATE operations. All translations on pairwise disjoint source/destination vertex pairs may be freely grouped. A "chain of translations" along consecutive vertices is also permitted: if TRANSLATE B→C and TRANSLATE A→B are both needed, they may share a timestep, provided each chained vertex except the rightmost actually holds a qubit at the start of the timestep (B→C vacates B in the same timestep that A→B fills it). Chain rule generalizes to arbitrarily long consecutive sequences where each qubit appears in at most one TRANSLATE. Junction-aware addition: when simulating a candidate translation batch, track per-junction entry vertices in a local dictionary. A translation TRANSLATE(j, b) where j is a junction whose current local entry is b must be rejected (would re-traverse the entry edge), and the batch boundary is closed. Update the local dictionary on every accepted translation: set entry on TRANSLATE(*, j), clear it on TRANSLATE(j, *). The same check applies between consecutive batches: a batch must start with the per-junction entry record from the previous batch. Non-translation timesteps: may contain only non-TRANSLATE operations (SEPARATE, MERGE, SWAP, GATE). Two such operations may share a timestep only if (i) the vertex sets they involve are pairwise disjoint, and (i) all junctions are empty at the start of the timestep. The vertex set of an operation is: - SWAP(v): v - GATE(v, ...): v - SEPARATE(v): v ∪ trap_graph.neighbors(v) - MERGE(v): v ∪ trap_graph.neighbors(v) (Sec. 1 guarantees every gate vertex has exactly two main-axis, non-junction neighbors.) In particular, a SEPARATE at v1 and a MERGE at v2 cannot share a timestep when their vertex sets (v_i ∪ neighbors(v_i)) intersect, even if v1 ̸= v2. If any junction holds ions when a non-translation timestep is being opened, an extra translation timestep must be inserted first to flush the junction. Strict program order -- implementation requirement: the grouper must process the post-processed op stream strictly sequentially. Each op either joins the current open batch or starts a new one; the grouper must never reorder a translation past a non-translation op or vice versa, even when their vertex sets are disjoint. The reason is that the validator (Sec. 7) executes ops in program order across timesteps and tracks per-timestep state; reordering a T into a batch that precedes a non-T it actually followed creates state mismatches that the validator catches. Translation-batch admission rule: an op T(s, t) joins the current T-batch iff (a) s is occupied at the *start* of the batch (initial occupancy snapshot, not the running occupancy after earlier ops in the batch), and (b) t is either initially empty OR is the source of some other op already accepted into the batch (the chain rule), and (c) s has not already been accepted as a source by another op in the batch, and (d) t has not already been accepted as a destination by another op in the batch, and (e) if s is a junction, the local junction-entry record does not record entry from t (no-roundtrip), and (f) following the chain_next map (source → dest of accepted ops) from t does not lead back to s -- this rejects 2-cycles like T(2,3), T(3,2) which the validator cannot resolve. Iterate the admission check to fixpoint: an op that initially fails rule (b) because its dest is initially occupied may later succeed once another op vacates that dest. Re-scan accepted ops in the batch after each new admission until no more accepts occur. The batch is bounded by the first non-T op in the stream -- extending across a non-T is forbidden (program-order rule above). This iterate-to-fixpoint behavior is what enables parallel-slide packing -- when the routing emits ops one-hop-per-walk in order (Stack-Method evac of q_inter first, then qa’s walk, then qb’s walk), the grouper interleaves them into the same translation timestep so long as each op’s source vertex was occupied at batch-start and each op’s destination was either initially empty or is vacated by another admitted op in the same batch. The Sec. 9 working example’s 12-timestep schedule relies on this property: TS3 packs the disjoint first-hops of q[0], q[1], q[2] into one timestep, and TS4 packs the disjoint second-hops into the next, even when the routing emitted the ops sequentially by qubit. Topological reordering helper. The strict-program-order grouper only admits ops in their emission order; if a routing primitive emits two chains’ hops back-to-back (chain X’s hops 1, 2, 3, then chain Y’s hops 1, 2, 3), the grouper packs only the prefix that satisfies the initial-occupancy rule and starts a new batch at the first failure. This is correct but produces longer schedules than necessary on the Sec. 9 example. To recover the tight bound, a recommended pre-grouping pass walks each consecutive-T stretch (between two consecutive non-T ops) and topologically reorders its T ops by dependency depth: a T depends on every prior T in the stretch that shares any source or destination, and the depth of a T is one more than the maximum depth of its dependencies. Within each depth class the original emission order is preserved (this maintains determinism). The reordered stream has each chain’s hop-k preceding any chain’s hop-(k+1), which is exactly the order that allows the grouper’s chain rule to merge them into a single timestep. This pass preserves sequential validity (it only swaps T ops within a stretch that are mutually independent) and must run before the grouper, after post-process roundtrip elimination. Updating the running occupancy after a T-batch closes: do not apply the per-op effect "source becomes empty, destination becomes 39 occupied" in batch-order, because in a chain the same vertex may be both a source for one op and a destination for another, and naive per-op updates corrupt that vertex depending on the iteration order. Use set semantics instead: first mark every vertex in the union of accepted sources as empty, then mark every vertex in the union of accepted destinations as occupied. A vertex that is both a source and a destination correctly ends up occupied (the chain shifted through it). SECTION 7 - VALIDATION AND OUTPUT At the end of the program, call the following function to validate the results and emit all output. Its implementation is already provided in ion_trap_compiler.py. def validate_and_output(trap_graph: TrapGraph, qubits: List[str], gates: List[QuantumGate], initial_state: Dict[int, List[str]], all_timesteps: List[List[Tuple]], time_begin: float, output_json: Optional[str] = None, stats_file: Optional[str] = None) # All parameters are the unchanged return values of parse_input (Sec. 4), initial_mapping (Sec. 5), and compile (Sec. 6). SECTION 8 - PERFORMANCE REQUIREMENTS The compiler must minimize runtime and peak RAM usage. Complexity should scale roughly linearly in the number of vertices, qubits, and gates. The acceptance tests in Sec. 11 span a wide size range: up to 40 qubits and 93 vertices (T9 invocation 2 -- qaoa_40 on graph_81_6_1), and up to roughly 34 600 gates (T11 invocations 4-5 -- hwb7_59, an 8-qubit circuit). No single invocation maxes out every dimension at once. The compiler should compile each as fast as is reasonable. Prefer greedy/heuristic approaches over exact optimization. TrapGraph already precomputes all-pairs distances and BFS parent tables in its constructor and caches reconstructed paths internally, so trap_graph.distance is O(1) and trap_graph.bfs_path / next_hop are essentially free after the first call -- the compiler does not need to add its own caching layer for these. Hot-path optimizations that are required for dense circuits (cnt3-5_179 and the larger qaoa benchmarks) to run in seconds rather than minutes: - evacuate’s internal BFS for empty landing targets (the routine Sec. 12.2 describes; conventionally named find_empty_target in the implementation) must cap the number of candidate landing paths it returns to a small constant (3 is a good default). The fallback-strategy chain in Sec. 12.5 already tries multiple strategies at higher levels with snapshot/restore, so each call only needs the nearest few candidates; returning 8+ multiplies walk_path work without improving the schedule. - Snapshot/restore must not deep-copy chain lists. Treat chain lists as immutable references -- any code that "mutates" a chain (e.g. SWAP, MERGE, SEPARATE, post-gate SWAP optimization) reassigns state[v] to a new list rather than mutating in place. With that invariant, snapshot reduces to dict.copy() on the three state dicts (O(N)) plus recording len(ops); restore reassigns those three dicts and truncates the op list. Naïve per-key list copies cost a measurable percentage of total runtime on dense traps because snapshot is called millions of times. - is_empty(v), is_junction(v), and neighbors(v) are called tens of millions of times. Inline the dict lookups in the hot loop bodies (state.get(v), membership in a cached _junctions_set, direct _adj[v] indexing) instead of going through method-call indirection. The semantic remains identical but avoids Python’s per-call frame overhead. - When delivering endpoints, prefer trying the cheapest strategies first (simple sequential walk, then rotation-through-gv, then aggressive park) and bail out of expensive multi-snapshot strategies as soon as a cheaper one would have made progress. Each strategy already wraps in snapshot/restore, so early termination is safe. SECTION 9 - WORKING EXAMPLE (VERIFICATION) The following example must produce a valid (not necessarily identical) shuttling sequence of at most 20 individual operations, completable in 12 timesteps or fewer. The bound is reachable from a Sec. 6.2 routing whose emission of disjoint translations is packed by the Sec. 6.3.3 iterate-to-fixpoint grouping rule into three-way parallel translation timesteps (see the reference TS3, TS4, TS9, TS10 below). Command: python ion_trap_compiler.py --circ example.qasm --graph graph_7_1_1.json --gate 3 Trap graph (graph_7_1_1.json): 7 8 | | Main axis 0 - 1 - 2 - 3 - 4 - 5 - 6 Stack vertex 7 attached to junction 1 Stack vertex 8 attached to junction 5 TrapGraph.junctions == [1, 5] Gate vertex: 3 Initial mapping: Map q[1],q[0] → Vertex 3 Map q[2] → Vertex 0 Reference 20-step sequence with 12 timesteps: 40 Timestep 1: 1. GATE cx q[0],q[1] at Vertex 3 Timestep 2: 2. SEPARATE Vertex 3 → q[1]→V2, q[0]→V4 Timestep 3: 3. TRANSLATE q[0]: V4→V5 4. TRANSLATE q[1]: V2→V3 5. TRANSLATE q[2]: V0→V1 Timestep 4: 6. TRANSLATE q[0]: V5→V6 7. TRANSLATE q[1]: V3→V4 8. TRANSLATE q[2]: V1→V2 Timestep 5: 9. MERGE V2+V4 → Vertex 3 (contains q[2],q[1]) Timestep 6: 10. GATE cx q[1],q[2] at Vertex 3 Timestep 7: 11. SWAP Vertex 3 (chain becomes q[1],q[2]) Timestep 8: 12. SEPARATE Vertex 3 → q[1]→V2, q[2]→V4 Timestep 9: 13. TRANSLATE q[1]: V2→V1 14. TRANSLATE q[2]: V4→V3 15. TRANSLATE q[0]: V6→V5 Timestep 10: 16. TRANSLATE q[1]: V1→V0 17. TRANSLATE q[2]: V3→V2 18. TRANSLATE q[0]: V5→V4 Timestep 11: 19. MERGE V2+V4 → Vertex 3 (contains q[2],q[0]) Timestep 12: 20. GATE cx q[0],q[2] at Vertex 3 SECTION 10 - CODE QUALITY - Single file, Python 3.12+. All Python libraries are permitted; however, only libraries needed to compute the requested output may be installed. - Determinism: the compiler must produce byte-identical output for identical inputs across runs, independent of PYTHONHASHSEED or any other process-level entropy. Iterations over sets, dicts, or any other unordered containers whose order can affect the emitted operation stream must be explicitly sorted (e.g., by qubit name, vertex index, or gate id). The random module must not be used without a fixed, in-source seed. - All graph traversals (BFS, DAG depth, routing reductions, push cascades, cycle detection in timestep grouping, etc.) must be iterative -- using an explicit stack or queue -- never recursive. Recursive traversal exceeds Python’s default recursion limit on 200-qubit / 100k-gate inputs and is forbidden. - No code path may rely on integer arithmetic of vertex indices to encode adjacency or topology role. Use trap_graph.neighbors / bfs_path / next_hop / distance for connectivity, and trap_graph.is_junction / is_on_main_axis / stack_of / stacks_at / main_axis to discriminate main-axis vertices, junctions, and stack slots. In particular, do not test "v <= M" or "v > M" to decide whether v is on the main axis or in a stack -- call is_on_main_axis(v) / stack_of(v) instead. SECTION 11 - ACCEPTANCE TEST MATRIX The implementation must pass every test below. Each test fixes the input, invocation, and (where stated) an expected bound; the schedule itself need not match any reference. Tests T1-T2 are small fixed checks; tests T3-T8 list multiple invocations of the same circuit on different graphs. Test T9 covers larger out-of-matrix circuits and graphs. Tests T10-T14 stress two-qubit delivery on progressively denser traps -- depth-1 side-stacks, stacked endpoints, multi-junction traps, and 15- to 25-qubit circuits -- the regime in which the heuristic routing alone is insufficient and the guaranteed delivery routine of Sec. 12.16 is required. Every invocation of every test must pass: it must run to completion and produce a complete, valid schedule, and meet any expected bound the test states. Tests T9-T14 carry no expected operation bound -- for them "pass" means only a complete, valid schedule. No-partial-schedule rule (applies to every test and every invocation): Partial compilation is not allowed. For any circuit, the compiler has exactly two permitted outcomes: (a) it returns a complete, valid schedule in which every gate of the circuit is executed (the schedule passes validate_and_output without any "not all gates have been executed" failure), or (b) it raises an exception. The compiler must never return a schedule that omits one or more gates. schedule_and_route must not "stop early and return what it has": if a gate cannot be routed by any available strategy, the compiler raises an exception rather than silently dropping that gate or any later gate. A run that ends by emitting a partial schedule is a failure even if the partial schedule is internally consistent. T1. Same-pair batching. Input: 10 gates, each on the same qubit pair (q0, q1). Invocation: python ion_trap_compiler.py --circ same_pair.qasm --graph graph_5.json --gate 2 Expected: q0 and q1 are mapped to vertex 2 in the initial state; the 10 GATE operations execute back-to-back on that vertex; SEPARATE, MERGE, SWAP, and TRANSLATE counts are all 0. graph_5.json has no junctions and exercises that the junction-aware code degrades gracefully to the linear case. T2. Sec. 9 cx-triangle. Input/invocation: as in Sec. 9. Expected: ≤ 20 individual operations, ≤ 12 timesteps; the first 2-qubit gate executes at vertex 3 with no preceding shuttling, because the default initial mapping (Sec. 5) co-locates q[0] and q[1] at vertex 3. The bound is reachable via Sec. 6.3.3’s 41 iterate-to-fixpoint grouping, which packs the disjoint per-qubit translations emitted by Sec. 6.2’s routing into three-way parallel translation timesteps. T3. qaoa_5.json -- chain-structured zero-SWAP target. Input: 5 qubits, 35 gates; two-qubit interaction graph is the path q0-q1-q2-q3-q4 (only 4 RZZ gates, all on adjacent pairs). Invocation 1: python ion_trap_compiler.py --circ qaoa_5.json --graph graph_11_1_1.json --gate 5 Invocation 2: python ion_trap_compiler.py --circ qaoa_5.json --graph graph_11_1_2.json --gate 5 Invocation 3: python ion_trap_compiler.py --circ qaoa_5.json --graph graph_11_2_1.json --gate 4 Invocation 4: python ion_trap_compiler.py --circ qaoa_5.json --graph graph_11_3_1.json --gate 3 Expected: 0 SWAP operations across all four invocations. This is the canonical test of the initial-placement heuristic in Sec. 5. T4. rd32-v0_66.json -- small reversible circuit, 4 qubits, 42 gates. Invocation 1: python ion_trap_compiler.py --circ rd32-v0_66.json --graph graph_9_1_1.json --gate 4 Invocation 2: python ion_trap_compiler.py --circ rd32-v0_66.json --graph graph_9_2_1.json --gate 3 Expected: schedule verifies; runtime under one second on commodity hardware. The smallest non-trivial benchmark. T5. 4mod5-v1_23.json -- 5 qubits, 102 gates; non-chain interaction graph. Invocation 1: python ion_trap_compiler.py --circ 4mod5-v1_23.json --graph graph_11_1_1.json --gate 5 Invocation 2: python ion_trap_compiler.py --circ 4mod5-v1_23.json --graph graph_11_1_2.json --gate 5 Invocation 3: python ion_trap_compiler.py --circ 4mod5-v1_23.json --graph graph_11_2_1.json --gate 4 Invocation 4: python ion_trap_compiler.py --circ 4mod5-v1_23.json --graph graph_11_3_1.json --gate 3 Expected: schedule verifies. T6. 4mod5-bdd_287.json -- 7 qubits, 106 gates. Invocation 1: python ion_trap_compiler.py --circ 4mod5-bdd_287.json --graph graph_15_1_1.json --gate 7 Invocation 2: python ion_trap_compiler.py --circ 4mod5-bdd_287.json --graph graph_15_2_2.json --gate 5 Invocation 3: python ion_trap_compiler.py --circ 4mod5-bdd_287.json --graph graph_15_3_1.json --gate 5 Invocation 4: python ion_trap_compiler.py --circ 4mod5-bdd_287.json --graph graph_15_5_1.json --gate 3 Expected: schedule verifies. T7. alu-v2_31.json -- 5 qubits, 640 gates. Invocation 1: python ion_trap_compiler.py --circ alu-v2_31.json --graph graph_11_1_1.json --gate 5 Invocation 2: python ion_trap_compiler.py --circ alu-v2_31.json --graph graph_11_1_2.json --gate 5 Invocation 3: python ion_trap_compiler.py --circ alu-v2_31.json --graph graph_11_2_1.json --gate 4 Invocation 4: python ion_trap_compiler.py --circ alu-v2_31.json --graph graph_11_3_1.json --gate 3 Expected: schedule verifies. T8. cnt3-5_179.json -- 16 qubits, 230 gates. Invocation 1: python ion_trap_compiler.py --circ cnt3-5_179.json --graph graph_33_1_1.json --gate 16 Invocation 2: python ion_trap_compiler.py --circ cnt3-5_179.json --graph graph_33_3_2.json --gate 10 Invocation 3: python ion_trap_compiler.py --circ cnt3-5_179.json --graph graph_33_5_4.json --gate 8 Invocation 4: python ion_trap_compiler.py --circ cnt3-5_179.json --graph graph_33_10_1.json --gate 7 Expected: schedule verifies. T9. Robustness on larger out-of-matrix circuits and graphs. Larger benchmark circuits on larger traps than the T1-T8 matrix. Invocation 1: python ion_trap_compiler.py --circ qaoa_25.json --graph graph_51_4_1.json --gate 10 Invocation 2: python ion_trap_compiler.py --circ qaoa_40.json --graph graph_81_6_1.json --gate 10 Invocation 3: python ion_trap_compiler.py --circ qv_25.json --graph graph_51_4_1.json --gate 10 Invocation 4: python ion_trap_compiler.py --circ qft_25.json --graph graph_51_5_1.json --gate 9 Invocation 5: python ion_trap_compiler.py --circ xeb_sy_25.json --graph graph_51_5_1.json --gate 9 Expected: 0 SWAP operations for invocations 1 and 2. T10. Tight-trap delivery. Five invocations that route benchmark circuits onto 15- to 17-vertex traps whose stack columns are only one vertex deep (graph_13_1_3 has junctions at V1/V4/V8/V11; graph_13_1_4 has junctions at V4/V8). Depth-1 stacks give almost no buffering, so these exercise delivery on single corridors that the roomier T6-T8 traps never produce. Invocation 1: python ion_trap_compiler.py --circ 4gt12-v0_86.json --graph graph_13_1_3.json --gate 6 Invocation 2: python ion_trap_compiler.py --circ 4gt12-v0_86.json --graph graph_13_1_4.json --gate 6 Invocation 3: python ion_trap_compiler.py --circ 4gt4-v1_74.json --graph graph_13_1_4.json --gate 6 Invocation 4: python ion_trap_compiler.py --circ alu-v2_30.json --graph graph_13_1_3.json --gate 6 Invocation 5: python ion_trap_compiler.py --circ alu-v2_30.json --graph graph_13_1_4.json --gate 6 The failure modes these exercise and the delivery method that handles them are described in Sec. 12.13. Invocation 5 exercises the tightest configuration: at one gate an endpoint sits on the gate vertex, three intermediates fill the only corridor to the other endpoint, and the single depth-1 side-stack is occupied -- the configuration that requires the stack-park delivery method of Sec. 12.13 rather than any single-buffer strategy. T11. Stacked-endpoint and occupied-stack delivery. Five invocations on 15- to 19-vertex traps that exercise failure modes distinct from T10: the side-stack the delivery wants to park on is already occupied, and an endpoint freshly extracted from a stack is shoved back into a dead-end stack arm by the extraction of the other endpoint. Invocation 1: python ion_trap_compiler.py --circ 4gt4-v0_79.json --graph graph_13_1_4.json --gate 6 Invocation 2: python ion_trap_compiler.py --circ mod8-10_178.json --graph graph_13_1_4.json --gate 6 Invocation 3: python ion_trap_compiler.py --circ rd53_135.json --graph graph_15_5_1.json --gate 3 Invocation 4: python ion_trap_compiler.py --circ hwb7_59.json --graph graph_17_2_4.json --gate 7 Invocation 5: python ion_trap_compiler.py --circ hwb7_59.json --graph graph_17_6_1.json --gate 3 These failure modes and the delivery methods that handle them are described in Sec. 12.14. T12. Dense multi-junction delivery. Five invocations of 9-qubit circuits on 23- to 25-vertex traps whose main axis carries four to six junctions, each with a depth-1 stack, and whose gate vertex (V9) sits mid-axis with several junctions between it and the endpoints. With nine qubits these traps are dense enough that, at some gate, two or more obstacles lie between an endpoint and its target with no buffer to pass them -- 42 the configuration that no seal-the-subtree delivery can resolve (Sec. 12.13(b)), so the rotor-conveyor routine is required. Invocation 1: python ion_trap_compiler.py --circ xeb_9.json --graph graph_19_1_5.json --gate 9 Invocation 2: python ion_trap_compiler.py --circ xeb_9.json --graph graph_19_1_6.json --gate 9 Invocation 3: python ion_trap_compiler.py --circ xeb_sy_9.json --graph graph_19_1_3.json --gate 9 Invocation 4: python ion_trap_compiler.py --circ xeb_sy_9.json --graph graph_19_1_5.json --gate 9 Invocation 5: python ion_trap_compiler.py --circ xeb_sy_9.json --graph graph_19_1_6.json --gate 9 The failure mode is described in Sec. 12.15(a); the rotor-conveyor delivery that handles it is the routine of Sec. 12.16. T13. Congested-endpoint-corridor delivery. Eight invocations of qft_15 (a 15-qubit circuit) on 33- to 35-vertex traps. With fifteen qubits these traps are denser still than T12: the rotor conveyor’s first step -- bringing the first endpoint to a gate-neighbor -- must succeed even when that endpoint’s corridor is congested, where a direct move to the neighbor does not suffice. Invocation 1: python ion_trap_compiler.py --circ qft_15.json --graph graph_31_1_9.json --gate 15 Invocation 2: python ion_trap_compiler.py --circ qft_15.json --graph graph_31_1_10.json --gate 15 Invocation 3: python ion_trap_compiler.py --circ qft_15.json --graph graph_31_2_7.json --gate 13 Invocation 4: python ion_trap_compiler.py --circ qft_15.json --graph graph_31_2_8.json --gate 13 Invocation 5: python ion_trap_compiler.py --circ qft_15.json --graph graph_31_2_10.json --gate 13 Invocation 6: python ion_trap_compiler.py --circ qft_15.json --graph graph_31_2_15.json --gate 14 Invocation 7: python ion_trap_compiler.py --circ qft_15.json --graph graph_31_3_8.json --gate 11 Invocation 8: python ion_trap_compiler.py --circ qft_15.json --graph graph_31_3_9.json --gate 13 The method -- funnel the first endpoint to the gate vertex rather than moving it directly to a gate-neighbor -- is described in Sec. 12.16(a). T14. Very-dense-trap delivery. Seven invocations of 16- to 25-qubit circuits on 35- to 55-vertex traps that are denser still than T13. They stress the rotor conveyor’s stash step: each rotor cycle stashes a rotated-out obstacle into the anchor endpoint’s subtree, and on a solidly packed corridor a naive stash either cannot reach a far-enough free vertex or walls itself off. The stash must follow the nearest-first, ripple-driven rule of Sec. 12.15(e). Invocation 1: python ion_trap_compiler.py --circ xeb_16.json --graph graph_33_1_10.json --gate 16 Invocation 2: python ion_trap_compiler.py --circ xeb_16.json --graph graph_33_2_15.json --gate 15 Invocation 3: python ion_trap_compiler.py --circ xeb_sy_16.json --graph graph_33_1_15.json --gate 16 Invocation 4: python ion_trap_compiler.py --circ xeb_sy_16.json --graph graph_33_2_15.json --gate 15 Invocation 5: python ion_trap_compiler.py --circ qv_20.json --graph graph_41_1_20.json --gate 20 Invocation 6: python ion_trap_compiler.py --circ qv_25.json --graph graph_51_1_15.json --gate 25 Invocation 7: python ion_trap_compiler.py --circ qv_25.json --graph graph_51_1_20.json --gate 25 Cross-cutting requirements over T2-T14: - For each circuit, the operation stream is byte-identical across two runs with different PYTHONHASHSEED values. - Total wall-clock time and peak RSS scale roughly linearly with number of vertices, qubits, and gates; no individual circuit takes more than a small multiple of the time predicted by linear extrapolation from the smallest circuit. - Every emitted SEPARATE / MERGE / SWAP / GATE timestep starts with all junction vertices empty, and every junction-traversing chain respects the no-roundtrip rule. SECTION 12 - IMPLEMENTATION RECIPES (CRITICAL DETAILS) This section consolidates non-obvious implementation details that the prose-level descriptions in Sec. 6 leave under-specified. Following these recipes is required for the acceptance tests in Sec. 11. 12.1 SNAPSHOT / RESTORE PATTERN Every routing primitive that may emit ops but then need to roll back must wrap its mutations in a snapshot/restore transaction. A snapshot captures four things: a shallow copy of the per-vertex chain state dict, a shallow copy of the qubit-to-vertex mapping, a shallow copy of the junction-entry dictionary, and the current length of the operation list. Restoring reassigns those three dicts from the captured copies and truncates the operation list back to the captured length (not clearing it entirely -- earlier ops outside this transaction must survive). Shallow-copy invariant: chain lists stored as values in state must be treated as immutable references. Every code path that "mutates" a chain (SWAP, MERGE, SEPARATE, the post-gate SWAP optimization, etc.) assigns a freshly built list to state[v] instead of mutating the existing list in place. With that invariant the snapshot can be three dict.copy() calls plus a length record, which is O(N) in the number of occupied vertices and roughly an order of magnitude faster than a deep copy. This matters: snapshot is called millions of times on dense circuits (see Sec. 8 hot-path notes). Every fallback level takes its own snapshot at entry and restores it on failure: per-gv attempt, per-role-swap attempt, the "snapshot dance" of Sec. 12.5 step 5 (park qa; evac gv; re-deliver qa; re-deliver qb), case (b) per-anchor attempts, declutter, decongest, the last-resort setup-and-case-b path, walk-path forward/reverse phases, evacuate per-candidate-path attempts, and cascade-push per-branch attempts. 12.2 EVACUATION BFS -- TRANSIT vs DESTINATION RULES When searching for an empty non-junction destination for an evac, the BFS rule is: For each neighbor nb of the current vertex u: - skip nb if it is in blocked and non-junction and non-empty (occupied non-junction in blocked is fully off-limits) - allow transit through nb otherwise (junction in blocked, empty non-junction in blocked, occupied non-junction not in blocked are all push-to-queue) - mark nb as target only if it is empty, non-junction, and not in blocked Empty blocked non-junctions transit because the chain only passes through them (after the walk completes they are empty again). Junctions in blocked transit because the chain enters and exits them in the same translation phase (the chain itself is never left on a 43 junction). Return a small constant number of candidate paths in BFS-distance order, not just the first. A cap of 3 candidates is the recommended default -- see Sec. 8 for the rationale. evacuate tries each in turn with snapshot/restore; the first whose walk-path (Sec. 12.3) succeeds wins. The fallback chain in Sec. 12.5 already retries at higher levels with looser blocked/avoid sets, so returning more candidates per call multiplies recursive walk_path work without improving the schedule. 12.3 WALK PATH -- TWO-PHASE EVACUATION To move a chain along a BFS path, evacuate intermediate obstacles first, then walk. The routine has two attempt orders separated by snapshot/restore: Forward order: iterate the path indices 1, 2, ..., len(path)-1. For each obstacle vertex u on the path (non-empty), evacuate u with pblocked = (outer blocked) ∪ (non-junction vertices of the path) minus u. If any evac fails, abandon forward-order, restore the snapshot, and try reverse order. Reverse order: same evac sweep but iterating indices in descending order: len(path)-1, ..., 2, 1. Same per-vertex pblocked. Walk phase (only after a complete evac sweep succeeds): for each consecutive (s, t) pair along the path, check (i) no junction no-roundtrip violation at s, (i) t is currently empty; on success emit TRANSLATE(s, t). Reverse-order is essential: when forward-order evac of the obstacle closest to the source fails (because its only escape route is blocked by an obstacle further along the path), evacuating the far-end obstacle first frees a corridor for the near-end one. Without this fallback, dense traps fail routinely. 12.4 CASCADE PUSH FOR EVACUATE (work-stack traversal) Note: this routine is distinct from Sec. 12.11 STACK PUSH (LIFO CASCADE), which inserts a chain into a stack column with the LIFO shift mechanics. Sec. 12.4 is the general-purpose iterative cascade that evacuate falls back on when its BFS finds no empty landing site; Sec. 12.11 is the stack-specific push that uses the Sec. 1 LIFO semantics. When evacuate’s BFS finds no reachable empty non-junction destination, fall back to a cascade push. The cascade push must be implemented iteratively with an explicit work-stack (per the Sec. 10 ban on recursive Python calls). The work-stack represents the in-progress "chain of pushes" being planned: each stack frame names a vertex whose chain needs to be moved, the vertex it was reached from (the push direction), and a deterministic iterator over the as-yet-untried candidate neighbors of that vertex. Per-vertex candidate-neighbor order: list the neighbors of the current vertex sorted as follows: first all empty non-junction neighbors (these are direct landing targets), then all empty-junction neighbors (transit only -- must continue the cascade), then all occupied non-junction neighbors (must cascade through them first by pushing a new work-stack frame). Within each class, sort by vertex index ascending. Skip any neighbor that is in blocked and non-junction and non-empty (protected occupied chain -- never disturb). Skip any neighbor that would violate the no-roundtrip rule at the current vertex. Iterative operation. Each loop iteration acts on the top of the work-stack: Case 1 -- top frame’s next candidate is an empty non-junction vertex that is not in blocked: emit TRANSLATE from top frame’s vertex to that neighbor; the chain has been pushed onto a valid landing site. Then unwind upward -- pop the frame, and for each remaining frame on the stack (parent, grandparent, ...) emit TRANSLATE from parent vertex into the now-empty child vertex (the slot just vacated). When the work-stack is empty, the original caller’s vertex has been freed; return success. Case 2 -- top frame’s next candidate is an empty junction or a blocked-empty non-junction: emit TRANSLATE into that vertex (transit), then push a new frame for that vertex onto the work-stack to continue the cascade beyond it (a chain may never finally land on a junction at the start of a non-translation timestep, and a blocked-empty vertex is transit-only). Case 3 -- top frame’s next candidate is an occupied non-junction not in blocked: push a new frame for that neighbor onto the work-stack (we’l push it out first, then come back to the parent). Case 4 -- top frame has no more candidates: pop the frame and try the next candidate of its parent. If the work-stack empties without a successful TRANSLATE having been emitted, the cascade has failed -- restore the snapshot and return False. Bound the total number of frames pushed at num_vertices + 4 to avoid pathological loops; on overflow, treat it as a Case 4 failure. 12.5 TWO-QUBIT ROUTING FALLBACK CHAIN Layering (read this first). The strategies of this subsection are heuristic: they produce short schedules (and are what meets ≤12-timestep bound of T2 and zero-swap target of T3 and T9’s invocations 1 and 2), but none of them is guaranteed to route every gate on a dense trap. The routing is made total by appending one guaranteed terminal level -- _deliver_complete (Sec. 12.16) -- after the heuristic levels below. So the full two-qubit delivery order is: the heuristic levels of this subsection (for schedule quality), then _deliver_complete (for the guarantee). An implementation that omits _deliver_complete will fail the dense Sec. 11 cases (T12-T14); one that uses only _deliver_complete will route everything but miss the T2/T3/T9 bounds. Both layers are required. The two-qubit gate routing must try strategies in this exact order; each level wraps its attempts in snapshot/restore. Inner attempt (per chosen gate vertex gv and per role assignment of qa/qb to l/r -- see Sec. 6.2 Step 1): 1. If either endpoint is in a stack at slot > 0 (precisely: trap_graph.stack_of(qpos[q]) is not None and stack_of(qpos[q])[2] > 0), run the stack-extraction routine described in Sec. 6.2 (Stack-reordering for trapped endpoints, including the slot-0 special case). This is the highest-impact step for dense traps. Note: an endpoint that is on a junction-vertex in transit, or at slot 0, does not need this step -- only the strict "slot > 0" condition triggers extraction. The extraction’s final junction-to-main-axis translation must obey the non-junction landing rule (Sec. 6.2 Phase 3): pick a non-junction main-axis neighbor of the stack’s junction whenever one exists, otherwise the subsequent walk toward the gate vertex will trigger no-roundtrip at the landing vertex and the whole routing fails. When both of the stack-junction’s main-axis neighbors are themselves junctions, pass the best gate vertex (by combined distance, Sec. 6.2 Step 1) as the target hint t to the extraction routine, so the extracted chain lands on the side facing gv (Sec. 6.2 Phase 3 tie-breaker and safe/unsafe filter). For a single-qubit gate’s pre-extract, use the gate vertex about to be selected as t. 44 2. Isolate both endpoints (Sec. 6.2 single-qubit-style separation if either shares a vertex). 3. Iteration loop applying Sec. 6.2 Step 2’s method-choice logic per iteration (cheapest of Stack-Method, Swap-Method, Park-the-endpoint; see "Method choice each iteration" in Sec. 6.2). Bound the iteration count at num_vertices · 6 + 30. As a practical fallback rule when the cost estimator yields a tie or is unreliable, prefer Stack-Method evacuation first and fall back to Swap-Method MERGE-SWAP-SEPARATE; this matches Sec. 6.2’s "Preferred displacement target" guidance. 4. Final delivery: bring qa to its target gv-neighbor and qb to the other gv-neighbor (according to the assignment chosen in Sec. 6.2 Step 1). On failure, try the rotation-through-gv variant described in Sec. 6.2 case (b) Step 6. Two-assignment rule (which gv-neighbor each endpoint targets): the spec’s tie-breaker for the (qa,qb) → (l,r) assignment in Sec. 6.2 Step 1 chooses one assignment by distance + name. But when that assignment’s walk fails on the first endpoint move (because its path passes through the other endpoint, which is in the keep set and refuses displacement under the strict-keep rule), the implementation must retry with the opposite assignment within the same inner attempt before escalating to the outer retries. Equivalently, try both assignments wrapped in their own snapshot/restore here, not only at outer level (b). This avoids unnecessary fallback escalation on the common case where the chosen assignment is blocked by the other endpoint and the opposite assignment works directly. Two-delivery-order rule (in which order the two endpoints are moved): within an assignment, also try delivering the endpoints in both orders: (qa first, then qb) and (qb first, then qa). For the case where qa is already at its target and the move of qb has to walk past qa, moving qb first (with qa still parked at its initial location) may free a path that moving qa first would not. Try both, again wrapped in snapshot/restore. 5. If gv still holds a non-endpoint chain after delivery: first try direct evacuate(gv, blocked = l, r); if that fails, run the snapshot dance (park qa off the (gv, l, r) triangle; evacuate gv; re-deliver qa to its gv-neighbor; re-deliver qb to the other). If the dance fails, run the full case (b) protocol from Sec. 6.2 (all four anchor combinations with rotation-through-gv in Step 6 as needed). 6. Clear junctions, emit MERGE, emit GATE. Outer retries (when the inner attempt fails for the current gv / role): (a) Try the next gate vertex in combined-distance order (Sec. 6.2 Step 1). (b) For each gate vertex, try both role assignments -- (qa→l, qb→r) and (qa→r, qb→l). Note: Sec. 12.5 step 4 (Two-assignment rule) already tries both assignments at the inner level; level (b) only fires when both inner assignments fail. (c) Declutter pass: push one non-endpoint chain onto any free stack slot 0, using stack-slot eviction (Sec. 6.2 Stack-slot eviction) when no slot 0 is free. Retry from (a). (d) Heavy decongest pass: evacuate any non-endpoint chain (main-axis chains first, then any chain) to any reachable empty non-junction. Retry from (a). (e) Last-resort setup-and-case-b: for every gate vertex, isolate both endpoints, manually deliver them to the gv-neighbors, then invoke the case (b) protocol. (e1) Park-the-endpoint variants -- invoke the Park-the-endpoint routine defined in Sec. 6.2 (Park-the-endpoint variant + Refinements) and enumerate both categories of park slot: (i) every free stack slot 0 (Sec. 6.2 Stack choice priority); (i) every empty non-junction main-axis vertex before the first junction and after the last junction (the linear-arm pattern documented in Sec. 12.12). For each (park_q ∈ qa, qb) × (park slot) combination, walk park_q onto the slot and re-attempt the full inner routing (steps 1-6 above), including iterative reduction on the parked state, before falling through to (e2). (e2) Iterative-reduction retry. Even when none of the above succeeds, run the Sec. 6.2 Step 2 iterative reduction loop with force-allowed evac: repeatedly displace one routing-intermediate at a time via Stack-Method (cascade-push into a stack), Swap-Method, or force-evac into any reachable empty non-junction (including main-axis-end vertices). Each iteration must propagate the qpos[qa], qpos[qb] vertices through a hard_blocked set so that recursive cascading evac never displaces the chain whose evacuation is currently in progress (see Sec. 12.10). (e3) Stack-push cascade retry. For each gate vertex and role, iteratively cascade-push routing-intermediates into stacks using the LIFO cascade described in Sec. 1: emit T(slot_k, slot_k+1) starting from the deepest occupied slot and working outward, then T(j, slot_0). All these translates can share a single translation timestep under the Sec. 6.3 chain rule. (f) Endpoint-at-gv reseat. This level handles the specific circular dependency in which the routing’s *own* keep-set blocks the only escape route the rest of the routing needs: pattern -- one endpoint q_gv sits at the gate vertex gv, while the other endpoint q_far sits either deep in a stack (slot > 0) or behind a chain that can only escape across gv. Pre-extract / decongest of q_far then needs to walk some non-endpoint through gv, but q_gv is in the keep set and refuses displacement, so the walk fails -- and the failure recurses through every prior retry level because each of them re-checks the keep set the same way. The remedy is to reseat q_gv once before the next retry round so gv becomes free as a transit/landing vertex. protocol -- take a snapshot. For each candidate neighbor n of gv in the order (a) gv’s main-axis neighbor whose tree-path to q_far does cross gv (i.e. n is on the OPPOSITE side of gv from q_far), then (b) the other main-axis neighbor: 1. Evacuate n if it is non-empty and the chain at n is not a keep qubit (use the standard evacuate with blocked = gv). If n holds a keep qubit, skip this candidate. 2. Translate q_gv from gv to n (this is the reseat). 3. Retry the entire inner attempt from Sec. 12.5 step 1 (now with q_gv at n instead of at gv). 4. On success, return. On failure, restore the snapshot and try the other candidate. why it is required -- every retry level (a)-(e) above assumes the keep-set semantics is unchanged across retries: keep qubits are strict-protected by every evacuate call. When the only blocker is one keep qubit sitting at gv, no amount of repeating the pipeline with different gv / role / declutter / decongest will dislodge it, because the keep set never relaxes. Reseating q_gv one step off gv breaks that fixed point. 45 why opposite-side preference -- q_far’s stack-extraction (or its walk if it is not in a stack) deposits its chain at a main-axis vertex on q_far’s own side of the trap. That landing is almost always one of gv’s two neighbors. If q_gv is reseated to the same side as q_far, the landing target collides with q_gv and the extraction fails again. Reseating to the opposite side keeps the landing target empty. caveats -- after the reseat, q_gv is at a gv-neighbor n. The inner attempt’s gv-selection MAY pick a different gv on retry (combined-distance order changes when q_gv moves), and the role-assignment may flip. Both are fine. If gv also holds a non-endpoint chain in addition to q_gv (i.e. q_gv is in a 2-chain at gv), the reseat would translate q_gv together with that non-endpoint partner -- q_gv must be isolated first (move the 2-chain to a gate vertex and SEPARATE, parking the partner aside) before its reseat translation can be a single TRANSLATE. Skip reseat entirely if q_gv shares gv with the other endpoint q_far (then Step 0 of the two-qubit routing applies instead). Cross-cutting strengthening of step 1 (not an outer retry -- applies on every inner attempt before any of (a)-(f) ever fire; placed here for locality with the related retry levels): [step-1-strengthening] Buried-2-chain stack extraction. The rules below are in effect on every attempt, including the first one. They extend the step-1 pre-extract documented in Sec. 6.2 (Stack-reordering for trapped endpoints). Case: the endpoint to extract is one ion of a 2-chain at slot k > 0 of a stack with one or more shallower slots also occupied. The Sec. 6.2 Phase 1/2/3 baseline can silently fail here because Phase 2 may skip a shallower slot whose chain cannot reach a non-junction destination on the first try, then Phase 3 attempts TRANSLATE into a still-occupied slot and fails Sec. 3’s dst-empty precondition. Two extensions to Sec. 6.2 Phase 1/2/3 cover this case: - Strict Phase 2: evacuate every occupied shallower slot d ∈ 0, ..., k-1 off stack S entirely, in order d = 0 outward. If any slot cannot be evacuated (chain is a keep qubit, or no landing target exists), the pre-extract fails immediately -- restore and fall through to outer retries (a)-(f). No partial Phase 2. - 2-chain unit transport in Phase 3: SEPARATE is gate-vertex-only (Sec. 3), so a 2-chain at a stack vertex cannot be split in place. Walk the whole 2-chain along the stack lane and then through j onto a non-junction main-axis neighbor (Sec. 6.2 Phase 3’s t-hint and safe/unsafe rule); each hop is one TRANSLATE of both ions together. Once on the main axis the 2-chain is split by the standard Sec. 6.2 single-qubit isolation flow (move to gate vertex, evac the gate vertex’s neighbors, SEPARATE). The partner stays wherever SEPARATE deposits it as an ordinary non-endpoint chain; no re-MERGE after the gate. 12.6 ENDPOINT-AT-GV (degenerate case (b)) Case (b) of Sec. 6.2 Step 3 is stated assuming the gv-chain is a non-endpoint. However, the case-(b) protocol is also invoked by the outer fallbacks (Sec. 12.5 c/d/e) in states where gv’s chain is one of the endpoints (for example, qa stayed at gv after the previous single-qubit gate). In that degenerate case, step 1 of the protocol (move anchor to anchor_target) clears gv as a side effect. The implementation must detect "gv empty after step 1" and skip the MERGE-SWAP-SEPARATE entirely: instead, deliver ‘other‘ to anchor_target (using rotation-through-gv if its tree-path passes through other_target), clear junctions, emit MERGE and GATE. This degenerate branch is already encoded in Step 3 of the case-(b) protocol in Sec. 6.2. Distinction from Sec. 12.5(f): the case-(b) endpoint-at-gv branch above handles the situation when q_gv can be delivered to its final anchor_target in a single translation, with no concurrent extraction or evacuation needed. The Sec. 12.5(f) reseat is for the harder situation where moving q_gv off gv is required just to unblock pre-extract or decongest of the other endpoint -- i.e. the reseat is mid-pipeline cleanup, not a final delivery. Use case (b) when q_gv merely needs to be at a gv-neighbor for MERGE; use Sec. 12.5(f) when gv itself must become a free transit/landing vertex for the rest of the routing to make progress. 12.7 ROUTING-STATE INVARIANTS At every entry to and exit from a routing primitive, the invariants are: - qpos[q] == v iff state[v] contains q. - Sum of |state[v]| over all v equals len(qubits). - Each vertex v has |state[v]| ≤ 2. - No junction has |state[j]| > 0 except immediately after a TRANSLATE into j (i.e. during a translation timestep) -- between non-translation ops, and at the boundary between every pair of consecutively-routed gates, every junction j must satisfy state[j] == [] and the j_entry dict (Sec. 6.2) must record no entry for j (equivalently: j_entry.get(j) is None). This is a hard invariant maintained by every primitive: · move() and walk_path() must not return while a chain rests on a junction; if the planned walk would terminate on a junction, the routine must extend the walk one more hop to drain the chain onto a non-junction neighbor before returning. · push(), evacuate(), and the cascade-push fallback may transit through a junction but must never leave a chain there at return time. · clear_junction(j) must be called before emitting any non-translation op whose vertex set involves vertices reachable through j. · The grouper / timestep packer (Sec. 6.3) must reject any candidate non-translation timestep whose preceding state has any junction occupied -- insert a flush TRANSLATE timestep first. Because of this invariant, both route_single_qubit_gate and route_two_qubit_gate are entitled to assume at entry that no qubit (including the keep qubit(s)) sits on a junction; no defensive lift step is needed. A violation found at entry is a bug in whichever primitive previously returned with a chain still on a junction, not a routing condition to recover from. - At the moment any of MERGE(gv), SEPARATE(gv), SWAP(gv), GATE(gv, _) is emitted: all junctions are empty; the vertices in the operation’s vertex set (gv and, for MERGE/SEPARATE, its two main-axis neighbors) match the operation’s preconditions stated in Sec. 3. After every primitive, assert these (in debug mode) to catch state corruption early. 12.8 POST-PROCESS ROUNDTRIP -- NESTED REMOVAL Roundtrip elimination must support nested removal. The basic singleton removal of (T(A→B), T(B→A)) is replay-checked against junction soundness -- if B is a junction whose immediately preceding entry was from the chain currently on B, removing only the inner pair exposes a junction roundtrip violation in the outer translations (Example 1 of Sec. 6.3). When a singleton fails replay, try a combined removal that also drops the smallest enclosing roundtrip pair. Iterate to fixpoint alternating with Pass 2 (consecutive cancellation). 46 Simpler safe guard (when the full replay is not implemented): refuse to remove any singleton (T(A→B), T(B→A)) where either A or B is a junction. This rejects all candidates that could expose a hidden junction-roundtrip violation in surrounding ops. It is more conservative than the general replay-based rule but preserves correctness with minimal implementation complexity. The full replay-based rule is preferred for stronger optimization. 12.9 TIE-BREAKERS -- APPLIED-EVERYWHERE RULES In addition to the tie-breakers stated inline in Sections 5 and 6, every routing primitive must apply the following consistent tie-breakers when multiple choices have equal primary score: - Choosing a gate vertex for routing a 2-qubit gate: primary score is distance(qpos[qa], gv) + distance(qpos[qb], gv); break ties by gate vertex index (ascending). - Choosing the (qa, qb) → (l, r) assignment: primary score is distance(qpos[qa], l) + distance(qpos[qb], r) versus distance(qpos[qa], r) + distance(qpos[qb], l); break ties by preferring the assignment in which the qubit with the smaller name lands at l. - Choosing an intermediate for the next Stack-Method / Swap-Method iteration: primary score is min(distance(qpos[qa], vi), distance(qpos[qb], vi)); break ties by vertex index (ascending), then by qubit name (ascending). - Iterating neighbors of a vertex during evacuate / push / cascade push: sort by vertex index (ascending) after applying the priority classes documented in each routine. - Snapshot/restore must rebuild dictionaries from the captured copies in a way that does not depend on Python’s hash randomization -- copy the keys in sorted order if any subsequent emission depends on dict iteration order. 12.10 RECURSIVE EVAC -- HARD_BLOCKED ACCUMULATION When walk_path’s forward-or-reverse evac phase recursively evacuates an obstacle u on the walk path, the inner evac may itself trigger another walk_path call (for the obstacle’s escape route), which may in turn evac another obstacle, and so on. Throughout this cascade, the outer walk’s source chain is still occupying the outer source vertex -- it has not yet been walked. If an inner evac displaces the outer source chain (by walking through the outer source’s vertex with force=True), the outer walk’s walk phase will fail because the source becomes empty. Implementation rule: evacuate, walk_path, and find_empty_targets each take an additional hard_blocked parameter -- a set of vertices the BFS is forbidden to traverse or land on, enforced regardless of force=True. The signatures become: walk_path(path, blocked, keep=None, force=False, hard_blocked=None) -> bool evacuate(v, blocked, keep=None, extra_avoid=None, force=False, hard_blocked=None) -> bool find_empty_targets(src, blocked, force=False, hard_blocked=None) -> List[List[int]] Propagation behavior: - walk_path forms its effective hard set as the union of the hard_blocked it received and path[0] (its own source vertex), and passes that union to every obstacle-evac call it makes during its evac phase. - evacuate forwards the hard_blocked it received unchanged into both find_empty_targets and the walk_path it invokes for each candidate path. - find_empty_targets skips every neighbor that is in hard_blocked: such a vertex is neither a transit vertex nor a landing target, even when force=True. Because each nested level adds its own source, the hard set grows monotonically down the recursion: every level’s hard set is a superset of its caller’s. Additionally, the outermost caller of evacuate (e.g. _displace_intermediate inside the Sec. 6.2 Step 2 loop) should seed hard_blocked with the current vertices of the routing’s keep set qpos[qa], qpos[qb], so that endpoint chains are never transited through during cascading force-evacs. Once the outer walk’s walk phase eventually runs, the sources have actually moved and their vertices become empty; hard_blocked is no longer relevant beyond the scope of that single outermost evacuate call. Without this rule, force=True cascade-evacs in linear-trap regions (long stack columns, long main-axis stretches) displace outer endpoint chains and the outer walk’s walk phase fails its "source occupied" precondition on the very first T it tries to emit. The failure surfaces only once the cascade depth grows, so it affects dense states while leaving sparse ones unaffected. 12.11 STACK PUSH (LIFO CASCADE) -- EXPLICIT EMISSION ORDER Note: this routine is distinct from Sec. 12.4 CASCADE PUSH FOR EVACUATE. Sec. 12.4 cascades chains out through occupied non-junctions until an empty landing site is found; the present routine inserts a chain into a stack column using the LIFO push mechanics of Sec. 1. The Sec. 1 LIFO push semantics ("a qubit chain at the junction j is translated to slot 0; every occupied slot shifts one slot deeper simultaneously") is realized in emission as a sequence of individual TRANSLATE operations, packed into one timestep by the Sec. 6.3 chain rule. The emission order matters because each individual T requires its destination empty at execution time. To push a chain currently at vertex v (anywhere reachable from j) onto a stack stk = [slot_0, slot_1, ..., slot_L-1] of junction j, the routine is: 1. Find the deepest occupied slot d (the largest index i such that slot_i is non-empty). If d == L - 1, the stack is at its bottom; fail (no room). 2. Emit cascade pushes from the deepest occupied slot outward toward slot 0: for each slot index i from d down to 0, if slot_i is currently occupied, emit TRANSLATE(slot_i, slot_i+1). Empty slots between occupied ones are skipped. After this sweep, slot_0 (stk[0]) is empty. 3. Walk the chain at v to junction j along its bfs_path, treating j as a transit-only vertex (do not invoke move()/walk_path() which would refuse to terminate at a junction; instead emit the T(s,t) sequence directly and evacuate any non-keep obstacles along the way). 4. Emit TRANSLATE(j, stk[0]). Chain-rule applicability: step 3’s walk-to-j fills j during the same translation batch, and step 4’s T(j, stk[0]) consumes the chain at j. By Sec. 6.3 grouping rule (b) ("t is either initially empty or is the source of some other op already accepted into the batch") and the chain-rule generalization, the entire emission of steps 2-4 forms one translation batch: every leftmost source (each cascade slot in step 2 and the source of the first walk-to-j hop in step 3) is initially occupied; every intermediate vertex (each shifted slot, the junction j, the walk-to-j path interior) is filled by an earlier-in-batch T and vacated by a later-in-batch T. The Sec. 6.3 47 iterate-to-fixpoint admission rule accepts all of them into a single translation timestep. Use this routine inside the Sec. 6.2 Stack-Method displacement ("push intermediate q_inter onto stack at j") and inside the Park-the-endpoint variant whenever the candidate park-slot is a stack vertex. For very-linear traps with deep stacks (graph_33_10_1: 10-deep stacks at V5 and V9), the cascade push lets a chain "displace into the bottom of the stack" while prior occupants shuffle one slot deeper, even when slot 0 itself was already occupied. 12.12 LINEAR-TRAP DEFINITION (graph_33_10_1 and similar) A trap is "very linear" iff it consists of one main axis with a small number of junctions, each of whose stack columns is at least 3 vertices deep and/or whose main-axis-end runs (the contiguous main-axis vertices past each junction in the direction away from gv) are at least 3 vertices long. Linear-arm pattern: stack_arm -- junction_a -- main_axis -- junction_b -- stack_arm | gv main-axis-end main-axis-end (left of (right of junction_a) junction_b) graph_33_10_1 is the canonical instance: a 15-vertex main axis (V0-V14) with two junctions (V5, V9) and a 10-deep stack at each junction (V15-V24 attached to V5; V25-V34 attached to V9). The four "arms" radiating from the gv-region -- left main-axis end (V0-V4), V5’s stack (V15-V24), V9’s stack (V25-V34), and right main-axis end (V10-V14) -- each give 5 to 10 vertices of empty space accessible only through the respective junction or gv-side path. Implementation consequence: every routine that enumerates "park slots" (Sec. 6.2 Park-the-endpoint Refinements, Sec. 12.5(e1)) must include main-axis-end vertices in addition to stack slot 0s. The three primitives used to navigate such traps -- Stack-Method cascade-push (Sec. 12.11), Park-the-endpoint with both stack-slot and main-axis-end targets (Sec. 6.2), and iterative Swap-Method (Sec. 6.2 Step 2) -- are sufficient to handle every dense state arising in the T6-T8 invocations of Sec. 11. 12.13 TIGHT TRAPS -- DEPTH-1 STACKS AND DELIVERY ON SINGLE CORRIDORS This subsection covers delivery on depth-1-stack traps, the regime the Sec. 11 T10 invocations exercise. Sec. 12.1-12.12 do not by themselves cover the single-corridor cases such traps produce; the rules below extend the earlier recipes to handle them. (a) DEPTH-1-STACK ("TIGHT") TRAPS. graph_13_1_3 and graph_13_1_4 are the canonical tight traps: a 13-vertex main axis whose every junction carries a stack column exactly one vertex deep. The "very linear" definition of Sec. 12.12 (stacks ≥ 3 deep, or main-axis-end runs ≥ 3 long) does not hold here, and the linear-trap navigation triad is not by itself sufficient. A tight trap offers almost no buffering: when a chain must pass a vertex, the displaced qubit very often has exactly one legal resting place, or none. Treat any trap with a depth-1 stack as tight and rely on the rules below for delivery. (b) THE ONE-BLANK-ON-A-TREE OBSTRUCTION. A tree has no cycles, so a sliding-block puzzle on a tree with a single empty vertex cannot reorder qubits -- the blank can only shuttle qubits back and forth along its incident path; the cyclic order is invariant. Concretely: if a 1-wide corridor between a delivery endpoint and the gate region is full except for one gap, the endpoint cannot pass the intermediates no matter how many translations are emitted. Genuine reordering on a tree needs either (i) two or more independent free buffers, or (i) the gate-vertex rotor (MERGE+SWAP+SEPARATE swapping the two gate-neighbor cells). A delivery routine that assumes "push the obstacle somewhere and retry" will livelock here; it must instead create a second buffer or fall through to a rotor/stack-park method. (c) EVAC LANDING PREFERENCE -- AVOID GATE VERTICES AND THE ACTIVE CORRIDOR. The Sec. 12.2 / 12.4 evac picks the nearest empty non-junction landing. On a tight trap "nearest" is frequently the gate vertex itself or a cell on the moving chain’s own remaining path -- both poisonous: a qubit parked on gv blocks the imminent MERGE, and a qubit dropped ahead on the mover’s path is immediately re-collided. Give evac (and the cascade and the landing BFS) an optional avoid set and a gate-vertex-last policy: - landings not on a gate vertex and not in avoid are first-class; - landings in avoid are demoted to transit-only; - a gate-vertex landing is used only when nothing else is reachable. Implement as ordered phases: try the landing BFS with avoid honored, then without; then the cascade with avoid honored and gv forbidden, then with avoid honored and gv allowed; only then the cascade with no restriction. Callers that walk a chain pass the chain’s remaining path as avoid, so obstacles settle behind the chain (the vacated trail) or into a side stack rather than ahead onto gv. (d) MONOTONIC SINGLE-HOP MOVE MUST FILL THE TRAIL. The whole-path-evacuate move (Sec. 12.3) is kept as the primary because it yields the tight timestep counts T2 needs. Its single-hop fallback is what survives tight traps, and it must be written so the moving chain advances exactly one vertex per iteration (cur → dst monotonically -- this alone guarantees termination), while each blocking qubit is evacuated with only the moving chain protected (cur in both blocked and hard) and the evacuee free to settle anywhere else, including the already-vacated trail behind the moving chain. Do not add the traversed/trail vertices to the evac’s blocked set: blocking the trail is what forces obstacles ahead onto the gate vertex where they become stuck. Pass the remaining path as the evac avoid set (see (c)) so the trail and side stacks are strictly preferred over cells ahead. (e) STACK-PARK DELIVERY. The four delivery strategies of Sec. 12.5 plus Park-the-endpoint (Sec. 6.2) all assume the parked endpoint goes to a far vertex chosen by distance from gv. On a tight trap the farthest vertex is on the opposite subtree’s main axis, which leaves that main corridor unavailable as buffer space and still blocks the parked endpoint’s own retrieve path. Add one more fallback, tried after Park-the-endpoint and before the guaranteed last-resort: 1. Park one endpoint on a stack vertex of its own subtree (not a main-axis vertex). A stack vertex is off the retrieve main path, so parking there frees the entire opposite-subtree main corridor as obstacle-buffer space. 2. Deliver the other endpoint to its gate-neighbor without hard-confining obstacles to its own subtree -- obstacles may now buffer in the freed corridor and in side stacks. 3. Decongest: move every non-endpoint that ended up on the parked endpoint’s retrieve path out into the mover’s subtree. 48 4. Retrieve the parked endpoint from its stack vertex to its gate-neighbor; the retrieve move evacuates any residual obstacle. 5. Clear the gate vertex (Sec. 12.6 rotation if it is sandwiched). Try the method for both (parked, mover) role assignments, each inside its own snapshot/restore transaction. Rationale: a depth-1 side-stack buffers only one obstacle, so a single corridor with one occupied stack cannot deliver past two or more intermediates; parking on a stack instead of in the corridor converts the whole opposite main axis into the second buffer that (b) proves is required. (f) IMPLEMENTATION DISCIPLINE. The tight-trap rules above must not perturb the schedules of the easy cases (in particular ≤12-timestep bound of T2 and zero-swap target of T3 and T9’s invocations 1 and 2). Confine the tight-trap behavior to a fallback path of any shared primitive (move, evac, cascade) and leave the primary path untouched, so gates the primary path already handles are unaffected. The whole T1-T14 matrix and the PYTHONHASHSEED determinism check must hold. The determinism requirement is on the emitted operation stream only: the human-readable "Compilation time" statistic is wall-clock and is expected to differ between runs. 12.14 STACKED ENDPOINTS -- EXTRACTION FIXPOINT AND OCCUPIED PARK SLOTS This subsection covers delivery on traps with shallow, mostly-occupied stacks, the regime the Sec. 11 T11 invocations exercise. It is distinct from Sec. 12.13: there the corridor geometry is the obstacle; here the difficulty is in endpoint preparation (getting the two endpoints onto deliverable vertices before delivery proper begins) and in an over-strict precondition of the stack-park method. (a) OCCUPIED PARK SLOTS ARE STILL VALID TARGETS. The stack-park delivery of Sec. 12.13(e) parks one endpoint on a stack vertex of its own subtree. A naive implementation enumerates only empty stack vertices and gives up ("no park slot") when every stack vertex in that subtree is occupied -- which is the common case on a tight trap with one shallow stack per junction. This is wrong: move() already evacuates whatever sits on its destination, so a stack vertex holding a non-endpoint is a perfectly good park target. Enumerate every stack vertex of the subtree whose chain contains neither endpoint; sort free ones first (tuple key (is_occupied, distance_to_gv, index)) so an empty slot is still preferred, then fall through to occupied ones. Only a stack vertex that holds an endpoint must be excluded. (b) ENDPOINT EXTRACTION MUST ITERATE TO A FIXPOINT. Before delivery, each endpoint that sits inside a stack column is walked out to a main-axis non-junction vertex (Sec. 6.2 / the extract-endpoint routine). Doing this as two independent, sequential calls -- extract qa, then extract qb -- is incorrect: extracting the second endpoint emits ordinary moves that can shove the first, already-extracted endpoint back down into a stack. Delivery then starts with an endpoint stacked, and on a dead-end stack arm (see (c)) no delivery strategy can recover. Correct approach -- extract both endpoints with a fixpoint loop: repeat (bounded by N+const): if neither endpoint is stacked: done; if qa is stacked: extract qa, protecting qb’s vertex when qb is already extracted; if qb is stacked: extract qb, protecting qa’s vertex when qa is already extracted; if the loop does not converge: raise (no partial schedule). Protecting a vertex means passing it in the extract move’s hard set so the partner is not displaced; if the protected extract fails, retry the same extract once with an empty hard set so progress is still possible. The mutual-protection + retry combination converges because a trap with two endpoints always has at least two main-axis non-junction vertices free between them on the benchmark sizes. (c) DEAD-END STACK ARMS -- WHY (b) MATTERS. A stack column is a dead-end path: its only exit is through its junction. If an endpoint is stacked at depth d and any other qubit sits between it and the junction, that endpoint cannot leave until the shallower qubit leaves first, and the shallower qubit cannot pass the endpoint (a 1-wide dead end has no room to pass -- cf. Sec. 12.13(b)). Extraction handles this correctly only when run as the last preparation step on that endpoint; if a later extraction re-buries it behind a fresh obstacle, delivery inherits an unsolvable local configuration. The fixpoint of (b) guarantees the final state has both endpoints on the main axis, so no delivery method ever has to extract from a dead-end arm itself. (d) ORDER OF PREPARATION STEPS. The required order inside the two-qubit delivery driver is: isolate qa (split it out of any shared chain), isolate qb, then the extract-both fixpoint of (b) -- never interleave isolate and extract per-endpoint, and never extract before both isolations are done, because isolate emits its own moves and can itself re-stack an endpoint. Each step is wrapped in the usual snapshot/restore transaction. 12.15 ROTOR-CONVEYOR -- THE GUARANTEED DELIVERY MECHANISM The Sec. 11 T12-T14 invocations require a delivery the heuristic chain cannot provide: the family of "deliver one endpoint, then the other" methods of Sec. 12.5/12.13/12.14 is fundamentally incomplete on dense traps, so a correct compiler must also provide one guaranteed delivery routine built on the gate-vertex rotor. This subsection describes the mechanism; Sec. 12.16 is the routine to implement and to wire into the fallback chain. (a) WHY THE SEAL-THE-SUBTREE METHODS CANNOT BE PATCHED. Every delivery in Sec. 12.5/12.13/12.14 ultimately moves one endpoint to a gate-neighbor and then the other. The moment an endpoint occupies a gate-neighbor, its subtree is sealed: that subtree connects to the rest of the trap only through that one gate-neighbor vertex, now occupied. An obstacle that must cross from one side to the other can no longer do so. On a dense trap (e.g. 9 qubits on a 23-vertex, multi-junction trap) there is always some gate where two or more obstacles sit between an endpoint and its target, the side-stacks cannot buffer them all, and at least one obstacle must cross the gate region -- which the seal makes impossible. No amount of corridor-sweeping, stack-parking, or delivery reordering removes this; it is a structural dead end. Counting confirms it: an endpoint N hops deep with k obstacles ahead and only s reachable side-stacks strands k-s obstacles when k > s. (b) THE GATE VERTEX IS A 3-CELL ROTOR. With single qubits at l and r, gv empty and all junctions empty, the sequence MERGE(gv), SWAP(gv), SEPARATE(gv) exchanges the qubits at l and r. This is the only primitive that moves a qubit from one subtree to the other without either qubit needing free space to pass the other -- exactly what defeats the obstruction of (a). (c) THE CONVEYOR LOOP. Given qa already on gate-neighbor ga, gv empty, and qb in the subtree of the other neighbor gb, this loop delivers qb to gb, draining every obstacle between qb and gb across the rotor into qa’s subtree: 49 Repeat until qb is the qubit of gb’s subtree closest to gb, then move qb straight to gb: - pick x = a qubit in gb’s subtree strictly closer to gb than qb (an obstacle between qb and its target); - move x to gb (x is closest, so its path carries no other qubit -- a clean translation); - rotor: MERGE/SWAP/SEPARATE at gv -- now x is at ga and qa is at gb (the rotor flips qa to the far side); - stash x off ga, deep into qa’s subtree (see (e)); - move qa back from gb to ga. Each cycle drains exactly one obstacle out of gb’s subtree, so the loop is bounded by the qubit count. Succeed when qa and qb sit on the two gate-neighbors, gv empty and no junction occupied. (d) CONVEYOR INVARIANTS (each is mandatory for correctness). - Isolate every qubit (not just the endpoints) before the conveyor: after a previous gate two non-endpoints can still be a merged 2-chain, and MERGE/SWAP/SEPARATE on a 3-chain drops a qubit (SEPARATE re-emits only chain[0] and chain[1]). - gv must be empty before every rotor cycle: clear it explicitly once before the loop (an endpoint-delivery move keeps gv off the landing set but does not evict a qubit already sitting on gv). - "Closest qubit to gb" is well defined: its path to gb carries no other qubit (any would itself be closer), so moving it to gb is a clean translation that disturbs nothing. - The rotor leaves qa on the far gate-neighbor each cycle; bring it back to ga before the next cycle. Verify the invariant (qa at ga, gv empty, junctions empty) before every MERGE/SWAP/SEPARATE and roll back if it does not hold. (e) STASHING ROTATED-OUT OBSTACLES -- NEAREST-FIRST, RIPPLE-DRIVEN. Every conveyor cycle of (c) rotates an obstacle x to ga and must stash it somewhere in ga’s subtree before the next cycle. On the very dense traps of Sec. 11 T14 (16-25 qubits) the naive stash fails two ways: - stashing x at the farthest free vertex needs a move across the whole subtree corridor, which is impossible once that corridor is packed (x cannot pass a wall of qubits -- (a) again); and - stashing only at currently-empty vertices fills the near-ga corridor first and seals off the far free space behind a wall, so the conveyor jams after a handful of cycles. Two measures make the stash robust: (i) Pre-decongest at the routine’s entry. Before the conveyor, spread every non-endpoint toward the trap extremities (the existing decongest routine, best-effort, never raising). This frees the gate-vertex corridor so the conveyor has somewhere to stash. (i) Stash nearest-first, and allow an occupied target. Enumerate the stash vertices of ga’s subtree ordered by distance to ga ascending (nearest first), excluding only junctions, gate vertices, ga itself, qb’s retrieve path, and any vertex holding an endpoint -- but not excluding occupied vertices. move(ga, u) to an occupied u is fine: move() evacuates u, and that evacuation ripples the local corridor one vertex toward the subtree’s free far end. Because the stash always targets the nearest spot and lets the ripple carry the displacement outward, the stashes never wall themselves off -- the conveyor keeps draining for as many cycles as the gate needs. General principle: when you must repeatedly park qubits into a packed region, push each one to the nearest slot and rely on the evacuation cascade to ripple the crowd outward; do not target far slots directly and do not restrict targets to empty vertices. 12.16 COMPLETE DELIVERY -- THE GUARANTEED ROUTINE _deliver_complete is the single delivery routine that makes routing total on dense traps. Implement it; the heuristic chain of Sec. 6.2/12.5/12.13/12.14 is then only an optimization that yields shorter schedules on the easy gates. Do not rely on the heuristic chain alone -- on dense traps it leaves some gates unroutable. (a) THE KEY ASYMMETRY: ROUTING TO gv IS ROBUST, ROUTING TO A NEIGHBOR IS NOT. Every routing failure on a dense trap reduces to one thing: an endpoint could not pass an obstacle inside a 1-wide corridor. That problem disappears when the destination is the gate vertex itself. Walk an endpoint q toward gv: q and every obstacle ahead of it travel the same direction, and the front-most obstacle simply exits across gv into the opposite subtree. No qubit ever has to pass another. So an unconstrained move(q, gv) -- blocked and hard both empty -- succeeds whenever the trap has free space anywhere, because the cascade evacuation always finds a hole on one side or the other. This is the "funnel". Routing to a gate-neighbor has no such property (a neighbor offers obstacles only one corridor direction once gv is taken), which is why a constrained delivery to a gate-neighbor can fail where the funnel does not. Corollary, and the key principle: a heuristic method fails not because the trap is unroutable but because its moves are over-constrained. The same move(q, gv) that fails with blocked=gv/hard=subtree succeeds with blocked=set()/hard=set(). When a delivery sub-step must simply succeed, pass it the emptiest possible blocked/hard sets and route through gv. (b) THE ROUTINE. _deliver_complete(qa, qb, gv, l, r): 1. Isolate every qubit (single-qubit chains -- Sec. 12.15(d)). 2. Funnel qa to gv with an unconstrained move(qa, gv). By (a) this succeeds whenever the trap has free space. 3. Read qb’s side; let gb be the gate-neighbor on qb’s side and ga the other. Drop qa on ga (evacuate ga, then T(gv, ga)). Choosing ga opposite qb’s side makes qb’s subtree the one to be drained. 4. Run the rotor conveyor of Sec. 12.15(c) (with its pre-decongest and nearest-first stash, Sec. 12.15(e)) to deliver qb to gb. 5. Succeed iff qa and qb sit on the two gate-neighbors, gv empty, no junction occupied. Step 2’s funnel is robust by construction; step 4’s rotor carries each obstacle past qb with neither needing room to pass. Together they make delivery total: no congestion pattern defeats this. (c) ORDERING AND COST. Keep the heuristic levels of Sec. 12.5 ahead of _deliver_complete in the fallback chain -- they produce shorter schedules on the gates they can handle, and _deliver_complete is the guaranteed catch-all that ends the chain. The rotor cost is O(corridor-length) per hard gate, so total wall-clock stays linear in gate count; a large circuit of many thousands of gates takes minutes to compile, which is the expected cost rather than a failure, and the no-partial-schedule rule means such a run must complete rather than be abandoned. Tests with a swap bound (only T3 and T9’s invocations 1 and 2, zero swaps) are unaffected because their gates are routed by the structured fast path and never reach the rotor; confirm this after wiring _deliver_complete into the fallback chain. 50 Appendix C: Prompt for the general compiler The prompt for the general-architecture compiler is reproduced below. It is issued with the optimized branched- architecture compiler as its seed and specifies the changes needed for an arbitrary connected trap graph. Its circuit files are as in Appendix A. The trap-graph files encode arbitrary connected graphs as a JSON edge list of vertex-identifier pairs, with the gate vertex given on the command line. Adapt the existing Ion-Trap Shuttling Compiler in ion_trap_compiler.py from a linear trap with junctions (a tree consisting of a main axis with attached side-stacks) to a general trap graph (an arbitrary connected undirected graph, which may or may not contain cycles). The compiler translates a quantum circuit into a sequence of physical shuttling operations, minimizing the number of timesteps. ion_trap_compiler.py already contains a complete and working compiler for the linear-with-junctions case. Read it: it is the source of truth for every rule and primitive that does not change in the adaptation. This prompt only describes what needs to change for the general-graph case; everything else -- the operation tuple format, the snapshot/restore pattern, the routing primitives’ contracts, the post-processing passes, the timestep-grouping admission rules, the iterative-traversal coding requirements, the no-partial-schedule rule, etc. -- is documented by the existing code and must be inferred from it. In particular, every hardware rule that the validator enforces is in the not-allowed-to-modify code. If anything in this prompt appears to conflict with what those functions enforce, the code is the spec. SCOPE OF THE ADAPTATION May be modified: initial_mapping, compile, and every internal helper function that one of them transitively calls. These must be rewritten so they handle general graphs correctly -- trees, graphs with one or more cycles, and mixes of the two. Must not be modified: the TrapGraph class, the QuantumGate class, parse_input, validate_and_output, and every helper they call. The TrapGraph class already exposes every topology helper the router needs. Do not extend it. INPUT FORMAT The TrapGraph constructor accepts an edge-list JSON whose entries are pairs of vertex identifiers given as strings: [["0", "1"], ["1", "2"], ["2", "3"], ...] Vertex identifiers are converted to int internally, so all comparisons -- including the validator’s u1 < u2 assertion for SEPARATE / MERGE neighbor pairs at gate vertices -- use numeric ordering. Identifiers need not start at 0, need not be contiguous, and need not be assigned in any particular pattern, but strings that parse as integers. The --gate command-line argument is a comma-separated list of vertex identifiers (e.g. --gate 3 or --gate 2,7), also parsed as ints. The graph itself has no spatial embedding -- there is no inherent "left" or "right" of a gate vertex. The validator nevertheless requires a canonical order on the gate vertex’s two neighbors, and it uses numeric comparison to define that order: in every SEPARATE / MERGE operation tuple (gv, u1, u2), the smaller-numbered neighbor is u1 and the larger-numbered neighbor is u2. The "left" / "right" language used in routing prose is just shorthand for this convention: - When a 2-chain [a, b] sits at gv and SEPARATE is applied, the validator places a at u1 (the smaller-numbered neighbor) and b at u2 (the larger-numbered neighbor). See apply_ts_non_trans’s ’S’ branch. - When the two empty neighbors u1, u2 hold single ions and MERGE is applied, the validator forms the chain [state[u1], state[u2]] at gv -- i.e. the smaller-numbered neighbor’s ion is the first element of the resulting chain. See apply_ts_non_trans’s ’M’ branch. The router that builds the operation stream must respect this convention when reasoning about chain order at gv: which qubit ends up at the smaller-numbered neighbor after SEPARATE is determined by which element is index 0 of the chain at gv, which in turn is determined by how the chain was assembled (e.g. by the order of two MERGEs combined with intervening SWAPs). The graph-builder does not need to align "left" and "right" with anything -- the numbering of the vertices alone fixes the convention. TRAPGRAPH METHODS TrapGraph exposes the standard graph primitives (vertices, neighbors, degree, distance, bfs_path, next_hop, is_junction, path_passes_through, junctions_on_path, subtree_through) and the general-graph topology helpers needed for cycle-aware routing: - articulation_points -> List[int] Vertices whose removal disconnects the graph. Useful as a coarse classifier: an articulation-point junction has at least one neighbor that becomes unreachable from its other neighbors when the junction is removed. Note: "is an articulation point" and "lies on a cycle" are independent properties (e.g. the shared vertex of a figure-8 is both on two cycles and an articulation point). For per-pair-of-edges reasoning, use per_junction_components below, not articulation_points. - bridge_edges -> List[Tuple[int, int]] Edges whose removal disconnects the graph. Returned as sorted (u, v) tuples with u < v numerically. An edge is a bridge iff it lies on no cycle. - per_junction_components(j: int) -> Tuple[frozenset, ...] For the junction j, the connected components of V \ j. This is the routing-relevant helper: given a chain that enters j via edge (a, j) and exits via edge (j, b), the chain can later reach a’s side without re-entering j via (a, j) iff a and b lie in the same component (i.e. an alternative arc through V \ j connects them). When they lie in different components, the chain is committed to 51 b’s side until j is emptied. Consult this helper at every junction-transit decision. - alternative_path(src: int, dst: int, forbidden: Set[int]) -> Optional[Tuple[int, ...]] Shortest path from src to dst that avoids every vertex in forbidden, or None if no such path exists. The endpoints src and dst are never excluded. Underpins the cycle-detour routing method: passing the obstacles on the canonical bfs_path as forbidden returns the alternative arc around them, if one exists. All four helpers are precomputed once in the TrapGraph constructor. articulation_points and bridge_edges are iterative Tarjan computations, O(|V| + |E|). per_junction_components is also O(|V| + |E|) per junction total O(|V|·(|V| + |E|)) for the whole table, with the results cached. alternative_path runs a fresh BFS on each call, O(|V| + |E|). WHAT IS DIFFERENT ON A GENERAL GRAPH A general graph may be a tree, may contain cycles, or may be a mix. The adaptation must handle all of these. Where the existing implementation assumes a tree structure or stack semantics, replace that assumption with one of the alternatives below. 1. Topology. A junction is still any vertex of degree > 2, a non-junction vertex has degree 1 or 2, and the gate-vertex constraints are unchanged (degree exactly 2; neither neighbor is a junction). Every junction rule still applies on the general graph: junctions hold ions only in transit; during SEPARATE / MERGE / SWAP / GATE every junction must be empty; the no-roundtrip rule holds at every junction the chain transits (a chain that entered j from a must leave j via some b != a). 2. No stacks, no main axis. Qubit vertices are simply non-junction non-gate vertices that hold up to 2 ions each, with no LIFO or ordering constraint. The existing tree-specific routing structures (stack-shaped side arms with depth-ordered slots, main-axis indexing, per-stack endpoint protection rules) are no longer meaningful on a general graph and must be replaced by general-graph routing during the rewrite. The specific code-visible structures to remove are listed under "REMOVE OR REPLACE" in the ROUTING section. 3. Cycles relax the no-roundtrip rule at cycle-member junctions. The structural difference between a tree and a cycle-containing graph is not "obstacles can be detoured around for free" -- a pure cycle is topologically a linear chain with the endpoints joined, so the 1-wide-corridor obstruction "ions cannot pass each other along a path" still holds on every edge. What changes is the freedom a chain has when transiting a junction that sits on a cycle. On a tree-junction j, the no-roundtrip rule forces every chain entering via edge a to leave via some other edge b; once committed to b, the chain cannot reach a’s side of j without first emptying j and re-entering. On a cycle-member junction j, a chain that needs to reach a’s side after exiting via b can take the cycle’s alternative arc back around, satisfying no-roundtrip via topology rather than via eviction. This is the main structural win. A secondary, situational win is obstacle bypass on a cycle: if one arc of a cycle is heavily packed and the other arc is mostly empty, routing along the empty arc avoids evicting the packed arc’s obstacles. The win is real only when the asymmetric packing makes the alternative arc strictly shorter than (eviction cost + direct arc); on uniformly packed cycles the alternative arc has roughly the same number of obstacles as the direct arc and the cycle-detour is a wash or a loss. The adaptation should exploit (1) whenever a chain transits a cycle-member junction (consult per_junction_components to know whether the entry and intended exit lie in the same component), and (2) opportunistically when alternative_path reports a strictly shorter obstacle-free path than the direct arc. 4. The set of routing methods that must remain after the adaptation: (a) cycle-detour (only applies when alternative_path returns a path and its cost beats the direct-arc-plus-eviction cost -- often loses on uniformly packed cycles); (b) park-the-endpoint at any empty non-junction vertex anywhere in the graph; (c) the standard MERGE / SWAP / SEPARATE Swap-Method (works on any graph, used as the unconditional fallback); (d) the gate-vertex rotor (MERGE / SWAP / SEPARATE on gv) as the terminal level of the fallback chain, since the rotor never relies on cycles -- it relies only on the gate-vertex having two non-junction neighbors, which is true on every legal trap graph. On a graph with no cycles at all, method (a) is unavailable on every iteration and the router falls through to (b), (c), (d) automatically. On a pure cycle (no junctions), method (a) is available on every iteration but rarely wins on cost, so the schedule length is similar to the linear-chain case. The structural cycle benefit (item 3) only materializes on graphs that have both cycles and junctions on those cycles. 5. Park-the-endpoint generalizes. In the existing linear-trap code, "park slot" meant either a stack column head or a main-axis-end vertex. On the general graph it means any empty non-junction vertex that lies off the routing-intermediate paths between the two endpoints’ current positions and their target gv-neighbors. Enumerate candidates by: candidates = [v for v in trap_graph.qubit_vertices if v not in routing_intermediate_paths and current_state.get(v, []) == []] Rank by total cost distance(qpos[endpoint], park_vertex) + distance(park_vertex, gv_neighbor); tie-break by vertex identifier ascending. Park-the-endpoint always has at least one candidate on a 2 * n + 1 non-junction-vertex trap because the placement leaves one empty non-junction vertex free. INITIAL MAPPING The four placement rules must remain in force unchanged (they are also enforced by check_state in the validator): - exactly ⌈len(qubits) / 2⌉ vertices hold qubits; - no vertex holds more than 2 qubits; - no junction vertex holds any qubit; - all remaining vertices are empty. The placement heuristic in the existing initial_mapping (circuit-DAG depth-weighted interaction graph → greedy maximum-weight matching 52 → greedy chain extraction → intra-pair orientation by total cross-pair weight → greedy assignment to candidate vertices sorted by minimum distance to any gate vertex, with the items[0]-equals-first-2q-gate override that places items[0] at the most-central gate vertex) is topology-agnostic: it uses only trap_graph.distance and the set of non-junction vertices. Carry it over unchanged. ROUTING The existing compile uses a multi-level routing pipeline (gate scheduling → routing-intermediate-set construction → iterative reduction → finalization → post-processing → timestep grouping). The pipeline structure carries over to the general graph. Read the existing code for the contract of every primitive (move, push, evacuate, walk_path, clear_junction, snapshot/restore, the routing-state invariants on junctions and endpoint protection, etc.). The changes required for the general-graph adaptation: REMOVE OR REPLACE in the existing code: - The park-candidate scaffolding at the top of _Compiler.__init__ -- the local_main_axis / local_on_main_axis / local_stacks_at recomputation and the _park_candidates / _stack_heads / _PARK_MAX state it produces. This entire block hardcodes the assumption that the graph is a linear main axis with stack-shaped side arms, and is used by _fast_two_park / _try_park_deliver to enumerate park slots only at stack-column heads and main-axis-end vertices. Rewrite the park-slot enumeration to use any empty non-junction vertex of the graph (see point 5 of "What is different"). - The conservative roundtrip-elimination guard inside _post_process (the rule that refuses to remove (A→B, B→A) whenever either A or B is a junction). Replace it with the replay-based junction-soundness check: replay the trace with the candidate removal applied and accept the removal iff no junction’s exit edge matches its immediately preceding entry edge in the residual. The replay-based check accepts strictly more removals, which matters on cycle graphs where an A→B detour at a cycle-member junction B can be sound (the chain entered B from somewhere else via the alternative arc before re-emerging at A). ADD: the cycle-detour routing method. For each routing-intermediate q_inter on the BFS path from an endpoint’s current vertex to its target gv-neighbor, call trap_graph.alternative_path with q_inter (and any already-placed endpoint that should stay stationary) in the forbidden set. If the call returns a path, the endpoint can walk along the alternative arc; q_inter stays where it is, and no SEPARATE / MERGE / SWAP is emitted for it. The bypass cost is just the extra translations the endpoint walks (alternative_arc_length minus direct_arc_length); see METHOD CHOICE below for the full cost comparison. The cycle-detour method is applicable only when the graph contains a suitable cycle. On trees and on dense tree-like subregions of a general graph, alternative_path returns None for any non-trivial obstacle set, and routing falls through to Park-the-endpoint or Swap-Method. Even when an alternative path exists, cycle-detour can lose on cost because the alternative arc may be much longer than the direct arc plus an eviction. The method is an optimization, not a correctness primitive -- never rely on it as the only displacement method. KEEP (these methods work on every general graph, with or without cycles): - Park-the-endpoint, with the generalized park-slot enumeration of point 5 of "What is different." - The Swap-Method intermediate displacement (MERGE → SWAP → SEPARATE on a gate vertex, shifting one intermediate one position outward per step). This is the unconditional fallback when neither cycle-detour nor Park-the-endpoint applies. The same-side handling of the existing implementation carries over verbatim. - The two-qubit finalization protocol when the gate vertex still holds a non-endpoint chain (_deliver_complete + _deliver_rotor in the existing code): try each of the two role assignments (qa-anchor / qb-anchor) wrapped in snapshot/restore, keep the cheaper. - The guaranteed-delivery terminal routine (_deliver_rotor in the existing code): funnel one endpoint to gv with an unconstrained move; drop it on the gv-neighbor opposite the other endpoint; run the MERGE / SWAP / SEPARATE rotor to drain obstacles across gv with nearest-first ripple-driven stashing of rotated-out obstacles. This routine relies only on the gate-vertex’s two non-junction neighbors and on the funnel-move-to-gv property, both of which hold on every legal trap graph regardless of cycle structure. METHOD CHOICE per iteration of the intermediate-set reduction loop. Estimate the cost of each applicable method in elementary translations. Both the bypass cost (extra distance walked along the alternative arc) and the eviction cost must be charged honestly: - cycle-detour: alternative_arc_length minus direct_arc_length, i.e. the extra translations the endpoint walks along the longer arc to avoid the intermediate. Free only when the alternative arc happens to be the same length as the direct one. Often the alternative arc is much longer, in which case cycle-detour loses on cost. - Park-the-endpoint: distance(qpos[endpoint], park_vertex) + distance(park_vertex, gv_neighbor). - Swap-Method: 4 + max(0, distance(endpoint, gv) + distance(intermediate, gv) - 2). The +4 accounts for the SEPARATE + SWAP + MERGE non-translation overhead. Pick the cheapest applicable method. Tie-break order when two methods yield equal estimated cost: (1) cycle-detour (no non-translation overhead), (2) Park-the-endpoint (also no SEPARATE/SWAP/MERGE), (3) Swap-Method. Within the same method, tie-break by the relevant vertex identifier ascending. Special case worth checking explicitly: when the intermediate sits on a cycle-member junction’s "wrong side" (i.e. between the endpoint and the junction, on the direct arc), cycle-detour around the junction may be the cheapest method even when the alternative arc is longer, because evicting an intermediate at a junction often requires the intermediate to first be moved off the junction via no-roundtrip-compliant routing, which can cascade. Consult per_junction_components to determine whether the alternative arc exists at all. WIRING. The multi-level routing fallback chain in the existing implementation remains in the same shape. The level-method names in the existing code (_route_two, _fast_two, _fast_two_park, _try_deliver_pair, _deliver_complete, _deliver_rotor and the snapshot/restore wrapping between them) form the skeleton; the general-graph adaptation changes which method-choice options are available at each level, not the level structure. CODE QUALITY The existing implementation’s coding standards apply unchanged. The ones most likely to bite during a rewrite: 53 - Single file, Python 3.12+. - Determinism: byte-identical output across PYTHONHASHSEED values. Sort every iteration over a set or dict whose order could leak into the emitted ops. - All graph traversals iterative -- explicit stack/queue, no recursion. This applies to BFS, DAG depth, evacuation cascades, and the timestep-grouping admission loop. - No integer-arithmetic-on-vertex-identifiers to encode topology role or position. Vertex identifiers are opaque ints: do not assume any structural meaning from the numbering (consecutive indices need not be neighbors; mid-range indices need not be interior vertices, etc.). Use trap_graph.is_junction together with trap_graph.articulation_points / per_junction_components for topology classification, and trap_graph.neighbors / trap_graph.next_hop / trap_graph.bfs_path for adjacency and routing. - The tree-specific scaffolding identifiers listed in "REMOVE OR REPLACE" (local_main_axis, local_on_main_axis, local_stacks_at, _stack_heads, _park_candidates, _PARK_MAX, _fast_two_park, _try_park_deliver) should not survive in the rewritten code. TESTING No-partial-schedule rule (applies to every (circuit, graph) test and every T1-T14 invocation below): the compiler has exactly two permitted outcomes for any circuit: (a) it returns a complete, valid schedule in which every gate is executed (the schedule passes validate_and_output without any "not all gates have been executed" failure), or (b) it raises an exception. The compiler must never return a schedule that omits one or more gates. If a gate cannot be routed by any available strategy, the compiler raises an exception rather than silently dropping that gate or any later gate. A run that ends by emitting a partial schedule is a failure even if the partial schedule is internally consistent. Test focus is single-gate-vertex architectures sized at 2 * n + 1 non-junction vertices for an n-qubit circuit. Single-gate-vertex architectures are the hardest because every two-qubit interaction must funnel through one gv, removing the ability to absorb obstacles at a second gate vertex. THE BENCHMARK CIRCUITS supplied in the working directory (example.qasm, same_pair.qasm, and the .json files: 4gt12-v0_86, 4gt4-v0_79, 4gt4-v1_74, 4mod5-bdd_287, 4mod5-v1_23, alu-v2_30, alu-v2_31, cnt3-5_179, hwb7_59, mod8-10_178, qaoa_5, qaoa_25, qaoa_40, qft_15, qft_25, qv_20, qv_25, rd32-v0_66, rd53_135, xeb_9, xeb_16, xeb_sy_9, xeb_sy_16, xeb_sy_25) must each compile to a valid schedule on a suitably sized general graph. The number of qubits in each circuit is the number of distinct qubit names appearing in its gates list. GRAPHS -- the test graphs are provided in the working directory as JSON edge-list files. The architecture-matrix graphs (groups A-E below) are named graph_<shape>_n<n>.json (one per shape per circuit qubit-count n, e.g. graph_cycle_n5.json, graph_subdivided_K4_n16.json); arch_graph_gates.json maps each (shape, n) to its gate vertex. The linear-with-junctions graphs used by the explicit T1-T14 invocations are named graph_<V>_<junction_depth>_<junction_distance>.json -- a main axis of V = 2 * n + 1 segments with the gate vertex at its center, junction segments spaced junction_distance apart along the axis, each carrying a side-stack of junction_depth vertices (e.g. graph_13_1_3 has depth-1 stacks every third segment; graph_19_1_5 has depth-1 stacks spaced 5 apart on a 19-segment axis) -- plus the plain path graph_5.json (no junctions; gate vertices 2). Every file uses the JSON edge-list format documented under "INPUT FORMAT" above. The descriptions below document how each provided graph is built and what routing capability it exercises. Every provided architecture graph satisfies: (i) gate-vertex degree exactly 2 (asserted by TrapGraph.__init__); (i) neither gate-vertex neighbor is a junction (asserted by TrapGraph.__init__ and by check_sep_merge_asserts); (i) exactly 2 * n + 1 non-junction vertices for the n-qubit test circuit. The total vertex count is 2 * n + 1 plus the number of junctions, which varies by architecture (zero for pure cycles and paths, one or more for the mixed and dense families below). The placement fills ⌈n / 2⌉ non-junction vertices with qubits and needs at least one empty non-junction vertex of headroom; (iv) connectivity (asserted by TrapGraph.__init__). REQUIRED ARCHITECTURE COVERAGE. For each circuit size n, a graph is provided for each of the fifteen test cases below (graph_<shape>_n<n>.json). The groups are chosen so each exercises a distinct routing capability; passing on one group does not imply passing on the others. Every entry’s construction is stated for general n so the same pattern scales to any circuit. The non-junction vertex count in every entry is exactly 2 * n + 1. GROUP A -- Tree shapes (no cycles, baseline). These graphs verify that the routing still works correctly when no alternative arc ever exists. The cycle-detour method is unavailable at every iteration; the router must compile every benchmark using only Park-the-endpoint, Swap-Method, and the gate-vertex rotor terminal. A1. path. A single path of 2 * n + 1 vertices, no junctions at all. Gate vertex mid-path. Total vertex count: 2 * n + 1. A2. caterpillar. A path of 2 * n + 1 vertices with k additional pendant vertices attached to k distinct interior vertices. Each pendant-bearing vertex has degree 3 and is a junction. All junctions are articulation points (every edge is a bridge). Non-junction vertices: (2 * n + 1 - k) interior + k pendants = 2*n + 1. Total vertex count: 2*n + 1 + k. A3. star. A central vertex of degree k connected to k arms whose lengths sum to 2 * n + 1. If k >= 3 the central vertex is a high-degree junction (degree 4, 5, ...). Gate vertex on one arm. Total vertex count: 2 * n + 2 (the 2 * n + 1 arm vertices plus the central junction). GROUP B -- Cycle-only shapes (one cycle, no junctions). A pure cycle is topologically a linear chain with one extra edge joining the endpoints. Routing on it is mostly the same as on a linear path: the 1-wide corridor constraint still holds on every edge, and the cycle-detour method usually loses on uniformly packed cycles because the alternative arc carries roughly as many obstacles as the direct arc. These graphs verify that the cycle-detour method does not regress the schedule when it does not help, and that the BFS-based alternative-arc search is correct when it does help (asymmetric obstacle packing). Expect schedule lengths similar to a linear-chain shape of the same vertex count, not dramatically better. B1. cycle. A single cycle of length 2 * n + 1, no junctions. Gate vertex anywhere on the cycle (a pure cycle is vertex-transitive, so the gate-vertex position is irrelevant up to relabeling). Total vertex count: 2 * n + 1. GROUP C -- Mixed-topology shapes (cycles and bridges in the same graph). These are the primary stress tests for the cycle benefit: each 54 contains at least one cycle-member junction (where the no-roundtrip rule relaxes via the alternative arc) and at least one bridge (where the routing must fall back to tree-style methods). The router must pick the right method per junction based on whether the junction lies on a cycle. C1. cycle_with_pendant. A cycle of length 2 * n + 1 plus k pendant vertices attached to k distinct cycle vertices. Each pendant-bearing cycle vertex is a junction; it is not an articulation point (the cycle survives its removal), so the no-roundtrip rule relaxes at it. The pendant edges are bridges. Non-junction vertices: (2 * n + 1 - k) cycle non-junctions + k pendant vertices = 2 * n + 1. Total vertex count: 2 * n + 1 + k. C2. lollipop. A cycle of length m + 1 plus a path-tail of length 2 * n + 1 - m attached to one cycle vertex. The attachment vertex has degree 3 and is an articulation point of the whole graph (removing it disconnects the tail from the cycle). Routing within the cycle benefits from the relaxed no-roundtrip at the attachment vertex; routing along the tail has no such relaxation. Non-junction vertices: m cycle vertices (all cycle vertices except the attachment) + (2 * n + 1 - m) tail vertices = 2 * n + 1. Total vertex count: 2 * n + 2 (the 2 * n + 1 non-junctions plus the attachment junction). C3. two_cycles_bridged. Two disjoint cycles connected by a path. The path endpoints (one in each cycle) are junctions; every edge on the connecting path is a bridge. The connecting path itself has zero, one, or more interior non-junction vertices. Non-junction vertices: the cycle non-junction vertices in cycle 1 plus those in cycle 2 plus the connecting-path interior vertices, summing to 2 * n + 1. Total vertex count: 2 * n + 3 if the connecting path has zero interior vertices (just one edge between the two junctions), more otherwise. GROUP D -- Dense / multi-cycle shapes (multiple overlapping cycles). Most or all junctions are cycle-member junctions, so the no-roundtrip relaxation applies almost everywhere. These verify that the router correctly handles junctions belonging to several cycles simultaneously. D1. theta. Two vertices joined by three internally disjoint paths. Both degree-3 vertices are junctions on the same pair of cycles. The gate vertex is on the interior of one of the three paths. Non-junction vertices: the path interiors, summing to 2 * n + 1. Total vertex count: 2 * n + 3. D2. figure8. Two cycles sharing one vertex. The shared vertex has degree 4 and is an articulation point of the whole graph: removing it splits the two cycles into two disjoint paths. Cycle-detour applies within each cycle but cannot cross the shared vertex (alternative_path through forbidden = shared returns None for any pair on different sides). Tests that the router does not mistakenly assume an alternative arc exists across the shared vertex. Non-junction vertices: (cycle1_length - 1) + (cycle2_length - 1) = 2 * n + 1. Total vertex count: 2 * n + 2. D3. cycle_with_chord. A cycle of length 2 * n + 3 plus one chord edge connecting two non-adjacent cycle vertices. The chord adds no new vertices, but its two endpoints (already cycle vertices) become junctions of degree 3. Non-junction vertices: 2 * n + 3 - 2 = 2 * n + 1. The chord creates two additional cycles (the chord plus each of the two arcs of the original cycle that it separates), giving three cycles total that share pairs of vertices. The gate vertex sits on the cycle interior at a non-junction position whose two neighbors are also non-junctions. Total vertex count: 2 * n + 3. D4. cycle_with_two_chords. A cycle of length 2 * n + 5 plus two non-crossing chord edges. The four chord endpoints become junctions of degree 3. Non-junction vertices: 2 * n + 5 - 4 = 2 * n + 1. Place the chord endpoints so that at least one consecutive run of three non-junction cycle vertices remains, then put the gate vertex in the middle of that run. (A naive placement that scatters all four chord endpoints uniformly leaves only length-2 non-junction runs, and no such vertex has two non-junction neighbors -- the construction then fails the gate-vertex constraint.) Total vertex count: 2 * n + 5. GROUP E -- Structured / parameterized families. These are adaptations of classical network topologies. The unadapted forms typically have every vertex at degree 3 or higher (so every vertex would be a junction and no qubit or gate vertex would exist). Each entry below describes both the base topology and the adaptation that introduces enough non-junction vertices to host the qubits and the gate vertex. The adaptation principle is the same in every case: subdivide selected edges by inserting degree-2 intermediate vertices, until the non-junction count reaches exactly 2 * n + 1 and a gate-vertex candidate (degree-2, both neighbors non-junctions) exists. E1. subdivided_K4. Base: the complete graph K4 has 4 vertices, each of degree 3, with 6 edges. Subdivide each edge by inserting one degree-2 vertex in the middle of the edge. After subdivision: 4 original vertices (junctions, still degree 3) + 6 subdivision vertices (non-junctions, degree 2). For larger n, subdivide each edge with more than one vertex -- k subdivision vertices per edge yields 6k non-junctions; tune the per-edge subdivision counts (they need not all be equal) so the total non-junction count equals 2 * n + 1. Pick a subdivision vertex on a sufficiently subdivided edge as the gate vertex so that its two neighbors (other subdivision vertices on the same edge) are non-junctions. Tests dense multi-cycle routing with junctions belonging to multiple short cycles each. E2. subdivided_Q3. Base: the 3-dimensional hypercube Q3 has 8 vertices (the corners of a cube), each of degree 3, with 12 edges. The 8 original vertices are all junctions in any subdivision. To get a viable gate vertex, at least one edge must be subdivided with 3 or more intermediate vertices (so the middle subdivision vertex has two subdivision-vertex neighbors, both non-junctions). The remaining edges may be subdivided with any number of vertices (including zero -- leaving them as direct Q3 edges between junctions). Tune the per-edge subdivision counts so the total subdivision-vertex count equals 2 * n + 1. For example, for n = 5 (need 11 non-junctions): one edge with 3 subdivisions for the gate vertex, plus 8 edges with 1 subdivision and 3 edges left direct = 3 + 8 = 11 non-junctions. Tests regularly-structured multi-cycle routing with every junction equivalent under graph automorphism. E3. subdivided_butterfly_B2. Base: the butterfly network B2 has 3 levels of 4 vertices each (12 vertices total) with edges following the butterfly bit-flip pattern between adjacent levels. The standard butterfly is constructed so every vertex has degree 4 (each level-i vertex connects to two vertices in level i-1 and two in level i+1, with end levels wrapping or terminating depending on the variant). Every vertex is a junction in the unadapted form, so no qubit or gate vertex exists. Adapt by subdividing every edge that lies on a candidate gate-vertex chain: a chain of three subdivision vertices in series on one edge (call them A-X1-X2-X3-B where A and B are original butterfly vertices) gives X2 as a viable gate vertex (its neighbors X1 and X3 are both non-junctions). For n = 4 (need 9 non-junctions), subdivide one edge with 3 vertices and another 6 edges with 1 vertex each (3 + 6 = 9 non-junctions). For larger n, distribute additional single-subdivision vertices across more edges. The level structure and the multiple short cycles between adjacent levels make this a stress test for routing through junctions belonging to many short cycles each. E4. ladder. Two parallel paths of P + 1 vertices each (so P edges along each path), connected by P + 1 rungs (edges between corresponding path-vertices). Subdivide each rung by inserting one degree-2 vertex in the middle. Junctions: the 2 * P - 2 internal path vertices (each has two path neighbors and one mid-rung neighbor, so degree 3). Non-junctions: 4 corner path vertices (degree 2 55 each, with one path neighbor and one mid-rung neighbor) plus P + 1 mid-rung vertices (degree 2 each, with two path-vertex neighbors). Total non-junctions: 4 + (P + 1) = P + 5. Set P = 2 * n - 4 so non-junctions = 2 * n + 1. Total vertex count 2 * (P + 1) + (P + 1) = 3 * (P + 1) = 6 * n - 9. Gate vertex: an end-rung mid-vertex (rung 0 or rung P), whose two neighbors are corner path-vertices, both non-junctions. (Interior-rung mid-vertices do not qualify because their neighbors are internal path junctions.) Tests routing on a two-rail topology with a regular cycle structure (every face is a 4-cycle). VERIFICATION (already satisfied by the provided files): - TrapGraph instantiates on each graph with len(tg.qubit_vertices) + len(tg.gate_vertices) == 2 * n + 1. - The smallest benchmark (same_pair.qasm or example.qasm) compiles on each graph; if that fails, the larger benchmarks on the same shape fail too. EXPLICIT INVOCATIONS (T1-T14). Beyond the architecture matrix above, the compiler must pass the explicit invocation suite below. It is the original linear-with-junctions test suite -- a linear main axis with depth-k side-stacks is a tree, a special case of a general graph, so every invocation the linear compiler passed must still pass after the general-graph adaptation. Each test fixes the input, invocation, and (where stated) an expected bound; the schedule itself need not match any reference. Tests T1-T2 are small fixed checks; T3-T8 list multiple invocations of one circuit on different graphs; T9 covers larger out-of-matrix circuits and graphs; T10-T14 stress two-qubit delivery on progressively denser traps (depth-1 side-stacks, stacked endpoints, multi-junction traps, 15- to 25-qubit circuits) -- the regime in which heuristic routing alone is insufficient and the guaranteed-delivery rotor is required. Tests T9-T14 carry no expected operation bound -- for them "pass" means only a complete, valid schedule. T1. Same-pair batching. Input: 10 gates, each on the same qubit pair (q0, q1). Invocation: python ion_trap_compiler.py --circ same_pair.qasm --graph graph_5.json --gate 2 Expected: q0 and q1 are mapped to vertex 2 in the initial state; the 10 GATE operations execute back-to-back on that vertex; SEPARATE, MERGE, SWAP, and TRANSLATE counts are all 0. graph_5.json has no junctions and exercises that the junction-aware code degrades gracefully to the linear case. T2. cx-triangle. Input: example.qasm -- three qubits, the gates cx q0,q1; cx q1,q2; cx q0,q2. Invocation: python ion_trap_compiler.py --circ example.qasm --graph graph_7_1_1.json --gate 3 Expected: ≤ 20 individual operations, ≤ 12 timesteps; the first 2-qubit gate executes at vertex 3 with no preceding shuttling, because the default initial mapping co-locates q[0] and q[1] at vertex 3. T3. qaoa_5.json -- chain-structured zero-SWAP target. Input: 5 qubits, 35 gates; two-qubit interaction graph is the path q0-q1-q2-q3-q4 (only 4 RZZ gates, all on adjacent pairs). Invocation 1: python ion_trap_compiler.py --circ qaoa_5.json --graph graph_11_1_1.json --gate 5 Invocation 2: python ion_trap_compiler.py --circ qaoa_5.json --graph graph_11_1_2.json --gate 5 Invocation 3: python ion_trap_compiler.py --circ qaoa_5.json --graph graph_11_2_1.json --gate 4 Invocation 4: python ion_trap_compiler.py --circ qaoa_5.json --graph graph_11_3_1.json --gate 3 Expected: 0 SWAP operations across all four invocations. This is the canonical test of the initial-placement heuristic. T4. rd32-v0_66.json -- small reversible circuit, 4 qubits, 42 gates. Invocation 1: python ion_trap_compiler.py --circ rd32-v0_66.json --graph graph_9_1_1.json --gate 4 Invocation 2: python ion_trap_compiler.py --circ rd32-v0_66.json --graph graph_9_2_1.json --gate 3 Expected: schedule verifies; runtime under one second on commodity hardware. The smallest non-trivial benchmark. T5. 4mod5-v1_23.json -- 5 qubits, 102 gates; non-chain interaction graph. Invocation 1: python ion_trap_compiler.py --circ 4mod5-v1_23.json --graph graph_11_1_1.json --gate 5 Invocation 2: python ion_trap_compiler.py --circ 4mod5-v1_23.json --graph graph_11_1_2.json --gate 5 Invocation 3: python ion_trap_compiler.py --circ 4mod5-v1_23.json --graph graph_11_2_1.json --gate 4 Invocation 4: python ion_trap_compiler.py --circ 4mod5-v1_23.json --graph graph_11_3_1.json --gate 3 Expected: schedule verifies. T6. 4mod5-bdd_287.json -- 7 qubits, 106 gates. Invocation 1: python ion_trap_compiler.py --circ 4mod5-bdd_287.json --graph graph_15_1_1.json --gate 7 Invocation 2: python ion_trap_compiler.py --circ 4mod5-bdd_287.json --graph graph_15_2_2.json --gate 5 Invocation 3: python ion_trap_compiler.py --circ 4mod5-bdd_287.json --graph graph_15_3_1.json --gate 5 Invocation 4: python ion_trap_compiler.py --circ 4mod5-bdd_287.json --graph graph_15_5_1.json --gate 3 Expected: schedule verifies. T7. alu-v2_31.json -- 5 qubits, 640 gates. Invocation 1: python ion_trap_compiler.py --circ alu-v2_31.json --graph graph_11_1_1.json --gate 5 Invocation 2: python ion_trap_compiler.py --circ alu-v2_31.json --graph graph_11_1_2.json --gate 5 Invocation 3: python ion_trap_compiler.py --circ alu-v2_31.json --graph graph_11_2_1.json --gate 4 Invocation 4: python ion_trap_compiler.py --circ alu-v2_31.json --graph graph_11_3_1.json --gate 3 Expected: schedule verifies. T8. cnt3-5_179.json -- 16 qubits, 230 gates. Invocation 1: python ion_trap_compiler.py --circ cnt3-5_179.json --graph graph_33_1_1.json --gate 16 Invocation 2: python ion_trap_compiler.py --circ cnt3-5_179.json --graph graph_33_3_2.json --gate 10 Invocation 3: python ion_trap_compiler.py --circ cnt3-5_179.json --graph graph_33_5_4.json --gate 8 Invocation 4: python ion_trap_compiler.py --circ cnt3-5_179.json --graph graph_33_10_1.json --gate 7 Expected: schedule verifies. T9. Robustness on larger out-of-matrix circuits and graphs. Larger benchmark circuits on larger traps than the T1-T8 matrix. Invocation 1: python ion_trap_compiler.py --circ qaoa_25.json --graph graph_51_4_1.json --gate 10 Invocation 2: python ion_trap_compiler.py --circ qaoa_40.json --graph graph_81_6_1.json --gate 10 Invocation 3: python ion_trap_compiler.py --circ qv_25.json --graph graph_51_4_1.json --gate 10 Invocation 4: python ion_trap_compiler.py --circ qft_25.json --graph graph_51_5_1.json --gate 9 Invocation 5: python ion_trap_compiler.py --circ xeb_sy_25.json --graph graph_51_5_1.json --gate 9 Expected: 0 SWAP operations for invocations 1 and 2. T10. Tight-trap delivery. Invocation 1: python ion_trap_compiler.py --circ 4gt12-v0_86.json --graph graph_13_1_3.json --gate 6 Invocation 2: python ion_trap_compiler.py --circ 4gt12-v0_86.json --graph graph_13_1_4.json --gate 6 Invocation 3: python ion_trap_compiler.py --circ 4gt4-v1_74.json --graph graph_13_1_4.json --gate 6 Invocation 4: python ion_trap_compiler.py --circ alu-v2_30.json --graph graph_13_1_3.json --gate 6 Invocation 5: python ion_trap_compiler.py --circ alu-v2_30.json --graph graph_13_1_4.json --gate 6 T11. Stacked-endpoint and occupied-stack delivery. Invocation 1: python ion_trap_compiler.py --circ 4gt4-v0_79.json --graph graph_13_1_4.json --gate 6 Invocation 2: python ion_trap_compiler.py --circ mod8-10_178.json --graph graph_13_1_4.json --gate 6 Invocation 3: python ion_trap_compiler.py --circ rd53_135.json --graph graph_15_5_1.json --gate 3 Invocation 4: python ion_trap_compiler.py --circ hwb7_59.json --graph graph_17_2_4.json --gate 7 Invocation 5: python ion_trap_compiler.py --circ hwb7_59.json --graph graph_17_6_1.json --gate 3 T12. Dense multi-junction delivery. Invocation 1: python ion_trap_compiler.py --circ xeb_9.json --graph graph_19_1_5.json --gate 9 Invocation 2: python ion_trap_compiler.py --circ xeb_9.json --graph graph_19_1_6.json --gate 9 Invocation 3: python ion_trap_compiler.py --circ xeb_sy_9.json --graph graph_19_1_3.json --gate 9 Invocation 4: python ion_trap_compiler.py --circ xeb_sy_9.json --graph graph_19_1_5.json --gate 9 Invocation 5: python ion_trap_compiler.py --circ xeb_sy_9.json --graph 56 graph_19_1_6.json --gate 9 T13. Congested-endpoint-corridor delivery. Invocation 1: python ion_trap_compiler.py --circ qft_15.json --graph graph_31_1_9.json --gate 15 Invocation 2: python ion_trap_compiler.py --circ qft_15.json --graph graph_31_1_10.json --gate 15 Invocation 3: python ion_trap_compiler.py --circ qft_15.json --graph graph_31_2_7.json --gate 13 Invocation 4: python ion_trap_compiler.py --circ qft_15.json --graph graph_31_2_8.json --gate 13 Invocation 5: python ion_trap_compiler.py --circ qft_15.json --graph graph_31_2_10.json --gate 13 Invocation 6: python ion_trap_compiler.py --circ qft_15.json --graph graph_31_2_15.json --gate 14 Invocation 7: python ion_trap_compiler.py --circ qft_15.json --graph graph_31_3_8.json --gate 11 Invocation 8: python ion_trap_compiler.py --circ qft_15.json --graph graph_31_3_9.json --gate 13 T14. Very-dense-trap delivery. Invocation 1: python ion_trap_compiler.py --circ xeb_16.json --graph graph_33_1_10.json --gate 16 Invocation 2: python ion_trap_compiler.py --circ xeb_16.json --graph graph_33_2_15.json --gate 15 Invocation 3: python ion_trap_compiler.py --circ xeb_sy_16.json --graph graph_33_1_15.json --gate 16 Invocation 4: python ion_trap_compiler.py --circ xeb_sy_16.json --graph graph_33_2_15.json --gate 15 Invocation 5: python ion_trap_compiler.py --circ qv_20.json --graph graph_41_1_20.json --gate 20 Invocation 6: python ion_trap_compiler.py --circ qv_25.json --graph graph_51_1_15.json --gate 25 Invocation 7: python ion_trap_compiler.py --circ qv_25.json --graph graph_51_1_20.json --gate 25 CROSS-CUTTING REQUIREMENTS over every (circuit, graph) test of the architecture matrix and every T1-T14 invocation: - The operation stream is byte-identical across two runs with different PYTHONHASHSEED values. - Total wall-clock time and peak RSS scale roughly linearly with number of vertices, qubits, and gates; no individual circuit takes more than a small multiple of the time predicted by linear extrapolation from the smallest circuit. - Every emitted SEPARATE / MERGE / SWAP / GATE timestep starts with all junction vertices empty, and every junction-traversing chain respects the no-roundtrip rule (both are enforced by the validator).