中性 Rydberg 原子量子计算编译的 Elona 算法
中性 Rydberg 原子量子计算机的建模
暂略。
保真度建模
考虑三个错误源：门、转移量子比特、量子比特退相干。将最终的保真度建模成
$$
f = (f_1)^{g_1}\cdot (f_2)^{g_2}\cdot (f_{exc})^{|Q|S - 2g_2}\cdot (f_{trans})^{N_{trans}}\cdot \prod_{q\in Q}\left(1 - \frac{T_q}{T_2}\right)
$$
其中各量的含义如下：
- $Q$：总的量子比特数；
- $f_1$：单量子比特门的保真度，为 $99.97%$；
- $f_2$：双量子比特门的保真度，为 $99.5%$；
- $f_{exc}$：其他量子比特也可能被双量子比特照射的激光激活，这将导致额外的保真度损失。其取值为 $99.75%$；
- $f_{trans}$：用 AOD 转移量子比特带来的保真度损失，为 $99.9%$；
- $T_q$：某个量子比特的闲置时间。
- $g_1, g_2, N_{trans}$ 等为操作次数，据其底数可推断是什么操作的次数。
线路规划（Scheduling）
在线路规划阶段，仅重点考虑优化作用双量子比特门带来的误差。回忆在中性 Rydberg 原子量子计算中，双量子比特门的作用是依靠照射全局的 Rydberg Laser，因此在保证线路正确的前提下，可尝试将若干个门划作一个 stage，同时完成双量子比特门。
首先考虑一个特例，即我们已经将整个线路划分成若干个内部可交换的组（commutation group）。仅在组内做优化，无非是一个边染色问题。每次，我们对一种颜色的同色边对应的 qubit 照射 Rydberg Laser 来作用双量子比特门，便可最小化 $g_2$。以下为图论近似算法中的经典结果：
定理（Misra-Gries）. 对于任意的图 $G$，令 $\chi(G) = \Delta$，存在一个多项式时间的算法，输出 $G$ 的一个边染色，其使用的颜色数不超过 $\Delta + 1$。
证明. 暂略。
对于最为一般的电路，假设任意两个（被施加于一个公共的比特的）门都不可交换，可以建立一个 DAG，然后用 bfs 给此 DAG 分层，每次对一层的门作用的 qubit 照射 Rydberg Laser。
量子比特放置（Placement）
考虑到移动量子比特需要一定的时间，从而导致另一个巨大的误差源——退相干时间。因此，我们需要最小化一个门作用的两个量子比特之间的距离，即最小化：
$$
\sum_{g\in G} w_g\cdot \mathrm{dis}(m(q), m(q’))
$$
其中 $m(\cdot)$ 表示量子比特放置的位置，$\mathrm{dis}$ 为欧几里得距离，$w_g$ 为一个权重。注意，这个目标是一个启发式的目标，因为实际上多个量子比特可以被同时移动，但是优化此目标也不无道理。
引入 $w_g$ 的动机是：在下一个 stage，我们可能会再重新 place 一次量子比特。因此最早作用的几个门更需要立即被考虑。我们将 $w_g$ 设置为：
$$
w_g = \max(0.1, 1 - s_g)
$$
其中 $s_g$ 为 $g$ 所在的 stage 的编号。现在我们将问题建模成了一个组合优化，并且附有一个良好的权值函数，原论文直接选择使用模拟退火来优化之。
量子比特路由（routing）
这一步是在给定量子比特位置的情况下，用尽可能少的 AOD 操作来把上一个 stage 中的 qubit 全都拉到下一个 stage 的对应位置。
根据 AOD 的要求，可以断定哪些 qubit 对不能是同一次 AOD Move 的操作对象。据此，可以建立一张图，称作冲突表。最少的 AOD 操作次数，无非是冲突表的色数。
文章采取每次找最大独立集（solver）乃至直接找极大独立集（手搓）的方法来贪心近似。