arxiv: 2605.05036 · v1 · submitted 2026-05-06 · 🪐 quant-ph · cs.DS

Recognition: unknown

Block Permutation Routing on Ramanujan Hypergraphs for Fault-Tolerant Quantum Computing

Joshua M. Courtney

Authors on Pith no claims yet

Pith reviewed 2026-05-08 16:20 UTC · model grok-4.3

classification 🪐 quant-ph cs.DS

keywords block permutation routingRamanujan hypergraphssurface code patchesquotient graphfault-tolerant quantum computinglattice surgerysyndrome extraction

0 comments

The pith

Block permutation routing on hypergraphs requires Θ(d_C log N_L) depth for surface-code quantum computing.

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

The paper establishes that routing rigid blocks of d_C² atoms each, representing surface code patches, on a reconfigurable lattice takes time Θ(d_C log N_L) where N_L is the number of blocks. This is shown by modeling the lattice as a hypergraph H, forming a quotient graph with blocks as supervertices, and proving the spectral ratio stays below one in the high-connectivity regime. An upper bound follows from congestion analysis with negative association of random permutations and serialization of each phase into O(d_C) steps; a matching lower bound combines the spectral phase count with per-phase traversal cost. If correct, this makes routing the dominant but logarithmically scaling cost once syndrome extraction is optimized to constant overhead via correlated decoding and lattice surgery. The bound integrates experimental error models and extends to trapped-ion systems with junction crossings.

Core claim

For hypergraph H, code distance d_C, block size s = d_C², number of blocks N_L, and guard distance g, the block routing number satisfies rt_B(H, s, g) = Θ(d_C log N_L). The upper bound uses spectral analysis of the quotient graph Q(G_cl(H), B) showing β_Q < 1 preserved in high connectivity, negative association for congestion, and serialization; the lower bound follows from the spectral lower bound on quotient phases plus per-phase traversal cost of Ω(d_C).

What carries the argument

The quotient graph Q(G_cl(H), B) with blocks as supervertices, whose preserved spectral ratio β_Q < 1 bounds the number of routing phases.

Load-bearing premise

The spectral ratio β_Q of the quotient graph stays strictly below one when blocks are treated as supervertices in the high-connectivity regime.

What would settle it

Constructing a hypergraph satisfying the model conditions where the quotient spectral ratio β_Q reaches or exceeds one, causing measured routing time to exceed O(d_C log N_L) for large N_L, would falsify the claim.

Figures

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

**Figure 1.** Figure 1: Quotient graph construction. Left: the physical graph view at source ↗

**Figure 2.** Figure 2: Three-layer spectral argument for quotient graph expansion. Layer 1 (Theorem view at source ↗

**Figure 3.** Figure 3: Numerical validation of the Θ(dC log NL) scaling. (a) Simulated routing depth Tsim versus the theoretical prediction dC log2 NL for dC ∈ {3, 5, 7} and NL ∈ {8, 16, 32, 64}. The dashed line is T = dC log2 NL; all points lie at or below this line, confirming the upper bound. (b) Normalized ratio α = Tsim/(dC log2 NL) versus NL. The ratio is bounded away from zero and bounded above by 1, consistent with the t… view at source ↗

read the original abstract

We analyze permutation routing of rigid blocks representing surface code patches of $d_C^2$ atoms on a reconfigurable lattice with hypergraph transformations. For a hypergraph $H$, code distance $d_C$, $s=d_C^2$, number of blocks $N_L$, and guard distance $g$, we show the block routing number $\mathrm{rt}_B(H, s, g) = \Theta(d_C \log N_L)$. A spectral analysis of the quotient graph $Q(G_{\mathrm{cl}}(H), B)$ (blocks as supervertices) shows that the spectral ratio $\beta_Q < 1$ is preserved in the high-connectivity regime. Negative association of block permutations and congestion bounds are used for random intermediate configurations. Serialization establishes that each quotient routing phase requires $O(d_C)$ physical sub-steps due to the block footprint width. A lower bound $\mathrm{rt}_B = \Omega(d_C \log N_L)$ follows from combining the spectral lower bound on quotient phases with the traversal cost per phase. We include error model analysis grounded in recent experimental results, syndrome extraction protocols (stop-and-correct, rolling active fault-tolerant (AFT) measurement, and adaptive deformation), and integration with lattice surgery compilation via the Litinski protocol. Composition with the correlated-decoding scheme reduces syndrome-extraction overhead from $O(d_C)$ to $O(1)$ per correction window, leaving routing as the leading-order contributor to the integrated $O(d_C \log N_L)$ depth. Spectral inheritance is organized in a hierarchy: exact (Haemers interlacing on equitable partitions), perturbative (Weyl bounds for near-equitable partitions, a practically relevant case for surface-code patches), and universal (higher-order Cheeger). Methods extend directly to QCCD trapped-ion architectures under the same regime condition, with junction crossings replacing AOD transports as the elementary single-hop translation.

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 derives a Θ(d_C log N_L) bound on block routing for surface-code patches on Ramanujan hypergraphs, but the argument that spectral expansion survives block contraction rests on unquantified perturbation terms.

read the letter

The main thing here is the concrete scaling rt_B = Θ(d_C log N_L) for routing rigid blocks of d_C² atoms with guard distance g. If the quotient-graph analysis works, it supplies a usable overhead law for reconfigurable architectures where depth must stay controlled as the number of logical qubits grows. The paper also folds in syndrome extraction details and shows that routing remains the leading term after correlated decoding and Litinski-style lattice surgery are applied. That practical tie-in is the part that could matter to people building compilers or hardware models. What is actually new is the specific combination: treating surface-code patches as supervertices on a hypergraph, invoking the hierarchy of Haemers interlacing plus Weyl bounds plus Cheeger to claim the spectral ratio β_Q stays below 1, then adding the O(d_C) serialization cost per phase and the matching lower bound. The extension note to QCCD ion traps is a minor but clean addition. The soft spot is exactly the one the stress-test flags. Surface-code patches induce a lattice partition whose deviation from equitability scales with d_C. The abstract invokes perturbative Weyl bounds for the near-equitable case but does not supply an explicit error term showing that the second eigenvalue of the normalized quotient adjacency matrix remains strictly less than the degree once blocks are contracted. Without that quantitative control, the number of routing phases could exceed O(log N_L) for some sequences of d_C and N_L, and the Θ claim would not hold. The lower bound side looks more robust because it only needs the standard spectral lower bound on the quotient. This is for people who work on physical-layer routing and compilation overhead in fault-tolerant quantum computing, especially those already using hypergraph or expander models. A reader who wants asymptotic statements tied to concrete error-correction protocols will get something usable. It deserves a serious referee because the claim is specific, the methods are standard, and the gap is narrow enough that referees can check the perturbation bounds directly rather than reject outright. I would send it to review with a request that the authors add the explicit Weyl error term or a numerical check for representative d_C values.

Referee Report

2 major / 2 minor

Summary. The manuscript claims to establish that the block routing number rt_B(H, s, g) for permuting rigid blocks of size s = d_C² (surface-code patches) on Ramanujan hypergraphs H is Θ(d_C log N_L). The upper bound follows from spectral analysis of the quotient graph Q(G_cl(H), B) (with blocks as supervertices) showing preservation of spectral ratio β_Q < 1 in the high-connectivity regime, negative association of block permutations for congestion control, and serialization showing O(d_C) physical sub-steps per quotient phase due to block footprint. A matching Ω(d_C log N_L) lower bound combines the spectral lower bound on phases with per-phase traversal cost. The result is integrated with error models from recent experiments, syndrome extraction protocols (stop-and-correct, rolling AFT, adaptive deformation), and Litinski lattice surgery, with correlated decoding reducing syndrome overhead to O(1) and leaving routing as the leading O(d_C log N_L) term. The approach extends to QCCD trapped-ion systems.

Significance. If the central asymptotic holds, the work supplies a tight, parameter-free scaling law for routing overhead in reconfigurable fault-tolerant architectures, directly impacting compiler depth estimates for surface-code quantum computing. It applies spectral graph theory (Haemers interlacing, Weyl perturbations, Cheeger inequalities) and negative-association techniques to hypergraph block routing, while grounding the analysis in experimental error models and concrete compilation protocols. The hierarchy of spectral inheritance and the matching lower bound are notable strengths; the extension to trapped-ion architectures broadens applicability. The result could inform hardware design choices for minimizing routing as the dominant cost after decoding optimizations.

major comments (2)

[Abstract and spectral analysis] Abstract and spectral analysis section: the claim rt_B = Θ(d_C log N_L) rests on the assertion that β_Q < 1 is preserved for the quotient graph Q(G_cl(H), B) under block supervertices in the high-connectivity regime. The manuscript invokes exact Haemers interlacing for equitable partitions, perturbative Weyl bounds for near-equitable partitions (relevant for surface-code patches), and universal Cheeger inequalities, but provides no explicit quantitative error term bounding the Weyl perturbation when the lattice partitioning deviates from equitability by an amount scaling with d_C. Without such a bound, it is possible that β_Q ≥ 1 for some sequences of d_C or N_L, rendering the number of routing phases super-logarithmic and collapsing the Θ(log N_L) factor. This is load-bearing for both the upper and lower bounds.
[Serialization and physical sub-steps] The serialization argument establishing O(d_C) physical sub-steps per quotient phase (due to block footprint width) is stated without a concrete accounting of how guard distance g and hypergraph transformations interact with the block size s = d_C² during AOD or junction crossings; an explicit per-phase cost derivation would be needed to confirm the overall Θ(d_C log N_L) scaling.

minor comments (2)

[Abstract] The notation rt_B(H, s, g) is used in the abstract before being defined; a brief parenthetical definition on first use would improve readability.
[Error model analysis] The error-model section references 'recent experimental results' without citing specific papers or datasets; adding 1-2 key references would strengthen grounding.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and valuable comments on our manuscript. We address the two major comments point by point below, providing clarifications and committing to revisions that strengthen the presentation of the spectral bounds and serialization analysis.

read point-by-point responses

Referee: [Abstract and spectral analysis] Abstract and spectral analysis section: the claim rt_B = Θ(d_C log N_L) rests on the assertion that β_Q < 1 is preserved for the quotient graph Q(G_cl(H), B) under block supervertices in the high-connectivity regime. The manuscript invokes exact Haemers interlacing for equitable partitions, perturbative Weyl bounds for near-equitable partitions (relevant for surface-code patches), and universal Cheeger inequalities, but provides no explicit quantitative error term bounding the Weyl perturbation when the lattice partitioning deviates from equitability by an amount scaling with d_C. Without such a bound, it is possible that β_Q ≥ 1 for some sequences of d_C or N_L, rendering the number of routing phases super-logarithmic and collapsing the Θ(log N_L) factor. This is load-bearing for both the upper and lower bounds.

Authors: We agree that an explicit quantitative error term for the Weyl perturbation would make the argument more rigorous and address the concern about potential sequences where β_Q might approach or exceed 1. Although the high-connectivity regime of Ramanujan hypergraphs and the controlled deviation (scaling as O(d_C) but normalized by the expansion properties) ensure β_Q < 1 - δ for some δ > 0 independent of N_L, we did not include a fully explicit bound in the original manuscript. In the revision, we will add a new lemma in the spectral analysis section that derives a quantitative Weyl bound: specifically, the perturbation in the spectral ratio is at most O( (d_C / λ) ) where λ is the Ramanujan eigenvalue gap, showing that for the relevant parameter regime (d_C << sqrt(N_L) or similar), β_Q remains bounded away from 1 by a constant margin. This preserves the O(log N_L) number of phases. We will also verify this with a small numerical example for moderate d_C. revision: yes
Referee: [Serialization and physical sub-steps] The serialization argument establishing O(d_C) physical sub-steps per quotient phase (due to block footprint width) is stated without a concrete accounting of how guard distance g and hypergraph transformations interact with the block size s = d_C² during AOD or junction crossings; an explicit per-phase cost derivation would be needed to confirm the overall Θ(d_C log N_L) scaling.

Authors: We acknowledge that the original manuscript states the O(d_C) cost without a fully detailed step-by-step derivation accounting for the interactions between g, the hypergraph transformations, and the block size s = d_C². To address this, we will expand the serialization subsection to include an explicit per-phase cost analysis. This will detail: (1) the number of single-hop translations needed to move a block of width d_C while maintaining guard distance g, (2) how AOD beam movements or junction crossings are serialized to avoid collisions, and (3) why the total physical sub-steps per quotient phase is bounded by O(d_C) rather than higher. This derivation will confirm that the per-phase cost is indeed linear in d_C, yielding the overall Θ(d_C log N_L) scaling when combined with the spectral bound on the number of phases. The revised text will include a figure illustrating the block movement sequence. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation applies external spectral theorems to hypergraph structure

full rationale

The central claim rt_B(H, s, g) = Θ(d_C log N_L) is obtained by combining an upper bound from quotient-graph expansion (via Haemers interlacing on equitable partitions, Weyl perturbation for near-equitable surface-code blocks, and Cheeger inequalities) with a matching lower bound from spectral expansion plus per-phase traversal cost O(d_C). These steps invoke standard results on Ramanujan hypergraphs and equitable partitions rather than any self-referential definition, fitted parameter renamed as prediction, or load-bearing self-citation chain. The preservation of β_Q < 1 is asserted as a consequence of the hypergraph's expansion properties under the stated regime, not by construction from the routing number itself. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard properties of Ramanujan hypergraphs and spectral interlacing theorems applied to the quotient graph; no free parameters are fitted and no new entities are postulated.

axioms (1)

domain assumption Spectral gap properties of Ramanujan hypergraphs and Haemers interlacing on equitable partitions hold for the block quotient graph
Invoked to preserve β_Q < 1 in the high-connectivity regime

pith-pipeline@v0.9.0 · 5647 in / 1205 out tokens · 55797 ms · 2026-05-08T16:20:42.547216+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

50 extracted references · 8 canonical work pages · 1 internal anchor

[1]

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
[2]

Bluvstein, A

D. Bluvstein, A. A. Geim, S. H. Li, S. J. Evered, J. P. Bonilla Ataides, G. Baranes, A. Gu, T. Manovitz, M. Xu, M. Kalinowski,et al., Nature649, 39 (2026). 18

2026
[3]

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
[4]

Quantum error correction below the surface code threshold.arXiv preprint arXiv:2408.13687, 2024

R. Acharya, L. Aghababaie-Beni, I. Aleiner, T. Andersen, M. Ansmann, F. Arute, K. Arya, A. Asfaw, N. Astrakhantsev, J. Atalaya,et al., arXiv preprint arXiv:2408.13687 (2024)

work page arXiv 2024
[5]

Nature614, 676 (2023)

2023
[6]

M. Cain, C. Zhao, H. Zhou, N. Meister, J. P. B. Ataides, A. Jaffe, D. Bluvstein, and M. D. Lukin, Physical Review Letters133, 240602 (2024)

2024
[7]

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
[8]

J. M. Courtney, Permutation routing on ramanujan hypergraphs with applications to neutral atom quantum architectures (2026), arXiv:2605.02498 [quant-ph]

work page internal anchor Pith review Pith/arXiv arXiv 2026
[9]

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
[10]

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
[11]

W. H. Haemers, Linear Algebra and its applications226, 593 (1995)

1995
[12]

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

1982
[13]

Leighton, B

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

1999
[14]

Dennis, A

E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, Journal of Mathematical Physics43, 4452 (2002)

2002
[15]

A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, Physical Review A—Atomic, Molecular, and Optical Physics86, 032324 (2012)

2012
[16]

I. Cong, H. Levine, A. Keesling, D. Bluvstein, S.-T. Wang, and M. D. Lukin, Physical Review X 12, 021049 (2022)

2022
[17]

L. Z. Cohen, I. H. Kim, S. D. Bartlett, and B. J. Brown, Science Advances8, eabn1717 (2022)

2022
[18]

Yuan and S

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

2025
[19]

D. M. Kornhauser,Coordinating pebble motion on graphs, the diameter of permutation groups, and applications, Master’s thesis, Massachusetts Institute of Technology (1984)

1984
[20]

Yu, arXiv preprint arXiv:1205.5263 (2012)

J. Yu, arXiv preprint arXiv:1205.5263 (2012)

work page arXiv 2012
[21]

Aichholzer, E

O. Aichholzer, E. D. Demaine, M. Korman, J. Lynch, A. Lubiw, Z. Masárová, M. Rudoy, V. V. Williams, and N. Wein, arXiv preprint arXiv:2103.06707 (2021)

work page arXiv 2021
[22]

Yang, Discrete mathematics311, 1290 (2011)

C. Yang, Discrete mathematics311, 1290 (2011)

2011
[23]

Wang, D.-Y

J. Wang, D.-Y. Huang, X.-L. Zhou, Z.-M. Shen, S.-J. He, Q.-Y. Huang, Y.-J. Liu, C.-F. Li, and G.-C. Guo, Physical review letters134, 240802 (2025)

2025
[24]

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
[25]

K.-C. Chen, F. Burt, S. Yu, C.-Y. Liu, M.-H. Hsieh, and K. K. Leung, in2025 IEEE International Symposium on Circuits and Systems (ISCAS)(IEEE, 2025) pp. 1–5

2025
[26]

A. W. Marcus, D. A. Spielman, and N. Srivastava, Annals of Mathematics , 327 (2015)

2015
[27]

Song, Y.-Z

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

work page arXiv 2023
[28]

Q. Xu, J. P. Bonilla Ataides, C. A. Pattison, N. Raveendran, D. Bluvstein, J. Wurtz, B. Vasić, M. D. Lukin, L. Jiang, and H. Zhou, Nature Physics20, 1084 (2024)

2024
[29]

Y. Wu, S. Kolkowitz, S. Puri, and J. D. Thompson, Nature communications13, 4657 (2022)

2022
[30]

Kielpinski, C

D. Kielpinski, C. Monroe, and D. J. Wineland, Nature417, 709 (2002)

2002
[31]

J. M. Pino, J. M. Dreiling, C. Figgatt, J. P. Gaebler, S. A. Moses, M. Allman, C. Baldwin, M. Foss-Feig, D. Hayes, K. Mayer,et al., Nature592, 209 (2021)

2021
[32]

S. A. Moses, C. H. Baldwin, M. S. Allman, R. Ancona, L. Ascarrunz, C. Barnes, J. Bartolotta, B. Bjork, P. Blanchard, M. Bohn,et al., Physical Review X13, 041052 (2023)

2023
[33]

Y. Wan, D. Kienzler, S. D. Erickson, K. H. Mayer, T. R. Tan, J. J. Wu, H. M. Vasconcelos, S. Glancy, E. Knill, D. J. Wineland,et al., Science364, 875 (2019). 19

2019
[34]

Murali, D

P. Murali, D. M. Debroy, K. R. Brown, and M. Martonosi, in2020 ACM/IEEE 47th Annual International Symposium on Computer Architecture (ISCA)(IEEE, 2020) pp. 529–542

2020
[35]

A. E. Brouwer and W. H. Haemers,Spectra of graphs(Springer Science & Business Media, 2011)

2011
[36]

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
[37]

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
[38]

Bhatia,Matrix analysis(Springer Science & Business Media, 2013)

R. Bhatia,Matrix analysis(Springer Science & Business Media, 2013)

2013
[39]

T. C. Kwok, L. C. Lau, Y. T. Lee, S. Oveis Gharan, and L. Trevisan, inProceedings of the forty-fifth annual ACM symposium on Theory of computing(2013) pp. 11–20

2013
[40]

Alon, Combinatorica6, 83 (1986)

N. Alon, Combinatorica6, 83 (1986)

1986
[41]

Joag-Dev and F

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

1983
[42]

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

1996
[43]

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

1989
[44]

Hoory, N

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

2006
[45]

Litinski, Quantum3, 128 (2019)

D. Litinski, Quantum3, 128 (2019)

2019
[46]

Horsman, A

D. Horsman, A. G. Fowler, S. Devitt, and R. V. Meter, New Journal of Physics14, 123011 (2012)

2012
[47]

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
[48]

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
[49]

Florescu, R

C. Florescu, R. Kyng, M. P. Gutenberg, and S. Sachdeva, arXiv preprint arXiv:2406.07252 (2024)

work page arXiv 2024
[50]

Ryan-Anderson, J

C. Ryan-Anderson, J. G. Bohnet, K. Lee, D. Gresh, A. Hankin, J. P. Gaebler, D. Francois, A. Chernoguzov, D. Lucchetti, N. C. Brown,et al., Physical Review X11, 041058 (2021). 20

2021