布局映射与长程交互利用｜中性原子量子计算知识库

在里德堡阵列上映射量子线路是一道"免费的午餐附带账单"：阻塞半径内的原子对直接纠缠、无需 SWAP，但每张长程门都会划出一个随距离增长的限制区，把并行度一点点吃回去——最优交互距离不是越大越好，而是"刚好够用"。

问题背景

映射（mapping）把线路比特指派到硬件位置，并在交互无法直接发生时插入通信操作。超导平台的耦合图稀疏且固定，SWAP 开销不可避免；中性原子阵列的交互半径 $r_{in t}$ 由里德堡阻塞给出，覆盖若干格点甚至接近整片阵列（见FPQA 计算模型与能力边界），因此”距离”不再直接等于”SWAP 数”。Baker 等人首次系统量化了这一红利与代价：交互距离（max interaction distance, MID）的增大确实消灭 SWAP，但限制体积随之扩张，串行化代价在天生高并行的线路上显现 Baker 2021。Brandhofer 等人则证明：当 AOD 行列位移被当作映射原语引入时，最优映射（SMT 精确求解）可以定量回答”什么样的硬件参数下位移优于 SWAP” Brandhofer 2021。

理论模型

交互图与限制区

把硬件建模为 2D 网格，交互图定义为

E = {(u, v) ∣ d (u, v) \leq d_{ma x}},

$d_{ma x}$ 即最大交互距离。参与门的一组原子会生成限制区：Baker 等取半径 $f (d) = d /2$ 的圆（ $d$ 为交互原子对间距离），限制区内（距任一交互原子小于 $f (d)$ ）的其他原子不得同时操作；两操作可并行当且仅当限制区互不重叠。注意 $f (d)$ 随 $d$ 增长——这就是”长程门吃并行度”的形式化来源；该模型可直接推广到多比特门（见多比特阻塞门） Baker 2021。它也是 Schmid 综述中限制半径 $r_{r e} = k r_{in t}$ （阻塞因子）框架的一个实例化 Schmid 2024。

成功概率模型

比较不同交互距离下的编译结果需要一个端到端指标。Baker 等把程序成功概率近似为”无门错误”与”无退相干错误”之积：前者为 $\prod_{i} p_{g a t e, i}^{n_{i}}$ （ $n_{i}$ 为 $i$ 比特门数），后者由各空闲段的 $e^{- Δ t / T_{1, 2}}$ 因子累乘给出。该指标把”门数（SWAP 消减）“与”深度（并行度）“两条编译收益统一到可比较的标尺上 Baker 2021。

前瞻式映射与路由评分

逐层（DAG frontier）处理线路，未来交互以指数衰减加权：

w (u, v) = ℓ \geq ℓ_{c} \sum e^{- ∣ ℓ_{c} - ℓ ∣},

初始布局按”交互频繁的比特放得近”评分 $s (u, h) = \sum_{v} d (h, φ (v)) w (u, v)$ 取最小；路由的 SWAP 评分同时惩罚”远离当前交互”与”破坏未来交互”，保证每步严格靠近目标 Baker 2021。

位移-交换混合的最优映射

Brandhofer 等把一维 AOD 位移（整行/整列平移一格，保持相对次序）编码为整数位移变量 $η_{p, t} \in Z$ ：正值为右移、负值为左移；两位移相等时两原子的相对位置不变，若原本相邻即可直接执行门。位移与 SWAP 共同进入 SMT（satisfiability modulo theories）模型，主要约束包括：每比特至多指派一个位置、位置指派只能沿交互图的边变更、同一时刻同一比特上至多发生一种操作（单比特门/多比特门/位移/SWAP 互斥）。优化目标可选最小化线路深度（ $min max_{c} z_{c}$ ）或最大化保真度：

max c \in U \sum lo g f_{c} + s \in S \sum lo g f_{s} + d \in D \sum lo g f_{d},

其中 $S$ 为插入的 SWAP 集、 $D$ 为位移集；由于位移不操作量子态，可取 $f_{d} \approx 1$ Brandhofer 2021。

交互距离、限制区与原生多比特门的关系示意（图源：Baker 2021 Fig. 2）

方法与实现

长程交互的收益扫描。Baker 等在 $10 \times 10$ 阵列上编译规模至 100 比特的基准（BV、Cuccaro 加法器、CNU、QFT-Adder、QAOA），MID 从 1（模拟超导近邻耦合）扫到全域连接 $\approx 13$ ：门数收益（全部来自 SWAP 消减）集中在前几档 MID，全域连接时 SWAP 归零、门数达到下界；深度随 MID 下降，但天生并行的线路（CNU、QFT-Adder）在高 MID 下出现限制区导致的串行化回摆——把实际编译结果与”无限制区”的理想调度对照即可分离出该项损失。工程结论有二：中等交互距离即可拿到大部分红利，硬件方应优先做高保真中短程门；限制区还有隐式抑制串扰的副作用，必要时可人为扩大限制区、以串行化换取更低的串扰误差 Baker 2021。

编译器本身以既有启发式为骨架：在 MID = 1、无限制区的设置下与开启 lookahead 的 Qiskit 对照，门数与深度均相当，验证了其作为基线的正确性 Baker 2021。

原生多比特门作为映射资源。三比特 Toffoli 分解需 6 个双比特门，原生执行可直接节省最高 $6 \times$ 门数并免掉 ancilla；映射器只需保证组内两两距离 $\leq d_{ma x}$ （限制了可行几何），详见Geyser：原生多比特门编译与Toffoli/CCZ 门 Baker 2021。

损失容忍映射。原子随机丢失（见原子损失与容损失架构）会使按满阵编译的线路失效。Baker 等比较了六种策略：整阵重载、全量重编译、虚拟重映射（查表改写地址，硬件开销约 $40 n s$ ）、次要重路由（移位后借道插入 SWAP）、以及”编译到次大交互距离”留余量。30 比特线路放在 100 比特阵列上时，重编译可容忍最高 70% 的原子丢失（失败仅剩拓扑断连），各重路由策略约 50%，但重编译计算代价最高——交互距离越大，各策略的容忍度都越高 Baker 2021。

最优位移映射的定标。SMT 模型用 Z3 求解，基准为至多 15 比特、深度至多 76 的算术/BV/QFT/随机 CX 线路。结论呈现清晰的参数依赖：当 SWAP 门慢于位移（运行时之比 $r > 1$ ）时深度平均下降最高 $31.3%$ （算术线路单条最高 $58.3%$ ）； $r = 2$ 时平均 $16.3%$ ； $r = 1$ 时仅 $0.8 - 2%$ 。保真度方面，SWAP 保真度 $f_{s} = 0.95$ 时最高提升 $29%$ （平均 $15%$ ）， $f_{s} = 0.999$ 时平均仅 $0.3%$ ——即位移值得启用当且仅当 SWAP 保真度明显低于 1 或 SWAP 不比位移快多少 Brandhofer 2021。精确求解的可扩展性局限催生了后续启发式框架（OLSQ-DPQA、Atomique 动态阵列编译、算法相关布局选择）。

参数与量级

量	典型值	来源
评估平台	$10 \times 10$ 网格，程序至 100 比特	Baker 2021
交互距离扫描	MID $= 1$ 至 $hypot (9, 9) \approx 13$ （全域连接）	Baker 2021
基准线路	BV、Cuccaro、CNU、QFT-Adder、QAOA（边密度 0.1）	Baker 2021
收益分布	门数/深度收益集中于最初几档 MID，随后饱和	Baker 2021
限制区半径	$f (d) = d /2$ （成对距离）	Baker 2021
原生 Toffoli 收益	1 步替代 6 个双比特门（最高 $6 \times$ 门数）	Baker 2021
真空碰撞丢失	概率 $\approx 0.0068$ /程序（均匀分布）	Baker 2021
读出丢失	踢出式测量约 $50%$ /次；无损方案约 $2%$ ；检测约 $6 m s$	Baker 2021
虚拟重映射开销	$\sim 40 n s$ （硬件查表）	Baker 2021
损失容忍度	重编译约 70%；重路由策略约 50%（30 比特/100 比特阵列）	Baker 2021
最优映射规模	$\leq 15$ 比特、深度 $\leq 76$ ；Z3 求解平均约 $20 min$	Brandhofer 2021
位移映射深度收益	SWAP 较慢时平均至 $31.3%$ （算术线路最高 $58.3%$ ）	Brandhofer 2021
位移映射保真度收益	最高 $29%$ （ $f_{s} = 0.95$ ）； $f_{s} = 0.999$ 时平均 $0.3%$	Brandhofer 2021
位移适用条件	SWAP 保真度 $< 0.999$ 或 SWAP 运行时不明显示优于位移	Brandhofer 2021

与其他概念的关系

交互距离与限制体积的物理出处是里德堡阻塞与里德堡相互作用： $d_{ma x}$ 的上限即阻塞半径，限制区对应里德堡串扰。
映射问题在中性原子上的完整能力背景（连接图动态化、多比特门、搬运）见FPQA 计算模型与能力边界；把位移原语用于分区间调度见分区架构与原子搬运与相干输运。
原生多比特门是映射的”免通信”资源：见多比特阻塞门、Toffoli/CCZ 门与Geyser：原生多比特门编译。
损失容忍映射是原子损失与容损失架构在编译层的对应面；并行度损失的分析承接并行纠缠门。
后续映射/布局工具的谱系：OLSQ-DPQA、Atomique、算法相关布局选择、受限寻址的分解与调度、最优重排与置换路由。

参考文献

J. M. Baker, A. Litteken, C. Duckering, H. Hoffmann, H. Bernien, F. T. Chong, “Exploiting Long-Distance Interactions and Tolerating Atom Loss in Neutral Atom Quantum Architectures”, ISCA (2021). NA010 · arXiv:2111.06469 · DOI 10.1109/ISCA52012.2021.00069
S. Brandhofer, I. Polian, H. P. Buchler, “Optimal Mapping for Near-Term Quantum Architectures based on Rydberg Atoms”, ICCAD (2021). NA011 · arXiv:2109.04179 · DOI 10.1109/ICCAD51958.2021.9643490

中性原子百科

探索

布局映射与长程交互利用