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

• URL: http://arxiv.org/abs/2605.05036v1
• Date: Wed, 06 May 2026 15:29:08 GMT
• Title: Block Permutation Routing on Ramanujan Hypergraphs for Fault-Tolerant Quantum Computing
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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) = Θ(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 $β_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 = Ω(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.

Related papers

• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  Empirical risk on datasets naturally exhibits similarities in $N=nm$ total samples.<n>We provide an analysis that avoids pessimistic convergence analysis.<n>Our results improve existing state-of-the-art regimes.
  arXiv  Detail & Related papers  (2026-06-14T14:11:07Z)
• Information-Theoretic Bounds for Sparse Covariance Estimation in the Vertical-Split Distributed Model [10.026496861838448]
  We show that imposing elementwise $s$-sparsity on the cross-covariance $C_21$ can reduce the required communication and sample complexity.<n>We establish a matching scheme based on covering-net quantization and entry-wise hard thresholding, that attains the $s$-sparse lower bound up to polylogarithmic factors.
  arXiv  Detail & Related papers  (2026-06-05T10:25:12Z)
• Permutation Routing on Ramanujan Hypergraphs with Applications to Neutral Atom Quantum Architectures [0.0]
  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.
  arXiv  Detail & Related papers  (2026-05-04T11:49:16Z)
• Deterministic Realization of Classical Dissipation on Quantum Computers [0.0]
  Lattice Boltzmann (LB) on quantum devices must reconcile unitary gate evolution with the dissipative emph collide step.<n>In the multiple-relaxation-time (MRT) class, we work in the common setting of emphmodewise diagonal moment relaxation, $m_r'=_r,m_r$ with $_rin[-1,1]$.<n>The main result is the dissipative MRT block; construction of the equilibrium moment vector$mmathrmeq=Mfmathrm
  arXiv  Detail & Related papers  (2026-04-28T09:36:40Z)
• Structural Analysis of Directional qLDPC Codes [5.685589351789461]
  Directional codes, recently introduced by Gehér--Byfield--Ruban citeGeher2025Directional, constitute a hardware-motivated family of quantum low-density parity-check (qLDPC) codes.<n>These codes are defined by stabilizers measured by ancilla qubits executing a fixed emphdirection word (route) on square- or hex-grid connectivity.
  arXiv  Detail & Related papers  (2026-02-22T05:59:57Z)
• Robust Sublinear Convergence Rates for Iterative Bregman Projections [21.689846521201588]
  We use entropic regularization to approximate linear programs whose constraints split into two (or more) tractable blocks.<n>We derive the flow-Sinkhorn algorithm for the Wasserstein-1 distance on graphs.
  arXiv  Detail & Related papers  (2026-02-01T18:20:19Z)
• Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
  We present a $textbfMA-OSMA$ algorithm to transfer the discrete submodular problem into a continuous optimization.<n>We also introduce a projection-free $textbfMA-OSEA$ algorithm, which effectively utilizes the KL divergence by mixing a uniform distribution.<n>Our algorithms significantly improve the $(frac11+c)$-approximation provided by the state-of-the-art OSG algorithm.
  arXiv  Detail & Related papers  (2025-02-07T15:57:56Z)
• Matching the Statistical Query Lower Bound for $k$-Sparse Parity Problems with Sign Stochastic Gradient Descent [83.85536329832722]
  We solve the $k$-sparse parity problem with sign gradient descent (SGD) on two-layer fully-connected neural networks.<n>We show that this approach can efficiently solve the $k$-sparse parity problem on a $d$-dimensional hypercube.<n>We then demonstrate how a trained neural network with sign SGD can effectively approximate this good network, solving the $k$-parity problem with small statistical errors.
  arXiv  Detail & Related papers  (2024-04-18T17:57:53Z)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  We consider a model where a dense cycle with expected bandwidth $n tau$ and edge density $p$ is planted in an ErdHos-R'enyi graph $G(n,q)$. We characterize the computational thresholds for the associated detection and recovery problems for the class of low-degree algorithms.
  arXiv  Detail & Related papers  (2023-02-13T22:51:07Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  We propose a novel method named Multi-block-probe Variance Reduced (MSVR) to alleviate the complexity of compositional problems. Our results improve upon prior ones in several aspects, including the order of sample complexities and dependence on strongity.
  arXiv  Detail & Related papers  (2022-07-18T12:03:26Z)
• Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity [121.83085611327654]
  We structured convex optimization problems with additive objective $r:=p + q$, where $r$ is $mu$-strong convex similarity. We proposed a method to solve problems master to agents' communication and local calls. The proposed method is much sharper than the $mathcalO(sqrtL_q/mu)$ method.
  arXiv  Detail & Related papers  (2022-05-30T14:28:02Z)
• Projection-free Graph-based Classifier Learning using Gershgorin Disc Perfect Alignment [59.87663954467815]
  In graph-based binary learning, a subset of known labels $hatx_i$ are used to infer unknown labels. When restricting labels $x_i$ to binary values, the problem is NP-hard. We propose a fast projection-free method by solving a sequence of linear programs (LP) instead.
  arXiv  Detail & Related papers  (2021-06-03T07:22:48Z)

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.