Scaling Qubit Mapping and Routing With Position Graph Abstraction and Memoization
Brent Russon 1 , Bao G. Bach 1 2 , Ed Younis 3 , Ilya Safro 2 4 · 2026
Read Scaling Qubit Mapping and Routing With Position Graph Abstraction and Memoization by Brent Russon 1 , Bao G. Bach 1 2 , Ed Younis 3 , Ilya Safro 2 4 (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-09237.txt.
Introduction
Russon and three colleagues speed up qubit mapping and routing, a major snag in quantum compilation. The problem bites hardest for trapped ion systems, where interactions demand ions be shuttled under strict movement, congestion, and trap limits. Their framework centres on a position graph, a unified picture of routing constraints, movement paths, and runnable spots that lets mappers work directly on shuttling hardware.
On that graph they speed up SABRE, a two way heuristic search, with relative move scoring that caches repeated move scores, and memoized fixes for repeated congestion. The optimisation removes redundant work without changing any routing or shuttling decision. The result is a practical route to scalable mapping and routing on trapped ion systems and across varied quantum hardware. Source code and data are promised on acceptance. The work pairs an architecture aware picture with cached heuristic scores, cutting wasted work where search repeats itself.
Catalog record
| CREATOR | Brent Russon 1 , Bao G. Bach 1 2 , Ed Younis 3 , Ilya Safro 2 4 |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 47 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.09237
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Scaling Qubit Mapping and Routing With Position Graph Abstraction and Memoization Brent Russon 1 , Bao G. Bach 1 2 , Ed Younis 3 , Ilya Safro 2 4 Abstract Scalable qubit mapping and routing remain major bottlenecks in quantum compilation, especially for Trapped-Ion Quantum Charge-Coupled device (TI-QCCD) architectures, where qubit interactions require physically shuttling ions under strict movement, congestion, and trap-capacity constraints. We present a compilation framework built around the position graph abstraction, a unified representation of executable locations, movement paths, and routing constraints that enables heuristic mappers to operate directly on shuttling-based hardware. Using this abstraction, we accelerate the SWAP-based BidiREctional heuristic search (SABRE) by implementing relative move scoring, which caches repeated heuristic move evaluations that arise during search, and memoized congestion resolution, which speeds up the resolution of repeated congestion. This optimization removes redundant computation without changing routing/shuttling decisions, improving the scalability of SABRE-based methods on TI-QCCD systems. Our results show that combining an architecture-aware abstraction with memoized heuristic evaluation yields a practical and effective path toward scalable qubit mapping and routing across heterogeneous quantum architectures. Reproducibility: the source code and data are available at [link will be available here upon acceptance] I Introduction Qudit mapping and routing are central bottlenecks in quantum compilation because hardware constraints often prevent logical two-qudit interactions from being executed directly [ 33 , 5 ] . This challenge is especially important for superconducting architectures and shuttling systems such as trapped-ion quantum charge-coupled device (TI-QCCD) architectures. In superconducting systems, physical qudits can be moved using SWAP operations along a given configuration [ 18 ] . In contrast, TI-QCCD requires physically shuttling ions through segments and junctions while respecting movement legality, trap-capacity limits, and congestion constraints [ 14 ] . As a result, routing overhead can dominate execution time and strongly affect scalability. Existing practical mapping methods are largely built around abstractions such as Coupling Graphs, which are well matched to SWAP-based routing on superconducting devices. However, architecture with qudit shuttling [ 19 , 24 , 6 ] , such as TI-QCCD, requires reasoning not only about which qudits should interact, but also about where ions can legally move, which intermediate positions are occupied, and whether a candidate path is blocked. These constraints make standard connectivity-only abstractions insufficient for expressing the shuttling-based routing. Our prior work addressed this challenge by introducing the Position Graph abstraction [ 2 ] , a hardware-aware representation that captures executable locations, movement paths, and routing constraints within a unified graph model. Built on top of this abstraction, the SHAW and SHAPER [ 2 ] compilers showed that heuristic search methods inspired by superconducting-qudit mapping can be adapted to shuttling-based trapped-ion compilation. Although this abstraction is expressive enough to capture the complex TI-QCCD hardware constraints, the initial implementation [ 2 ] suffers from scalability issues where it can take a day to shuttle a 128 -qudit circuit on a 180 -ion space device. This paper takes the next step toward the practical deployment of the Position Graph abstraction, which substantially improves the scalability, enabling large-scale shuttling with both Superconducting and TI-QCCD architectures. We demonstrate that this richer abstraction does not incur meaningful overhead compared to previous methods, and highlight performance improvements to BQSkit’s SABRE [ 12 , 29 ] and SHAW algorithms by using cached results of architectural information modeled by the Position Graph. These include finding all-pairs shortest paths, their distance matrix, and an executable subgraph. While the Position Graph enables architecture-aware routing, heuristic search over QCCD states can still incur substantial overhead because the same local blockage and congestion situations are evaluated repeatedly during routing. To reduce this overhead, we introduce LightSHAW , a cached variant of SHAW’s congestion-resolution procedure. LightSHAW reuses architecture-dependent information such as movement paths and local clearing regions, and it avoids recomputing local congestion scores when the same occupied local configuration recurs during recursive blockage clearing. These caches reduce repeated graph traversal and local occupancy scanning while preserving SHAW’s routing decisions. In addition to improving SHAW, we evaluate the runtime cost of using the Position Graph abstraction in a standard superconducting routing setting. A concern with richer architectural models is that they may impose unnecessary overhead when the target device is well described by a traditional Coupling Graph. To test this directly, we instantiate LightSABRE using both a conventional Coupling Graph backend and a Position Graph backend. The two implementations perform the same routing decisions and produce identical compiled circuits, allowing the comparison to isolate the cost of the abstraction itself. Our results show that the Position Graph can match the runtime of the Coupling Graph while retaining the ability to represent richer hardware structure when needed. This suggests the practicality of the Position Graph, maintaining runtime while potentially serving as a unification for different types of architectures (we already showed for SWAP-based and shuttling-based architectures). In summary, this paper makes the following contributions: 1. We identify and remove redundant computations in SHAW by caching shortest MOVE paths, travel-time distances, and blockage-related path information used repeatedly during routing. 2. We introduce LightSHAW, a cached variant of SHAW that memoizes local congestion geometry and occupancy-sensitive congestion scores, reducing repeated work during recursive blockage resolution while preserving the routing behavior of the original algorithm. 3. We demonstrate that the Position Graph abstraction can replace the traditional Coupling Graph for LightSABRE-style routing with negligible runtime overhead, showing that a richer architecture model need not come at the cost of slower compilation. 4. We provide an open-source implementation of the Position Graph framework and its routing machinery, supporting experimentation across both superconducting and TI-QCCD compilation workflows and future extension across heterogeneous quantum architectures. Fig. 1: Example of mapping a QCCD-based TI architecture to its corresponding Position Graph. Figure (a) shows a real hardware configuration, and Figure (b) shows the Position Graph abstraction that represents the hardware configuration. Here, (i) each position vertex in the Position Graph represents a physical location where an ion may reside. The vertex colored purple indicates that an ion is currently occupying this location, while the uncolored (white) vertex indicates that this position is empty. (ii) Each vertex with a black border represents the available position inside a trap, while the vertex with a yellow border represents abstract intermediate positions where a qudit may temporarily reside while moving between traps. (iii) The dotted black edges within each trap indicate pairs of positions between which a two-qudit gate operation is possible, while the straight line indicates the physical connection that allows operations such as swap. (iv) The blue edges abstract the path where the ion can move (without stopping) to reach another trap. II Background II-A Quantum Compilation In quantum computing, compilation is the process of converting a logical quantum circuit into an equivalent circuit that can be executed directly on a specific quantum processing unit (QPU). This requires adapting the circuit to hardware-dependent constraints, including restricted qudit connectivity, imperfect gate fidelities, and other architectural limitations. Effective compilation is especially important in the NISQ setting, where noise and short coherence times make resource efficiency critical. As a result, quantum compilation generally aims to reduce both circuit size and execution time in order to improve overall reliability. The two central stages of this process are