Scaling Qubit Mapping and Routing With Position Graph Abstraction and Memoization

This paper introduces a compilation framework for Trapped-Ion QCCD architectures that leverages a position graph abstraction and memoization techniques to significantly accelerate the SABRE heuristic search for qubit mapping and routing by eliminating redundant computations while preserving decision quality.

The Gist

Imagine you are trying to organize a massive, high-stakes dance competition inside a crowded, narrow hallway. The dancers are qubits (the basic units of quantum computers), and the goal is to get specific pairs of dancers to meet up in the same small room (a "trap") to perform a special duet (a quantum gate).

However, there are strict rules:

1. The Hallway is Crowded: You can't just teleport dancers; they have to physically walk through the hallway.
2. No Double-Booking: Only a certain number of dancers can fit in a room at once.
3. Traffic Jams: If a dancer needs to walk past another dancer who is standing still, the path is blocked. You have to figure out how to move the standing dancer out of the way first.

This is the challenge of Quantum Compilation for a specific type of quantum computer called a Trapped-Ion QCCD. The paper you provided describes a new "traffic control system" that makes organizing this dance much faster and more efficient.

Here is a breakdown of what the authors did, using simple analogies:

1. The Old Map vs. The New "Position Graph"

The Problem: Previously, computer programs used a simple map called a "Coupling Graph." This map was like a subway diagram that only showed which stations were connected. It was great for computers where you just swap two items (like trading seats), but it failed for these ion computers where you have to physically move ions through a complex maze of hallways and rooms.

The Solution: The authors introduced the Position Graph.

• Analogy: Think of the old map as a subway line drawing. The new Position Graph is a full 3D architectural blueprint of the building. It doesn't just show which rooms are connected; it shows every single tile on the floor, every hallway, every door, and exactly how long it takes to walk from one spot to another.
• Why it matters: This allows the computer to understand the real physical constraints, like "You can't walk through that wall" or "That room is too small for two people."

2. The "Traffic Cop" Problem (Congestion)

The Problem: When the computer tries to move a dancer (ion) to a room, it often finds the path blocked by another dancer. The old software would stop, look at the map, calculate a new path, and try again. If the path was blocked again, it would calculate again. This was like a GPS that recalculates the entire route from scratch every time you hit a red light. It was incredibly slow.

The Solution: The authors created LightSHAW (a "Light" version of their previous system).

• Analogy: Imagine a traffic cop who keeps a memo pad (a cache).
  • Memoization: Instead of recalculating the distance from Point A to Point B every time, the cop writes it down once. If the same situation happens again, they just look at the note.
  • The "Blockage Profile": The system remembers that "If you try to go from Hallway 1 to Room 5, you always have to pass through Door 3." It pre-calculates the "penalty" for that door being blocked.
  • The Result: When a jam happens, the system doesn't panic and re-calculate everything. It quickly checks its notes: "Ah, I know this jam. I know exactly how to clear it." This makes the process much faster.

3. The "Smart Filter" (Pruning)

The Problem: When deciding which room a group of dancers should go to, the computer used to check every single possible room in the building, doing a full calculation for each one.

• Analogy: It's like trying to find the best restaurant in a city by walking into every single one, ordering a meal, tasting it, and then deciding.

The Solution: They added a Pruning step.

• Analogy: Before walking into a restaurant, the system checks a "menu preview" (a lower-bound score). If the preview says, "This place is definitely too expensive," the system skips it immediately without ever stepping inside. It only does the full, expensive check on the few restaurants that look promising. This saves a massive amount of time.

4. The Big Surprise: It Works for Simple Systems Too

The Claim: Usually, when you make a map more detailed (like going from a subway map to a 3D blueprint), the computer gets slower because it has to process more data.

• The Result: The authors tested their new "Position Graph" on simple systems (Superconducting computers) that don't need the complex 3D blueprint. They found that the new system was just as fast as the old, simple system.
• Analogy: It's like upgrading from a paper map to a GPS app. You might think the GPS is slower because it has more data, but they optimized it so well that it runs just as fast as the paper map for simple trips, while still being able to handle complex detours when needed.

Summary of Results

The paper claims that by using this new "Position Graph" and the "LightSHAW" memory tricks:

1. Speed: They can compile (organize) quantum circuits for large, complex ion computers much faster than before.
2. Scalability: As the number of dancers (qubits) grows, the time it takes to organize them grows much more slowly than before.
3. Reliability: The system can handle "tighter" buildings (more crowded rooms) where other systems fail completely.
4. Versatility: This single system can now handle both the simple "swap" computers and the complex "shuttling" computers without slowing down.

In short, they built a smarter, faster traffic control system that remembers past jams and skips bad routes, allowing quantum computers to perform complex dances without getting stuck in traffic.

Technical Summary

Technical Summary: Scaling Qubit Mapping and Routing With Position Graph Abstraction and Memoization

Problem Statement

Scalable qubit mapping and routing remain critical bottlenecks in quantum compilation, particularly for Trapped-Ion Quantum Charge-Coupled Device (TI-QCCD) architectures. Unlike superconducting systems where routing is modeled via SWAP operations on a static coupling graph, TI-QCCD requires physically shuttling ions through segments and junctions. This process is constrained by movement legality, trap capacity limits, and congestion (where intermediate positions are occupied).

Existing heuristic methods, such as SABRE, rely on abstractions like Coupling Graphs that are insufficient for TI-QCCD because they cannot express the complex constraints of physical transport, intermediate occupancy, and path blocking. While a prior work introduced the Position Graph abstraction to unify executable locations, movement paths, and routing constraints, its initial implementation suffered from severe scalability issues. For instance, compiling a 128-qubit circuit on a 180-ion device could take a day due to redundant computations during heuristic search and congestion resolution.

Methodology

The paper proposes a compilation framework that enhances the Position Graph abstraction with caching and memoization strategies to eliminate redundant computations without altering routing decisions.

1. Position Graph Abstraction

The framework utilizes the Position Graph ($G_p$), a labeled graph where:

• Vertices represent occupiable physical locations (traps, intermediate transport regions).
• Edges represent valid transitions (swaps within a trap, merge/split between trap and transport, or movement within transport).
• Labels distinguish between operation types (swap, merge/split, move).
  This abstraction generalizes the Coupling Graph (used for superconducting systems) to support the richer topology of TI-QCCD.

2. Architecture-Level Caching

To reduce overhead, the authors pre-compute and cache architecture-dependent quantities that remain static during a compilation run:

• All-pairs shortest paths and distance matrices.
• Executable subgraphs derived from edge labels.
• Path blockage profiles: For any source-target movement, a cached list of intermediate positions that could cause blockage, along with fixed penalties for resolving them.

3. LightSHAW: Memoized Congestion Resolution

The core contribution is LightSHAW, a cached variant of the SHAW (SHuttling-AWare) heuristic. SHAW resolves congestion recursively when a moving ion is blocked by an occupied position. LightSHAW optimizes this via a two-level cache:

• Local Scoring-Set Cache: Caches the set of nearby positions to inspect for a given candidate clearing move, avoiding repeated graph traversal to define the search neighborhood.
• Configuration-Keyed Congestion Memoization: Memoizes the congestion score based on a "local occupancy signature" ($\sigma$). The key is $(p, t, b, d, \sigma)$, where $p$ is the candidate position, $t$ is the target, $b$ is the blockage, $d$ is the search depth, and $\sigma$ represents the occupancy of the local scoring set. This allows the system to reuse scores for repeated local congestion patterns without re-scanning the entire device.

4. Trap Selection Pruning

To optimize the selection of target traps for multi-qubit gates, the authors implement a lower-bound pruning strategy. They compute an optimistic lower bound on the routing cost for each trap (ignoring congestion and distinct slot requirements). Traps are evaluated in increasing order of this bound; exact scoring stops once the lower bound of the next candidate exceeds the best exact score found so far.

5. Validation on Superconducting Architectures

To ensure the Position Graph does not impose unnecessary overhead on simpler architectures, the authors instantiated LightSABRE (a SABRE variant) using both a traditional Coupling Graph backend and a Position Graph backend. Both implementations were configured to make identical routing decisions, isolating the cost of the abstraction itself.

Key Contributions

1. Redundant Computation Removal: Identification and caching of shortest MOVE paths, travel-time distances, and blockage-related path information in SHAW.
2. LightSHAW Algorithm: Introduction of a memoized congestion-resolution procedure that reuses architecture-dependent information (movement paths, local clearing regions) and local occupancy scores, significantly reducing repeated work during recursive blockage clearing.
3. Abstraction Overhead Analysis: Demonstration that the Position Graph can replace the Coupling Graph for LightSABRE routing with negligible runtime overhead, proving that richer architectural models do not inherently compromise compilation speed.
4. Open-Source Framework: Provision of an implementation supporting both superconducting and TI-QCCD workflows, facilitating experimentation across heterogeneous quantum architectures.

Experimental Results

The authors evaluated the framework using benchmarks including QAOA, QFT, and Hamiltonian simulation circuits (TFIM, TFXY) ranging from 16 to 512 qubits.

• Compilation Time Scaling: LightSHAW significantly outperforms the original SHAW and the state-of-the-art QCCDSim simulator in terms of scaling.
  • SHAW: Scales as $O(x^{3.91})$.
  • QCCDSim: Scales as $O(x^{3.04})$.
  • LightSHAW: Scales as $O(x^{1.72})$.
  • While LightSHAW has higher overhead for very small circuits compared to QCCDSim, it matches or exceeds QCCDSim performance on larger circuits (e.g., 180-ion architectures) and scales much more favorably.
• Operation Time (Quality): LightSHAW produces schedules with significantly lower total operation time (gate execution + shuttling) compared to QCCDSim. For example, on a 512-qubit QAOA circuit, LightSHAW achieved an operation time ratio of 0.171 relative to QCCDSim, indicating a ~6x reduction in execution time.
• Robustness: In strict resource-constrained scenarios (high ion utilization per trap), QCCDSim frequently failed to produce valid compilations (denoted as 'X' in results), whereas LightSHAW successfully completed all instances.
• Superconducting Compatibility: When applied to superconducting routing (LightSABRE), the Position Graph backend matched the runtime of the traditional Coupling Graph backend, confirming that the abstraction introduces no significant penalty for simpler architectures.

Significance

The paper argues that the Position Graph abstraction provides a practical and effective path toward scalable qubit mapping and routing across heterogeneous quantum architectures. By combining architecture-aware representation with memoized heuristic evaluation, the framework resolves the scalability bottleneck of TI-QCCD compilation without sacrificing performance on superconducting systems. The results suggest that compiler infrastructure can move beyond minimal adjacency models to support complex physical constraints (like shuttling) while maintaining the efficiency required for large-scale quantum compilation. The work establishes that a unified representation can serve both SWAP-based and shuttling-based architectures, enabling a single framework to handle diverse hardware constraints.