可重排原子阵列的最优 Routing 算法
Abstract. 本文是 2411.05061 的阅读笔记。
问题设定
考虑习见的中心原子阵列量子计算机上的由 SLM 固定的原子阵列，并配备 AOD 移动。现在想要用 AOD 实现原子的重排。
问题 1（Atom Array Reconfiguration）. $S$ 是编号为 $0, 1, …, N - 1$ 的原子组成的集合。令 $\sigma: S\rightarrow S$ 是一个置换。每次你可以选择 $S$ 的一个满足某些规则的子集，用 AOD 拖动对应的原子，将其移动到指定的位置，以实现将置换 $\sigma$。
此处 AOD 移动有两种模型。
- (Grid Transfer) 习见的 AOD 移动操作；
- (Selective Transfer) 你可以在 SLM 上照射某种激光以加深势阱，从而实现不拉走被 AOD 子矩阵照射的某些原子。
1D Routing Protocol
我们考虑一个 $1\times n$ 的布满原子的 SLM 阵列。不妨再假设我们还有一个 $1\times n$ 的全空闲 SLM 阵列作为交换空间。那么现在明显有一个 $O(\log n)$ 次 AOD 操作的重排算法，即直接快速排序。
可以证明这个算法达到了理论下界。理论下界是相当显然的。设 $\boldsymbol{p}^i = p_1^i, …, p_n^i$ 指示了当前第 $i$ 个 SLM 里面放的原子编号，$\mathcal{R}(\boldsymbol{p})$ 为其最长反链。若你只用 AOD 拉了 $j \leq |\mathcal{R}(\boldsymbol{p}^i)| / 2$ 个原子，那么其他 $|\mathcal{R}(\boldsymbol{p}^i)| / 2$ 个原子的位置关系分毫未变；若你拉了 $j > |\mathcal{R}(\boldsymbol{p}^i)|$ 个原子，那么这 $j$ 个原子的相对位置不能改变。总而言之，有
$$
\mathcal{R}(\boldsymbol{p}^i) \geq 2\mathcal{R}(\boldsymbol{p}^{i + 1})
$$
注意 $\mathcal{R}(\boldsymbol{p}^1)$ 可以是 $n$（逆序排列），而 $\mathcal{R}(\boldsymbol{p}^T)$ 必须是 $1$，因此 $T = \Omega(\log n)$。
2D Routing Protocol
不失一般性地假设我们有 $N = 2^d$ 个原子，其中 $d$ 为偶数。这 $N$ 个原子被囚禁于一个 $\sqrt N\times \sqrt N$ 网格的第 $(i, j)$ 号位置上的原子编号为 $i_2j_2$，即 $i, j$ 的二进制的拼接。此外还是假设你有一个一模一样的空辅助 SLM 阵列摆在旁边。
论文是怎么做的我没仔细看，但是我感觉下面这个算法也可以：这里的核心想法是对行和列分别运行 1D Protocol。如果你只允许 Grid Transfer，不妨逐行完成 1D Routing。复杂度为 $O(\sqrt N\log n)$。如果你允许 Selective Transfer，那么一次就可以完成每行的重排，复杂度为 $O(\log n)$。后者显然达到了下界，因为这不弱于 $1\times \sqrt N$ 的 1D 重排。接下来着重证明前者也到了下界。
对于前者我们考虑一个信息论证明。每次 AOD 操作时，你可以选择一个 $i\times j$（其中 $i, j\leq m = \sqrt N$）的矩阵，将其拉到辅助空间上的一个 $i\times i$ 的位置上。总的合法操作方法的可能性数 $k$ 有
$$
k \leq \sum_{i = 0}^m\sum_{j = 0}^m \binom mi^2\binom mj^2 \leq \binom{2m}{m}^2 \leq (2e)^{4m}
$$
那么 $T$ 步操作能够产生的可能排列总数要求为
$$
\frac{k^{T + 1} - k}{k - 1} \geq (m^2)!
$$
这就要求
$$
T\log k = \Omega(m^2\log m)
$$
解出 $T = \Omega(m\log m) = \Omega(\sqrt N\log N)$。因此算法 $1$ 也是紧的。