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

• URL: http://arxiv.org/abs/2605.02498v2
• Date: Tue, 05 May 2026 13:35:01 GMT
• Title: Permutation Routing on Ramanujan Hypergraphs with Applications to Neutral Atom Quantum Architectures
• Abstract summary: We consider the routing of neutral atoms on a reconfigurable lattice in terms of hypergraph transformations.<n>Hypergraphs reframe the qubit routing problem by replacing Nenadov's two-sided spectral gap hypothesis with a one-sided condition based on eigenvalue centering.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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) = Θ(\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 $Θ(\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 $\mathrm(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 = Θ(\sqrt{n})$.

Related papers

• Asymptotically Optimal Depth Fermionic Permutation on 2D Grid Quantum Architecture without Ancillas [1.0712892191688657]
  Simulating fermionic systems on qubit hardware involves many nonlocal interactions.<n>Recent works reduce this Jordan-Wigner routing overhead to polylogarithmic depth under all-to-all connectivity.<n>We present a fermionic permutation protocol tailored to 2D grid architectures that achieves the optimal $O(sqrtN)$ depth.
  arXiv  Detail & Related papers  (2026-05-25T17:07:47Z)
• Block Permutation Routing on Ramanujan Hypergraphs for Fault-Tolerant Quantum Computing [0.0]
  We analyze permutation routing of rigid blocks representing surface code patches of $d_C2$ atoms on a reconfigurable lattice.<n>A spectral analysis of the quotient graph $Q(G_mathrmcl(H), B)$ shows that the spectral ratio $_Q 1$ is preserved in the high-connectivity regime.
  arXiv  Detail & Related papers  (2026-05-06T15:29:08Z)
• Low-depth fermion routing without ancillas [32.445850550281726]
  We show that fermion routing can be performed in depth $O(log2 N)$ emph without ancillas, measurements, or feedforward.<n>We construct efficient mappings with $O(log2 N)$ depth between all product-preserving ternary tree fermionic encodings.
  arXiv  Detail & Related papers  (2025-10-06T17:59:13Z)
• Quantum Speedups for Polynomial-Time Dynamic Programming Algorithms [4.832760917132771]
  We introduce a quantum dynamic programming framework that allows us to directly extend to the quantum realm a large body of classical dynamic programming algorithms.<n>The corresponding quantum dynamic programming algorithms retain the same space complexity as their classical counterpart, while achieving a computational speedup.
  arXiv  Detail & Related papers  (2025-07-01T14:55:18Z)
• Quantum Routing and Entanglement Dynamics Through Bottlenecks [1.1936126505067601]
  We consider the entanglement dynamics and routing between two regions only connected through an intermediate "bottleneck" region with few qubits.<n>We show an upper bound on the average amount of bipartite entanglement between $L$ and $C,R$ that can be generated in time $t$ by such architecture-respecting Hamiltonians.<n>We also show that, in systems of free particles, we can route optimally on the star graph in time $Theta(sqrtN)$ using Hamiltonian quantum routing.
  arXiv  Detail & Related papers  (2025-05-22T17:33:11Z)
• Implicit Hypersurface Approximation Capacity in Deep ReLU Networks [0.0]
  We develop a geometric approximation theory for deep feed-forward neural networks with ReLU activations. We show that a deep fully-connected ReLU network of width $d+1$ can implicitly construct an approximation as its zero contour.
  arXiv  Detail & Related papers  (2024-07-04T11:34:42Z)
• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
  We study the problem of gradient descent learning of a single-index target function $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$<n>We prove that a two-layer neural network optimized by an SGD-based algorithm learns $f_*$ with a complexity that is not governed by information exponents.
  arXiv  Detail & Related papers  (2024-06-03T17:56:58Z)
• Optimal and Efficient Algorithms for Decentralized Online Convex Optimization [51.00357162913229]
  Decentralized online convex optimization (D-OCO) is designed to minimize a sequence of global loss functions using only local computations and communications.<n>We develop a novel D-OCO algorithm that can reduce the regret bounds for convex and strongly convex functions to $tildeO(nrho-1/4sqrtT)$ and $tildeO(nrho-1/2log T)$.<n>Our analysis reveals that the projection-free variant can achieve $O(nT3/4)$ and $O(n
  arXiv  Detail & Related papers  (2024-02-14T13:44:16Z)
• Scalable Quantum Networks: Congestion-Free Hierarchical Entanglement Routing with Error Correction [0.0]
  Quantum Tree Networks (QTN) is an architecture for hierarchical multi-flow entanglement routing. Network design is a $k$-ary tree where end nodes are situated on the leaves and routers at the internal nodes. Our network-level simulations demonstrate a size-independent threshold behavior of QTNs.
  arXiv  Detail & Related papers  (2023-06-15T15:52:08Z)
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
  We show that a novel deterministic method for preparing arbitrary quantum states requires fewer quantum resources than previous methods. We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations.
  arXiv  Detail & Related papers  (2023-03-03T18:23:20Z)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  We study the episodic reinforcement learning (RL) problem modeled by finite-horizon Markov Decision Processes (MDPs) with constraint on the number of batches. We design a computational efficient algorithm to achieve near-optimal regret of $tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot) hides logarithmic terms of $(S,A,H,K)$ in $K$ episodes. Our technical contribution are two-fold: 1) a near-optimal design scheme to explore
  arXiv  Detail & Related papers  (2022-10-15T09:22:22Z)
• On the Optimal Memorization Power of ReLU Neural Networks [53.15475693468925]
  We show that feedforward ReLU neural networks can memorization any $N$ points that satisfy a mild separability assumption. We prove that having such a large bit complexity is both necessary and sufficient for memorization with a sub-linear number of parameters.
  arXiv  Detail & Related papers  (2021-10-07T05:25:23Z)
• Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
  We show that a given suboptimality $epsilon0$ is achieved master/workers networks in $Omegabig. We then propose algorithms matching the lower bounds either types of networks (up to log-overs) We assess effectiveness of the proposed algorithms on a robust logistic regression problem.
  arXiv  Detail & Related papers  (2021-07-22T14:25:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.