OLSQ-DPQA：可重构阵列的 Qubit 映射｜中性原子量子计算知识库

OLSQ-DPQA 的本质是把"哪些门放进哪个里德堡阶段、每个原子此刻在哪里、如何在阶段之间搬运"这三件事统一写成可满足性模理论（SMT）约束，从而第一次为可动态重构的中性原子阵列求出（近）最优的 qubit 映射——它定义了问题，也用指数级的求解时间暴露了问题，由此催生了 Enola、Atomique、Q-Pilot 等整个可重构阵列编译器家族。

问题背景

中性原子平台在规模与保真度上已进入第一梯队：超过 1,000 qubit 的阵列、99.97% 的单比特门与 99.5% 的双比特门保真度，使其成为最具竞争力的技术路线之一 Tan 2025。动态可编程量子阵列（dynamically field-programmable qubit array, DPQA，也称场可编程量子阵列，见FPQA 计算模型）由两类光阱组成：空间光调制器（SLM）产生的静态阱，以及二维声光偏转器（AOD）产生的可动阱。AOD 阱位于若干行与列的交叉点，整行/整列平移即可携带原子相干移动；原子可在 SLM 与 AOD 之间转移。全局里德堡激光照亮整个平面，凡是落在里德堡半径 $r_{b}$ （约 $6 μ m$ ）内的原子对都会自动执行 CZ 门，而交互位点（interaction site）之间需相隔 $2.5 r_{b}$ ，使多体交互只发生在同一位点之内 Tan 2025。

这一硬件模型带来与固定架构完全不同的编译问题：两比特门的”耦合图”不再固定，而是由编译器在每个阶段现场设计。编译因此分解为三个相互纠缠的子任务——调度（哪些门放进同一个里德堡阶段）、放置（每个阶段原子在哪个位点）、路由（阶段之间如何移动原子）。约束包括：同一阶段内一个 qubit 至多参与一个门；AOD 的行/列在移动中不能交叉或越过彼此（否则原子相撞丢失）；以及最隐蔽的一条——闲置原子被里德堡激光照到也会积累激发误差，因此阶段数本身就是一个必须最小化的代价。Tan、Bluvstein、Lukin 与 Cong 在 ICCAD 2022 提出的 OLSQ-DPQA（optimal layout synthesis for DPQA）是第一个把这三件事作为整体优化求解的编译器 Tan 2022，期刊扩展版 “Compiling Quantum Circuits for Dynamically Field-Programmable Neutral Atoms Array Processors” 发表于 Quantum 8, 1281 (2024)。

DPQA 硬件示意：SLM 静态阱、AOD 行列移动、全局里德堡激光与 2.5rb 间距交互位点（图源：Tan 2025 Fig. 1）

形式化模型

SMT 表述

OLSQ-DPQA 把量子布局综合（quantum layout synthesis, QLS）表述为带约束的优化问题，交给 SMT 求解器搜索最优解。决策变量包括：每对有门关系的 qubit 在各阶段是否处于同一交互位点（门执行变量）、每个原子各阶段所在的位置变量、SLM/AOD 归属与搬运变量；约束编码了 AOD 行列保序、位点容量与”同一阶段一个 qubit 至多一个门”。目标是最大化并行执行的门数、最小化搬运次数。由于问题本身是 NP 完全的，SMT 求解时间指数增长——原实现一天只能处理不超过 90 qubit 的电路 Tan 2025。公式的一个结构性限制是：两个里德堡阶段之间至多安排一次重排，这保证了公式规模可控，却也阻碍了”多个重排步骤接力完成一轮门分组”的探索；且原子转移未被计入目标函数，事后检查其输出会发现不少”非必要搬运” Tan 2025。

保真度模型

评估该类编译器需要统一的保真度模型。按领先实验的参数 Tan 2025：单比特门保真度 $f_{1} = 99.97%$ （ $T_{Ram} = 625 ns$ ），双比特门 $f_{2} = 99.5%$ （ $T_{Ryd} = 360 ns$ ），被里德堡激光照射但未参与门的 qubit 保真度 $f_{exc} = 99.75%$ ，原子转移 $f_{trans} = 99.9%$ （ $T_{trans} = 15 μ s$ ），相干时间 $T_{2} = 1.5 s$ 。整个流程的保真度为

f = (f_{1})^{g_{1}} (f_{2})^{g_{2}} (f_{exc})^{∣ Q ∣ S - 2 g_{2}} (f_{trans})^{N_{trans}} q \in Q \prod (1 - \frac{T _{q}}{T _{2}}),

其中 $g_{1}, g_{2}$ 是单/双比特门数， $S$ 是里德堡阶段数， $N_{trans}$ 是原子转移总数， $T_{q}$ 是 qubit $q$ 的空闲时间。指数项 $∣ Q ∣ S - 2 g_{2}$ 正是”旁观原子”付出的代价：一次照射中每个没做门的原子的损失与做门的原子的损失同量级。AOD 运动满足匀加速关系 $d / t^{2} = a$ （ $a = 2750 m/ s^{2}$ ）。

以 NA028 中的三门小例子为算例 Tan 2025： $(f_{2})^{3} = 0.9851$ ；一个旁观原子贡献 $f_{exc} = 0.9975$ ，双比特项合计 $0.9826$ ；3 次转移贡献 $0.99 9^{3} = 0.9970$ ；最长搬运 $2 \times 2.5 r_{b} \approx 21.2 μ m$ 需时 $87.8 μ s$ ，7 个 qubit 的退相干项合计 $0.9996$ ——总保真度 $97.92%$ 。这个公式揭示了三个独立的优化抓手：减少阶段数 $S$ 、减少搬运次数 $N_{trans}$ 、缩短空闲时间 $T_{q}$ 。

方法与实现

OLSQ-DPQA 的求解流程是”一次性整体求解”：把调度、放置、路由变量全部放入同一个 SMT 公式，由求解器迭代搜索。在 DAG 前沿调度中，它倾向于把当前前沿能并行的门全部塞进当前阶段；对 ising 类基准这会拉长关键路径。后续改进沿”分解 + 启发式”路线展开，代表是同一课题组的 Enola Tan 2025：

调度：把可交换门组（commutation group）的调度归约为图的边染色——门为边、阶段为颜色，同一 qubit 不能同时出现在两条同色边上，最优阶段数即边色数 $χ^{'} (G)$ 。Misra–Gries 算法在 $O (n^{3})$ 时间内给出至多 $S_{opt} + 1$ 个阶段的调度（定理保证）；依赖子电路用 ASAP 调度（本身最优）。
放置：以门两端欧氏距离的加权和 $\sum_{g} w_{g} dist (m (q), m (q^{'}))$ 为代价，用 Fast-SA 模拟退火优化；默认采用”动态放置”——每个阶段后只重排需要移动的原子，越早执行的门权重越高（ $w_{g} = max (0.1, 1 - 0.1 s_{g})$ ）；搜索限制在 $max (⌊ n ⌋ + 4)$ 见方区域内。
路由：一次搬运写成四元组 $(x, y, x^{'}, y^{'})$ ，冲突关系（同 row 拾取必须同 row 放下、行列保序被破坏等）构成冲突图，可并行搬运集合即独立集。sortIS 用贪心极大独立集（ $O (n^{4})$ ）；windowIS 固定窗口 $K = 1000$ 只在窗口内建图，复杂度降为 $O (n^{2} lo g n)$ ；拾取与放下的低层指令沿用 OLSQ-DPQA 的 CodeGen（逐行拾取、拾取行列可横移）。

可扩展性上的差距是数量级的：100 qubit 电路 Enola 一分钟内可编出更高保真度的结果，10,000 qubit 用 windowIS 只需约 25 分钟（同规模 sortIS 需约 3.4 小时；1,000→10,000 qubit 运行时间从 18.8 s 增至约 1,040 s，符合 $O (n^{2} lo g n)$ ）Tan 2025。

最优 DPQA 路由的 NP 困难性已在 AOD 拾取时间优化上被证明 Tan 2025，这解释了后续工作为何普遍转向启发式。其他后继者：Q-Pilot Wang 2024 只移动”飞行 ancilla”来中继 SLM 比特间的门；Atomique Wang 2024 用多 AOD 阵列加 SWAP 的混合策略；分治式的 DasAtom 与面向分区架构的 Arctic 也都把 OLSQ-DPQA 作为公共基线。展望多 AOD 硬件：在 90 qubit QAOA 上用 2、3、4 个 AOD 轮流执行搬运批次，可将整体保真度再提升 1.54×、1.79×、1.94× Tan 2025。

Enola 对 OLSQ-DPQA 的误差分解对比：双比特门项、搬运项、退相干项随 qubit 数变化（图源：Tan 2025 Fig. 2）

实验结果与对比

对比在 OLSQ-DPQA 论文自己的基准上进行：3-regular MaxCut QAOA（30–90 qubit，问题幺正 $U_{C}$ 为每个 qubit 参与 3 个可交换 ZZ 门）Tan 2025。90 qubit 处 OLSQ-DPQA 平均使用 14.6 个里德堡阶段（理论下界为 3——每个 qubit 只参与 3 个门），Enola 只用 4 个，阶段数降低 3.7 倍；按统一保真度模型重算，OLSQ-DPQA 的双比特门保真度项仅 0.0414（搬运项 0.592、退相干项 0.223），双比特门误差是主导误差源，Enola 把双比特项提高到 0.406，整体保真度提升 5.9 倍。在依赖子电路上两者互有胜负：多数情况 ASAP 调度与 OLSQ-DPQA 阶段数相同，个别 ising 基准 OLSQ-DPQA 因关键路径拉长而明显更差，而个别只需一次重排的基准（multiply_n13、seca_n11）OLSQ-DPQA 反而占优 Tan 2025。

指标（90 qubit QAOA，除非注明）	OLSQ-DPQA	Enola	提升
里德堡阶段数（平均）	14.6	4	3.7×
双比特门保真度项	0.0414	0.406	~9.8×
整体保真度（相对值）	1	5.9	5.9×
与 Atomique 的阶段数对比	—	—	8.7×
与 Q-Pilot 的阶段数对比	—	—	10.5×
最大可编译规模	90 qubit / 天	100 qubit / 分钟；10,000 qubit / 25 min	—

对启发式后继（Q-Pilot、Atomique）而言，ancilla 的生成回收与 SWAP 插入都需要额外阶段，90 qubit 处阶段数比 Enola 多 10.5× 与 8.7×，双比特门保真度项分别低至 1/5806 与 1/779，总保真度也全面落后 Tan 2025。这一系列数字的共同教训是：里德堡阶段数（即全局激光照射次数）是 DPQA 编译的第一阶指标——旁观激发误差使阶段数的代价远超门数本身。

参数与量级

量	典型值	来源
单比特门	$f_{1} = 99.97%$ ， $625 ns$	Tan 2025
双比特门	$f_{2} = 99.5%$ ， $360 ns$	Tan 2025
旁观激发	$f_{exc} = 99.75%$ （每次照射）	Tan 2025
原子转移	$f_{trans} = 99.9%$ ， $15 μ s$	Tan 2025
相干时间 $T_{2}$	$1.5 s$	Tan 2025
AOD 加速度	$a = 2750 m/ s^{2}$	Tan 2025
里德堡半径 / 位点间距	$r_{b} = 6 μ m$ ； $2.5 r_{b} = 15 μ m$	Tan 2025
90 qubit QAOA 阶段数	OLSQ-DPQA 14.6（下界 3）；Enola 4	Tan 2025

与其他概念的关系

问题定义建立在FPQA 计算模型之上：全局里德堡激光、AOD 行列约束与交互位点离散化都是该模型的形式化要素。
双比特门本身即阻塞 CZ 门；阶段内多对门并行执行的物理基础见并行纠缠门。
AOD 搬运的相干性是整个框架成立的物理前提，详见原子搬运与相干输运。
长程交互免 SWAP 的思想与固定阵列上的布局映射与长程交互利用一脉相承，但 DPQA 把耦合图本身变成了优化变量。
启发式后继者：Atomique 动态阵列编译、Q-Pilot 飞行 ancilla 编译、Arctic：FPQA 调度、DasAtom 分治搬运；公平比较这些编译器的方法学见编译器公平评测与可视化。
AOD 寻址的行/列约束在 1D 控制下的极端情形由受限寻址的分解与调度处理。
值得注意的是优化目标依赖硬件假设：若里德堡激光可单独寻址，闲置 qubit 不再吃旁观激发，优化目标就从”最少阶段数”转为”最少门数”，整个问题退化回带 SWAP 的固定架构映射 Tan 2025。

参考文献

B. Tan, D. Bluvstein, M. D. Lukin, J. Cong, “Qubit Mapping for Reconfigurable Atom Arrays”, Proc. 41st IEEE/ACM ICCAD (2022). NA014 · DOI 10.1145/3508352.3549331
D. B. Tan, D. Bluvstein, D. M. Lukin, J. Cong, “Compiling Quantum Circuits for Dynamically Field-Programmable Neutral Atoms Array Processors”, Quantum 8, 1281 (2024)（期刊扩展版，题录经 NA028 参考文献核实）· DOI 10.22331/q-2024-03-14-1281
D. B. Tan, W.-H. Lin, J. Cong, “Compilation for Dynamically Field-Programmable Qubit Arrays with Efficient and Provably Near-Optimal Scheduling”, Proc. 30th ASPDAC (2025). NA028 · arXiv:2405.15095
H. Wang et al., “Atomique: A Quantum Compiler for Reconfigurable Neutral Atom Arrays”, ISCA (2024). NA019
H. Wang et al., “Q-Pilot: Field Programmable Qubit Array Compilation with Flying Ancillas”, Proc. 61st DAC (2024). NA026

中性原子百科

探索

OLSQ-DPQA：可重构阵列的 Qubit 映射