1. Bibliographic Information

1.1. Title

BOSS: Blocking algorithm for optimizing shuttling scheduling in Ion Trap

1.2. Authors

• Xian Wu$^{\dag 1}$

• Chenghong Zhu$^{\dag 1}$

• Jingbo Wang**

• Xin Wang†*

  Affiliations:

• †The Hong Kong University of Science and Technology (Guangzhou)

• ‡Beijing Academy of Quantum Information Sciences

• wangjb@baqis.ac.cn

• felixxinwang@hkust-gz.edu.cn

1.3. Journal/Conference

This paper was published as a preprint on arXiv. The abstract indicates it was published on 2024-12-04T16:31:17.000Z. arXiv is a widely respected open-access repository for preprints of scientific papers in various fields, including physics, mathematics, computer science, quantitative biology, quantitative finance, statistics, electrical engineering and systems science, and economics. It serves as a crucial platform for rapid dissemination of research findings before formal peer review and publication in academic journals or conference proceedings.

1.4. Publication Year

2024 (as indicated by the Published at (UTC) timestamp: 2024-12-04T16:31:17.000Z).

1.5. Abstract

Ion traps are a leading technology for quantum hardware, offering benefits like high-fidelity gates, extensive connectivity, and long coherence times. A critical challenge in these systems is the impact of shuttling operations on fidelity loss and execution times. To address this, the authors developed BOSS, an efficient blocking algorithm designed to enhance shuttling efficiency. This optimization not only improves the shuttling process but also boosts the overall effectiveness of ion trap devices. The algorithm was tested on multiple applications using up to 4000+ two-qubit gates and qubits ranging from 64 to 78. BOSS significantly reduces the number of shuttles in most applications, achieving a maximum reduction of 96.1%. The research also includes simulations with realistic experimental parameters, incorporating sympathetic cooling, which provides higher fidelity and more accurate execution time estimates reflective of practical scenarios.

1.6. Original Source Link

Official source: https://arxiv.org/abs/2412.03443v1 PDF link: https://arxiv.org/pdf/2412.03443v1.pdf This paper is currently a preprint on arXiv.

2. Executive Summary

2.1. Background & Motivation

The field of quantum computing holds immense promise for revolutionizing computational capabilities, with trapped-ion technology emerging as a particularly strong candidate due to its high qubit control, long coherence times, and all-to-all connectivity. However, trapped-ion systems face significant scalability challenges. As the number of ions (qubits) increases, the phonon modes (quantized vibrational modes) become densely packed, leading to a decline in two-qubit gate fidelity. Furthermore, individual ion addressing with lasers becomes complex and costly for larger systems, impacting scalability.

To overcome these laser-based control limitations, researchers have explored ion shuttling, where qubits are physically moved via microelectrodes to fixed laser interaction zones. This shuttling approach streamlines qubit manipulation, reduces hardware costs, and stabilizes the number of required lasers and optical components. However, shuttling operations introduce new challenges: fidelity loss due to heating effects during ion movement and elongated execution times because gates can only be applied when ions are within the execution zone. Previous methods for shuttling optimization often lead to an excessive number of shuttling operations or are computationally expensive for large circuits. The core problem this paper aims to solve is to develop an efficient compilation method for linear-tape trapped-ion quantum hardware platforms (like TILT) that effectively balances fidelity improvement from segmentation and hardware cost reduction with the need to minimize fidelity loss and execution time due to ion movement.

2.2. Main Contributions / Findings

The paper introduces BOSS, an innovative blocking algorithm designed to optimize shuttling scheduling in ion trap quantum computers, particularly for TILT architectures. Its primary contributions and findings are:

• Innovative Blocking Algorithm: BOSS segments quantum circuits into smaller blocks, strategically scheduling these blocks to optimize the number of shuttling operations. This approach allows for increased parallelism by executing more gates simultaneously within an execution zone, thereby reducing qubit vacancy rates and the overall number of shuttles.

• Realistic Performance Evaluation: The algorithm's performance is evaluated by estimating execution time and fidelity using parameters from modern ion trap systems, including sympathetic cooling mechanisms and diverse gate implementation times (e.g., amplitude-modulated (AM) and phase-modulated (PM) gates). This provides a more refined estimate that aligns closely with practical experimental scenarios.

• Significant Reduction in Shuttles: Compared to existing methods, BOSS significantly reduces the number of shuttles across most applications, achieving a maximum reduction of 96.1% and an average improvement of 16.6%. This directly translates to higher circuit fidelity by mitigating errors associated with ion movement.

• Substantial Improvement in Execution Time: The algorithm demonstrates considerable progress in execution time, with a maximum reduction of 179.6 times and an average improvement of 61.5 times. This is attributed to the reduced qubit idle rate and enhanced concurrent execution efficiency.

• Enhanced Scalability: BOSS exhibits superior scalability with a time complexity of $O(ng)$ (where $n$ is the number of qubits and $g$ is the number of gates), which is significantly faster than previous methods ($O(ng^2)$). This allows for rapid circuit compilation even for larger and more intricate circuits, demonstrating its potential for future large-scale quantum computers.

  The key findings are that BOSS effectively addresses the shuttling bottleneck in ion trap systems, leading to more efficient, higher-fidelity, and faster quantum computations, especially crucial for the NISQ (Noisy Intermediate-Scale Quantum) era and the path towards fault-tolerant quantum computing (FTQC).

3. Prerequisite Knowledge & Related Work

3.1. Foundational Concepts

To understand this paper, a basic grasp of quantum computing principles and the specifics of ion trap quantum hardware is essential.

• Qubit (Quantum Bit):

  • Conceptual Definition: A qubit is the fundamental unit of quantum information. Unlike a classical bit, which can only be in a state of 0 or 1, a qubit can exist in a superposition of both 0 and 1 simultaneously.
  • Explanation: This superposition allows quantum computers to process information in fundamentally different ways than classical computers. The state of a single qubit is represented as a linear combination of two orthogonal basis states, $|0\rangle$ and $|1\rangle$.
  • Mathematical Representation: For a single qubit: $|\psi\rangle = \alpha|0\rangle + \beta|1\rangle$, where $\alpha$ and $\beta$ are complex amplitudes, and $|\alpha|^2 + |\beta|^2 = 1$ ensures normalization (the probabilities of measuring 0 or 1 sum to 1). For an $n$-qubit system, there are $2^n$ possible computational basis states, and the state can be written as $|\psi\rangle = \sum_{i=0}^{2^n-1} \alpha_i|i\rangle$, with $\sum_{i=0}^{2^n-1} |\alpha_i|^2 = 1$.

• Quantum Operations (Quantum Gates):

  • Conceptual Definition: Quantum gates are unitary transformations that manipulate the states of qubits. They are the building blocks of quantum circuits and are analogous to logic gates in classical computing.
  • Explanation: Quantum gates can be single-qubit or multi-qubit. Single-qubit gates rotate the qubit's state on the Bloch sphere. Two-qubit gates, like the Controlled-NOT (CNOT) or Mølmer-Sørensen (MS) gate, can entangle qubits, which is crucial for quantum algorithms.
  • Examples from Paper:
    • Single-qubit rotation gates: $R_a(\theta) = e^{-i\theta\sigma_a/2}$, where $a \in \{x, y, z\}$ and $\sigma_a$ are Pauli matrices: $ \sigma_x = \begin{pmatrix} 0 & 1 \ 1 & 0 \end{pmatrix}, \quad \sigma_y = \begin{pmatrix} 0 & -i \ i & 0 \end{pmatrix}, \quad \sigma_z = \begin{pmatrix} 1 & 0 \ 0 & -1 \end{pmatrix}. $ The paper also mentions a general single-qubit gate in trapped-ion computing: $ R(\theta, \phi) = \begin{pmatrix} \cos(\theta/2) & i e^{i\phi} \sin(\theta/2) \ i e^{-i\phi} \sin(\theta/2) & \cos(\theta/2) \end{pmatrix}. $ Here, $\theta$ is controlled by pulse time, and $\phi$ by the relative phase of the laser.
    • Two-qubit Mølmer-Sørensen (MS) gate: $ U_{MS}(\theta_{ij}) = \begin{pmatrix} \cos(\frac{\theta_{ij}}{2}) & 0 & 0 & i \sin(\frac{\theta_{ij}}{2}) \ 0 & \cos(\frac{\theta_{ij}}{2}) & i \sin(\frac{\theta_{ij}}{2}) & 0 \ 0 & i \sin(\frac{\theta_{ij}}{2}) & \cos(\frac{\theta_{ij}}{2}) & 0 \ i \sin(\frac{\theta_{ij}}{2}) & 0 & 0 & \cos(\frac{\theta_{ij}}{2}) \end{pmatrix}. $ Here, (i, j) represents the two ion indexes involved in the gate, and $\theta_{ij}$ is the entanglement angle between them.

• Dependency Graph (Directed Acyclic Graph - DAG):

  • Conceptual Definition: A dependency graph is a graphical representation of quantum circuits where each gate is a node and directed edges indicate the order in which gates must be executed.
  • Explanation: An edge from gate $g_i$ to $g_j$ means $g_j$ cannot start until $g_i$ is complete. This helps identify parallelizable operations and the critical path (longest path), which determines the minimum execution time (depth) of the circuit. Its time complexity for construction is $O(g)$, where $g$ is the number of gates.

• Trapped-Ion Quantum Computer:

  • Conceptual Definition: A type of quantum computer that uses ions (charged atoms) trapped by electromagnetic fields as qubits. Lasers manipulate the internal states of these ions to perform quantum operations.
  • Explanation: Ions are typically cooled to near absolute zero to minimize thermal motion. Their internal electronic states define the $|0\rangle$ and $|1\rangle$ qubit states. Lasers are used for cooling, state preparation, gate operations, and measurement. The phonons (quantized vibrations) of the ion chain can be used to mediate interactions (entanglement) between ions, enabling two-qubit gates.

• AOM (Acousto-Optic Modulator) / AOD (Acousto-Optic Deflector):

  • Conceptual Definition: Optical devices used to control laser beams. AOMs modulate the intensity or frequency, while AODs can steer laser beams to different spatial positions.
  • Explanation: In trapped-ion systems, AOMs/AODs are crucial for individually addressing specific ions within a chain, allowing quantum gates to be applied to selected qubits without affecting others. However, their angular range and cost can limit scalability.

• TILT (Trapped-Ion Linear-Tape) Architecture:

  • Conceptual Definition: A scalable trapped-ion architecture where the entire chain of ions (qubits) is physically shuttled back and forth past fixed laser beams. Gates are applied only to ions positioned within a designated execution zone (also referred to as AOM zone or control region).
  • Explanation: Instead of steering lasers to ions, ions are moved to laser beams. This simplifies optics and calibration, reducing hardware complexity and cost. It offers advantages in scalability over traditional QCCD (Quantum Charge Coupled Device) architectures in some aspects, such as simultaneous gate application. Figure 1 provides an overview of TILT.

• Shuttling:

  • Conceptual Definition: The controlled physical movement of ions within an ion trap using microelectrodes to change electric potentials.

  • Explanation: Shuttling allows ions to be brought into or out of laser interaction zones, or to be rearranged for specific gate operations. While shuttling preserves the qubit's internal state, it can introduce heating, leading to fidelity loss and requiring re-cooling. The speed and distance of shuttling impact fidelity.

    The following figure (Figure 1 from the original paper) shows the system architecture:

    该图像是一个示意图，展示了线性陷阱离子量子计算机的结构。在AOM区内，量子位是完全连接的，但在执行AOM区外的量子操作时，需要通过移动离子来实现。图中展示了执行区、激光和线性带移动的功能。

3.2. Previous Works

The paper frames its contribution in the context of existing challenges and solutions in trapped-ion quantum computing. The main previous works discussed are:

• Initial TILT Formalization and Compilation (Wu et al., 2021 [77]):

  • Description: This work formalized the TILT architecture and proposed a compiling algorithm aimed at maximizing fidelity by reducing SWAP gates. Their core idea was to insert SWAP gates to ensure that qubits involved in a two-qubit gate are sufficiently close (within the maximum length of an execution zone). If the distance was too large, a heuristic function determined where to insert SWAP gates to reduce the distance. Subsequently, the tape (ion chain) would be scheduled heuristically.
  • Critique by current paper: The current paper identifies several drawbacks:
    1. Time-consuming: Their heuristic function needs to calculate all remaining gates to identify suitable SWAP insertion locations, which becomes computationally expensive as the number of gates increases.
    2. Excessive Shuttles: This method does not explicitly aim to lower the shuttle count, potentially leading to more shuttling operations and greater fidelity loss.
    3. Local Optimization: It focuses on individual gates and ignores the overall circuit information, potentially missing opportunities for global optimization.
    4. Inefficient Execution Zone Utilization: It only reduces the distance between two-qubit gates but does not fully leverage the capacity of the execution zone to perform multiple gates concurrently.

• ILP-based Scheduling for TILT (Wu et al., 2019 [78]):

  • Description: This work proposed an Integer Linear Programming (ILP) approach to obtain optimal solutions for ion movement and quantum gate scheduling in the TILT architecture. ILP methods are known for finding provably optimal solutions.
  • Critique by current paper: The ILP method becomes impractical as the number of qubits and gates increases due to its high computational cost. The paper notes that the worst-case shuttle number can be exponential to the qubit number, making ILP prohibitively slow for larger systems.

• General Compilers (Qiskit [2], tket [67]):

  • Description: These are general-purpose quantum compilers designed to translate quantum algorithms into executable quantum circuits for various quantum hardware platforms.
  • Critique by current paper: While capable of compiling for ion trap devices, their general nature means they are not tailored to the unique characteristics and constraints of specific ion trap system configurations (like TILT). This can lead to sub-optimal results compared to device-specific compilation strategies.

• QCCD (Quantum Charge Coupled Device) Architecture:

  • Description: Another promising trapped-ion architecture that uses multiple segmented traps interconnected to form a larger quantum computer. Ions can be moved between segments and traps to facilitate gate operations.
  • Relation to TILT: The paper states that QCCD will require more intricate junction shuttle and trap designs as it scales. It notes that scheduling within each QCCD trap resembles that of TILT, suggesting TILT strategies can inform QCCD scaling. Some works (e.g., [49], [61], [74]) focus on QCCD using heuristic functions.

3.3. Technological Evolution

The evolution of trapped-ion quantum computing has been driven by the dual goals of increasing gate fidelity and enhancing scalability.

1. Early Systems (Single Traps): Initially, research focused on small numbers of ions in single traps, demonstrating fundamental quantum operations and entanglement. These systems achieved very high gate fidelities but faced severe scalability limitations. The long-range Coulomb interactions among ions cause the phonon modes (shared vibrational modes) to become more complex with more ions, degrading two-qubit gate fidelity and making individual ion addressing difficult.

2. Laser Control (AOMs/AODs): To manipulate individual ions, sophisticated laser control mechanisms like AOMs and AODs were developed. While effective for smaller systems, scaling these components (e.g., ensuring two distinct laser beam paths per qubit) leads to increased volume, cost, and engineering challenges.

3. Segmented Traps (QCCD, TILT): To overcome laser-addressing and phonon-mode scalability issues, the concept of moving ions (shuttling) was introduced.

   • QCCD architectures (proposed in 2002 [37]) divide the ion trap into multiple segments or modules, allowing ions to be moved between processing zones and storage zones. This enables localized gate operations and modular scaling.
   • TILT architectures (formalized in 2021 [77]) represent a simplification where the entire ion chain is moved past fixed laser interaction zones. This reduces the complexity of trap design and optics compared to QCCD while still enabling shuttling.

4. Compilation for Movement-based Architectures: With the introduction of ion movement, quantum compilation shifted from purely logical qubit mapping to physical ion scheduling. The challenge became how to efficiently orchestrate ion shuttling and gate execution to minimize errors and execution time. This led to heuristic (e.g., [77]) and ILP-based (e.g., [78]) approaches.

   This paper's work fits into the current stage of optimizing compilation techniques for TILT and similar movement-based trapped-ion architectures. It aims to provide practical implementation strategies for near-term ion trap devices by addressing the immediate scalability and efficiency challenges posed by shuttling. It acknowledges the promise of QCCD for long-term scalability but focuses on TILT as a more practical near-term solution.

3.4. Differentiation Analysis

Compared to the main methods in related work, particularly the TILT compilation approach by Wu et al. [77], BOSS introduces several core differences and innovations:

• Focus on Blocking vs. Individual Gate Optimization:

  • Previous Work [77]: Primarily focuses on individual two-qubit gates. It inserts SWAP gates to reduce the distance between qubits involved in a gate if they are outside the AOM zone's connectivity limit. The tape movement is then scheduled to enable these gates. This approach looks at gates one at a time.
  • BOSS: Employs an innovative blocking algorithm (TILT Blocking) that groups multiple executable gates into larger blocks. The goal is to maximize gate parallelism within an execution zone (defined by AOM size), thereby executing more gates between shuttling operations. This shifts the optimization from single gate distance reduction to maximizing the utilization of the entire execution zone.

• Mechanism for Reducing Shuttles:

  • Previous Work [77]: While SWAP gates are inserted to enable gates, the reduction of shuttles is a secondary outcome of the tape scheduling heuristic. The paper notes that their method did not aim to lower the shuttle count, which could lead to greater fidelity loss.
  • BOSS: Directly aims to reduce the number of shuttles as a primary objective. By creating blocks that fully utilize the execution zone, it reduces the vacancy rate of qubits and, consequently, the frequency of shuttling operations required to bring new sets of qubits into the zone. The block scheduling algorithm further optimizes shuttle movements based on these blocks.

• Computational Complexity and Scalability:

  • Previous Work [77]: Has a worst-case time complexity of $O(ng^2)$ for SWAP gate insertion, where $n$ is the number of qubits and $g$ is the number of two-qubit gates. This makes it time-consuming for larger circuits.
  • BOSS: Achieves a significantly lower time complexity of $O(ng)$. This computational efficiency allows BOSS to compile much larger and more complex quantum circuits rapidly, demonstrating superior scalability.

• Fidelity and Execution Time Estimation:

  • Previous Work [77]: Focused on fidelity by reducing SWAP gates but perhaps with less comprehensive modeling of experimental parameters.
  • BOSS: Incorporates more realistic experimental parameters, including sympathetic cooling times and various two-qubit gate implementation times (e.g., AM and PM gates). This leads to a more accurate fidelity estimation and execution time prediction that better reflects practical ion trap systems.

• Exploitation of Ion Trap Connectivity:

  • Previous Work [77]: Primarily focuses on making qubits adjacent or within a certain distance for a gate.

  • BOSS: Better utilizes the inherent full connectivity of ion trap systems within the execution zone. By creating blocks that gather as many gates as possible whose qubits fit within the execution zone size, it maximizes the concurrent execution capability of the hardware.

    In summary, BOSS differentiates itself by moving from a localized, gate-by-gate optimization strategy to a more global, block-based approach that maximizes execution zone utilization, directly targets shuttle reduction, offers superior scalability, and provides a more realistic performance assessment through comprehensive experimental parameter modeling.

4. Methodology

The BOSS algorithm aims to optimize shuttling scheduling in Trapped-Ion Linear-Tape (TILT) architectures by employing a blocking strategy. This section details the principles, the baseline algorithm it improves upon, and the core BOSS algorithm itself, including its blocking and scheduling components, and a discussion of its time complexity.

4.1. Principles

The core principle behind BOSS is to maximize gate parallelism and minimize shuttling operations by intelligently grouping quantum gates into blocks that can be executed concurrently within the execution zone of a TILT device.

In TILT systems, quantum operations can only be performed when ions are within a specific laser interaction region, known as the execution zone (or AOM zone). This execution zone has a maximum size (e.g., 16 or 32 qubits), and all qubits within it are considered fully connected, meaning any two-qubit gate between them can be executed. Shuttling is required to bring qubits into this zone or rearrange them. Each shuttle operation introduces fidelity loss due to heating effects and adds to the execution time.

The intuition is that if more gates can be executed within a single execution zone configuration before shuttling is required, the overall number of shuttles will decrease. This implies reducing the vacancy rate—the percentage of qubits in the execution zone not involved in any gate operations. BOSS addresses this by:

1. Circuit Blocking: Dividing the quantum circuit into blocks of gates. Each block contains gates whose qubits can collectively fit and be operated upon within an execution zone.

2. Block Scheduling: Efficiently scheduling the movement of ions (and SWAP gates if necessary) between blocks to bring the required qubits for the next block into the execution zone with a minimal number of shuttles.

   This block-centric approach leverages the full connectivity within the execution zone, allowing for more parallel operations and fewer disruptive shuttling events.

4.2. Core Methodology In-depth

4.2.1. Baseline Algorithm

The paper first introduces a simple baseline algorithm for comparison. This baseline represents a TILT adaptation of heuristic approaches typically used in superconducting quantum systems, where the primary goal is to make gates executable by inserting SWAP gates and moving the tape.

Algorithm 1: Baseline Scheduling

$$1 Input C 2 G = { } 3 Get initial map π and initial execution zone Z 4 while 1 do 5 g = get_next_gate(C) 6 if g is executable then 7 G = G ∪ g 8 update C 9 else if g.q1 or g.q2 is in Z do 10 swap = FindProperSwap() 11 update mapping π 12 G = G ∪ swap 13 else do 14 tape_move = FindProperTapeMovement() 15 update execution zone Z 16 G = G ∪ tape_move 17 end if 18 end while 19 return G$$

Explanation of Algorithm 1:

• Line 1: Input C: The algorithm takes a quantum circuit $C$ as input.

• Line 2: $G = { }$: An empty set $G$ is initialized to store the compiled sequence of gates, SWAP operations, and tape movements.

• Line 3: $Get initial map π and initial execution zone Z$: An initial mapping $π$ of logical qubits to physical ions and the current execution zone $Z$ (the segment of ions under laser control) are established.

• Line 4: while 1 do: The algorithm enters an infinite loop, processing gates until the circuit is fully compiled.

• Line 5: g = get_next_gate(C): It attempts to retrieve the next gate $g$ from the circuit $C$ that is ready for execution (e.g., its dependencies are met).

• Line 6: if g is executable then: Checks if gate $g$ can be executed in the current execution zone $Z$ with the current qubit mapping $π$. A gate is executable if its target qubits are within $Z$ and all its dependencies have been resolved.

• Line 7: $G = G ∪ g$: If $g$ is executable, it is added to the compiled sequence $G$.

• Line 8: update C: The circuit $C$ is updated to reflect the execution of $g$ (e.g., marking $g$ as done, potentially making other gates ready).

• Line 9: else if g.q1 or g.q2 is in Z do: If $g$ is not directly executable (e.g., its qubits are not adjacent or too far apart within $Z$ for the specific gate type), but at least one of its qubits ($q_1$ or $q_2$) is currently within the execution zone $Z$.

• Line 10: $swap = FindProperSwap()$: A heuristic function is called to determine and insert a suitable SWAP gate. A SWAP gate exchanges the positions of two qubits to bring the target qubits of $g$ closer or into an executable configuration.

• Line 11: $update mapping π$: The qubit mapping $π$ is updated to reflect the SWAP operation.

• Line 12: $G = G ∪ swap$: The SWAP gate is added to the compiled sequence $G$.

• Line 13: else do: If $g$ is not executable and neither of its qubits are in $Z$ (meaning the execution zone needs to be moved entirely).

• Line 14: tape_move = FindProperTapeMovement(): A heuristic function is called to determine the optimal tape movement (shuttle) to reposition the execution zone $Z$ to include the qubits required by $g$.

• Line 15: update execution zone Z: The execution zone $Z$ is updated to its new position.

• Line 16: G = G ∪ tape_move: The tape movement instruction is added to the compiled sequence $G$.

• Line 17-18: end if, end while: The if-else block ends, and the loop continues until the circuit is complete.

• Line 19: return G: The fully compiled sequence $G$ is returned.

  The paper notes that this baseline might not perform well because it doesn't fully exploit the TILT architecture's features, particularly its full connectivity within the execution zone and the need to minimize shuttle counts over gate counts.

4.2.2. Detailed Algorithm (BOSS)

BOSS introduces a blocking algorithm (TILT Blocking) and a corresponding scheduling algorithm (TILT Block Scheduling) to overcome the limitations of the baseline.

4.2.2.1. TILT Blocking

This algorithm aims to partition executable circuits into blocks. The main idea is to group gates based on their active qubits (the qubits they operate on). Two groups of qubits are combined if a two-qubit gate involves qubits from both groups, and the resulting combined group of qubit indexes does not exceed the maximal block size $Z$ (which corresponds to the AOM size).

The following figure (Figure 3 from the original paper) shows an example of circuit blocking:

Algorithm 2: TILT Blocking

1 Input circuit C, maximal block size Z
2 Get the dependency graph G of circuit C
3 Initialize block list B = { }
4 Initialize waiting list w = { }
5 Initialize Group list G
6 while G.frontier is not empty do
7   Get a gate g from G.frontier
8   if g is single qubit gate do
9     G(g.idx) = G(g.idx) ∪ g
10  else
11    Union_set = G(g.idx1) ∪ G(g.idx2) ∪ g
12    if Union_set has no more than Z indexes do
13      G(g.idx1) = G(g.idx2) = Union_set
14    else
15      w.append(g)
16    end if
17  end if
18  if G.frontier is empty do
19    Pick a group p from G which has most indexes
20    for q ∈ G do
21      if q.idx == p.idx, clear q
22    end for
23    B.append(p)
24    G.frontier = G.frontier ∪ w
25    clear w
26  end if
27 end while
28 for p ∈ G do
29   B.append(p)
30 end for
31 return B

Explanation of Algorithm 2:

• Line 1: Input circuit C, maximal block size Z: The quantum circuit $C$ and the maximum number of qubits that can be in an execution zone $Z$ (e.g., AOM size) are inputs.

• Line 2: Get the dependency graph G of circuit C: A dependency graph $G$ is constructed for $C$ to track gate dependencies and identify executable gates.

• Line 3: $Initialize block list B = { }$: An empty list $B$ is created to store the final blocks of gates.

• Line 4: $Initialize waiting list w = { }$: A waiting list $w$ is initialized to temporarily hold gates that cannot be immediately added to a current block because their qubits would exceed the maximal block size.

• Line 5: Initialize Group list G: A Group list $G$ is initialized. This Group list is conceptually a collection of qubit sets (or groups) where each qubit belongs to a group, and gates are added to these groups. It acts like a union-find data structure, where G(idx) refers to the set of qubits currently associated with qubit idx.

• Line 6: while G.frontier is not empty do: The main loop continues as long as there are gates in the frontier of the dependency graph $G$ (i.e., gates that are ready to be considered for blocking).

• Line 7: Get a gate g from G.frontier: An executable gate $g$ is selected from the frontier. The paper specifies using a First-In-First-Out (FIFO) selection strategy here, which helps in grouping gates at similar depths and reducing the number of partitioned blocks.

• Line 8: if g is single qubit gate do: If $g$ is a single-qubit gate.

• Line 9: $G(g.idx) = G(g.idx) ∪ g$: The single-qubit gate $g$ is added to the group associated with its qubit g.idx.

• Line 10: else: If $g$ is a two-qubit gate.

• Line 11: Union_set = G(g.idx1) ∪ G(g.idx2) ∪ g: A potential union set Union_set is formed by combining the qubit groups of the two qubits g.idx1 and g.idx2 involved in $g$, along with $g$ itself. This Union_set represents the set of all qubits that would be involved if $g$ were added to the current block involving g.idx1 and g.idx2.

• Line 12: if Union_set has no more than Z indexes do: Checks if the number of distinct qubits in Union_set (i.e., the size of the combined qubit group) is less than or equal to the maximal block size $Z$.

• Line 13: G(g.idx1) = G(g.idx2) = Union_set: If the Union_set fits within $Z$, the qubit groups for g.idx1 and g.idx2 are united to form this new Union_set. This means these qubits are now considered part of the same block.

• Line 14: else: If Union_set exceeds $Z$.

• Line 15: w.append(g): The gate $g$ cannot be added to the current block and is placed in the waiting list $w$ for later consideration.

• Line 16-17: end if, end if: The conditional blocks end.

• Line 18: if G.frontier is empty do: If all gates in the current dependency graph frontier have been processed (either added to groups or to the waiting list).

• Line 19: Pick a group p from G which has most indexes: A group $p$ from the Group list $G$ (representing a collection of qubits and gates that form a potential block) is selected. The heuristic is to pick the group with the most qubit indexes, aiming to maximize block utilization.

• Line 20: for q ∈ G do: Iterates through all qubit groups $q$ in $G$.

• Line 21: $if q.idx == p.idx, clear q$: If a qubit group $q$ is the same as the selected group $p$, it is cleared from $G$. This signifies that $p$ is now being finalized as a block.

• Line 22-23: end for, B.append(p): The group $p$ is added to the final block list $B$.

• Line 24: $G.frontier = G.frontier ∪ w$: The waiting list $w$ is added to the dependency graph frontier G.frontier, making these previously deferred gates available for the next iteration of blocking.

• Line 25: clear w: The waiting list $w$ is cleared.

• Line 26-27: end if, end while: The conditional and main loop end.

• Line 28: for p ∈ G do: After the main loop, any remaining qubit groups in $G$ (which might contain single-qubit gates or small two-qubit gates that didn't form large blocks) are processed.

• Line 29: B.append(p): Each remaining group $p$ is added to the block list $B$.

• Line 30: end for: The loop ends.

• Line 31: return B: The final list of blocks $B$ is returned.

  The authors state that this method's key novelty is an efficient union-find like approach (though not explicitly named union-find in the pseudocode) that avoids computing minimum cuts, which significantly reduces computational complexity while lowering qubit vacancy rates within blocks.

4.2.2.2. TILT Block Scheduling

After circuit blocking, the next step is to schedule these blocks for execution. Since the qubits within a block might not be physically adjacent on the tape, or might not be in the execution zone, shuttle operations and SWAP gates are required. The proposed method aims to achieve this with limited shuttle movements.

The following figure (Figure 5 from the original paper) illustrates how to move selected qubits:

Algorithm 3: TILT Block Scheduling

$$1 Input block list B = {b0, b1, · . . , bL−1}, AOM size Z 2 Initialize tape T = [0, 1, · · · , n − 1] 3 Initialize execution head h 4 for bi ∈ B do 5 if ∀idx ∈ bi, idx ∈ [h, h + Z) do 6 execute bi 7 continue 8 end if 9 select the middle index mi of bi on the tape T 10 move the left half qubit of bi to the right of mi 11 move the right half qubit of bi to the left of mi 12 execute bi 13 end for$$

Explanation of Algorithm 3:

• Line 1: $Input block list B = {b0, b1, · . . , bL−1}, AOM size Z$: The algorithm takes the previously generated block list $B$ (containing $L$ blocks) and the AOM size $Z$ as input.

• Line 2: $Initialize tape T = [0, 1, · · · , n − 1]$: Represents the initial physical arrangement of $n$ qubits on the linear ion trap tape.

• Line 3: Initialize execution head h: $h$ denotes the starting index of the current execution zone on the tape T. The execution zone spans from $h$ to $h + Z - 1$.

• Line 4: for bi ∈ B do: The algorithm iterates through each block $b_i$ in the block list $B$.

• Line 5: $if ∀idx ∈ bi, idx ∈ [h, h + Z) do$: Checks if all qubits (idx) required by the current block $b_i$ are already within the current execution zone $[h, h + Z)$.

• Line 6: execute bi: If all qubits are in the execution zone, the block $b_i$ is executed.

• Line 7: continue: The loop proceeds to the next block without any shuttling.

• Line 8: end if: The conditional ends.

• Line 9: select the middle index mi of bi on the tape T: If shuttling is needed, the middle index $m_i$ of the qubits involved in block $b_i$ (on the current tape $T$) is identified. This serves as a target for grouping them.

• Line 10: move the left half qubit of bi to the right of mi: Ions on the left side of $m_i$ that are part of $b_i$ are shuttled to positions to the right of $m_i$, effectively consolidating them around $m_i$.

• Line 11: move the right half qubit of bi to the left of mi: Similarly, ions on the right side of $m_i$ that are part of $b_i$ are shuttled to positions to the left of $m_i$. This operation, potentially involving SWAP gates, brings all qubits of $b_i$ into a compact, contiguous region.

• Line 12: execute bi: Once the qubits of $b_i$ are spatially arranged to fit within an execution zone (centered or near $m_i$), the tape is shuttled so that $b_i$ can be executed.

• Line 13: end for: The loop ends.

  The paper states that for an AOM of size $m$, moving $k < m$ qubits a distance $d$ requires $\lceil d / (m-k) \rceil$ shuttles. The minimal shuttle count can be obtained by using $\lfloor k = m/2 \rfloor$. This scheduling technique moves qubits no more than $n$ distance overall and involves no more than $m/2$ ions per shuttle. Consequently, the shuttle count between each block is less than $2n/m$. The total number of SWAP gates introduced will not exceed $\lfloor m/2 \rfloor s$, where $s$ is the shuttle number.

4.2.2.3. Complexity Discussion

• Time Complexity of TILT Blocking: The blocking procedure (Algorithm 2) has a time complexity of $O(ng)$, where $n$ is the qubit count and $g$ is the gate number of the input circuit $C$.

• Time Complexity of TILT Block Scheduling: The scheduling procedure (Algorithm 3) has a time complexity that does not exceed $O(kmL) = O(nL)$, where $k$ is roughly $\lceil n/m \rceil$ (representing the number of segments the tape can be divided into, related to $n$ and $m$) and $L$ is the number of blocks. Since $L \le g/m$, the scheduling complexity can also be expressed in terms of $g$.

• Overall Time Complexity of BOSS: The overall time complexity of BOSS is $O(nL + ng)$, which simplifies to $O(ng)$ given $L \le g/m$.

• Comparison with Previous Work: The previous work [77] has a worst-case time complexity of $O(ng^2)$ for inserting SWAP gates. BOSS is significantly faster.

• NP-hard Problem: The paper acknowledges that qubit mapping and gate scheduling problems on quantum devices are generally NP-hard. Therefore, finding a workable, efficient solution like BOSS is prioritized over finding a theoretically optimal (but computationally infeasible) one.

  The following figure (Figure 4 from the original paper) provides another example of a block schedule:

  该图像是示意图，展示了在离子阱中执行的量子位的转移过程。图中显示了 $|q_0\rangle$, $|q_1\rangle$, $|q_2\rangle$ 等量子态的移动，强调了调度操作中对量子位的影响。每个盒子内的量子态在执行移动时的状态变化清晰可见。

5. Experimental Setup

5.1. Datasets

The authors used several significant quantum applications as benchmarks to assess the efficacy of the BOSS algorithm. These benchmarks were chosen to represent a diverse range of quantum computing contexts, from near-term superconducting device-suited circuits with nearest-neighbor gates to algorithms demonstrating quantum advantages. The focus of the evaluation was exclusively on two-qubit gates due to their higher error rates and longer runtimes compared to single-qubit gates. Single-qubit gates were excluded for consistency and comparison with prior work [77].

The following are the results from Table I of the original paper:

Description of Benchmarks:

• Adder: Based on the Cucarro adder [18], a 32-bit adder circuit [71]. It involves short-distance gates.

• BV (Bernstein-Vazirani): A common NISQ application used for benchmarking quantum devices, characterized by long-distance gates.

• QAOA (Quantum Approximate Optimization Algorithm): A hybrid iterative method for combinatorial optimization problems like max-cut [19] and the SK model [20], typically using nearest-neighbor gates.

• ALT (Alternating Layered Ansatz): Commonly used in variational quantum eigensolver (VQE) [19], also characterized by nearest-neighbor gates.

• RCS (Random Circuit Sampling): Proposed by Google to demonstrate quantum supremacy [25], involves nearest-neighbor gates.

• QFT (Quantum Fourier Transform): A key component of Shor's algorithm [64] and phase estimation algorithms [38], involving long-distance gates.

• SQRT (Square Root): An application from ScaffCC [33] that finds the square root number using Grover's search, typically involving long-distance gates.

  The experiments were conducted using AOM sizes of 16 and 32, on a Windows 11 system with AMD Ryzen 5 6600H CPU and 16-GB physical memory, using Python 3.9.

5.2. Evaluation Metrics

The effectiveness of the BOSS algorithm is evaluated using three primary metrics: shuttling number, execution time, and fidelity (represented as success rate). Each metric is calculated based on realistic ion trap system parameters.

5.2.1. Shuttling Number

• Conceptual Definition: This metric directly quantifies the total count of physical ion movement operations (shuttles) required to execute a quantum circuit. It directly correlates with fidelity loss and execution time due to the heating effects and overhead associated with each shuttle. A lower shuttling number indicates higher efficiency.
• Calculation: The shuttling number is a direct count of tape_move operations performed by the block scheduling algorithm (Algorithm 3, lines 10-11). For BOSS, the shuttle count between each block is bounded by less than $2n/m$, where $n$ is the number of qubits and $m$ is the AOM size.

5.2.2. Execution Time

• Conceptual Definition: The execution time measures the total duration required to complete the quantum circuit, accounting for gate execution times, shuttling durations, and essential ion trap operations like cooling and readout. This metric provides a practical estimate of how long a quantum algorithm would run on a real ion trap device.
• Mathematical Formula: $ t_{exec} = v_m \times dist + \sum_d t_d + t_1 + t_2 + t_3 $
• Symbol Explanation:
  • $t_{exec}$: Total execution time of the quantum circuit.
  • $v_m$: The shuttling speed, set to $1 \, \mu \mathrm{m}/\mu \mathrm{s}$ [10]. This is the speed at which ions are moved during shuttling operations.
  • dist: The total shuttle distance, which is the sum of all distances moved by ions during shuttling operations throughout the circuit execution.
  • $\sum_d t_d$: The sum of maximum gate times for each circuit depth $d$. This accounts for the actual time spent executing quantum gates. The paper considers various two-qubit gate implementation times:
    • Duan AM gate [79]: $\tau_{\mathrm{Duan}}(d) = 100d - 22$ (time in microseconds). $d$ here refers to the distance between ions for the gate.
    • Trout AM gate [73]: $\tau_{\mathrm{Trout}}(d) = 38d + 10$ (time in microseconds). This is a faster but less accurate AM gate.
    • PM gate [45]: $\tau_{\mathrm{PM}}(d) = 5d + 160$ (time in microseconds). This PM gate has a weaker dependence on distance but is slower for nearby qubits.
  • $t_1$: Initial cooling time for ion preparation. This includes Doppler cooling ($10 \, \mathrm{ms}$) and sideband cooling ($50 \, \mu \mathrm{s}$). $ t_1 = 10 , \mathrm{ms} + 50 , \mu \mathrm{s}. $
  • $t_2$: Mid-circuit cooling time after shuttling operations. This is necessary to mitigate heat-induced quantum noise. It is proportional to the number of shuttle operations. $ t_2 = 40 , \mu \mathrm{s} \times s_m. $ Here, $s_m$ is the total number of shuttle operations.
  • $t_3$: Readout time. This is the time required to extract quantum information from the ions at the end of the circuit. A typical readout time to achieve fidelity over 0.9999 is $150 \, \mu \mathrm{s}$. $ t_3 = 150 , \mu \mathrm{s}. $

5.2.3. Fidelity (Success Rate)

• Conceptual Definition: Fidelity quantifies how well the quantum circuit performs as intended, representing the probability of obtaining the correct output. It is crucial for assessing the reliability of quantum computations. The success rate is an overall measure that combines gate fidelity and shuttle fidelity.
• Mathematical Formula (for gate and shuttle fidelity):
  • Gate Fidelity (two-qubit gates only, as single-qubit gates are considered high fidelity and don't entangle with phonon modes): $ F_{gate} = 1 - \epsilon_{laser} N^2 $
    • Symbol Explanation:
      • $F_{gate}$: Fidelity of a single two-qubit gate.
      • $\epsilon_{laser}$: Precision coefficient of instrument manipulation, set to $1/256000$ in the simulation. This value ensures two-qubit gates achieve a fidelity of 99.9% in AOM 16 cases.
      • $N$: The number of ions (qubits) in the laser interaction region (execution zone). Fidelity decreases as $N$ increases due to entanglement with phonon modes.
  • Shuttle Fidelity: $ F_{\mathrm{shuttle}} = 1 - \epsilon_{\mathrm{shuttle}} m $
    • Symbol Explanation:
      • $F_{\mathrm{shuttle}}$: Fidelity loss due to shuttling.
      • $\epsilon_{\mathrm{shuttle}}$: The residual entanglement between ion and phonon during the shuttle operation, set to 0.001 in the simulation.
      • $m$: The number of shuttle operations performed. The fidelity decreases linearly with the number of shuttles.
• Overall Success Rate Formula: $ F = F_{gate}^g \times \prod_{m=1}^S (1 - \epsilon_{\mathrm{shuttle}} m) $
  • Symbol Explanation:
    • $F$: The overall success rate of the quantum circuit.
    • $F_{gate}$: The average fidelity of a single two-qubit gate (as defined above).
    • $g$: The total number of two-qubit gates in the circuit.
    • $\prod_{m=1}^S (1 - \epsilon_{\mathrm{shuttle}} m)$: The product representing the cumulative fidelity loss due to $S$ shuttle operations, where $m$ iterates from 1 to $S$ for each shuttle. This models the decreasing fidelity with each subsequent shuttle. Note that this formula implies that each subsequent shuttle incurs a fidelity loss dependent on its ordinal number, not a constant fidelity loss per shuttle. However, given the context of $F_{\mathrm{shuttle}} = 1 - \epsilon_{\mathrm{shuttle}} m$, it is more likely that $m$ here is the number of shuttles executed so far or $S$ is the total number of shuttles and the $\prod_{m=1}^S$ notation is a simplified way to represent the cumulative effect, but the $F_{\mathrm{shuttle}}$ formula itself is a function of a single $m$. For clarity, the typical interpretation of such a product would be $F = F_{gate}^g \times (1 - \epsilon_{\mathrm{shuttle}})^S$, assuming a constant per-shuttle error. However, adhering strictly to the provided formula, it suggests a more complex, escalating error accumulation with each shuttle.

5.3. Baselines

The BOSS algorithm is primarily compared against:

• Previous Work (Wu et al., 2021 [77]): This is the main comparative baseline. As described in Section 3.2, this method focuses on inserting SWAP gates to reduce qubit distances for individual two-qubit gates and then heuristically scheduling tape movements.
• Baseline (Algorithm 1): The paper also introduces a simpler baseline algorithm (Algorithm 1) which is a TILT adaptation of heuristic approaches used in superconducting quantum systems. This baseline prioritizes making individual gates executable by swapping or shuttling as needed. While providing a general comparison point, the previous work [77] serves as the more direct, state-of-the-art comparison for TILT architectures.

6. Results & Analysis

The experimental evaluation of BOSS focuses on shuttling number, execution time, fidelity (success rate), and scalability, demonstrating significant improvements over previous methods. The experiments were conducted on quantum applications using AOM sizes of 16 and 32.

6.1. Core Results Analysis

6.1.1. Shuttling Number

The shuttling number is a critical metric because each shuttle operation introduces fidelity loss and contributes to execution time. BOSS aims to minimize this.

The following figure (Figure 6 from the original paper) shows the number of shuttling operations:

该图像是一个条形图，展示了不同应用下的搬运操作数量，包括基线（蓝色）、之前的方法（深蓝色）和我们的算法（粉色）。图中显示，使用我们的算法在大部分应用中显著减少了搬运次数，最高可达96.1%的减少。

As shown in Figure 6, BOSS consistently reduces the number of shuttling operations across most benchmark applications compared to the baseline and the previous work [77]. The numerical details in Table II further highlight this improvement. For example, with an AOM size of 32, BOSS achieves a remarkable 96.1% reduction in shuttles for SQRT and an 88.4% reduction for QFT. The average improvement in shuttle number is 16.6%.

The improvement stems from BOSS's blocking strategy, which better utilizes the execution zone. By grouping multiple gates into blocks, BOSS ensures that no qubit within the execution zone remains idle, allowing more gates to be performed between consecutive shuttle operations. In contrast, the previous work [77] primarily focuses on reducing the distance for individual two-qubit gates and does not fully leverage the concurrent execution capability of the TILT device within the AOM zone.

An interesting observation is that BOSS performs worse than existing algorithms on RCS (Random Circuit Sampling). This is attributed to the inherent characteristics of RCS circuits, where the distance between qubits for all two-qubit gates often remains small (e.g., less than 15 for AOM 16) under trivial initial mappings. In such cases, the previous algorithm [77] does not need to insert many SWAP gates and primarily focuses on the shuttle schedule, giving it an advantage. BOSS might introduce more SWAP gates (e.g., 336 for QFT with AOM 16 compared to 120 for the previous method), but this difference is negligible when considering the overall number of gates and the significant reduction in shuttles.

6.1.2. Execution Time

The execution time is another crucial metric, directly impacting the practicality of quantum algorithms.

The following figure (Figure 7 from the original paper) shows a comparative analysis of the execution time with previous work [77] utilizing AM gate implementation [73]:

该图像是条形图，展示了在 AOM16 和 AOM32 条件下，不同应用（如 Adder、BV、QAOA 等）的评估时间对比。横轴为应用名称，纵轴为评估时间（秒），不同颜色的条形表示本研究和之前工作的结果。

Figure 7 and Table II demonstrate that BOSS achieves substantial progress in execution time. For AOM size 16, the SQRT application shows the highest performance improvement, with a 179.6 times reduction, and QFT shows a 56.3 times reduction. The average improvement across applications is 61.5 times. This improved execution time is primarily attributed to the reduced idle rate among qubits in the execution zone and the enhanced concurrent execution efficiency of two-qubit gates, along with optimized preprocessing time.

The paper also investigates the impact of different two-qubit gate implementation models.

The following figure (Figure 8 from the original paper) shows the evaluation times for AOM16 and AOM32 across different applications:

该图像是柱状图，展示了在不同应用下，AOM16和AOM32的评估时间（单位为秒）。图中分别以蓝色、紫色和粉红色表示三种不同算法的运行时间，数据显示在多个应用中算法表现的差异。

Figure 8 compares execution times for AM (amplitude-modulated) and PM (phase-modulated) gate implementations. For short-distance communication circuits (like Adder, QAOA, ALT), Trout AM gates [73] generally yield reduced execution times. Conversely, for long-distance communication circuits (e.g., QFT, SQRT), PM gates [45] offer superior performance due to their weaker reliance on qubit-qubit separation. The Trout AM gate implementation allows applications to potentially conclude within seconds, highlighting the viability of ion trap systems for comprehensive depth circuits given their long coherence times.

An interesting finding is that for some applications, AOM 32 might take longer to execute than AOM 16. This counter-intuitive result is explained by the fact that AOM 32 allows gates to act on farther qubits, which can sometimes lead to different scheduling choices that do not necessarily optimize for execution time in all cases. The authors note that optimizing execution time could be a future work direction.

6.1.3. Fidelity (Success Rate)

The fidelity or success rate is crucial for reliable quantum computation.

The following figure (Figure 9 from the original paper) shows the success rate comparison on different applications:

该图像是一个图表，展示了不同电路大小下各应用的编译时间。随着电路大小的增加，'SQRT'的编译时间显著增长，而'Adders'和'QAOA'却保持在较低水平。该图表清晰显示了编译时间与电路大小之间的关系。

Figure 9 illustrates the success rate comparison. BOSS achieves a significantly higher success rate than the previous work [77]. For instance, for QFT with AOM size 16, their success rate was less than $1 \times 10^{-14}$, whereas BOSS achieves over $4 \times 10^{-3}$. This improvement is attributed to BOSS's effective use of cooling processes and a more accurate gate fidelity model.

The paper's gate fidelity model ($F_{gate} = 1 - \epsilon_{laser} N^2$) assumes that gate fidelity decreases rapidly as the number of ions $N$ in the AOM zone increases, leading to an overall fidelity reduction as AOM size grows (observed in Figure 9, where AOM 16 often yields higher fidelity than AOM 32). This model is presented as more accurately reflecting real experimental conditions. The authors predict that as technology advances and gate fidelity does not drop as quickly with increasing AOM size, their fewer-shuttle approach will demonstrate even greater advantages.

6.1.4. Scalability

The scalability of a compilation method is essential for handling increasingly large quantum circuits.

The following figure (Figure 10 from the original paper) shows the compilation time varies with the size of the circuit:

该图像是图表，展示了不同应用程序的成功率。横坐标为应用程序名称，纵坐标为成功率，采用对数坐标轴。图中包含了理想条件下的成功率以及使用16和32 AOM的成功率对比。

Figure 10 demonstrates BOSS's superior scalability by showing compilation time as circuit size (number of qubits) increases. The results largely align with the theoretical time complexity of $O(ng)$. For Adder and QAOA circuits, which have a linear relationship between gates and qubits and predominantly nearest-neighbor gates, the compilation time increases linearly with circuit size. For QFT, where the number of gates increases quadratically with qubits, the compilation time also shows an approximately quadratic increase.

Despite these increases, BOSS exhibits exceptional performance. Compiling a QFT circuit with 180 qubits takes less than 1.2 seconds with BOSS. This is a stark contrast to the previous method [77], which required over 60 seconds to compile a QFT circuit with only 64 qubits. This highlights BOSS's efficiency and ability to handle complex quantum circuits as qubit counts grow, positioning it as a more viable solution for larger NISQ devices.

6.2. Data Presentation (Tables)

The following are the results from Table II of the original paper:

Table II Legend:

• $T_{pre}$: Compilation time of previous method [77] (in seconds).
• $T_{boss}$: Compilation time of BOSS method (in seconds).
• $S_{base}$: Shuttle number of baseline algorithm.
• $S_{pre}$: Shuttle number of previous method [77].
• $S_{boss}$: Shuttle number of BOSS method.
• $\Delta S := S_{pre} - S_{boss}$: Difference in shuttle numbers between previous method and BOSS.
• $\Delta S / S_{pre}$: Percentage reduction in shuttle numbers for BOSS compared to previous method.
• $t_{pre}$: Execution time of previous method [77] (using Trout model, in seconds).
• $t_{boss}$: Execution time of BOSS method (using Trout model, in seconds).
• $t_{pre} / t_{boss}$: Ratio of execution times (previous method / BOSS), indicating how many times faster BOSS is.

6.3. Ablation Studies / Parameter Analysis

The paper does not present explicit ablation studies breaking down the BOSS algorithm into its components. However, it implicitly performs a parameter analysis by evaluating its performance under different AOM sizes (16 and 32) and with different two-qubit gate implementation times (Trout AM and PM models).

• Impact of AOM Size: The results consistently show that a larger AOM size (32 vs. 16) generally leads to a reduction in shuttle numbers (e.g., QFT Sboss 48 for AOM 16 vs. 8 for AOM 32). This is intuitive as a larger AOM zone can accommodate more qubits, thus reducing the need for shuttling. However, a larger AOM size does not always translate to faster execution time or higher fidelity in all cases. As discussed, for some applications like QFT with AOM 32, execution time might be longer than AOM 16 due to the choice of gates acting on farther qubits. Moreover, the fidelity model suggests that gate fidelity decreases rapidly with an increasing number of ions in the AOM zone ($N^2$ dependency), which can lead to lower overall success rates for AOM 32 compared to AOM 16 for certain applications (e.g., QFT success rate with AOM 16 is higher than AOM 32 in Figure 9). This highlights a trade-off that BOSS navigates.

• Impact of Two-Qubit Gate Implementation Times: By comparing results using AM and PM gate models (Figure 8), the authors show that the optimal choice of gate type depends on the communication patterns of the circuit. Trout AM gates are better for short-distance gates, while PM gates are more beneficial for long-distance gates. This demonstrates the flexibility of BOSS to be integrated with various physical gate implementations and provides practical guidance for hardware designers.

• Impact of Cooling Mechanisms: The inclusion of sympathetic cooling in the execution time and fidelity estimation is a key aspect of BOSS's realistic evaluation. The midway cooling time ($t_2$) directly accounts for the heating effects of shuttling, and its inclusion leads to significantly higher success rates compared to previous work that did not model such detailed cooling processes. This emphasizes the importance of comprehensive noise modeling for accurate performance prediction.

7. Conclusion & Reflections

7.1. Conclusion Summary

This paper introduces BOSS, a novel blocking algorithm designed to optimize shuttling scheduling in Trapped-Ion Linear-Tape (TILT) quantum computing systems. By intelligently segmenting quantum circuits into blocks and efficiently scheduling their execution, BOSS significantly reduces the number of required shuttling operations—achieving up to a 96.1% reduction and an average of 16.6% across various applications. This reduction directly translates to improved circuit fidelity by mitigating errors associated with ion movement. Furthermore, BOSS drastically cuts down execution times, with a maximum speed-up of 179.6 times and an average of 61.5 times, primarily due to increased gate parallelism and better utilization of the execution zone. The algorithm's superior scalability ($O(ng)$ time complexity compared to $O(ng^2)$ for previous methods) enables it to handle larger and more complex quantum circuits efficiently. By incorporating realistic experimental parameters, including sympathetic cooling and diverse gate implementation times, BOSS offers a more accurate and practical assessment of ion trap system performance, paving the way for more effective quantum computations in the NISQ era and towards fault-tolerant quantum computing.

7.2. Limitations & Future Work

The authors acknowledge several limitations and propose future research directions:

• Greedy Approach: The current BOSS algorithm primarily relies on greedy methods for blocking and scheduling. While efficient, greedy algorithms do not guarantee global optimality.
• Incorporating Heuristic Functions: A potential future work direction is to integrate more sophisticated heuristic functions into the blocking and scheduling framework. This aligns with qubit mapping strategies in superconducting devices and, while potentially incurring additional time overhead, could yield improved solutions (e.g., further reducing shuttle numbers).
• Minimizing SWAP Gate Insertions: The authors observed that SWAP operations can decrease fidelity. Future efforts could be directed towards minimizing the use of insert SWAP gates, drawing inspiration from work on superconducting systems [29], [40], [80], [81].
• Optimizing Execution Time Explicitly: While BOSS significantly reduces execution time, the paper noted that AOM 32 sometimes resulted in longer execution times than AOM 16 because gates could act on farther qubits, suggesting that the current optimization might not always prioritize execution time directly. Explicitly optimizing for execution time in all scenarios could be a future goal.
• Linking Multiple TILT Architectures: The paper highlights that the realization of large-scale QCCD devices depends on linking several linear-tape trapped-ion architectures. Efficient compilation techniques like BOSS for TILT are fundamental components for this goal, implying future work in coordinating such linked systems.

7.3. Personal Insights & Critique

This paper presents a highly relevant and practical contribution to the field of trapped-ion quantum computing. The problem it tackles—efficiently managing ion shuttling—is a critical bottleneck for scaling these promising quantum hardware platforms.

Strengths:

• Practicality and Realism: The inclusion of sympathetic cooling, various gate implementation times, and realistic fidelity models makes the BOSS algorithm and its evaluation highly practical. This moves beyond theoretical idealizations and provides valuable guidance for experimentalists and hardware developers.
• Significant Performance Improvement: The reported reductions in shuttle numbers (up to 96.1%) and execution times (up to 179.6x) are substantial and directly address key challenges in ion trap scalability and fidelity.
• Scalability: The $O(ng)$ time complexity is a major advantage, making BOSS applicable to larger NISQ circuits where previous methods become computationally intractable. This is crucial for bridging the gap between small-scale demonstrations and practical quantum applications.
• Focus on Block Utilization: The core idea of blocking to maximize execution zone utilization is intuitive and effective. It leverages the full connectivity property within the AOM zone that is unique to ion trap systems, a feature often underutilized by compilers adapted from other quantum architectures.

Potential Issues/Areas for Improvement:

• Greedy Nature vs. Global Optimality: While the greedy approach is efficient and necessary for NP-hard problems, it might not always find the globally optimal solution. The paper itself acknowledges this, suggesting heuristics as future work. A more detailed exploration of the trade-offs between greedy efficiency and potential solution quality would be beneficial.
• SWAP Gate Overhead: Although the paper states that BOSS can introduce more SWAP gates than previous methods (e.g., for QFT), and that this difference is "negligible," the impact of these additional SWAP gates on fidelity (which can be significant) could be further quantified or minimized within the blocking or scheduling phases. The proposed Fidelity formula explicitly includes gate fidelity $F_{gate}^g$, so increasing $g$ (by adding SWAPs) would reduce overall fidelity, even if shuttles are reduced.
• Detailed Union-Find Implementation: The TILT Blocking algorithm (Algorithm 2) mentions a Group list G and an operation G(g.idx1) = G(g.idx2) = Union_set, which hints at a union-find like structure. Providing a more explicit description of how the Group list $G$ is implemented and how union operations are performed would enhance clarity for readers unfamiliar with custom union-find structures.
• Generalizability Beyond TILT: While BOSS is tailored for TILT, the underlying principles of blocking and efficient resource utilization could potentially be adapted to other segmented ion trap architectures like QCCD, especially for scheduling within individual traps. A discussion on its broader applicability could be insightful.
• Comparison to Other Blocking/Scheduling Algorithms: While comparing to [77] is crucial, a broader comparison with other gate scheduling or mapping algorithms (even those not specific to ion traps but that employ similar concepts of block execution or parallelism) might provide a richer context for its innovation.

Inspirations and Applications:

• The blocking strategy could inspire similar compiler optimizations for other quantum computing modalities facing connectivity or movement constraints, where maximizing concurrent operations within a localized processing unit is key.
• The rigorous fidelity and execution time modeling serves as an excellent template for future quantum compiler research, emphasizing the need to account for realistic hardware imperfections and operational overheads.
• BOSS offers concrete guidance for ion trap hardware designers, indicating the value of optimizing AOM size (balancing connectivity with fidelity loss due to $N$ ions) and the choice of two-qubit gate implementations based on circuit characteristics (short-distance vs. long-distance).
• The demonstration of scalability is a critical step towards enabling larger quantum algorithms to run on near-term ion trap devices, accelerating the path to demonstrating practical quantum advantage.