1. 论文基本信息

1.1. 标题

BOSS: Blocking algorithm for optimizing shuttling scheduling in Ion Trap

1.2. 作者

Xian Wu, Chenghong Zhu, Jingbo Wang, Xin Wang †The Hong Kong University of Science and Technology (Guangzhou) ‡Beijing Academy of Quantum Information Sciences

1.3. 发表期刊/会议

预印本 (Preprint) 形式发布在 arXiv。

1.4. 发表年份

2024年 (UTC: 2024-12-04T16:31:17.000Z)

1.5. 摘要

离子阱 (Ion Trap) 技术作为量子硬件的前沿，在量子计算领域展现出无与伦比的优势，例如高保真度门 (high-fidelity gates)、广泛的连接性 (extensive connectivity) 和更长的相干时间 (prolonged coherence times)。本文探讨了这些系统中穿梭操作 (shuttling operations) 的关键作用，特别是它们对保真度损失 (fidelity loss) 和执行时间延长 (elongated execution times) 的影响。为了应对这些挑战，我们开发了 BOSS (Blocking algorithm for optimizing shuttling scheduling in Ion Trap)，这是一种高效的阻塞算法 (blocking algorithm)，旨在提高穿梭效率。这种优化不仅增强了穿梭过程，还提升了离子阱设备的整体效能。我们使用多达 4000 多个双量子比特门 (two qubit gates) 和 64 到 78 个量子比特 (qubits) 的多个应用程序进行了实验。我们的方法在大多数应用程序上显著减少了穿梭次数，最大减少幅度达 96.1%。此外，我们的研究还包括了结合了同情冷却 (sympathetic cooling) 的真实实验参数模拟，提供了更高的保真度 (fidelity) 和更精确的执行时间估算，从而更贴近实际场景。

1.6. 原文链接

• 原文链接: https://arxiv.org/abs/2412.03443v1
• PDF 链接: https://arxiv.org/pdf/2412.03443v1.pdf

2. 整体概括

2.1. 研究背景与动机

量子计算是现代物理学和计算机科学中最令人兴奋的前沿领域之一，有望彻底改变我们的计算能力。在众多量子计算平台中，离子阱技术因其高量子比特控制度、长相干时间以及全连接能力而成为主要候选者。然而，离子阱系统在扩展性方面面临诸多挑战。

核心问题在于，随着量子比特数量的增加，长程库仑相互作用导致离子链中的声子 (phonons) 模式密度更高，这会显著降低双量子比特门 (two-qubit gates) 的保真度。此外，实现对单个离子的精确寻址也变得更具挑战性，从而难以达到容错量子计算所需的严格错误阈值。激光控制方法面临体积和成本问题，限制了扩展性。

为了应对这些挑战，研究人员转向了离子阱量子计算的一个关键特性：通过微电极在空间中移动量子比特 (shuttling operations)。这种方法催生了可扩展的设计，并允许在移动的量子比特上实现量子算法。线性离子阱中的分段操作允许量子比特的任意交换和移动，但这也带来了新的挑战：如何在保证保真度、降低硬件成本的同时，有效管理因离子移动引起的加热效应导致的保真度损失和编译时间增加。

本文试图解决的核心问题是：如何在离子阱线性带式 (TILT) 架构中，高效且迅速地编译通用量子电路或算法，以最小化穿梭操作带来的保真度损失和执行时间，从而实现离子阱设备的更大规模和更高性能。现有的方法 (例如 [77]) 往往在插入 SWAP 门时计算量大，且未能有效降低穿梭次数，也未充分利用离子阱设备在特定区域内量子比特全连接的潜力。因此，开发一种能有效管理穿梭操作、优化编译效率和执行性能的方法至关重要。

2.2. 核心贡献/主要发现

本文的主要贡献和关键发现总结如下：

• 引入创新阻塞算法 BOSS (Blocking algorithm for optimizing shuttling scheduling in Ion Trap)： 提出了一种创新的阻塞算法，将量子电路分解为更小的块 (blocks)，通过高效的策略调度来优化穿梭次数。这种方法减少了每个块中量子比特的空闲率，从而在相同执行区域内执行更多门，有效降低了穿梭需求。
• 综合性性能评估与真实参数模拟： 算法性能评估考虑了现代离子阱系统的实际实验参数，包括同情冷却 (sympathetic cooling) 和多样化的门实现时间。这使得对执行时间和保真度的估计更为精确，更贴近实际场景。
• 显著减少穿梭次数： 实验结果表明，与现有方法相比，BOSS 在大多数应用中显著减少了穿梭次数，最高可达 96.1% 的减少，平均改进为 16.6%。
• 大幅提升执行效率： 在执行时间方面取得了显著进展，最大减少了 179.6 倍，平均改进了 61.5 倍。这主要得益于执行区域内量子比特空闲率的降低，从而提高了双量子比特门的并发执行效率。
• 提高成功率： 结合冷却过程的优化利用，BOSS 算法比现有方法实现了更高的成功率。
• 卓越的扩展性： 算法的编译时间复杂度为 $O(ng)$ (其中 $n$ 是量子比特数，$g$ 是门数量)，即使对于大规模电路也能实现快速编译，例如，编译 180 量子比特的 QFT (Quantum Fourier Transform) 电路仅需不到 1.2 秒，远优于现有方法。

3. 预备知识与相关工作

本节旨在为读者提供理解本文所需的基本概念、理论基础，并概述相关的先前研究，以便更好地理解本文的创新点和技术演进。

3.1. 基础概念

3.1.1. 量子比特 (Qubit)

量子比特 (Qubit) 是量子计算中的基本信息单位。与经典比特只能处于 0 或 1 态不同，量子比特可以处于 0 态 ($|0\rangle$)、1 态 ($|1\rangle$) 或它们的任意叠加态 (superposition state)。对于一个单量子比特，其状态可以表示为 $| \psi \rangle = \alpha | 0 \rangle + \beta | 1 \rangle$，其中 $\alpha$ 和 $\beta$ 是复数振幅，满足 $| \alpha | ^ { 2 } + | \beta | ^ { 2 } = 1$。对于 $n$ 个量子比特的系统，它有 $2^n$ 个计算基态，其状态可以表示为 $| \psi \rangle = \sum _ { i } ^ { 2 ^ { n } - 1 } \alpha _ { i } | i \rangle$，其中 $\sum _ { i } ^ { 2 ^ { n } - 1 } | \alpha _ { i } | ^ { 2 } = 1$。

3.1.2. 量子门 (Quantum Operations)

量子门 (Quantum Operations) 是对量子比特进行操作的酉矩阵 (unitary matrices)，它们通过矩阵-向量乘法变换量子状态。

• 单量子比特门 (Single-Qubit Gates): 常见的单量子比特旋转门 (rotation gates) 表示为 $R _ { a } ( \theta ) = e ^ { - i \theta \sigma _ { a } { \bar { / } } 2 }$，其中 $a \in \{ x , y , z \}$。$\sigma_a$ 是泡利矩阵 (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} .$$ 在离子阱量子计算中，通过调整激光脉冲的持续时间和相对相位差，可以实现任意单量子比特操作 $R ( \theta , \phi )$： $$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}$$
• 双量子比特门 (Two-Qubit Gates): 实现双量子比特门需要使用独立寻址的激光器。
  • C-Z 门 (Controlled-Z gate): Cirac 和 Zoller [17] 提出，本质上是受控相位门。
  • Mølmer-Sørensen (MS) 门: Mølmer 和 Sørensen 提出，不需要严格冷却到离子基态。其矩阵形式如下： $$U _ { M S } ( \theta _ { i j } ) = \begin{pmatrix} { \cos ( \frac { \theta _ { i j } } { 2 } ) } & { { 0 } } & { { 0 } } & { { i \sin ( \frac { \theta _ { i j } } { 2 } ) } } \\ { { 0 } } & { { \cos ( \frac { \theta _ { i j } } { 2 } ) } } & { { i \sin ( \frac { \theta _ { i j } } { 2 } ) } } & { { 0 } } \\ { { 0 } } & { { i \sin ( \frac { \theta _ { i j } } { 2 } ) } } & { { \cos ( \frac { \theta _ { i j } } { 2 } ) } } & { { 0 } } \\ { { i \sin ( \frac { \theta _ { i j } } { 2 } ) } } & { { 0 } } & { { 0 } } & { \cos ( \frac { \theta _ { i j } } { 2 } ) } \end{pmatrix}$$ 其中 (i, j) 表示两个离子索引，$\theta_{ij}$ 表示两个离子之间的纠缠角 (entangle angle)。

3.1.3. 依赖图 (Dependency Graph)

为了描述量子电路中的依赖关系，使用有向无环图 (Directed Acyclic Graph, DAG)，即依赖图 (dependency graph)。电路中的每个门表示图中的一个节点，有向边表示依赖关系。例如，从门 $g_i$ 到 $g_j$ 的边意味着 $g_j$ 只能在 $g_i$ 执行后才能执行。该图有助于理解门之间的关系并方便将它们划分为块。在均匀时间槽假设下，依赖图中的最长路径提供了电路深度的下限。构建依赖图的时间复杂度为 $O(g)$，其中 $g$ 是输入门的数量。

3.1.4. 离子阱量子计算机 (Trapped-Ion Quantum Computer)

在离子阱量子计算中，利用离子的内部状态作为量子比特。通过激光束对离子进行冷却、操控和测量。离子的独特优势在于其内部状态在移动时不受影响，这为穿梭操作提供了基础。

3.1.5. TILT 架构 (Trapped-Ion Linear-Tape Architecture)

TILT (Trapped-Ion Linear-Tape) 架构 [77] 是一种线性离子阱设计，其特点是校准更容易、光学系统简化且硬件成本降低。在 TILT 系统中，整个离子链会前后移动，以便在特定区域（称为执行区或 AOM 区）内对量子比特进行操作。激光束被固定，而离子被移动到与激光束对应的位置。这种设计稳定了所需激光器、AOM (Acousto-Optic Modulators) 和 AOD (Acousto-Optic Deflectors) 的数量，降低了扩展成本。

图 1 展示了 TILT 架构的概览。在 AOM 区内的量子比特是完全连接的，这意味着它们之间可以直接应用双量子比特门。然而，要在 AOM 区之外执行量子操作，就需要移动离子，即进行穿梭操作。

3.1.6. 穿梭操作 (Shuttle Operation)

穿梭操作 (Shuttle Operation) 是在 TILT 架构中实现量子比特操作的关键技术。它利用微电极产生动态电势场，移动离子链中的离子，使其进入激光束的固定操作区域（AOM 区）。

• 原理: 离子的内部量子信息状态在移动过程中保持不变。通过精确控制微电极上的直流或交流电序列，离子可以在芯片上自由移动。
• 挑战: 理想情况下，绝热且足够慢的移动不会导致离子加热。但实际中，有限时间内的移动会导致离子加热，超过阈值可能导致量子比特丢失。相比距离，穿梭速度对保真度 (fidelity) 影响更大。本质上，穿梭操作会累积类似泡利 Z 型 (Pauli Z-type) 错误。
• 重要性: 穿梭操作显著增强了离子阱量子计算的扩展性，因为微电极的设计和制造比复杂激光系统更简单、成本更低。

3.1.7. AOM (Acousto-Optic Modulator) / AOD (Acousto-Optic Deflector)

AOM (声光调制器) 或 AOD (声光偏转器) 是光学器件，用于通过声波调制或偏转激光束。在离子阱量子计算中，它们对于将激光束分裂和引导到不同的离子位置至关重要，以实现单个量子比特的寻址和操作。

3.1.8. NISQ 时代 (Noisy Intermediate-Scale Quantum Era)

NISQ (Noisy Intermediate-Scale Quantum Era) 时代是指当前量子计算设备的特点是噪声大 (Noisy)、规模适中 (Intermediate-Scale) 且量子比特纠错能力有限。在这个时代，硬件的错误率仍然较高，量子比特数量不足以实现完全容错的量子计算。因此，算法和编译技术需要特别关注如何在有限资源和高噪声环境下优化性能，例如减少门数量、缩短执行时间、降低穿梭次数以最大化保真度。

3.2. 前人工作

离子阱量子计算领域的研究工作可以大致分为对架构的探索和对编译算法的优化。

3.2.1. 架构探索

• QCCD (Quantum Charge Coupled Device) 架构 [37]: QCCD 是一种模块化离子阱架构，包含多个阱 (traps) 和连接这些阱的通道，允许离子在不同区域之间移动和操作。随着规模的扩大，QCCD 需要更复杂的结 (junction) 穿梭和阱设计。虽然 QCCD 具有很高的扩展潜力，但其复杂性使其从小规模演示扩展到大型量子设备面临挑战。
• TILT (Trapped-Ion Linear-Tape) 架构 [77]: 相较于 QCCD，TILT 架构的优势在于它不依赖于尚未在所需复杂性级别上展示的组件。TILT 将离子链作为一个整体移动，在固定激光操作区 (AOM zone) 内执行门操作。TILT 架构还允许对一个或多个量子比特同时应用门，这是当前 QCCD 无法做到的。

3.2.2. 编译算法

• 通用量子编译器 (General Quantum Compilers):
  • Qiskit [2] 和 $\Delta\text{t}|\text{ket}\rangle$ [67] 等通用编译器虽然提供了离子阱设备的编译能力，但它们可能没有针对特定的离子阱系统配置和模拟进行优化。这可能导致次优的结果，尤其是在处理离子阱特有的穿梭操作时。
• 超导量子设备编译器 (Superconducting Quantum Device Compilers):
  • 大量研究集中于超导量子设备的编译器，主要目标是减少 SWAP 门插入 [29], [40], [53], [82]。这些方法通常将硬件约束建模为连接图，其中双量子比特门只能应用于有边的量子比特对之间。在此过程中，图的结构是静态的，只通过 SWAP 门改变逻辑量子比特到物理节点的映射。
  • 与 TILT 的差异: 超导设备的编译器不适用于 TILT 架构，因为 TILT 架构中的拓扑结构是动态变化的。门操作仅限于一个执行区，这形成一个具有多个隔离顶点的连接子图。每次穿梭操作都会改变连接子图的组成，引入了穿梭过程与图结构完整性之间的动态交互。因此，传统的超导编译算法无法直接应用于 TILT 架构。
• 离子阱特定编译器 (Ion Trap Specific Compilers):
  • 小规模设备性能评估 [41]: 一些早期工作侧重于评估小规模量子设备的性能，例如比较 5 量子比特离子阱设备和超导量子计算设备。本文则使用真实设备参数来估计离子阱系统在扩展时的特性和性能。
  • ILP (Integer Linear Programming) 方法 [78]: Wu et al. 提出了使用整数线性规划方法来获得离子移动和量子门调度的最优解。然而，这种方法随着量子比特数量的增加而扩展性不佳，因为穿梭次数在最坏情况下可能呈指数增长，导致计算时间过长。
  • 启发式算法 [77]: Wu et al. 还提出了一种启发式算法来减少穿梭次数。该算法通过插入 SWAP 门，使得每个双量子比特门所作用的两个量子比特之间的距离小于最大长度，从而确保门可以在一个执行区内执行。当执行区没有可执行门时，该算法会使用启发式函数决定移动 AOM 头。
    • 缺点: 这种方法在寻找插入 SWAP 门的合适位置时，需要计算所有剩余的门，导致计算耗时，尤其是当门数量增加时。它也没有明确地以降低穿梭次数为目标，可能导致更多的穿梭操作，从而增加保真度损失。该方法只关注单个门，忽略了电路的整体信息。
• QCCD 架构的启发式方法 [49], [61], [74]: 其他工作还关注使用启发式函数来优化 QCCD 架构，研究了模拟技术对阱大小、拓扑结构和门实现的影响。

3.3. 技术演进

量子计算硬件的演进路径，特别是离子阱技术，主要体现在如何高效、可扩展地实现量子比特的操控和互联。

1. 早期离子阱 (Early Ion Traps): 最初的离子阱系统将所有离子囚禁在一个公共阱中，通过激光直接寻址。然而，随着离子数量增加，声子模式的密集化和个体寻址的工程挑战限制了其扩展性。
2. QCCD 架构的提出 (QCCD Architecture Proposal): 为解决扩展性问题，Kielpinski 等人 [37] 提出了 QCCD 架构，通过分段阱和离子穿梭在不同区域（如存储区、交互区）之间移动离子，以克服单一阱的限制。
3. TILT 架构的出现 (Emergence of TILT Architecture): TILT 架构 [77] 进一步简化了 QCCD 的复杂性，采用线性离子链在固定激光操作区（AOM 区）内进行操作，通过移动整个离子链而不是单个离子或小簇离子，来简化光学系统和控制。
4. 编译算法的适配与优化 (Adaptation and Optimization of Compilers): 随着硬件架构的演进，需要开发专门的编译算法来充分利用新架构的特性，并解决其带来的新挑战。例如，针对 TILT 架构，如何高效地调度离子穿梭以最小化错误和时间，成为关键研究方向。从 ILP 的精确但慢速方法 [78]，到启发式但可能次优的方法 [77]，再到本文提出的 BOSS 算法，技术演进的趋势是寻求在保证性能的前提下，提高编译效率和可扩展性。

3.4. 差异化分析

本文提出的 BOSS 算法与现有工作相比，核心区别和创新点如下：

• 与 Wu et al. [77] 的启发式方法对比：

  • 目标函数不同： [77] 的目标是通过插入 SWAP 门来缩短双量子比特门中量子比特之间的距离，以满足 AOM 区的距离限制，并启发式地调度磁带移动。它没有明确地以降低穿梭次数为首要目标。BOSS 则明确旨在通过创新的阻塞策略来最小化穿梭次数，并同时最大化每次穿梭间的门并行执行。
  • 编译策略不同： [77] 逐个处理门，并使用启发式函数在需要时插入 SWAP 门，这在量子比特数量增加时会非常耗时 ($O(ng^2)$)。BOSS 采用“阻塞 (blocking)”方法，将门分组，一次性处理一个块，并通过 union-find 方式高效地将门分组，显著减少了每个块中量子比特的空闲率。
  • 性能提升： BOSS 在编译时间上远快于 [77]，在穿梭次数和执行时间上也有显著改进。例如，对于 RCS (Random Circuit Sampling) 电路，[77] 表现更好，因为 RCS 的门本来就距离短，不需要插入 SWAP 门，而 [77] 主要关注调度。但对于 QFT (Quantum Fourier Transform) 和 SQRT (Square Root) 等长距离门电路，BOSS 的优势非常明显。

• 与 Wu et al. [78] 的 ILP 方法对比：

  • 可扩展性： ILP 方法旨在找到最优解，但其计算复杂度高，随着量子比特数量的增加，时间消耗呈指数级增长，导致其在实际大规模应用中不切实际。BOSS 算法采用启发式阻塞和调度，虽然不保证最优，但具有 $O(ng)$ 的时间复杂度，提供了卓越的可扩展性。

• 与超导量子设备编译器的对比：

  • 硬件模型： 超导设备的编译器处理的是静态拓扑结构，通过 SWAP 门改变逻辑量子比特到物理量子比特的映射。TILT 架构则具有动态拓扑，穿梭操作会改变执行区域内连通子图的组成。BOSS 算法针对 TILT 的动态特性进行了优化，例如，它不依赖于静态的 SWAP 门插入，而是通过整体移动离子链来适应门的执行需求。

• 创新点总结： BOSS 的核心创新在于其阻塞算法，它在 TILT 架构下，通过将门高效地分组到块中，并在调度时最小化这些块之间的穿梭操作。这种方法在保证合理编译时间的前提下，显著提高了硬件利用率（降低空闲率），从而减少了穿梭次数和总执行时间，并提高了整体保真度。

4. 方法论

本节将详细阐述 BOSS 算法 (Blocking algorithm for optimizing shuttling scheduling in Ion Trap) 的方法原理、核心算法细节及其复杂度分析。

4.1. 方法原理

BOSS 算法的核心思想是“阻塞 (blocking)”。它将量子电路分解成一系列更小的块 (blocks)。每个块内部的量子门可以被视为一个逻辑上的多量子比特门，并且在离子阱的执行区域 (AOM zone) 内进行操作。通过这种方式，BOSS 旨在：

1. 最大化并行执行： 在每个块内部，尽可能多地并行执行量子门，从而减少门的执行总时间。

2. 最小化穿梭操作： 通过精心设计的阻塞和调度策略，减少在不同块之间切换时所需的离子穿梭次数。由于穿梭操作是导致保真度损失和执行时间增加的主要因素，最小化穿梭次数对于提高整体电路性能至关重要。

3. 提高执行区利用率： 减少执行区内量子比特的“空闲率 (vacancy rate)”，即确保执行区内的量子比特尽可能参与到门操作中。

   这种方法是对现有逐门处理策略的改进，它从更宏观的“块”层面优化调度，从而更好地利用离子阱设备在特定区域内全连接的特性。

4.2. 核心方法详解

本文提出的算法主要分为两个阶段：电路阻塞 (Circuit Blocking) 和 块调度 (Block Scheduling)。

4.2.1. 电路阻塞 (TILT Blocking)

电路阻塞的目的是将量子电路中的门分组到块中，每个块操作的量子比特数不超过执行区的最大尺寸 $Z$。这样，每个块内的相关量子比特可以在一个执行区域内同时操作。

以下是 Algorithm 2: TILT 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) U g
10  else
11    Union_set = G(g.idx1) U G(g.idx2) U 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 in G do
21      if q.idx == p.idx, clear q
22    end for
23    B.append(p)
24    G.frontier = G.frontier U w
25    clear w
26  end if
27 end while
28 for p in G do
29   B.append(p)
30 end for
31 return B

符号解释：

• $C$: 输入的量子电路。
• $Z$: 执行区的最大尺寸，即一个块中可包含的最大量子比特索引数量。
• $G$: 电路的依赖图 (Dependency Graph)。
• $B$: 存储最终阻塞后的块的列表 (Block List)。
• $w$: 等待列表 (Waiting List)，用于存储暂时无法加入当前块的门。
• $G$ (在步骤 5 初始化): 一个表示量子比特分组的数据结构，这里实际是一个并查集 (union-find) 结构，用于跟踪哪些量子比特属于同一个组（即可能被分到同一个块）。G(g.idx) 表示与 g.idx 量子比特相关的当前组。g.idx1 和 g.idx2 分别是双量子比特门作用的两个量子比特的索引。
• G.frontier: 依赖图 $G$ 中当前可执行的门的集合。

步骤详解：

1. 输入 (Input): 接收量子电路 $C$ 和最大块尺寸 $Z$。
2. 构建依赖图 (Get Dependency Graph): 根据电路 $C$ 生成依赖图 $G$。
3. 初始化 (Initialize):
   • $B$：空的块列表，将存储最终的电路块。
   • $w$：空的等待列表，用于暂存因尺寸限制无法立即合并到当前块的门。
   • $G$ (Group list)：初始化一个数据结构，每个量子比特最初都属于自己的独立组。
4. 主循环 (while G.frontier is not empty): 持续处理可执行的门，直到依赖图中没有更多可执行的门。
   • 获取门 (Get a gate): 从 G.frontier 中取出一个门 $g$。G.frontier 包含了所有当前没有未完成前置依赖的门。
   • 处理单量子比特门 (if g is single qubit gate): 如果 $g$ 是单量子比特门，它只作用于 g.idx。将其添加到与 g.idx 相关的组中。
   • 处理双量子比特门 (else): 如果 $g$ 是双量子比特门，它作用于 g.idx1 和 g.idx2。
     • 尝试合并 (Union_set): 创建一个 Union_set，包含 g.idx1 所在的组、g.idx2 所在的组以及门 $g$ 本身。
     • 检查尺寸限制 (if Union_set has no more than Z indexes): 如果合并后的 Union_set 所涉及的量子比特总数不超过 $Z$ (即执行区的最大尺寸)，则将 g.idx1 和 g.idx2 所在的组合并为 Union_set。这表示 $g$ 可以与这些量子比特的现有组一起构成一个块。
     • 否则 (else): 如果合并会导致块尺寸超出 $Z$，则将门 $g$ 添加到 $w$ (等待列表) 中，它将在稍后被考虑。
   • 处理当前层完成 (if G.frontier is empty): 当 G.frontier 变空时，表示当前层所有可执行的门都已处理完毕。
     • 选择最大组 (Pick a group p): 从 $G$ 中选择一个包含最多量子比特索引的组 $p$。这代表了一个尽可能大的、可并行执行的块。
     • 清空已选组 (for q in G): 将 $p$ 中所有量子比特的组信息清除，表示这些量子比特已经在一个块中处理完毕，可以为后续块腾出空间。
     • 添加到块列表 (B.append(p)): 将选定的组 $p$ 添加到最终的块列表 $B$ 中。
     • 更新可执行门 (G.frontier = G.frontier U w): 将等待列表 $w$ 中的所有门移到 G.frontier，并清空 $w$，以便在下一轮循环中处理。
5. 处理剩余组 (for p in G): 循环结束后，$G$ 中可能还存在一些未被放入块的组。将它们逐一添加到 $B$ 中。
6. 返回 (return B): 返回最终的块列表 $B$。

关键的创新点：

• 工会查找 (Union-Find) 方法： 算法内部使用了一种新颖的 union-find 方法进行高效阻塞。这与电路切割 (circuit cutting) 算法中的最小割 (minimum cut) 问题不同，本文无需最小化子图之间的切边数量，从而显著降低了计算复杂度。

• FIFO (First-In-First-Out) 策略： 在步骤 7 中，从 G.frontier 获取门时采用 FIFO 策略，这类似于广度优先搜索 (BFS)。它有助于将处于同一“深度”的门分组到同一个块中，从而增加相邻块之间共享量子比特的频率，这对于后续调度和执行很有帮助。

  通过这种阻塞方法，BOSS 能够减少每个块中量子比特的空闲率，意味着相同电路可以用更少的块完成，并潜在地减少所需的穿梭次数。

4.2.2. 块调度 (TILT Block Scheduling)

在电路阻塞阶段完成后，我们会得到一个块列表 $B$。然而，这些块中的量子比特在物理磁带上的位置可能不相邻。块调度阶段的目标是引入额外的 SWAP 门和穿梭操作，以确保每个块中的量子比特能够被移动到执行区域中并执行。

以下是 Algorithm 3: TILT Block Scheduling 的详细步骤：

$$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 in B do 5 if ∀idx in bi, idx in [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$$

符号解释：

• $B$: 阻塞阶段生成的块列表，$b_i$ 是其中的一个块。
• $Z$: AOM 的尺寸，即执行区的宽度。
• $T$: 表示物理离子链上的量子比特映射，初始为 $[0, 1, ..., n-1]$。
• $h$: 执行区的头部索引。

步骤详解：

1. 输入 (Input): 接收块列表 $B$ 和 AOM 尺寸 $Z$。
2. 初始化 (Initialize):
   • $T$：初始化量子比特在磁带上的逻辑映射，例如 $[0, 1, ..., n-1]$。
   • $h$：初始化执行头的索引。
3. 遍历块 (for bi in B): 顺序处理每个块 $b_i$。
   • 检查是否在执行区内 (if ∀idx in bi, idx in [h, h + Z) do): 检查当前块 $b_i$ 中所有量子比特的索引 idx 是否都已位于当前的执行区 $[h, h+Z)$ 内。
     • 如果已在区内 (execute bi, continue): 如果是，则直接执行 $b_i$，然后继续处理下一个块，无需穿梭。
   • 否则 (end if): 如果 $b_i$ 的量子比特不在执行区内。
     • 选择中间索引 (select the middle index mi): 在磁带 $T$ 上选择 $b_i$ 中量子比特的中间索引 mi。
     • 移动左半部分 (move the left half qubit): 将 $b_i$ 中位于 mi 左侧的量子比特移动到 mi 的右侧（靠近 mi）。
     • 移动右半部分 (move the right half qubit): 将 $b_i$ 中位于 mi 右侧的量子比特移动到 mi 的左侧（靠近 mi）。
     • 执行块 (execute bi): 将所有相关量子比特移动到执行区后，执行块 $b_i$。

关键的穿梭优化：

• 集中移动策略： 该算法通过将块 $b_i$ 中所有需要操作的量子比特向其“中间索引”mi 集中移动。图 5 直观展示了这一过程：将分散的量子比特移动到一起，以便它们能被一个执行区覆盖。
• 最小穿梭次数： 对于一个尺寸为 $m$ 的 AOM，移动 $k < m$ 个量子比特距离 $d$，最少需要 $\lceil d / (m - k) \rceil$ 次穿梭。通过选择 $k = \lfloor m/2 \rfloor$（即每次穿梭移动一半的量子比特），可以实现最小的穿梭计数。由于每次移动的距离不会超过量子比特总数 $n$，并且每次穿梭移动的离子数不超过 $m/2$，因此每个块之间的穿梭次数被限制在 $2n/m$ 以内。
• SWAP 门数量： 该算法引入的 SWAP 门数量不会超过 $\lfloor m/2 \rfloor s$，其中 $s$ 是穿梭次数。

4.2.3. 复杂度讨论 (Complexity Discussion)

1. 阻塞过程 (Blocking Procedure):

   • 时间复杂度为 $O(ng)$。其中 $n$ 是量子比特数，$g$ 是输入电路中的门数量。
   • 这个复杂度源于在依赖图上遍历门，并进行并查集操作。每个门最多访问两次其涉及的量子比特，并查集操作在摊销意义上接近常数时间。

2. 调度过程 (Scheduling Procedure):

   • 时间复杂度不超过 $O(k m L)$，其中 $k = \lceil n/m \rceil$ 是将整个离子链划分为 $m$ 大小AOM区域所需的近似份数，$m$ 是 AOM 大小，$L$ 是块的数量。
   • 进一步简化，由于 $k m \approx n$，所以调度过程的复杂度为 $O(nL)$。
   • 因为块的数量 $L \leq g/m$ (每个块至少包含 $m$ 个门，或平均 $m$ 个门)，所以 $O(nL)$ 也可以近似为 $O(ng/m)$。

3. 总时间复杂度 (Overall Time Complexity):

   • 综合阻塞和调度，算法的总时间复杂度为 $O(ng + nL)$。
   • 考虑到 $L \leq g/m$，总复杂度可以近似表示为 $O(ng)$。

4. 与前人工作对比：

   • 前人工作 [77]: 该方法首先插入 SWAP 门，以确保每个双量子比特门的距离小于 AOM 尺寸。寻找最佳插入 SWAP 门的启发式函数在最坏情况下需要 $O(ng^2)$ 的时间复杂度。调度过程不是主导项。

   • ILP 方法 [78]: 基于整数线性规划的方法，其穿梭次数在最坏情况下可能与量子比特数量呈指数关系，导致非常高的计算复杂度，不适合大规模电路。

     结论： BOSS 算法在时间复杂度上具有显著优势，其 $O(ng)$ 的复杂度使其能够比现有方法更快地找到解决方案，尤其是在处理更复杂的电路时。鉴于超导设备上的量子比特映射问题是 NP-hard 问题 [66]，离子阱设备上的门调度问题也被认为是 NP-hard。因此，在合理的时间内找到一个可行的解决方案，比找到最优解更为重要，而 BOSS 算法在这一点上表现出色。

5. 实验设置

本节将详细介绍本文用于评估 BOSS 算法性能的实验设置，包括所使用的基准电路、模拟参数以及用于评估的关键指标。

5.1. 数据集 (Benchmarks)

本文选择了一系列具有代表性的量子应用程序作为基准测试电路，这些电路涵盖了不同的量子比特规模、门数量以及通信模式（短距离、最近邻、长距离），以全面评估 BOSS 算法的有效性。

以下是原文 Table I 的转录：

数据集描述：

• Adder：基于 Cucarro 加法器 [18] 的 32 比特加法器电路，QASM (Quantum Assembly Language) 代码来源于 [71]。它主要包含短距离门 (Short-distance gates)。
• BV (Bernstein-Vazirani)：一个在 NISQ (Noisy Intermediate-Scale Quantum) 时代常用的基准应用，用于测试设备性能。它包含长距离门 (Long-distance gates)。
• QAOA (Quantum Approximate Optimization Algorithm)：一种混合迭代方法，用于解决组合优化问题，例如 MaxCut [19] 和 SK 模型 [20]。它主要使用最近邻门 (Nearest-neighbor gates)。
• ALT (Alternating Layered Ansatz)：一种在变分量子本征求解器 (VQE, Variational Quantum Eigensolver) 中常用的 ansatz [19]。它也主要使用最近邻门 (Nearest-neighbor gates)。
• RCS (Random Circuit Sampling)：由 Google 提出用于展示量子优越性 (quantum supremacy) 的电路 [25]，其 QASM 代码来源于 [25]。它主要使用最近邻门 (Nearest-neighbor gates)。
• QFT (Quantum Fourier Transform)： Shor 算法 [64] 和相位估计算法 [38] 的关键组成部分。它包含大量的长距离门 (Long-distance gates)。
• SQRT (Square Root)：来源于 ScaffCC [33]，通过 Grover 搜索算法寻找平方根。它包含长距离门 (Long-distance gates)。

选择理由： 这些基准电路的选择旨在展示 BOSS 算法在不同量子计算上下文中的多功能性和广泛适用性。它们覆盖了：

1. 不同的门数量： 从 64 个双量子比特门 (BV) 到 4032 个双量子比特门 (QFT)。
2. 不同的量子比特数： 从 64 个到 78 个。
3. 不同的通信模式： 包括短距离、最近邻和长距离通信门。 本文仅关注双量子比特门 (two-qubit gates)，因为它们通常具有更长的运行时 (runtimes) 和更高的错误率 (error rates)；单量子比特门可以合并，且对总体性能影响较小。

5.2. 模拟参数

实验在 Windows 11 系统、AMD Ryzen 5 6600H CPU 和 16GB 物理内存的配置下，使用 Python 3.9 环境运行。

• AOM 尺寸： 评估了 16 和 32 两种 AOM 尺寸，代表了执行区域的不同宽度。
• 激光精度系数 ($\epsilon_{laser}$): 设定为 $1/256000$，以确保 AOM 尺寸为 16 时双量子比特门能达到 99.9% 的保真度。
• 穿梭残余纠缠系数 ($\epsilon_{shuttle}$): 设定为 0.001，用于模拟穿梭操作带来的保真度损失。
• 穿梭速度 ($v_m$): 设定为 $1 \mu \mathrm{m} / \mu \mathrm{s}$ [10]。

5.3. 评估指标

本文采用以下指标来全面评估 BOSS 算法的性能：

5.3.1. 穿梭数量 (Shuttling Number)

1. 概念定义: 穿梭数量 (Shuttling Number) 是指在执行整个量子电路过程中，离子链需要移动以将量子比特带入执行区域的总次数。由于每次穿梭操作都可能引入误差和额外的执行时间，因此穿梭数量越少越好，它是衡量算法穿梭效率的关键指标。
2. 数学公式: 该指标没有直接的数学公式，通常是计数，表示为 $S$。
3. 符号解释: $S$ 代表在编译和执行整个量子电路过程中，离子链（tape）被移动以适应门操作的总次数。

5.3.2. 编译时间 (Compilation Time)

1. 概念定义: 编译时间 (Compilation Time) 是指将高层量子算法（或量子电路描述）转换为可在离子阱硬件上物理执行的指令序列（例如包含穿梭和门操作）所需的时间。高效的编译器应在短时间内完成这一转换。
2. 数学公式: 该指标没有直接的数学公式，通常是计时。
3. 符号解释: $T_{pre}$ 指代现有方法的编译时间，$T_{boss}$ 指代 BOSS 方法的编译时间。

5.3.3. 执行时间 (Execution Time)

1. 概念定义: 执行时间 (Execution Time) 是指一个量子电路从开始到结束在离子阱设备上实际运行所需的总时间。这包括门操作时间、离子穿梭时间、初始冷却时间、中途冷却时间以及最终的读出时间。准确估计执行时间对于评估量子应用的实际可行性至关重要。
2. 数学公式: $$t_{exec} = v_m \times dist + \sum_d t_d + t_1 + t_2 + t_3$$
3. 符号解释:
   • $t_{exec}$: 整个量子电路的估计总执行时间 (Execution Time)。
   • $v_m$: 离子穿梭速度 (shuttling speed)，单位 $\mu \mathrm{m} / \mu \mathrm{s}$。
   • dist: 在整个电路执行过程中离子链移动的总距离 (total shuttle distance)。
   • $\sum_d t_d$: 编译后电路深度 $d$ 上的所有门操作时间之和。其中 $t_d$ 是在特定深度上所有门中最大的门实现时间。
   • $t_1$: 初始冷却时间 (initial cooling time)，包括 Doppler 冷却和边带冷却，即 $10 \mathrm{ms} + 50 \mu \mathrm{s}$。
   • $t_2$: 中途冷却时间 (midway cooling time)，在每次穿梭操作后进行，公式为 $40 \mu \mathrm{s} \times s_m$，其中 $s_m$ 是总穿梭操作次数。
   • $t_3$: 量子状态读出时间 (readout time)，设定为 $150 \mu \mathrm{s}$。

5.3.4. 双量子比特门实现时间 (Two-qubit Gate Implementation Time)

1. 概念定义: 双量子比特门实现时间 (Two-qubit Gate Implementation Time) 是指在离子阱中执行一个双量子比特门所需的物理时间。这个时间通常与两个离子之间的距离有关。本文考虑了三种门实现方式：Duan AM 门、Trout AM 门和 PM 门。
2. 数学公式:
   • Duan AM 门 [79]: $$\tau_{\mathrm{Duan}}(d) = 100d - 22$$
   • Trout AM 门 [73]: $$\tau_{\mathrm{Trout}}(d) = 38d + 10$$
   • PM 门 [45]: $$\tau_{\mathrm{PM}}(d) = 5d + 160$$
3. 符号解释:
   • $\tau$: 双量子比特门的实现时间，单位为微秒 ($\mu \mathrm{s}$)。
   • $d$: 两个离子之间的距离 (distance)。

5.3.5. 保真度 (Fidelity) / 成功率 (Success Rate)

1. 概念定义: 保真度 (Fidelity) 或 成功率 (Success Rate) 衡量的是量子操作或整个量子电路执行成功的概率。对于离子阱系统，保真度受多种因素影响，包括门操作精度和穿梭操作引入的误差。高保真度是实现可靠量子计算的关键。
2. 数学公式:
   • 双量子比特门保真度 ($F_{gate}$): 考虑到激光操作区域内离子数量对保真度的影响，假设使用振幅调制 (AM) MS 门： $$F_{gate} = 1 - \epsilon_{laser} N^2$$
   • 穿梭操作保真度 ($F_{shuttle}$): 穿梭操作会累积误差，保真度损失与穿梭次数呈线性关系： $$F_{shuttle} = 1 - \epsilon_{shuttle} m$$
   • 整体成功率 ($F$): 整个电路的成功率是所有双量子比特门的保真度乘积和所有穿梭操作保真度的乘积： $$F = F_{gate}^g \times \prod_{m=1}^S (1 - \epsilon_{shuttle} m)$$
3. 符号解释:
   • $F_{gate}$: 单个双量子比特门的保真度。
   • $\epsilon_{laser}$: 仪器操作的精度系数 (precision coefficient of instrument manipulation)，在模拟中设定为 $1/256000$。
   • $N$: 激光相互作用区域内的离子数量 (number of ions in the laser interaction region)。
   • $F_{shuttle}$: 单次穿梭操作的保真度。
   • $\epsilon_{shuttle}$: 在穿梭操作期间离子和声子之间的残余纠缠 (residual entangle)，在模拟中设定为 0.001。
   • $m$: 在 $\prod$ 符号下，代表第 $m$ 次穿梭操作。
   • $F$: 整个量子电路的总体成功率 (overall success rate)。
   • $g$: 整个电路中双量子比特门的总数量 (total gate number)。
   • $S$: 整个电路中总穿梭次数 (total shuttle number)。

5.4. 对比基线

本文主要将 BOSS 算法的性能与 Wu et al. 在 2021 年提出的启发式算法 [77] 进行比较。该基线算法旨在通过插入 SWAP 门来最大化保真度，从而减少由穿梭操作引起的 SWAP 门数量。它通过启发式函数来寻找插入 SWAP 门和调度磁带移动的最佳位置。

6. 实验结果与分析

本节将详细分析 BOSS 算法在各项评估指标上的实验结果，并与基线方法进行比较。

6.1. 核心结果分析

6.1.1. 穿梭数量 (Shuttling Number)

以下是原文 Table II 的转录：

符号解释：

• Tpre(s): 现有方法 [77] 的编译时间 (秒)。

• Tboss(s): BOSS 方法的编译时间 (秒)。

• Sbase: 基线（未优化的）穿梭数量。

• Spre: 现有方法 [77] 的穿梭数量。

• Sboss: BOSS 方法的穿梭数量。

• $ΔS$: 现有方法与 BOSS 方法穿梭数量的差值，即 $S_{pre} - S_{boss}$。

• $ΔS/Spre$: 穿梭数量的相对减少百分比，即 $(S_{pre} - S_{boss}) / S_{pre}$。

• tre(s): 现有方法 [77] 的执行时间 (Trout 模型，秒)。

• tboss(s): BOSS 方法的执行时间 (Trout 模型，秒)。

• tpre/tboss: 现有方法与 BOSS 方法执行时间的比值，表示 BOSS 的加速倍数。

  以下是原文 Figure 6 的转录：

  

  图 6. 穿梭操作数量 (越低越好)。

  分析：

• 显著减少： 从 Table II 和 Figure 6 可以看出，BOSS 算法在大多数应用中显著减少了穿梭次数。例如，在 AOM 尺寸为 32 时，QFT 和 SQRT 的穿梭次数分别减少了 88.4% 和 96.1%，这是非常巨大的提升。

• 平均改进： 总体而言，BOSS 的平均穿梭次数改进为 16.6%。

• 对长距离门电路的优势： 对于 QFT 和 SQRT 这类包含大量长距离门的应用，BOSS 表现出了尤其突出的优势。这是因为 BOSS 算法能够更好地利用执行区的全连接特性，通过阻塞将更多的门并行执行，从而减少了将分散的量子比特移动到一起所需的穿梭。

• RCS 的特例： BOSS 在 RCS (Random Circuit Sampling) 应用上的表现却不如现有算法，甚至增加了穿梭次数（AOM 16 时增加 63.1%，AOM 32 时增加 90.9%）。这主要是因为 RCS 电路固有的特性——在初始映射下，所有双量子比特门之间的距离都不超过 15。在这种情况下，现有算法无需考虑 SWAP 门插入，只需专注于穿梭调度，因此具有显著优势。而 BOSS 的阻塞策略可能会导致将原本距离较近的门打包，反而需要更多的穿梭来移动整个块。

• 利用率提升： BOSS 算法通过将电路划分为块，使得在每个执行区内可以执行更多的门，从而降低了量子比特的空闲率。以 QFT 为例，BOSS 确保执行区内的量子比特不处于空闲状态，使得两次连续穿梭操作之间可以执行更多的门。

• SWAP 门： 尽管 BOSS 可能引入更多的 SWAP 门（例如 AOM16 的 QFT 需要 336 个 SWAP 门，而现有方法仅需要约 120 个），但与总门数量相比，这些额外的 SWAP 门数量是可忽略不计的。

6.1.2. 执行时间 (Execution time)

以下是原文 Figure 7 的转录：

图 7. 使用 AM 门实现 [73] 的执行时间与之前工作 [77] 的比较分析。

分析：

• 显著改进： 从 Table II 和 Figure 7 可以看出，BOSS 算法在执行时间方面取得了显著进展。SQRT (AOM 16) 实现了最大的性能提升，执行时间减少了 179.6 倍，平均改进了 61.5 倍。

• Trout AM 门模型： 使用 Trout AM 门（$\tau_{\mathrm{Trout}}(d) = 38d + 10$）的实现进一步缩短了执行时间，使得某些应用有望在数秒内完成。

• 原因： 执行时间的改进主要归因于两个方面：

  1. 降低空闲率： 阻塞算法减少了执行区内量子比特的空闲率，提高了双量子比特门的并发执行效率。
  2. 优化的预处理时间： BOSS 算法的编译时间远低于现有方法，这间接减少了总的“准备+执行”周期。

• 离子冷却与读出： 评估中包含了离子冷却、初始态准备和读出时间，这使得执行时间的估计更加精细，更符合当代离子阱系统的实际情况。这表明，在离子阱量子比特相干时间较长的优势下，BOSS 提出的方法使得执行具有深层电路的复杂应用变得可行。

  以下是原文 Figure 8 的转录：

  

  图 8. 门实现对执行时间的影响。对于 AM 来说，短距离门表现更好，而对于 PM 来说，长距离门表现更好。

  分析：

• AM 与 PM 门的比较： Figure 8 比较了 AM (Amplitude Modulated) 门和 PM (Phase Modulated) 门实现对执行时间的影响。

  • 短距离通信电路： 对于 Adder, QAOA, ALT, RCS 等短距离通信电路，使用 Trout AM 门（$\tau_{\mathrm{Trout}}(d) = 38d + 10$）通常能获得更短的执行时间。
  • 长距离通信电路： 对于 QFT 和 SQRT 等长距离通信电路，PM 门（$\tau_{\mathrm{PM}}(d) = 5d + 160$）的实现可能提供更好的执行时间性能，因为 PM 门对离子间距离的依赖性较弱（距离系数 $d$ 较小）。

• AOM 尺寸的影响： 在某些应用中，AOM 尺寸为 32 时执行时间反而比 AOM 尺寸为 16 时长。这是因为更大的 AOM 尺寸允许门作用于更远的量子比特，但本研究的目标不是优化执行时间本身，而是优化穿梭。

6.1.3. 保真度 (Fidelity) / 成功率 (Success Rate)

以下是原文 Figure 9 的转录：

图 9. 不同应用上的成功率比较 (越高越好)。

分析：

• 更高成功率： BOSS 算法比现有方法 [77] 实现了更高的成功率。这主要是因为 BOSS 更好地利用了冷却过程。例如，对于 AOM 尺寸为 16 的 QFT，现有方法的成功率低于 $1 \times 10^{-14}$，而 BOSS 的成功率超过 $4 \times 10^{-3}$。
• 门保真度模型： 文中使用的双量子比特门保真度模型为 $F_{gate} = 1 - \epsilon_{laser} N^2$，其中 $N$ 是激光相互作用区域内的离子数量。这意味着随着 $N$ 的增加（即 AOM 尺寸增大，能够同时容纳和操作的离子数量增多），单门保真度会迅速下降。
• 穿梭保真度模型： 穿梭操作的保真度模型为 $F_{shuttle} = 1 - \epsilon_{shuttle} m$，其中 $m$ 是穿梭次数。
• AOM 尺寸与保真度： Figure 9 的实验结果表明，随着 AOM 尺寸的增加，整体保真度反而可能下降。这与门保真度模型一致，即更大的 $N$ 导致更低的 $F_{gate}$。这与 [77] 中理想模型的假设（AOM 尺寸增大不降低门保真度）形成对比。本文的保真度公式被认为更准确地反映了真实条件。
• 穿梭减少的重要性： 当门保真度不随 AOM 尺寸的增加而快速下降时（即技术进步），BOSS 这种减少穿梭次数的方法将表现出更大的优势。

6.1.4. 扩展性 (Scalability)

以下是原文 Figure 10 的转录：

图 10. 编译时间随电路规模的变化。电路规模指电路中的量子比特数量，AOM 尺寸为 16。

分析：

• 符合预期的时间复杂度： Figure 10 展示了 BOSS 算法的编译时间随电路规模变化的趋势。结果与理论上 $O(ng)$ 的时间复杂度预期大致吻合，其中 $n$ 为量子比特数，$g$ 为门数量。
• 线性增长： 对于 Adder 和 QAOA 电路，它们的门数量与量子比特数量呈线性关系，且主要包含最近邻（或短距离）门。因此，它们的编译时间也随量子比特数量的增加呈线性增长。
• 二次方增长： 对于 QFT 电路，其门数量与量子比特数量呈近似平方关系。因此，其编译时间也随量子比特数量的增加呈近似平方关系。
• 卓越效率： 即使对于 180 量子比特的 QFT 电路，BOSS 算法的编译时间也不超过 1.2 秒。相比之下，现有方法 [77] 编译 64 量子比特的 QFT 电路就需要超过 60 秒。这一显著差异凸显了 BOSS 算法在处理复杂量子电路时的卓越效率和扩展性。

6.2. 数据呈现 (表格)

本节已在 6.1.1. 穿梭数量 (Shuttling Number) 中完整转录了原文 Table II。

7. 总结与思考

7.1. 结论总结

本文提出了 BOSS (Blocking algorithm for optimizing shuttling scheduling in Ion Trap) 算法，旨在解决离子阱量子计算中穿梭操作带来的保真度损失和执行时间延长问题。通过将量子电路划分为逻辑块并优化块之间的穿梭调度，BOSS 算法显著提升了离子阱设备的效率和可靠性。

主要成果包括：

• 创新的阻塞算法： 有效地将量子门分组，最大化了执行区域内的并行性，并减少了量子比特的空闲率。
• 显著减少穿梭次数： 在大多数应用中，穿梭次数平均减少 16.6%，最高可达 96.1%，有效降低了因离子移动引入的误差。
• 大幅缩短执行时间： 执行时间平均缩短 61.5 倍，最高可达 179.6 倍，这使得复杂量子电路的运行变得更加可行。
• 提高成功率： 结合对同情冷却的考虑，算法显著提升了整体电路的成功率。
• 卓越的扩展性： 编译时间复杂度为 $O(ng)$，使其能够高效处理大规模量子电路，展现出在未来大型 QCCD (Quantum Charge Coupled Device) 设备上执行实际量子应用的潜力。

7.2. 局限性与未来工作

论文作者指出了当前工作的局限性并展望了未来的研究方向：

• 贪婪方法限制： 当前算法主要依赖贪婪方法 (greedy methods)。虽然这提供了良好的效率，但可能无法找到全局最优解。未来工作可以考虑在框架中融入更复杂的启发式函数 (heuristic functions)，这可能有助于找到更优的解决方案，尽管可能会增加额外的编译时间开销。
• SWAP 门优化： 论文观察到插入 SWAP 门会导致保真度下降。因此，未来的研究方向之一是努力最小化 SWAP 门的使用。这可以借鉴超导系统 [29], [40], [80], [81] 中减少 SWAP 门的方法，并将其适配到 TILT 架构。
• 动态门实现选择： 虽然论文比较了 AM 和 PM 门实现，并指出不同类型的门在短距离和长距离通信中各有优势，但并未深入探讨如何在编译过程中动态选择最佳的门实现方式，以进一步优化执行时间。

7.3. 个人启发与批判

7.3.1. 个人启发

1. 硬件感知编译的重要性： 本文再次强调了针对特定量子硬件架构（如 TILT）进行定制化编译优化的重要性。简单地将通用编译器或针对其他架构（如超导）的方法应用于离子阱系统是次优的。理解硬件的物理限制（如 AOM 区域、穿梭机制、冷却过程）并将其融入编译策略，是释放量子计算潜力的关键。
2. 阻塞策略的普适性： 提出的“阻塞”概念，即将量子门分组以提高并行度并优化资源（如穿梭）使用，是一个非常有价值的思路。这种宏观优化视角不仅适用于离子阱，也可能启发其他量子计算平台或甚至经典并行计算任务的调度优化。
3. 现实参数建模的必要性： 论文中详细考虑了初始冷却、中途冷却、读出时间以及与距离相关的门实现时间等现实物理参数，这使得性能评估更加可靠和具有指导意义。对于 NISQ 时代的量子计算，这种对“噪声”和“时间”的精细建模至关重要。
4. 编译效率与扩展性： 在 NP-hard 问题背景下，找到一个在合理时间内具有良好扩展性的“可行解”比追求“最优解”更重要。BOSS 算法的 $O(ng)$ 复杂度在处理日益增长的量子比特数和门数量时，为其提供了强大的竞争优势。

7.3.2. 批判

1. RCS 性能劣势的深入分析： 论文提到 BOSS 在 RCS 电路上表现不佳，甚至增加了穿梭次数，并将其归因于 RCS 本身门距离较短，现有算法无需插入 SWAP。虽然这是合理的解释，但如果能更深入地分析 BOSS 阻塞策略在哪些具体情况下会导致这种“反效果”，并探讨是否有针对这种电路特征的改进措施，将使算法更加鲁棒。例如，是否可以设计一个动态策略，根据电路的连接模式（稀疏/密集、短距离/长距离）自适应地选择阻塞或逐门调度。
2. AOM 尺寸对保真度的影响： 论文指出，其门保真度模型 $F_{gate} = 1 - \epsilon_{laser} N^2$ 意味着 AOM 尺寸（进而影响 $N$）增大时，门保真度可能下降。这解释了 Figure 9 中 AOM 32 成功率低于 AOM 16 的现象。虽然这个模型反映了现实，但读者可能会对 $N$ 与 AOM 尺寸 $Z$ 的具体关联感到困惑。进一步明确 $N$ 是如何根据 $Z$ 决定的，以及这种平方关系在物理上的根源，将有助于初学者更全面地理解。
3. SWAP 门数量的权衡： 论文承认 BOSS 会引入更多的 SWAP 门，但认为其数量与总门数量相比可忽略不计。然而，考虑到 SWAP 门本身也会消耗时间和引入误差，如果能在减少穿梭和减少 SWAP 门之间找到一个更好的权衡点，或者提出一个统一的成本函数来优化这两个因素，将是未来的重要方向。
4. 贪婪选择的潜在次优性： 尽管在 NP-hard 问题中贪婪方法是必要的，但如何在贪婪选择中引入更多的前瞻性或启发式信息（例如，不仅仅是选择最大组，而是考虑该组对后续块调度的影响），是提升算法性能的常用手段。论文提到了未来可以引入启发式函数，但若能提供一些初步的探索性思路，将更有价值。
5. 物理实现挑战的更具体讨论： 论文在动机和背景部分提到了离子阱面临的诸多物理实现挑战。尽管方法论解决了穿梭调度问题，但如果能在总结或未来工作中，更具体地讨论 BOSS 算法如何与微电极设计、激光控制技术等更深层的物理工程问题相结合，以实现整体的硬件-软件协同优化，将使其更具影响力。