Square-root Time Atom Reconfiguration Plan for Lattice-shaped Mobile Tweezers

1. Problem Statement

Neutral-atom quantum computing relies on optical tweezers to trap and manipulate atoms. However, the initial loading of atoms into a static tweezer array is a stochastic process, resulting in a high defect rate (50–60% vacant sites). To build fault-tolerant quantum computers, these defects must be removed by reconfiguring the randomly loaded atoms into a specific, defect-free target geometry (e.g., a perfect $L \times L$ grid or an arbitrary pattern).

Key Challenges:

• Time Constraints: Atoms have limited trap lifetimes due to background gas collisions. Reconfiguration must be fast to minimize atom loss.
• Hardware Limitations: Current Acousto-Optic Deflector (AOD) systems can generate 2D lattices of mobile tweezers, allowing for parallel transport. However, existing planning algorithms often restrict movement to 1D patterns or require complex relay paths, failing to fully exploit the parallel transport capacity of 2D AODs.
• Scalability: Previous algorithms (e.g., PSC, Tetris) typically achieve $O(N)$ reconfiguration time or $O(\sqrt{N})$ operations with $O(\sqrt{N})$ travel distance per atom, leading to high total transportation costs ($O(N)$) under linear cost models.

2. Methodology

The authors propose a scalable planning algorithm that reconfigures $N$ atoms in $O(\sqrt{N})$ time. The approach is based on a divide-and-conquer strategy that decomposes the 2D reconfiguration problem into a sequence of simpler 1D shuttling tasks.

Core Model

• System: A static $n \times n$ tweezer array (where $N \approx n^2$) and mobile AOD tweezers that can capture atoms in a 2D lattice pattern and shift them one unit in four directions (Up, Down, Left, Right).
• Cost Model: The objective is to minimize the number of operations $|p|$. Since AODs can move multiple atoms in parallel, the time cost is dominated by the number of operation cycles, not the total distance traveled by individual atoms.
• Simplification: Unlike previous models allowing complex multi-step paths, this model restricts operations to uniform shifts of entire rows or columns within a selected lattice pattern.

Algorithm Components

The algorithm consists of two main modules:

A. 1D Shuttling Solver
This module solves the problem of aligning atoms along a single axis (e.g., row-wise). It uses two steps:

1. Leftward Alignment: Shifts all atoms in a row to the leftmost available positions using $n-1$ parallel operations.
2. Rightward Delivery: Shifts atoms from the left-aligned state to their specific target positions within the row using another $n-1$ operations.

• Result: Any 1D alignment task is solved in $O(n) = O(\sqrt{N})$ time.

B. Decomposer (Divide-and-Conquer)
The decomposer breaks an arbitrary 2D reconfiguration problem into at most three 1D shuttling tasks:

1. Three-Step Strategy (Guaranteed Solution):
   • Step 1 (Row Balancing): Use column-wise shuttling to equalize the number of atoms in each row (distributing atoms via round-robin).
   • Step 2 (Column Finalizing): Use row-wise shuttling to match the column sums of the target geometry.
   • Step 3 (Row Finalizing): Use column-wise shuttling to match the exact target geometry.
   • Theoretical Basis: The existence of intermediate geometries is guaranteed by the Gale–Ryser theorem, which provides conditions for the existence of a binary matrix with given row and column sums.
2. Two-Step Strategy (Optimization): Attempts to skip the balancing step if the initial geometry already satisfies specific sum conditions. It fails for some edge cases but is faster when applicable.
3. Grid Formation Strategy (Peephole Optimization): For the specific case of creating a square grid, the algorithm gathers atoms toward the top-left corner. A "peephole optimization" technique skips redundant shift operations, significantly reducing the operation count for grid targets.

3. Key Contributions

• $O(\sqrt{N})$ Time Complexity: The first algorithm to theoretically and practically achieve $O(\sqrt{N})$ reconfiguration time for arbitrary target geometries by fully exploiting 2D parallel transport.
• High Reliability: Unlike heuristic approaches (e.g., PSC/Tetris) that may fail for certain initial configurations, this algorithm guarantees a valid solution for any initial and target geometry using the Gale–Ryser theorem and a fallback three-step strategy.
• Hardware Feasibility: The algorithm relies only on simple row/column shift operations, avoiding complex lattice compression/expansion that can cause heating or require difficult hardware control.
• Scalability: It scales efficiently to large systems (demonstrated up to $N \approx 4 \times 10^5$ atoms) without requiring a linear increase in control hardware.

4. Experimental Results

The authors evaluated the algorithm against State-of-the-Art (SOTA) methods (PSC/Tetris and the Hungarian algorithm) using numerical simulations on a $632 \times 632$ grid.

• Transportation Cost:
  • For grid geometries with $N = 2 \times 10^5$, the proposed method reduced the total transportation cost to 1/7 of the PSC algorithm under the square-root cost model, and 1/83 under the linear cost model.
  • The total cost scales as $O(\sqrt{N})$, whereas SOTA methods scale as $O(N)$.
• Reconfiguration Time:
  • The proposed algorithm achieves the shortest estimated reconfiguration time for $N \ge 2000$.
  • It captures 32%–35% more atoms than PSC for grid targets due to higher efficiency and fewer failed attempts.
• Parallelism:
  • The proposed algorithm moves 1.8 to 116 times more atoms in parallel per operation compared to PSC.
  • While individual atoms travel slightly longer distances (up to 2.75x), the massive parallelism drastically reduces the total time.
• Reliability:
  • Achieved a 100% success rate for arbitrary formation problems.
  • For grid formation, the fallback three-step strategy ensured 100% success, whereas PSC failed in up to 4% of cases for large $N$.
• Planning Overhead:
  • The planning time is $O(N \log N)$, which is negligible compared to the physical reconfiguration time for $N \le 10^6$.

5. Significance

This work represents a critical step toward large-scale, fault-tolerant neutral-atom quantum computers. By reducing the reconfiguration time from linear to square-root complexity, the algorithm minimizes atom loss during the setup phase, which is currently a major bottleneck. The ability to guarantee defect-free arrays for arbitrary geometries using simple, hardware-friendly operations makes the approach highly practical for near-term experimental implementation. The open-source code provided allows for immediate integration into existing neutral-atom experimental platforms.