算法相关布局选择｜中性原子量子计算知识库

经典编译里"布局"是把逻辑比特放到给定的硬件图上；中性原子把问题倒过来——原子阵列本身可以被排成不同的二维拓扑，于是"给线路选一个阵列形状"成了编译流程最前端的新自由度，Qompose 用一个小型神经网络替线路挑选方形/两种三角拓扑中最合适的一个。

问题背景

光镊阵列的物理本性允许把原子排成几乎任意的二维图样（见原子装配无缺陷阵列），但绝大多数编译器默认方形网格（square grid）。Qompose 的作者首先用实验指出：阵列拓扑（topology）显著影响量子线路的执行——同一个算法在不同拓扑上的关键路径脉冲数与保真度可以差别巨大，而且没有一个拓扑对所有算法都最优 Silver 2024。这与FPQA 计算模型中”连接性是编译变量而非硬件常量”的论断一脉相承。

拓扑影响执行的机制是限制区（restriction zone，即里德堡阻塞导致的串扰禁区）：一个比特参与里德堡门时，其交互半径内的邻居不能同时被同样的脉冲寻址。不同排布下”谁的邻居是谁”不同，于是门能否并行、是否要插入 SWAP，都随拓扑改变。一个直观例子：在 square 与 S-triangle 上，CX(q1,q2) 与 CX(q5,q6) 无阻塞重叠、可并行；同样的两个门在 T-triangle 上却因 q1 的交互半径盖住 q5、q2 盖住 q6 而必须串行 Silver 2024。

Qompose 把候选拓扑限定为三种可以平面铺满（tessellating）的简单形状：Square（传统方格）、S-Triangle 与 T-Triangle（两种三角格子）。即便只在这个三选一的小空间里，选对拓扑的收益也已经可观——这正说明布局选择是一个此前被系统性忽视的优化维度。

理论模型

三个优化目标

Qompose 对给定线路 $U$ 与候选拓扑 $T \in {s q, s Δ, t Δ}$ 估计三个互不一致的指标：

关键路径脉冲数：里德堡门需要多个激光脉冲，关键路径上的脉冲数决定执行时长下界，误差也沿关键路径累积；
总脉冲数：所有门脉冲之和，决定总错误概率与”整条线路重来一次”的概率；
保真度：Qiskit Aer 加合成噪声模型模拟得到的线路级保真度（单比特门错误率 $0.01$ ，两/三比特门按张量幂叠加）。

同一电路在不同指标下的最优拓扑可以不同：例如 Mod5D1 基准在”保真度”指标下首选 T-Triangle，在”关键路径脉冲数”与”总脉冲数”指标下却首选 S-Triangle Silver 2024。因此单一模型无法同时最大化两个目标，Qompose 为每个指标分别训练模型。

静态电路特征

为了让模型不必真的跑一遍映射-路由-调度就能预测各拓扑的表现，Qompose 提取 14 个静态特征：电路宽度 $W = q_{a c t i v e}$ 、深度 $D$ 、门密度、纠缠方差 $E V$ 、程序通信度 $P C$ 、关键深度 $C D$ 、纠缠比 $E R$ 、单/双/三比特门比例，以及三个经典的 PageRank 统计量（均值、最大值、标准差）。核心几个的形式化定义是 Silver 2024：

ρ = \frac{G _{1 q} + 2 G _{2 q} + 3 G _{3 q}}{W \cdot D}, C D = \frac{n _{e d}}{n _{e}}, E R = \frac{n _{e}}{n _{g}},

其中 $G_{k q}$ 是 $k$ 比特门数量， $n_{e d}$ / $n_{e}$ 分别是关键路径上/全部的两比特门数， $n_{g}$ 是总门数。程序通信度 $P C = \sum_{i} d (q_{i}) / (W (W - 1))$ 是相互作用图的归一化平均度；纠缠方差 $E V$ 基于两比特门在比特上的分布统计刻画图的互联程度（互联越高、新门越可能复用旧比特）。PageRank 在线路的加权邻接矩阵上迭代至收敛（损失低于固定 $ϵ$ ），其标准差高意味着复杂性集中在少数中心比特上——这类电路往往在某种特定拓扑上更有利。

预测器

每个（拓扑，指标）组合训练一个小型回归网络：输入层 14 个神经元、两个各 15 神经元的隐藏层（ReLU）、单输出；Adam 优化器（学习率 $0.001$ ）、平均绝对误差损失、400 轮训练，5 折交叉验证（80%/20% 划分）。推理时对三个拓扑各做一次回归，取预测值最优者作为分类结果——这种”回归即分类”的做法显著优于直接训练分类器，因为各指标的相对差才是决策依据 Silver 2024。

方法与实现

流程：模型训练 → 拓扑预测 → 映射 → SWAP 插入 → DAG 调度 → 执行。训练数据是按多变量高斯参数化生成的随机指令集（20–100 条指令、宽度 5–70、可调三比特门率与单比特门率），在三种拓扑上真实调度执行后作为回归标签。

映射：先用加权邻接图找出共同出现最多的比特对，放到网格中心（ $L_{0} = ar g min_{P} \sum_{p} (P - P_{n})^{2}$ 的启发式：常用比特居中，最易被其他比特到达）；随后逐个把新比特 $q$ 放到使加权和最大的位置

L = ar g (i, j) max v \sum \frac{w ( q , v )}{( i - v _{i} ) ^{2} + ( j - v _{j} ) ^{2}},

即偏向与已放置比特权重大、距离近的空位。放完后若某门的参与比特超出交互半径，则沿最短路径逐格插入 SWAP。

调度：以抽象时间步构建依赖 DAG，每个门的时间步数按其所需脉冲数设定；每步贪心地调度所有就绪且互不阻塞的门。整个工具链开源，是第一个允许研究者系统探索中性原子拓扑权衡的实验框架 Silver 2024。

GRAPHINE。同一个团队在 SC 2023 发表的 GRAPHINE 是这条路线的前作，主张按应用生成特定用途的里德堡原子阵列（application-specific Rydberg atom arrangement）Patel 2023。本站语料未收录其提取文本，此处仅作题录级介绍；从标题即可看出其定位——把”阵列形状由应用决定”作为编译输入的一部分，Qompose 则可视为该思想在”少量实用拓扑 + 学习型选择器”上的落地与量化。

三种拓扑（Square / S-Triangle / T-Triangle）与限制区阻塞差异示意（图源：Silver 2024 Fig. 2）

实验结果与对比

评估覆盖随机线路与 19 个真实基准（VQE、QAOA、ISING、QFT15、HLF、加法器、Simon、Bernstein-Vazirani、CH/SHA-256 组件等）Silver 2024：

指标	结果	条件
关键路径脉冲数下降	$8.4%$	随机线路，相对随机选拓扑
关键路径脉冲数下降	$5.4%$	真实基准，相对随机选拓扑
关键路径相对最差拓扑加速	$19%$	随机线路，接近 Oracle
拓扑选择命中率	19 选对 18	真实基准最优拓扑
CH（SHA-256 组件）省脉冲	$32.3%$	T-Triangle 相对 S-Triangle
总脉冲数最差拓扑	Square	随机线路总体

两个结构性观察值得强调。其一，“哪个拓扑最好”随基准剧烈变化——关键路径脉冲数指标下的排名 Silver 2024：

基准	第 1	第 2	第 3
HLF	S-Triangle	Square	T-Triangle
Mult25	Square	T-Triangle	S-Triangle
QFT15	T-Triangle	S-Triangle	Square

其二，同一电路在不同指标下最优拓扑不同：Mod5D1 上保真度首选 T-Triangle，关键路径与总脉冲数却首选 S-Triangle（总脉冲数 T-Triangle 并列）Silver 2024。所以布局选择器必须与用户选定的优化目标（FoM）绑定——这与FPQA 计算模型中按能力轴切换优化目标的主张一致。

参数与量级

量	典型值	来源
候选拓扑	3 种（Square / S-Triangle / T-Triangle）	Silver 2024
神经网络	$14 - 15 - 15 - 1$ ，ReLU，Adam lr $0.001$	Silver 2024
训练轮数 / 损失	400 epochs，平均绝对误差，5 折交叉验证	Silver 2024
训练线路	随机指令集 20–100 条，宽度 5–70	Silver 2024
特征维度	14（量子描述子 + PageRank 统计 + 门占比）	Silver 2024
噪声模型	单比特门错误率 $0.01$ ，Aer $5000$ shots	Silver 2024
关键路径脉冲改进	$8.4%$ （随机）/ $5.4%$ （真实基准）	Silver 2024

与其他概念的关系

拓扑差异的物理根源是里德堡阻塞造成的限制区；交互半径与限制半径的定义在FPQA 计算模型中形式化。
布局选好之后的逻辑-物理映射与 SWAP 插入属于布局映射与长程交互利用的范畴；面向可重构（可搬运）阵列的完整映射见OLSQ-DPQA与Atomique 动态阵列编译。
“按应用定制硬件资源”的思想在门层面由Geyser：原生多比特门编译承接（按应用合成原生多比特门块），在阵列层面即 GRAPHINE。
任意形状阵列的物理实现依赖原子装配无缺陷阵列；拓扑灵活性对平台整体竞争力的意义见中性原子量子计算硬件全景。
多个编译方案之间的公平比较方法学见编译器公平评测与可视化。

参考文献

D. Silver, T. Patel, D. Tiwari, “Qompose: A Technique to Select Optimal Algorithm-Specific Layout for Neutral Atom Quantum Architectures”, arXiv:2409.19820 (2024). NA027 · arXiv:2409.19820
T. Patel, D. Silver, D. Tiwari, “GRAPHINE: Enhanced Neutral Atom Quantum Computing using Application-Specific Rydberg Atom Arrangement”, Proc. SC 2023 (2023). NA015 · DOI 10.1145/3581784.3607032
L. Schmid, D. F. Locher, M. Rispler, et al., “Computational capabilities and compiler development for neutral atom quantum processors”, Quantum Sci. Technol. 9, 035023 (2024). NA009 · arXiv:2309.08656

中性原子百科

探索

算法相关布局选择