General circuit mapping algorithm for neutral atom quantum computers

This paper proposes a graph-theoretic framework and genetic algorithm-based solver to optimize qubit mapping for neutral atom quantum computers, minimizing transfer counts and distances while respecting spatial constraints to improve execution efficiency.

The Gist

The Big Picture: Moving Furniture in a Smart House

Imagine you have a very special, high-tech house (the Neutral Atom Quantum Computer) where the "furniture" is actually tiny atoms that hold information. These atoms are like guests at a party.

To perform a calculation (run a quantum circuit), these guests need to talk to each other. But there's a catch: they can only have a conversation if they are standing very close together (within a few micrometers). If they are too far apart, they can't interact.

In this house, the guests don't just walk; they are physically moved around by invisible laser "tweezers." This process of moving them is called remapping.

The Problem:
Moving these atoms is slow, risky, and energy-intensive. If you move them too much, they might get lost or break (lose their quantum state). If you move them inefficiently, the whole calculation takes too long and fails. The challenge is: How do you rearrange the guests so they can talk to the right people, using the fewest moves and the least amount of walking?

The Solution: A New "Moving Plan" Algorithm

The authors of this paper created a new mathematical tool (an algorithm) to solve this moving puzzle. Here is how they did it, broken down into three steps:

1. Drawing the Map (Graph Theory)

First, they looked at the list of instructions (the circuit) and turned it into a map.

• The Analogy: Imagine breaking a long movie script into scenes. In each scene, certain characters need to be near each other.
• The Innovation: They realized that instead of trying to solve the whole movie at once, they could look at the "handoffs" between scenes. They used a branch of math called graph theory to figure out the absolute minimum number of times a character must move from one scene to the next. They proved that if you minimize the moves for every single transition between scenes, you automatically get the best overall plan.

2. The "Stick" Packing Method (Encoding)

Once they knew who needed to move, they needed to figure out where to put them on the grid to avoid collisions.

• The Analogy: Imagine the atoms are packed into long, flexible "sticks" or bundles. Some sticks hold one person, some hold two.
• The Innovation: Instead of trying to move every single atom individually, the algorithm treats these bundles as single units. It can slide a whole "stick" to a new spot or shuffle the people inside the stick. This simplifies the problem massively, allowing the computer to find a solution much faster.

3. The Genetic Algorithm (The Trial-and-Error Coach)

Finally, they used a "Genetic Algorithm" to find the perfect arrangement.

• The Analogy: Think of this like a coach training a team. The coach generates hundreds of different moving plans.
  • Some plans are great at minimizing the total distance walked.
  • Some plans are great at letting people move in parallel (many people moving at once).
  • The coach picks the best plans, mixes their features, and tries again. Over time, the team evolves to find the most efficient way to move.

What Did They Find?

The authors tested their new method against the best existing tools (called ZAC and MQT).

• Fewer Moves: Their method consistently found ways to move the atoms fewer times than the other tools. It hit the theoretical "perfect score" for the minimum number of moves required.
• Shorter Walks: When they tuned the algorithm to care about distance, the atoms walked significantly shorter paths (sometimes 300% shorter!) compared to the other tools.
• Parallelism: When they tuned it to care about moving many atoms at the same time, they often achieved better results than the competition.

The Trade-Off: Distance vs. Speed

The paper highlights a crucial choice for the people building these computers:

• Do you want to minimize the total distance the atoms travel (to save time and reduce errors from moving too far)?
• Or do you want to minimize the number of moves (to let the laser tweezers move many atoms at once in parallel)?

Their tool allows the user to choose. It's like having a GPS that can give you the "shortest route" or the "fastest route" depending on your traffic conditions.

Summary

This paper provides a new, mathematically proven "moving company" for quantum computers. It doesn't just guess where to put the atoms; it calculates the absolute best way to rearrange them to ensure the quantum computer runs faster, more accurately, and with fewer mistakes. It works for both simple layouts and complex, multi-room (zoned) quantum computers.

Technical Summary

Technical Summary: General Circuit Mapping Algorithm for Neutral Atom Quantum Computers

Problem Statement
Neutral Atom Quantum Computers (NAQC) offer a scalable platform characterized by long coherence times, flexible qubit arrangements, and native multi-qubit gate capabilities (e.g., CCZ, Ck-phase). However, executing quantum circuits on NAQC hardware requires physically moving atoms via optical tweezers to bring qubits into proximity for entanglement gates (Rydberg blockade). This "remapping" process introduces significant overhead:

1. Fidelity Loss: Each transfer carries a risk of atom loss or state change. While single-transfer success rates are high (>0.99), cumulative errors become prohibitive for circuits with many qubits or transfers.
2. Time Overhead: Transfers consume time, reducing the overall computation window.
3. Optimization Challenge: Existing compilers (e.g., ZAC, MQT) often rely on heuristics like simulated annealing or greedy algorithms. While they improve upon earlier methods, they lack explicit theoretical lower bounds for the number of required transfers and do not provide a general formulation that simultaneously optimizes for total distance traveled and parallel transfer operations (PTOs) across both monolithic (M-arch) and zoned (Z-arch) architectures.

Methodology
The authors propose a unified, circuit-independent mathematical framework based on graph-theoretic combinatorial optimization. The methodology proceeds in four distinct stages:

1. Graph Representation (Theoretical Foundation):

   • The quantum circuit is decomposed into a directed acyclic graph (DAG) where vertices represent "instructions" (groups of gates acting on specific qubits within a stage) and edges represent transitions between stages.
   • The problem of minimizing transfers between stages is modeled as finding a maximum weighted matching in bipartite subgraphs connecting consecutive stages.
   • Theorem 3.1 & 3.2: The authors prove that the minimum number of transfers for both M-arch and Z-arch can be derived by summing the local minimums of these matchings. For Z-arch, the graph is decomposed into zone-specific subgraphs, with mandatory transfers occurring between zones.

2. Stick Encoding (Problem Reduction):

   • To optimize the physical placement of atoms, the authors introduce a "stick encoding." This representation abstracts the mapping problem by grouping qubits that remain static between stages into "sticks."
   • Within a stick, qubits form "substicks." The encoding captures the intrinsic degrees of freedom (DoFs): the 2D spatial coordinate of the stick on the atomic grid and a Boolean variable indicating if the substicks within a multi-qubit stick are swapped.
   • This encoding decouples the decision of which qubits to move (determined by the graph matching) from the placement of those qubits, allowing for efficient optimization of the traveled distance.

3. Genetic Algorithm (Optimization):

   • A Genetic Algorithm (GA) is employed to solve the resulting nonlinear integer program.
   • The GA operates without crossover, relying instead on local random modifications (moving sticks or shuffling substicks) to explore the configuration space.
   • The objective function is flexible, allowing the user to prioritize minimizing the total distance traveled, maximizing the number of parallel transfers, or a weighted combination of both.

4. Parallel Transfer Operations (PTO) Construction:

   • A post-processing step constructs the sequence of parallel transfers.
   • The algorithm analyzes the transfer digraph to detect cycles. If a cycle exists (atoms blocking each other's paths), a "parking space" (an empty atomic slot) is used to break the cycle, requiring one additional transfer.
   • A greedy algorithm then schedules the transfers, ensuring compatibility with hardware constraints (e.g., Acousto-Optical Deflector limitations) to maximize parallelism while avoiding collisions.

Key Contributions

• General Mathematical Framework: The paper provides the first graph-theoretic formulation that determines the theoretical lower bound for the number of atom transfers required for any quantum circuit on NAQC platforms, applicable to both monolithic and zoned architectures.
• Novel Encoding: The introduction of "stick encoding" effectively reduces the complexity of the mapping problem by isolating the degrees of freedom related to spatial placement and internal qubit ordering.
• Trade-off Control: The framework explicitly enables a trade-off between minimizing the total distance traveled by atoms (reducing time) and maximizing parallel transfer operations (reducing latency).
• Theoretical Guarantees: Unlike previous heuristic approaches, this work provides provable lower bounds for transfer counts (Theorem 3.1/3.2) and demonstrates that the proposed method consistently reaches these bounds.

Results
The authors benchmarked their algorithm against state-of-the-art mappers, specifically ZAC (a reuse-aware zoned architecture mapper) and MQT (Munich Quantum Toolkit).

• Transfer Count: The proposed method consistently achieves the theoretical minimum number of transfers (within 0–2 transfers due to cycle-breaking requirements) across all tested circuits. In contrast, ZAC often exceeds this theoretical minimum.
• Distance and Parallelism:
  • When optimizing for distance, the proposed method significantly reduces the total traveled distance compared to ZAC (e.g., ~333% improvement for the QFT circuit).
  • When optimizing for parallel transfers, the method often outperforms both ZAC and MQT in the number of PTOs, particularly for complex circuits.
• Flexibility: The results highlight a trade-off: optimizing for distance does not always minimize PTOs, and vice versa. The GA allows practitioners to tune the objective function based on specific hardware parameters (e.g., the relative speed of tweezer movement vs. trap switching).

Significance and Claims
The paper claims to provide both a theoretical baseline and a practical tool for efficient, architecture-aware quantum circuit compilation.

• Theoretical: It establishes that the minimal number of transfers can be determined via graph matching, offering a benchmark for future compiler development.
• Practical: It offers a flexible optimization tool that allows practitioners to generate hardware-aware mappings. By reducing movement-induced errors and better exploiting atom transfer parallelism, the method directly improves execution efficiency on NAQC devices.
• Scalability: The approach is described as general and scalable, capable of handling various gate sets (including multi-qubit gates) and adaptable to future NAQC architectures with additional zones (e.g., for CCZ gates).

The authors maintain a modest tone regarding execution time, noting that the optimal choice between minimizing distance or PTOs depends on specific hardware parameters (e.g., SLM/AOD switching speeds vs. tweezer movement speeds) which vary across platforms. They recommend running the mapper with different parameters to select the best solution for a given device.