DasAtom 分治搬运

DasAtom 的本质是"先分治、后穿梭"：把 CZ 线路按层切成若干个子电路，使每个子电路的交互图都能作为架构图的子图同构嵌入到紧凑网格上——于是子电路内部的门全部直接可执行、零 SWAP——然后只用原子搬运在子电路的嵌入之间切换；它同时吃到了长程交互与原子穿梭两份红利，在 QFT 类通用线路上把保真度提高了几个数量级。

问题背景

中性原子平台有两条别的架构没有的”免费”路由手段：一是长程交互——交互半径 $R_{\mathrm{int}}$ 内的原子对可以直接执行 CZ 门；二是原子穿梭（atom shuttling）——用 AOD 携带原子在计算中移动。已有编译器往往只用其中一条：SWAP 路线的 Tetris 在固定原子阵列上模仿超导编译器，靠长程交互换取稠密连接但不搬原子；搬运路线的 Enola、Atomique 为规避里德堡串扰把原子间距拉大（Enola/Atomique 假设原子间距为交互半径的 2.5 倍），牺牲了交互密度 Huang 2025。DasAtom（divide-and-shuttle atom approach）把两者结合：线路分块后每块的嵌入利用稠密长程连接，块间切换用高保真原子搬运完成。

DasAtom 的目标架构与 DPQA（见FPQA 计算模型）类似，但假设 CZ 门由可单独寻址的里德堡激光逐个执行，且原子以紧凑间距 $d\le R_{\mathrm{int}}$ 排布在 $\lceil \sqrt{n}\rceil \times \lceil \sqrt{n}\rceil$ 网格上。作者强调这一”每个能力都有实验演示、但尚无器件同时具备”的架构假设没有原理性障碍 Huang 2025。

形式化模型

架构图与并行约束

原子阵列的架构图 $AG=(V,E)$ 中，边定义为

$$E=\{(p_i,p_j)\mid p_i,p_j\in V,D(p_i,p_j)\le R_{\mathrm{int}}\},$$

$D$ 为欧氏距离，交互半径 $R_{\mathrm{int}}=r_{\mathrm{int}}d$，$r_{\mathrm{int}}\in \{1,\sqrt{2},2\}$ 时边分别对应网格上的横纵向、对角线与跨两格邻居。两个 CZ 门 $g$（作用于 $p_i,p_j$）与 $g^{\prime }$（作用于 $p_a,p_b$）可并行执行，当且仅当跨门的所有原子对满足

$$D(p_u,p_v)>R_{\mathrm{restr}},u\in \{i,j\},v\in \{a,b\},$$

即限制半径 $R_{\mathrm{restr}}\ge R_{\mathrm{int}}$ 内不允许出现别的门的原。默认 $d=3\mu m$、$R_{\mathrm{int}}=6\mu m$、$R_{\mathrm{restr}}=12\mu m$ Huang 2025。

嵌入与交互图

线路 $C$ 的交互图 $IG(C)$ 以 qubit 为点、双比特门为边。若 $IG(C)$ 可一一嵌入（即子图同构，subgraph isomorphism）到 $AG$，映射 $f$ 下每个门 $CZ(q,q^{\prime })$ 都有 $D(f(q),f(q^{\prime }))\le R_{\mathrm{int}}$，全部直接可执行、无需任何 SWAP。DasAtom 的分治就是寻找子电路划分 $C_1,\dots ,C_k$（每块由连续 CZ 层组成，$1={\ell }_1\le m_1<{\ell }_2\le \cdots \le m_k=m$），使每个 $IG(C_i)$ 都可嵌入。以 QFT-5 为例：线路含 12 个 CZ 层，可分成两个子电路，第二块只含最后 4 个 CZ 门 Huang 2025。

成本模型

设 $T_2$ 为相干时间，$m$ 为 CZ 门数，$h$ 为编译后深度，$s$ 为原子转移次数，$D$ 为各并行搬运最大距离之和，$v$ 为移动速度，编译线路的近似成功概率为

$$P(C)=\exp (-\frac{T_{\mathrm{idle}}}{T_2})\times f_{\mathrm{cz}}^m\times f_{\mathrm{trans}}^s,T_{\mathrm{idle}}=nT-m{t}_{\mathrm{cz}},$$

总执行时间 $T=h{t}_{\mathrm{cz}}+s{t}_{\mathrm{trans}}+D/v$。默认参数：$T_2=1.5s$、$f_{\mathrm{cz}}=0.995$、$t_{\mathrm{cz}}=0.2\mu s$、$t_{\mathrm{trans}}=20\mu s$、$v=0.55\mu m/\mu s$。该模型定量解释了 DasAtom 的两大优势来源：一次 SWAP（3 个 CZ）固定损失 $f_{\mathrm{cz}}^3\approx 0.985$，而以 $0.55\mu m/\mu s$ 搬运原子，移动一万多微米才折损同等保真度——但搬运在时间上比 SWAP 慢上百倍，所以关键是用分治把搬运次数 $s$ 与移动距离 $D$ 压到最少 Huang 2025。

方法与实现

DasAtom 流水线四步 Huang 2025：

1. 分解与提层：把线路分解到原生门集 $\{CZ,R_x,R_y,R_z\}$，移除单比特门（约定单/双比特门分阶段执行），再把 CZ 线路切成 $L_1,\dots ,L_m$ 层。
2. 分治划分：从第一层起贪心扩展，用 VF2 子图同构算法（Rustworkx 实现）检验当前层区间 $C[i_{\mathrm{last}}:i]$ 的交互图是否仍可嵌入网格；不可嵌入时切出一块。整块粒度划分使 VF2 调用次数只有 $O(\mathrm{depth})$，而逐门划分的调用数随深度指数增长。
3. 逐块嵌入：为每个子电路 $C_i$ 求嵌入 $f_i:IG(C_i)\hookrightarrow G(b,b)$，$b=\lceil \sqrt{n}\rceil$；块内所有门直接执行，同时用限制半径约束过滤可并行门。例如映射中 $D(f(q_3),f(q_4))=d<R_{\mathrm{restr}}$ 时，$CZ(q_1,q_3)$ 与 $CZ(q_0,q_4)$ 就不能并行。
4. 穿梭路由：把每个 qubit 的位移写成四元组 $m_i=(x_i,y_i,x_i^{\prime },y_i^{\prime })$，两条移动不满足行列保序条件 $(x_i\ast x_j)\iff (x_i^{\prime }\ast x_j^{\prime })$、$(y_i\ast y_j)\iff (y_i^{\prime }\ast y_j^{\prime })$（$\ast \in \{<,=,>\}$）时互为冲突；冲突图上 compatible 移动集合即独立集，贪心求极大独立集分批并行搬运，把 $f_i$ 变换到 $f_{i+1}$。与 Enola 不同，DasAtom 的冲突图不含”对偶移动”——它只需把两个原子拉进交互半径，而非对齐到同一位点。

DasAtom 流程图：CZ 线路 → 分层 → 分治划分与嵌入 → 穿梭路由循环（图源：Huang 2025 Fig. 6）

实现为 Python（开源）；DasAtom/Enola 实验在 MacBook（i5、16 GB）上完成，Tetris/Atomique 在 512 GB 服务器上完成。作者用 VF2 在约一小时内编出 500 qubit 的 QFT；但 QV 类近完全交互图在超过 25 qubit 时嵌入检验变慢，需要更快的（近似）子图同构算法如 PathLAD+ Huang 2025。

实验结果与对比

基准一为 Tetris 论文的 33 个 RevLib/Qiskit 线路（5–16 qubit，最多 3,089 个 CZ 门），基准二为 MQTBench 的 5–50 qubit 线路（DJ、GHZ、QFT、QV、two-local、W 态、3-regular MaxCut QAOA），对比 Tetris、Enola 与 Atomique Huang 2025。

30-qubit QFT：DasAtom 保真度相对 Enola、Tetris、Atomique 分别提升 415.8×、10.6×、16.1×；运行时间上 Enola、Tetris、Atomique 分别是 DasAtom 的 9,851×、384×、2.6×。

基准（几何平均保真度）	DasAtom	Tetris	Enola	Atomique
33 个 RevLib 线路	0.03458	0.01951	0.0033（静态）	0.0018
20-qubit 七种拓扑线路	0.2832	0.0865	0.0979（动态）	0.2104
——其中 QFT-20	0.1176	0.0237	0.0178	0.0606
QFT（5–50 qubit）	0.0066	$3.65\times 10^{-4}$	$2.63\times 10^{-6}$	$8.31\times 10^{-4}$
3-regular（10–60 qubit）	0.8548	0.2547	0.2785	0.7890
DJ（5–50 qubit）	0.8412	0.6791	0.6413	0.8615

平均而言 DasAtom 保真度是 Tetris、Enola、Atomique 的 1.77×、10.48×、19.21×（最大 case “square root 7” 达 27.4×、$1.05\times 10^6$×、$1.69\times 10^7$×）；QFT 上相对 Atomique 平均 7.9×。对 DJ、W 态这类稀疏交互图线路，Atomique 可与之相当甚至略胜，而 QFT、QV 这类稠密（近完全）交互图线路正是分治嵌入的主场：交互图与架构图匹配良好时几乎零 SWAP、零搬运。提升随 qubit 数指数增长的机理也清楚：Tetris/Atomique 的 SWAP 数至少线性增长，Enola 的空闲时间随搬运距离与转移次数增长，而 $P(C)$ 对 $T_{\mathrm{idle}}$ 指数敏感 Huang 2025。

消融实验给出三条边界。其一，保真度对 $f_{\mathrm{cz}}$ 最敏感；$f_{\mathrm{trans}}$ 只影响 DasAtom 与 Enola；$T_2$（0.15–15 s）对除 Tetris 外都敏感；原子间距从 1 增到 20 μm 只让 QFT-20 损失约 3–7%。其二，转移时长 $t_{\mathrm{trans}}$ 从 20 升到 40 μs 损失 11.8%，是仅次于门保真度的短板。其三，当 $f_{\mathrm{trans}}\le 0.99$ 且 $f_{\mathrm{cz}}\ge 0.98$ 时 Tetris 反超——若搬运保真度不够高，穿梭的优势会被吞噬；极端对照是：若用穿梭去模拟 SWAP 门，DasAtom 在 QFT-50 上对 Tetris 的优势会从 8,108× 缩水到 3.14× Huang 2025。

参数与量级

量	典型值	来源
相干时间 $T_2$	$1.5s$	Huang 2025
CZ 门	$f_{\mathrm{cz}}=0.995$，$t_{\mathrm{cz}}=0.2\mu s$	Huang 2025
原子转移	$t_{\mathrm{trans}}=20\mu s$（$f_{\mathrm{trans}}$ 默认取 1）	Huang 2025
搬运速度	$v=0.55\mu m/\mu s$	Huang 2025
原子间距 / 交互半径	$d=3\mu m$；$R_{\mathrm{int}}=6\mu m$（$r_{\mathrm{int}}=2$）	Huang 2025
限制半径	$R_{\mathrm{restr}}=12\mu m$	Huang 2025
30-qubit QFT 提升	对 Enola 415.8×、Tetris 10.6×、Atomique 16.1×	Huang 2025
最大演示规模	500-qubit QFT，约 1 小时	Huang 2025

与其他概念的关系

• 块间切换依赖原子搬运与相干输运：冲突图建模与并行搬运调度直接继承自 Enola 的独立集路由。
• 子图同构嵌入思想与固定阵列上的布局映射与长程交互利用同源，DasAtom 把它升级为”每块一个最优嵌入”。
• 相对于 SMT 全局求解的OLSQ-DPQA与启发式调度的Arctic，DasAtom 代表第三条路线：分治+逐块精确嵌入。
• 与Atomique 动态阵列编译的对比说明硬件假设的重要性：紧凑阵列+单独寻址（DasAtom）对大间距+全局激光（Atomique）在通用线路上差距悬殊。
• 并行 CZ 的限制半径约束是阻塞 CZ 门串扰条件在编译层的表述，其物理来源见里德堡相互作用。
• 嵌入检验复杂度提醒我们编译器评测要同时报告保真度与编译时间，见编译器公平评测与可视化。

参考文献

• Y. Huang, D. Gao, S. Ying, S. Li, “DasAtom: A Divide-and-Shuttle Atom Approach to Quantum Circuit Transformation”, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. (2025). NA029 · DOI 10.1109/tcad.2025.3532818 · arXiv:2409.03185
• D. B. Tan, W.-H. Lin, J. Cong, “Compilation for Dynamically Field-Programmable Qubit Arrays with Efficient and Provably Near-Optimal Scheduling”, ASPDAC (2025)（Enola，DasAtom 的搬运模块与对比基线）. NA028
• H. Wang et al., “Atomique: A Quantum Compiler for Reconfigurable Neutral Atom Arrays”, ISCA (2024). NA019
• Y. Li, Y. Zhang, M. Chen, X. Li, P. Xu, “Timing-Aware Qubit Mapping and Gate Scheduling Adapted to Neutral Atom Quantum Computing”, IEEE TCAD 42, 3768 (2023)（Tetris，题录经 NA029 参考文献核实）· DOI 10.1109/TCAD.2023.3261244