arxiv: 2605.02498 · v2 · submitted 2026-05-04 · 🪐 quant-ph · cs.DS· math-ph· math.MP

Recognition: 3 theorem links

· Lean Theorem

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

Joshua M. Courtney

Authors on Pith no claims yet

Pith reviewed 2026-05-08 18:11 UTC · model grok-4.3

classification 🪐 quant-ph cs.DSmath-phmath.MP

keywords permutation routingRamanujan hypergraphsneutral atom quantum computingqubit routingclique expansionspectral hypergraph theoryentanglement assisted routing

0 comments

The pith

Ramanujan hypergraphs let neutral-atom qubits route permutations in Theta(log N) depth via clique-expansion matchings.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that Ramanujan (d,r)-regular hypergraphs on N vertices have routing numbers of order log N when permutations are routed by successive matchings in the associated clique expansion graph. This replaces the usual two-sided spectral gap requirement with a one-sided eigenvalue centering condition on the hypergraph. The approach is motivated by reconfigurable neutral-atom lattices, where hypergraph edges represent allowed atom moves. If the bound holds, it supplies a concrete way to achieve logarithmic-depth permutation routing at scale, together with overlay and entanglement-assisted variants that keep the depth logarithmic while controlling hardware capacity.

Core claim

The central claim is that the routing number rt(H) of a Ramanujan (d,r)-regular hypergraph H on N vertices satisfies rt(H) = Theta(log N) when routing proceeds by matchings in the clique expansion G_cl(H). The proof substitutes a one-sided centering condition on eigenvalues for Nenadov's two-sided gap hypothesis. The same spectral property is used to derive scaling results for Song-Fan-Miao coverings, a virtual-overlay capacity-depth tradeoff for 3D AOL architectures, abelian Alon-Boppana barriers on affine Cayley graphs, recursive routing lifts through towers of coverings, entanglement-assisted teleportation depth, and hierarchical multi-scale schemes with boundary-only transfers.

What carries the argument

The Ramanujan (d,r)-regular hypergraph together with its clique-expansion graph, whose one-sided eigenvalue centering supplies the spectral gap needed for the logarithmic routing bound.

If this is right

Song-Fan-Miao coverings exist and scale for Ramanujan families of every uniformity.
Multi-layer virtual overlays achieve Theta(log N) routing depth with only O(log N) independent layers in 3D AOL hardware.
Towers of k-fold Ramanujan coverings support recursive routing lifts that keep depth O(log N).
Pre-distributed Bell pairs allow entanglement-assisted routing with O(log N) teleportation depth and a stable crossover near four routing rounds.
Hierarchical multi-scale routing reaches O(log squared N / log b) depth with optimal block size b equal to Theta of the square root of n.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same hypergraph construction might supply logarithmic-depth routing primitives for other reconfigurable quantum platforms beyond neutral atoms.
The reported 15-30 percent congestion reduction via affine derandomization on non-Ramanujan Cayley graphs suggests a practical intermediate route while explicit large Ramanujan hypergraphs are being built.
The hybrid greedy-Valiant protocol that yields a factor-three speedup could be tested directly in current neutral-atom hardware to measure the gap between asymptotic and practical performance.

Load-bearing premise

Ramanujan (d,r)-regular hypergraphs exist at the required scales and the one-sided eigenvalue centering condition is enough to replace the two-sided spectral gap hypothesis in the routing analysis.

What would settle it

An explicit family of large Ramanujan hypergraphs whose clique-expansion routing number is omega(log N), or a concrete counterexample showing that the one-sided centering condition alone fails to produce the Theta(log N) bound.

Figures

Figures reproduced from arXiv: 2605.02498 by Joshua M. Courtney.

**Figure 1.** Figure 1: Dependency graph for hypergraph qubit routing results. view at source ↗

read the original 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) = \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 $\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 = \Theta(\sqrt{n})$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper reframes neutral-atom routing via Ramanujan hypergraphs to claim Θ(log N) depth, with some hardware angles that could matter if the spectral replacement holds.

read the letter

The main point is that this work casts qubit routing on reconfigurable neutral-atom lattices as permutation routing on (d,r)-regular Ramanujan hypergraphs, where routing proceeds by matchings in the clique expansion, and derives a Θ(log N) bound. The virtual overlay theorem for 3D AOL architectures and the use of pre-distributed Bell pairs for entanglement-assisted teleportation are the parts that feel most directly tied to hardware constraints and could influence design choices if the numbers check out. The integration of SFM coverings, the abelian Alon-Boppana barrier on Z_n^2 Cayley graphs, and the hybrid greedy-Valiant protocol with its reported congestion and speedup observations also show an effort to connect theory to practical scales. The hierarchical multi-scale bounds and displacement-energy analysis add some breadth. The soft spot sits in the central spectral step. Replacing Nenadov's two-sided gap hypothesis with a one-sided eigenvalue-centering condition is presented as sufficient for the routing bound, but the abstract gives no visible sketch showing that the necessary mixing or discrepancy controls survive without the lower eigenvalue bound. If any part of the argument still needs both sides, the Θ(log N) conclusion weakens. Existence of the required large Ramanujan hypergraphs is assumed rather than shown, and the 15-30% congestion and ~3x speedup figures read as empirical rather than derived outputs. The paper is aimed at researchers working on neutral-atom architectures and on expander-based algorithms for quantum hardware. Someone focused on routing bottlenecks or reconfigurable lattices would get concrete ideas from the AOL and entanglement sections even if the proofs need tightening. It deserves a serious referee because the application is timely and the reframing is a fresh combination, though revisions would almost certainly be required on the spectral details and supporting derivations.

Referee Report

2 major / 0 minor

Summary. The paper claims to prove that the routing number rt(H) of a Ramanujan (d,r)-regular hypergraph H on N vertices is Θ(log N) when routing proceeds via matchings in the clique expansion G_cl(H). It reframes neutral-atom qubit routing by substituting Nenadov's two-sided spectral-gap hypothesis with a one-sided eigenvalue-centering condition, establishes scaling for Song-Fan-Miao coverings, proves a virtual-overlay capacity-depth tradeoff for 3D AOL architectures, identifies an abelian Alon-Boppana barrier on Z_n^2 Cayley graphs, and reports empirical gains (15-30% congestion reduction, ~3x hybrid speedup, O(log N) depths) for hierarchical, entanglement-assisted, and greedy-adaptive protocols.

Significance. If the central Θ(log N) bound is rigorously established, the work supplies a spectral-hypergraph foundation for scalable permutation routing in reconfigurable neutral-atom lattices, directly addressing a key bottleneck in quantum hardware design. The explicit replacement of a two-sided gap by a one-sided centering condition, together with the virtual-overlay and hierarchical results, would constitute a substantive advance at the intersection of extremal graph theory and quantum architecture.

major comments (2)

The central derivation (reframing the routing problem via one-sided eigenvalue centering to obtain rt(H) = Θ(log N)): the manuscript must demonstrate that every step of the Nenadov-style argument that previously required a two-sided spectral gap (e.g., control of both upper and lower adjacency eigenvalues for discrepancy or mixing bounds on the sequence of matchings) continues to hold under the weaker one-sided centering condition; without an explicit verification or counter-example check, the replacement does not yet establish the claimed bound.
The statement that SFM coverings scale for Ramanujan families of every uniformity: the scaling argument is invoked to support the hierarchical multi-scale routing bounds, yet no explicit dependence on the Ramanujan parameters (d,r) or the one-sided centering is supplied, leaving the O(log N) depth claim for the tower of coverings unsupported.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thorough review and insightful comments on our manuscript arXiv:2605.02498. We address each major comment point by point below, clarifying the proofs and indicating where we will strengthen the exposition in the revised version.

read point-by-point responses

Referee: The central derivation (reframing the routing problem via one-sided eigenvalue centering to obtain rt(H) = Θ(log N)): the manuscript must demonstrate that every step of the Nenadov-style argument that previously required a two-sided spectral gap (e.g., control of both upper and lower adjacency eigenvalues for discrepancy or mixing bounds on the sequence of matchings) continues to hold under the weaker one-sided centering condition; without an explicit verification or counter-example check, the replacement does not yet establish the claimed bound.

Authors: We thank the referee for this important point. While the manuscript reframes the argument using the one-sided centering condition in place of the two-sided gap, we acknowledge that an explicit step-by-step verification of the Nenadov argument under this weaker condition would strengthen the presentation. In the revised manuscript, we will include a detailed appendix or subsection that verifies each relevant step, such as the discrepancy and mixing bounds, showing where the one-sided condition suffices due to the specific structure of the clique-expansion matchings. revision: yes
Referee: The statement that SFM coverings scale for Ramanujan families of every uniformity: the scaling argument is invoked to support the hierarchical multi-scale routing bounds, yet no explicit dependence on the Ramanujan parameters (d,r) or the one-sided centering is supplied, leaving the O(log N) depth claim for the tower of coverings unsupported.

Authors: We agree that the scaling should be stated more explicitly. The SFM covering construction preserves the Ramanujan property with the one-sided centering for any fixed uniformity r, and the depth of the tower is O(log N) with the constant depending on d and r but independent of N. In the revision, we will expand Theorem 5.1 to include the explicit dependence: the covering depth is at most C(d,r) log N, where C(d,r) is derived from the spectral gap. This supports the O(log N) hierarchical routing bound without additional assumptions. revision: yes

Circularity Check

0 steps flagged

No circularity: routing bound derived from external Ramanujan assumption and one-sided centering

full rationale

The paper proves rt(H) = Θ(log N) for Ramanujan (d,r)-regular hypergraphs by reframing routing via matchings in G_cl(H) and substituting Nenadov's two-sided spectral gap hypothesis with a one-sided eigenvalue centering condition. No equations or steps reduce the bound to a fitted parameter, self-definition, or self-citation chain by construction. The Ramanujan property, SFM coverings, and virtual overlay theorem are invoked as external inputs or prior independent results; the Θ(log N) claim follows from the stated spectral assumptions rather than tautology. Empirical observations (congestion reduction, speedup) are presented separately from the proof.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the existence and spectral properties of Ramanujan hypergraphs plus standard expander mixing lemmas; no new free parameters are introduced in the abstract, but the routing depth bounds implicitly rely on the degree and uniformity parameters being fixed while N grows.

axioms (2)

domain assumption Ramanujan (d,r)-regular hypergraphs exist for the required (d,r) and arbitrarily large N
Invoked to obtain the Θ(log N) routing number via the clique-expansion matching argument.
domain assumption One-sided eigenvalue centering condition suffices for the routing bound
Replaces Nenadov's two-sided spectral gap hypothesis; stated as the key reframing step.

pith-pipeline@v0.9.0 · 5641 in / 1515 out tokens · 47652 ms · 2026-05-08T18:11:48.414771+00:00 · methodology

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Block Permutation Routing on Ramanujan Hypergraphs for Fault-Tolerant Quantum Computing
quant-ph 2026-05 unverdicted novelty 5.0

Block permutation routing number on Ramanujan hypergraphs for surface code patches is Theta(d_C log N_L), with spectral analysis preserving key connectivity properties.

Reference graph

Works this paper leans on

44 extracted references · 7 canonical work pages · cited by 1 Pith paper

[1]

Constantinides, A

N. Constantinides, A. Fahimniya, D. Devulapalli, D. Bluvstein, M. J. Gullans, J. Porto, A. M. Childs, and A. V. Gorshkov, arXiv preprint arXiv:2411.05061 (2024)

work page arXiv 2024
[2]

Stade, L

Y. Stade, L. Schmid, L. Burgholzer, and R. Wille, in2024 IEEE International Conference on Quantum Computing and Engineering (QCE), Vol. 1 (IEEE, 2024) pp. 784–795

2024
[3]

H. Wang, P. Liu, D. B. Tan, Y. Liu, J. Gu, D. Z. Pan, J. Cong, U. A. Acar, and S. Han, in2024 ACM/IEEE 51st Annual International Symposium on Computer Architecture (ISCA) (IEEE, 2024) pp. 293–309

2024
[4]

Bluvstein, H

D. Bluvstein, H. Levine, G. Semeghini, T. T. Wang, S. Ebadi, M. Kalinowski, A. Keesling, N. Maskara, H. Pichler, M. Greiner,et al., Nature604, 451 (2022)

2022
[5]

S. J. Evered, D. Bluvstein, M. Kalinowski, S. Ebadi, T. Manovitz, H. Zhou, S. H. Li, A. A. Geim, T. T. Wang, N. Maskara,et al., Nature622, 268 (2023)

2023
[6]

Bluvstein, S

D. Bluvstein, S. J. Evered, A. A. Geim, S. H. Li, H. Zhou, T. Manovitz, S. Ebadi, M. Cain, M. Kalinowski, D. Hangleiter,et al., Nature626, 58 (2024)

2024
[7]

Wurtz, A

J. Wurtz, A. Bylinskii, B. Braverman, J. Amato-Grill, S. H. Cantu, F. Huber, A. Lukin, F. Liu, P. Weinberg, J. Long,et al., arXiv preprint arXiv:2306.11727 (2023)

work page arXiv 2023
[8]

B. W. Reichardt, A. Paetznick, D. Aasen, I. Basov, J. M. Bello-Rivas, P. Bonderson, R. Chao, W. van Dam, M. B. Hastings, A. Paz,et al., arXiv preprint arXiv:2411.1182210(2024)

work page arXiv 2024
[9]

Song, Y.-Z

Y.-M. Song, Y.-Z. Fan, and Z. Miao, arXiv preprint arXiv:2310.01771 (2023)

work page arXiv 2023
[10]

Marcus, D

A. Marcus, D. A. Spielman, and N. Srivastava, in2013 IEEE 54th Annual Symposium on Foun- dations of computer science(IEEE, 2013) pp. 529–537

2013
[11]

Nenadov, Combinatorica43, 737 (2023)

R. Nenadov, Combinatorica43, 737 (2023)

2023
[12]

L. G. Valiant, SIAM journal on computing11, 350 (1982)

1982
[13]

Joag-Dev and F

K. Joag-Dev and F. Proschan, The Annals of Statistics , 286 (1983)

1983
[14]

D. P. Dubhashi and D. Ranjan, BRICS Report Series3(1996)

1996
[15]

Leighton, B

T. Leighton, B. Maggs, and A. W. Richa, Combinatorica19, 375 (1999)

1999
[16]

Rabani and É

Y. Rabani and É. Tardos, inProceedings of the twenty-eighth annual ACM symposium on Theory of computing(1996) pp. 366–375

1996
[17]

N. Alon, F. R. Chung, and R. L. Graham, inProceedings of the twenty-fifth annual ACM sympo- sium on Theory of Computing(1993) pp. 583–591

1993
[18]

Feldman, J

P. Feldman, J. Friedman, and N. Pippenger, SIAM Journal on Discrete Mathematics1, 158 (1988)

1988
[19]

Friedman and A

J. Friedman and A. Wigderson, Combinatorica15, 43 (1995)

1995
[20]

Lubotzky, B

A. Lubotzky, B. Samuels, and U. Vishne, Israel journal of Mathematics149, 267 (2005)

2005
[21]

Friedman,A proof of Alon’s second eigenvalue conjecture and related problems(American Math- ematical Soc., 2008)

J. Friedman,A proof of Alon’s second eigenvalue conjecture and related problems(American Math- ematical Soc., 2008)

2008
[22]

Bordenave, arXiv preprint arXiv:1502.04482 (2015)

C. Bordenave, arXiv preprint arXiv:1502.04482 (2015)

work page arXiv 2015
[23]

Alon, Combinatorica6, 83 (1986)

N. Alon, Combinatorica6, 83 (1986)

1986
[24]

Yuan and S

P. Yuan and S. Zhang, Quantum9, 1757 (2025)

2025
[25]

Stade, W.-H

Y. Stade, W.-H. Lin, J. Cong, and R. Wille, in2025 IEEE/ACM International Conference On Computer Aided Design (ICCAD)(IEEE, 2025) pp. 1–9

2025
[26]

Hsieh and W.-K

S.-Y. Hsieh and W.-K. Mak, in2026 31st Asia and South Pacific Design Automation Conference (ASP-DAC)(IEEE, 2026) pp. 184–190

2026
[27]

Romão, D

F. Romão, D. Vonk, E. Giortamis, D. Sprokholt, and P. Bhatotia, arXiv preprint arXiv:2601.08504 (2026)

work page arXiv 2026
[28]

D. B. Tan, D. Bluvstein, M. D. Lukin, and J. Cong, Quantum8, 1281 (2024)

2024
[29]

Z. Guo, R. A. van Herk, E. J. Vredenbregt, and S. J. Kokkelmans, arXiv preprint arXiv:2510.09398 (2025)

work page arXiv 2025
[30]

Levine, A

H. Levine, A. Keesling, G. Semeghini, A. Omran, T. T. Wang, S. Ebadi, H. Bernien, and M. Greiner, Phys. Rev. Lett123, 170503 (2019)

2019
[31]

Ebadi, T

S. Ebadi, T. T. Wang, H. Levine, A. Keesling, G. Semeghini, A. Omran, D. Bluvstein, R. Samaj- dar, H. Pichler, W. W. Ho,et al., Nature595, 227 (2021). 23

2021
[32]

Arora, E

S. Arora, E. Hazan, and S. Kale, Theory of computing8, 121 (2012)

2012
[33]

F. R. Chung, Journal of the American Mathematical Society2, 187 (1989)

1989
[34]

Alon and V

N. Alon and V. D. Milman, Journal of Combinatorial Theory, Series B38, 73 (1985)

1985
[35]

Hoory, N

S. Hoory, N. Linial, and A. Wigderson, Bulletin of the American Mathematical Society43, 439 (2006)

2006
[36]

W. T. Tutte, Journal of the London Mathematical Society1, 107 (1947)

1947
[37]

Friedman, R

J. Friedman, R. Murty, and J.-P. Tillich, Journal of Combinatorial Theory, Series B96, 111 (2006)

2006
[38]

J. W. S. Cassels,An introduction to Diophantine approximation, 45 (CUP Archive, 1965)

1965
[39]

D. A. Carlson,Tixne-Space and Size-Space Tradeofis for Oblivious Computations, Ph.D. thesis, Brown University (1981)

1981
[40]

O.GabberandZ.Galil,inProceedings of the 20th Annual Symposium on Foundations of Computer Science, SFCS ’79 (IEEE Computer Society, USA, 1979) p. 364–370

1979
[41]

Bapat, A

A. Bapat, A. M. Childs, A. V. Gorshkov, and E. Schoute, PRX quantum4, 010313 (2023)

2023
[42]

Henriet, L

L. Henriet, L. Beguin, A. Signoles, T. Lahaye, A. Browaeys, G.-O. Reymond, and C. Jurczak, Quantum4, 327 (2020)

2020
[43]

Browaeys and T

A. Browaeys and T. Lahaye, Nature Physics16, 132 (2020)

2020
[44]

Lubotzky, R

A. Lubotzky, R. Phillips, and P. Sarnak, Combinatorica8, 261 (1988). 24

1988