最优重排与置换路由｜中性原子量子计算知识库

重排（rearrangement）是中性原子编译里替代 SWAP 门的那一步：给定一个目标排列，用尽量少的”并行搬运步”把 N 个原子送到位。答案出人意料地依赖硬件细节——现在的整行整列 AOD 移动注定要 $Θ (N lo g N)$ 步，而一个简单的”选择性转移”升级或换用 Ramanujan 覆盖拓扑就能压到 $Θ (lo g N)$ 。

问题背景

在固定耦合图的架构里，路由是插 SWAP 门；在可重构原子阵列里，路由是物理搬原子：一次重排可以让原本相距很远的原子彼此贴近，因此耦合图模型根本不适用——单个时间步内可以发生”上一步还相距很远”的原子对之间的交换 Constantinides 2024。编译的三段式——里德堡门执行、比特到原子的映射、原子重排——必须联合优化，而重排的快慢直接决定相干时间内能做完多少层门，是电路深度、退相干与保真度的主导项之一 Constantinides 2024 Courtney 2026。

值得注意的是求解手段的分工：SMT 类编译器（如OLSQ-DPQA）能找到最优解，但 SMT 问题一般是 NP-hard，实际规模下代价过高；启发式编译器高效却未必最优。因此”最坏情形保证”只能来自可证明的下界与匹配协议——这正是路由理论要补上的一环 Constantinides 2024。

硬件上有两套镊子：SLM 产生静态阵列，AOD 在行×列交点形成可移动陷阱（行列不可交叉以防原子碰撞，见FPQA 计算模型与原子搬运与相干输运）。把原子从 SLM 装载到 AOD 有两种方式：网格转移（grid transfer，现状）——AOD 网格覆盖到的原子全部一起转移；选择性转移（selective transfer，提议）——用第二块 SLM 在任意格位”压住”不想移动的原子，只转移选中的子集 Constantinides 2024。这一字之差造成了下界的指数分离。

形式化模型

路由数与移动模型

给定 $N$ 个原子与目标置换 $π \in S_{N}$ ，一个路由步定义为常数次 SLM↔AOD 转移加常数次势阱升降、且结束时原子回到 SLM 阵列的 rearrangement；实现任意置换所需步数的最大值称为该移动模型的路由数（routing number）Constantinides 2024。不同硬件约束给出不同模型：

1D 有序交换：一步交换两条等长子数组（保持各自内部顺序）；与”洗牌”模型（riffle shuffle，需 $N /2$ 个额外空阱）等价，均满足路由数 $Ω (lo g N)$ ——任何置换若把某集合 $R$ 的相对次序完全颠倒，每步至多救回一半，故至少 $lo g_{2} ∣ R ∣$ 步；分治算法 $lo g_{2} N$ 步达成 Constantinides 2024。
2D 网格转移：一步是两个同维数组合矩形 $R = A \times B$ （ $A$ 、 $B$ 分别为行、列集合）之间的按序交换。计数论证给出下界： $N! = 2^{Θ (N l o g N)}$ 个置换必须各有独立路由方案，而单步可实现的置换只有 $2^{O (N l o g N)}$ 个，故最坏置换需要 $Ω (N lo g N)$ 步 Constantinides 2024。
2D 选择性转移：一步是带掩码的矩形按序交换（掩码 $M : Z \to {0, 1}$ 指定矩形内哪些对真正交换）。同样的计数论证只给 $Ω (lo g N)$ Constantinides 2024。

Ramanujan 超图上的谱路由

Courtney 把置换路由放到超图上： $(d, r)$ -正则超图 $H$ 是 Ramanujan 的，若所有非平凡特征值满足 $∣ λ_{i} - (r - 2) ∣ \leq 2 (d - 1) (r - 1)$ ；其团扩张图 $G_{c l} (H)$ （两顶点相邻当且仅当共享一条超边）度为 $d^{'} = d (r - 1)$ ，谱比 $β = λ_{*} / d^{'} < 1$ 。路由步取 $G_{c l}$ 上的一个匹配并同时交换各边两端的原子。主定理：

rt (H) = Θ (lo g N), 更精确地 rt (H) = O (\frac{lo g N}{1 - β}),

下界来自计数（每步匹配度至多 $d^{'}$ ， $T$ 步至多 $(d^{'})^{T}$ 个落点）；上界组装谱图论的标准管线：Chung 直径界 $D \leq 2 lo g_{2} N / lo g_{2} (1/ β)$ 、Valiant 散射-聚集（随机中间置换）给出拥塞 $C = O (lo g N)$ ，再用 Leighton–Maggs–Rao 调度 $T = C + D + o (C + D)$ Courtney 2026。

最少转移的分解定理

面向分区架构（见分区架构），Gentil 等把映射问题建成量子有向图（节点=各阶段的比特位置，边=阶段间转移），并证明： $Z$ 区架构下全局最少转移数可由各分区子图分别最小化得到（定理 3.2，记号 $λ_{q}$ ），据此提出非线性整数规划模型并用遗传算法求解，优化目标是总搬运距离与并行转移操作（PTO）数的可调权衡 Gentil 2026。

方法与实现

匹配下界的协议（NA024）。核心是把 $d$ 维超立方体 $Q_{d}$ 嵌入 $N \times N$ 网格：原子按二进制地址放置，行=前 $⌈ d /2 ⌉$ 位、列=后 $⌊ d /2 ⌋$ 位。按某一位 $k$ 分组的两组原子各成等维组合矩形，于是一次（掩码）矩形交换即可同时交换所有”地址仅第 $k$ 位不同”的原子对；套用超立方体路由算法得 $2 lo g_{2} N - 1$ 步（选择性转移）。无选择性时，每个掩码交换拆成逐行矩形交换，共至多 $N (2 lo g_{2} N - 1)$ 步 Constantinides 2024。

对结构较稀的目标还有更快的专用协议：称 $π$ 为列（行）稀疏，若其在每列（行）上至多作用于 $poly (lo g N)$ 个非恒等元素。任何此类稀疏置换可在不依赖选择性转移的网格模型下 $poly (lo g N)$ 步完成——每轮用压缩递归把 $Ω (N)$ 个原子对齐到目标行、在单行上做 1D 路由后整行交换，再逆压缩复原其余原子；压缩与逆压缩各至多 $lo g_{2} N$ 步 Constantinides 2024。另外，全部上下界对”大矩形阵列的子阵列”照样成立（如六角、三角或 Kagome 格点附加 $O (N)$ 个空位即可嵌入），无需重证 Constantinides 2024。

让 Ramanujan 落地（NA044）。三条路线：其一是虚拟覆盖层——在网格上叠 $L$ 层独立随机 $d_{0}$ -正则图，并集的谱比按 $β = O (1/ L d_{0})$ 改善（数值验证 $d_{0} = 8$ 、 $L \leq 16$ 、 $N \leq 256$ ）；3D 声光透镜（AOL）容量为 $k$ 时路由深度 $T = O (N / (k (1 - β)))$ ，容量 $Ω (N)$ 即达 $O (lo g N)$ 。其二是 SFM 覆盖塔：从 Fano 平面 $P G (2, 2)$ （ $N_{0} = 7$ ）出发， $2^{7} = 128$ 个随机 $Z_{2}$ 电压指派中 $93.8%$ 给出 Ramanujan 二重覆盖， $T / lo g_{2} N$ 保持于 $[1.07, 1.66]$ ；但跨层谱比会累积增长（ $0.17 \to 0.50 \to 0.86$ ），一致界 $\overset{ˉ}{β} < 1$ 尚无一般证明。其三是负结果：固定次数的 Cayley 图（ $Z_{2}^{n}$ 上）因阿贝尔 Alon–Boppana 屏障不可能是 Ramanujan 的，仿射去随机化只能换来 15%–30% 的拥塞削减 Courtney 2026。

传送路由的摊销账（NA044）。沿纠缠覆盖层预分发 Bell 对后，路由本身不再搬运原子（只需 LOCC），深度 $T_{route} = O (lo g N / (1 - β_{e n t}))$ ；成本转移到配对分发： $d_{e n t} \cdot N /2$ 对 Bell 态仍需物理运输，随机覆盖边的平均格距 $\overset{ˉ}{d}_{g r i d} \approx N /2$ ，并行度 $k$ 下分发耗时 $T_{d i s t} = O (d_{e n t} N N / k)$ ；每轮分发提供 $R = d_{e n t} / T_{route}$ 个路由轮次，摊销成本 $T_{am or t} = T_{route} + T_{d i s t} / R$ Courtney 2026。

工程映射器（NA040）。转移方案由迁移有向图上的最大权匹配导出；“棍/子棍”（stick/substick）编码把同区连续格位绑成可整体重排的单元，使阶段间位置决策保持时间关联；遗传算法的评分函数可在”总距离倒数”与”PTO 数倒数”之间切换，也可加权拟合真实硬件时序（镊子速度与 SLM/AOD 切换快慢的相对大小决定该优化哪个）Gentil 2026。

硬件设计准则（NA044）。把上述结果按单步 AOD 容量 $k_{0}$ 与每电路路由轮数 $R$ 归纳为三条 Courtney 2026：

容量决定拓扑选择： $k_{0} \geq N /2$ 时单个 Ramanujan 覆盖层即达 $Θ (lo g N)$ ； $k_{0} \geq N / lo g N$ 时叠 $L = O (lo g N)$ 层随机覆盖同样达标； $k_{0} = O (N)$ 以下分层路由至多 $O (lo g^{2} N / lo g b)$ ；
覆盖层结构： $d \approx 2 lo g_{2} N$ 的随机正则图按 Friedman 定理近似 Ramanujan，是推荐默认； $Z_{2}^{n}$ 上的代数 Cayley 覆盖因阿贝尔屏障不可行，SFM 覆盖塔是建设性替代；
长电路阈值： $R \geq 4$ 层置换路由的电路值得沿 Ramanujan 纠缠覆盖预分发 Bell 对；在线（目标未知）场景先贪心约 $0.5 lo g_{2} N$ 步、再对残差跑 Valiant。

组合矩形交换的单步实现：SLM/AOD 转移时序与矩形按序交换（图源：Constantinides 2024 Fig. 3）

实验结果与对比

四个路由 regime 的完整图景（ $N$ 原子）Courtney 2026：

拓扑	移动模型	路由深度	出处
网格	任意匹配	$Θ (N)$	Folklore（等周下界，行/列排序达成）
网格	AOD 行/列移动	$Θ (N lo g N)$	Constantinides 等
Ramanujan 超图	匹配	$Θ (lo g N)$	Courtney 2026
网格	选择性转移	$Θ (lo g N)$	Constantinides 等

协议侧，网格转移任意置换至多 $N (2 lo g_{2} N - 1)$ 步、选择性转移 $2 lo g_{2} N - 1$ 步，均饱和下界至常数因子 Constantinides 2024。NA044 的实用数字：网格叠加 4 层随机覆盖（ $d_{0} = 8$ ）在 $N = 144$ 时较纯网格加速 $2.7 \times$ ；串扰 $γ = 0.2$ 下多层容量保持约 $71%$ （层数开销约 $40%$ ）；贪心位移匹配约 $0.9 lo g_{2} N$ 步后停滞（消除约 $83%$ 位移能），贪心–Valiant 混合协议实用规模加速约 $3 \times$ ；分层路由（块 $b \approx n$ 、两层）在 $N = 256$ 时深度降至平坦方案的 $0.67$ ；预分发 Bell 对的传送路由盈亏平衡点约 $R \approx 4$ 层置换路由（ $N = 256$ 时 4.5、 $N = 40000$ 时 3.7），混合传送+物理搬运在 $N = 1024$ 达 $6 \times$ Courtney 2026。

NA040 与分区架构最强调制器的对比（2Z 架构、十个基准线路）：所提方法在全部测试线路上达到理论最少转移数（至多差 1–2），ZAC 因二部图复用模型不必达理论最优；以 QFT（ $n = 29$ ）为例，ZAC 的转移数多约 $92%$ （840 对 436），总搬运距离多约 $333%$ （34434 对 $7949 μ m$ ）；MQT 映射器仅在 PTO 数上可比 Gentil 2026。

参数与量级

量	典型值	来源
网格 AOD 路由下界/协议	$Ω (N lo g N)$ / $N (2 lo g_{2} N - 1)$ 步	Constantinides 2024
选择性转移路由	$Ω (lo g N)$ / $2 lo g_{2} N - 1$ 步	Constantinides 2024
Ramanujan 超图路由	$rt (H) = O (lo g N / (1 - β))$ ， $β < 1$	Courtney 2026
AOL 容量-深度权衡	$T = O (N / (k (1 - β)))$ ； $k = Ω (N) \Rightarrow O (lo g N)$	Courtney 2026
多层谱增益	$β (G_{\cup}) = O (1/ L d_{0})$	Courtney 2026
混合贪心–Valiant 加速	$\sim 3 \times$ ；传送混合 $6 \times$ （ $N = 1024$ ）	Courtney 2026
NA040 对比 ZAC（QFT, n=29）	转移数 $- 92%$ ，距离 $- 333%$	Gentil 2026

与其他概念的关系

重排的物理载体是镊子搬运的相干性与速度上限，见原子搬运与相干输运；装载任意目标阵列的前置步骤是原子装配无缺陷阵列，运行中的连续重排与阵列维持见原子重排与连续运行。
路由步的并行度受行/列不可交叉约束，其来源与 AOD 模型见FPQA 计算模型；把重排嵌入完整映射-调度流程的编译器有OLSQ-DPQA、DasAtom 分治搬运与Atomique 动态阵列编译。
NA040 的最少转移定理面向分区架构，同族的编译器还有PowerMove 分区架构编译与ZAP 架构与编译器。
超边=可同时 blockade 的一组原子：超图模型的物理基础是里德堡阻塞； $k_{0} \geq N /2$ 等容量阈值对应的硬件路线见大规模阵列与连续运行。

参考文献

N. Constantinides, A. Fahimniya, D. Devulapalli, D. Bluvstein, M. J. Gullans, J. V. Porto, A. M. Childs, A. V. Gorshkov, “Optimal Routing Protocols for Reconfigurable Atom Arrays”, arXiv:2411.05061 (2024). NA024 · arXiv:2411.05061
J. M. Courtney, “Permutation Routing on Ramanujan Hypergraphs with Applications to Neutral Atom Quantum Architectures”, arXiv:2605.02498 (2026). NA044 · arXiv:2605.02498
N. Gentil, R. S. Lous, A. Todri-Sanial, “General circuit mapping algorithm for neutral atom quantum computers”, arXiv:2606.20503 (2026). NA040 · arXiv:2606.20503

中性原子百科

探索

最优重排与置换路由