Permutation Routing on Ramanujan Hypergraphs with Applications to Neutral Atom Quantum Architectures

Courtney, Joshua M. · 2026

| 编号 NA044 | 主题 编译、布局与调度 |

摘要

摘要保留原文（英文）

摘要取自 arXiv / 出版方元数据，未作翻译，以保证与原文一致。

2026 · 预印本；未核实后续正式发表 We consider the routing of neutral atoms on a reconfigurable lattice in terms of hypergraph transformations. We prove the routing number of a Ramanujan $(d,r)$-regular hypergraph on $N$ vertices satisfies $\mathrm{rt}(H)=\Theta (\log N)$, where routing is via matchings in the clique expansion graph $G_{\mathrm{cl}}(H)$. Hypergraphs reframe the qubit routing problem by replacing Nenadov’s two-sided spectral gap hypothesis with a one-sided condition based on eigenvalue centering. Song—Fan—Miao (SFM) coverings scale for Ramanujan families of every uniformity. A virtual overlay theorem establishes a capacity—depth tradeoff for 3D acousto-optic lens (AOL) architectures, with multi-layer stacking achieving $\Theta (\log N)$ routing with $L=O(\log N)$ independent overlay layers. An abelian Alon—Boppana barrier shows that fixed-degree Cayley graphs on ${\mathbb{Z}}_n^2$ cannot be Ramanujan and affine derandomization on such graphs achieves 15—30% congestion reduction. Towers of $k$-fold Ramanujan coverings yield $(H_L)=O(\log N)$ by recursive routing lift. Entanglement-assisted routing by pre-distributed Bell pairs achieves $O(\log N)$ teleportation depth with a stable crossover at $\sim 4$ routing rounds. Displacement energy analyzes greedy adaptive routing, identifying stalling and a hybrid greedy—Valiant protocol achieving $\sim 3\times$ speedup at practical scales. Hierarchical multi-scale routing achieves $O({\log }^{2}N/\log b)$ depth with boundary-only transfers at capacity $k=O(\sqrt{N}\log N)$, and $O(\log N)$ depth with optimal block size $b=\Theta (\sqrt{n})$.

全文共 24 页；文本提取件位于 .extracted/papers/NA044.txt（不随站点发布）。

本站词条在引用该文献时，会以 wikilink（sources/NA044）链接到本页；右侧「反向链接」面板自动列出所有引用它的词条。