Scaling Qubit Mapping and Routing With Position Graph Abstraction and Memoization
For quantum compilation researchers, this work provides a practical method to scale mapping and routing on shuttling-based architectures, though it is an incremental improvement over existing SABRE-based methods.
The paper tackles the bottleneck of scalable qubit mapping and routing in quantum compilation for Trapped-Ion QCCD architectures. By introducing a position graph abstraction and memoization techniques, they accelerate the SABRE heuristic, achieving improved scalability without altering routing decisions.
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.