1 Introduction↩︎

Recent demonstrations of quantum low-density parity check (qLDPC) code architectures [1]–[3] substantially reduce physical-qubit overhead for fault-tolerant quantum computation compared to surface codes, realizing a constant overhead [4]. These works use routing primitives moving qubits between data and ancilla positions across each syndrome extraction cycle. While syndrome-extraction circuit depth (number of CNOT layers) is well-understood for these codes [5], [6], atom-rearrangement depth required to support each circuit layer has yet to be characterized in terms of the underlying Tanner graph spectrum. Impetus for this characterization stems from both hardware runtime bottlenecks in atom/ion reconfigurations and assessing the potential advantage of incorporating an effective third dimension to reduce routing overhead in neutral atom and trapped ion qubit architectures.

We give a closed-form formula \(\beta_{\mathrm{HGP}}= (1 + \beta_{\mathrm{base}})/2\) and an exact diameter identity \(D_T= 2 D_{\mathrm{base}}\) for hypergraph-product/lifted-product (HGP/LP) code Tanner graphs (Sec. 3). Using Fourier diagonalization (Theorem 5), we reduce the bivariate bicycle (BB) Tanner graph spectrum to \(lm\) independent \(2 \times 2\) singular-value decompositions, and prove that no scalar \((1+\beta_{\mathrm{base}})/2\)-style one-liner holds for BB codes. We give a syndrome-extraction protocol and depth bound for a 2D acousto-optic deflector (AOD) atom array augmented with \(L_{\mathrm{layers}}\) stacked 3D acousto-optic lens (AOL) planes, applicable uniformly to HGP, LP, and BB codes (Sec. 4). Section 5 gives a numerical comparison to Xu et al. [2]’s scheme on the published HGP code family, under matched amortization assumptions, with BB codes (Sec. 6.1) measured in the same framework.

We connect to two recent qLDPC architectures, situated among a growing body of neutral-atom qLDPC layout and routing work [7]–[10]. Xu et al. [2] implement HGP/LP codes on reconfigurable atom arrays with 2D divide-and-conquer scrambling. Bravyi et al. [1] demonstrate bivariate bicycle (BB) codes on superconducting hardware whose Tanner graph decomposes into two edge-disjoint planar subgraphs (Sec. 6). We refer to and pipeline Algorithm 3 from Xu et al. [2], requiring \(2\delta_c = 8\) atom rearrangements per syndrome cycle on single-layer AOD hardware (constant in \(N\)). Our scheme on multi-layer 3D AOL with \(L_{\mathrm{layers}}\) stacked planes requires \(\lceil 2\delta_c/L_{\mathrm{layers}}\rceil\) AOL pattern activations per cycle (also constant in \(N\)), with no atom motion in the application phase. The one-time setup cost \(T_{\mathrm{Valiant}}\) to bring atoms into canonical positions grows as \(\Theta(\log N)\) but amortizes over the \(R \gtrsim 10^3\) syndrome rounds of a memory experiment. The per-cycle speedup is \(L_{\mathrm{layers}}\) for \(L_{\mathrm{layers}}\leq \chi' = 8\) and saturates at \(8\times\) for \(L_{\mathrm{layers}}\geq 8\). Both schemes are \(O(1)\) per cycle in atom-array reconfigurations, and the multi-layer architecture contributes a constant-factor advantage. For non-QC HGP/LP codes, both schemes remain applicable, since Xu et al. [2]’s Algorithm 1 handles arbitrary 1D permutations as well as shifts, while our AOL patterns are arbitrary matchings rather than shifts, but remain pre-storable on Bluvstein [11]-style hardware. With König-optimal edge coloring, \(\chi'(G_T) = 2\delta_c\) for both QC and non-QC bases. The only non-QC cost becomes an offline preprocessing burden of computing and storing \(\chi'\) AOL patterns (Sec. 5.5). Table 1 situates the multi-layer AOL protocol against existing routing regimes for syndrome extraction at qLDPC scale.

2 Background↩︎

2.1 Ramanujan graphs and routing↩︎

Following previous work [12], a \(d\)-regular graph \(G\) is Ramanujan [13]–[15] if its non-trivial eigenvalues satisfy \(|\lambda_i| \leq 2\sqrt{d-1}\) for \(i \neq 1, N\). Random regular graphs are nearly Ramanujan [16] (see also the expander survey [17]). The spectral ratio \(\beta = \lambda_\star / d\) where \(\lambda_\star = \max(|\lambda_2|, |\lambda_N|)\) controls the routing depth via Valiant’s two-phase scheme [18], [19]. There we find that for a \(d'\)-regular Ramanujan graph \(G\) on \(N \geq 16\) vertices with spectral ratio \(\beta\): \[\label{eq:papier1-bound} \mathrm{rt}(G) \leq \frac{4(d' + 6)}{d' \log_2(1/\beta)} \log_2 N + 19 \log_2 N,\tag{1}\] acting as a tight bound in the worst case but loose by \(\sim 25\times\) for HGP code Tanner graphs (see Sec. 4.3).

2.2 HGP and LP qLDPC code Tanner graphs↩︎

For a classical parity-check matrix \(H\) (size \(m \times n\)) with bipartite Tanner graph \(G_{\mathrm{base}}\), the HGP code \(\mathrm{HGP}[H, H']\) (Tillich–Zémor [20], generalizing the quantum hypergraph-product construction of Kovalev–Pryadko [21]) has \(N = nn' + mm'\) data qubits, \(m_X = mn'\) X-checks, and \(m_Z = nm'\) Z-checks. We focus on the self-product case \(H = H'\) throughout this paper.

The full Tanner graph \(G_T\) is bipartite, with qubits on one side and all checks on the other. We index nodes as \[\begin{align} \text{L-qubits } (v, w) &\in V \times V, \quad \text{R-qubits } (c, c') \in C \times C, \\ \text{X-checks } (c, w) &\in C \times V, \quad \text{Z-checks } (v, c') \in V \times C, \end{align}\] where \(V = \{1, \ldots, n\}\) are variable nodes and \(C = \{1, \ldots, m\}\) are check nodes of \(G_{\mathrm{base}}\). Edges follow the standard HGP definition.

LP codes [22] are HGP codes built from a \(\mathbb{Z}_L\) voltage cover of a base \(H\). The lifted-product and balanced-product constructions [22]–[24] and quantum Tanner/expander codes [25]–[27] are the route to asymptotically good qLDPC codes. The lifted matrix \(H_{\text{lift}}\) has size \(mL \times nL\), and the LP Tanner graph is \(\mathrm{HGP}[H_{\text{lift}}, H_{\text{lift}}]\).

2.3 Atom-array hardware: 2D AOD and 3D AOL↩︎

We take the hardware model of a 2D atom array on an \(L \times L\) grid (\(N = L^2\) atoms), with acousto-optic deflectors (AOD) providing arbitrary atom-pair connectivity through coherent transport [2], [11], building on the reconfigurable Rydberg-array platform [28]–[33]. 3D acousto-optic lattices (AOL) augment this with multiple stacked “layers” of independent AOD patterns, denoted here as \(L_{\mathrm{layers}}\), a premise supported by demonstrated 3D atom-array assembly [34] and by recent 3D acousto-optic transport hardware [35]–[37].

In previous work (Xu et al. [2]), atom rearrangement uses a divide-and-conquer 1D scrambling algorithm achieving arbitrary permutations in \(O(\log L)\) recursive levels. Each level requires parallel atom motion of distance up to \(L = \sqrt{N}\), with per-level wall-clock \(\sim 3\) ms at \(N \sim 10^4\) scaling as \(O(N^{1/4})\) under constant-acceleration physics. This \(\sim 3\) ms figure is a long-range cubic-spline transport time (Xu et al. Methods Eq. 7, a \(\sim\!500~\mu\)m sweep; cf.the \(3\) ms AOD rearrangement sweep of Endres et al. [38]), taken as the cost for the one-time full-array scrambling of the setup phase. We distinguish this transport time from the short-range per-gate move used inside a syndrome cycle, whose demonstrated characteristic time is \(\sim 200~\mu\)s (\(0.55~\mu\)m \(\mu\)s\(^{-1}\) cubic-velocity profile) [11], [39].

2.4 Comparison baseline↩︎

Per Xu et al. [2] Algorithm 3, pipelining requires \(2\delta_c\) rearrangement layers per syndrome cycle, where \(\delta_c\) is the chromatic index of the underlying classical parity-check Tanner graph. For a \((3,4)\)-biregular base, \(\delta_c = 4\), giving: \[\label{eq:xu-baseline} T^{\text{Xu et al.}}_{\text{cycle}} = 2 \delta_c = 8,\tag{2}\] constant in \(N\) for fixed code structure. Each per-cycle rearrangement layer is a short-range data\(\leftrightarrow\)ancilla move, whose demonstrated characteristic wall-clock is \(\sim 200~\mu\)s [11], [39], giving \(8 \times 200~\mu\)s \(\approx 1.6\) ms per syndrome cycle at \(N \sim 10^4\). Gate-depth count of 16 entangling layers (“\(4\delta_c\)” in their notation) is a separate quantity from the rearrangement-layer count.

3 Spectral Characterization of qLDPC Tanner Graphs↩︎

This section presents structural results for the Tanner graphs of two qLDPC families.

3.1 Spectrum decomposition (Result 1a)↩︎

Across nine random \((3,4)\)-biregular bases at \(n = 12\) (HGP code on 441 nodes), we account for all eigenvalues by the multiset of Eq. ?? . Full-rank \(H\) (rank \(r = m = 9\)) gives 75-84% product-mode eigenvalues, while rank-deficient \(H\) (e.g., \(r = 7\) or \(8\)) gives 56-76% product-modes with the remainder split between boundary and zero modes. The mean product fraction over the tested seeds is \(\approx 70 \pm 9\%\). Figure 1 visualizes this decomposition for the \([[225, 9, 4]]\) instance, and every measured eigenvalue lands on a predicted product or boundary position from the multiset Eq. ?? .

3.2 Closed-form spectral ratio (Result 1b)↩︎

Numerically, we evidence this result with double-precision matching across 26 instances spanning base sizes \(n \in \{12, 16, 20, 24\}\) and LP-style lift orders (\(L \in \{2, 3, 4, 5, 6, 8\}\)). For example, on the [[225, 9, 4]] HGP code: \(\beta_{\mathrm{base}}= 0.7609\) predicts \(\beta_{\mathrm{HGP}}= 0.8804\) to all measured digits, implicating computability of the full Tanner graph spectral structure from a single SVD on the base parity-check matrix. The closed form feeds directly into the routing-depth bound, making the “single SVD” claim quantitative.

3.3 Diameter identity (Result 2)↩︎

For random \((c, r)\)-biregular base graphs, \(D_{\mathrm{base}}= O(\log n / \log d_{\text{base}})\) where \(N_{\mathrm{HGP}} = \Theta(n^2)\), so \[D_T= 2 D_{\mathrm{base}}= O\!\left(\log \sqrt{N_{\mathrm{HGP}}}\right)= O(\log N_{\mathrm{HGP}}).\] The constant in front of \(\log N_{\mathrm{HGP}}\) is \(1/\log d_{\text{base}}\) via the base graph’s expansion, which is tighter than the generic diameter bound’s constant \(1/\log_2(1/\beta_{\mathrm{HGP}})\), improving the constant on a mutual \(O(\log N)\) scaling.

3.4 Spectral reduction for bivariate-bicycle codes↩︎

The results above rest on the hypergraph-product structure \(H_X = (H \otimes I \mid I \otimes H^T)\). As it stands, the results above do not extend to bivariate-bicycle (BB) codes. Those are built from two commuting circulant polynomials rather than a product of a base code with itself. BB codes nonetheless carry a different abelian symmetry, being the translation group \(\mathbb{Z}_l \times \mathbb{Z}_m\) of the underlying torus. This yields an analogous reduction of the routing-relevant spectrum via Fourier diagonalization.

A BB code [1] on \(n = 2lm\) qubits (and its multivariate generalization [40]) is specified by two polynomials \[A(x,y), B(x,y) \in \mathbb{F}_2[x,y]/(x^l - 1,\, y^m - 1),\] acting as \(lm \times lm\) circulant \(0/1\) matrices \(A, B\). Its Calderbank-Shor-Steane (CSS) check matrices are \(H_X = (A \mid B)\) and \(H_Z = (B^T \mid A^T)\), so \[\label{eq:bb-check} \mathcal{H} = \begin{pmatrix} A & B \\ B^T & A^T \end{pmatrix},\tag{6}\] as the qubit-to-check biadjacency of the Tanner graph (size \(2lm \times 2lm\)). The nonzero eigenvalues of the bipartite Tanner adjacency are \(\pm \sigma_i(\mathcal{H})\).

Unlike Theorem 2, the BB ratio \(\beta_{\mathrm{BB}}\) has no closed form depending only on individual block ratios \(\beta_A, \beta_B\). The Perron value \(\sigma_1 = s_1(0,0) = w_A + w_B\) (where \(w_A, w_B\) are the polynomial weights) is fixed by the weights, but the second-largest singular value is attained at a nonzero character \((a,b)\) whose location depends on monomial exponents. If we assert a transplanted form \[\beta_{\mathrm{BB}} = (1 + \max(\beta_A, \beta_B))/2,\] we overshoot the four published Bravyi codes by \(0.12\)–\(0.17\) and the result fails to hold numerically for non-degenerate codes.

We check Theorem 5 against direct diagonalization of the full Tanner adjacency across 52 BB codes, including the four published Bravyi instances [1] and 48 random codes spanning polynomial weights \(w \in \{2,3,4\}\) (Tanner max-degree \(\Delta = 2w \in \{4,6,8\}\)) and torus sizes up to \(lm = 144\) (\(N_{G_T} = 576\)). The maximum eigenvalue discrepancy over the whole sweep was \(3.1 \times 10^{-14}\). An independent re-derivation taking the singular values of the explicit check matrix 6 (rather than the Tanner adjacency) agreed to \(5.6 \times 10^{-14}\) on a fresh sample up to \(N_{G_T} = 800\). For the published Bravyi codes the reduction reproduces the measured ratios of Sec. 6.1 (\(\beta_{\mathrm{BB}} = 0.667, 0.872, 0.828, 0.828\)) to all reported digits.

As with the product-code results, the routing-relevant spectrum of a BB code is computable without ever instantiating the full Tanner graph, making spectral screening of BB polynomial families tractable at scales where full diagonalization is infeasible.

3.5 Random-voltage Ramanujan fraction for LP codes↩︎

For LP codes built from random voltage assignments on a fixed 3×5 base support mask (mirroring the family in Xu et al. [2]), we measured the fraction of voltage assignments yielding Ramanujan-Tanner graphs (Feng–Li bipartite condition \(\sigma_2 \leq \sqrt{c-1} + \sqrt{r-1}\) on the lifted classical Tanner graph) across a sweep of lift orders \(L \in \{2, \ldots, 16\}\).

This phenomenon is also found in Courtney [12] Sec.  7’s covering-tower analysis on the Fano plane (94% Ramanujan at \(k=2\)), supporting random-voltage code search as a practical strategy for producing routing-friendly LP code instances.

4 Multi-Layer AOL Routing Protocol↩︎

4.1 Algorithm↩︎

We apply a one-time Valiant routing on the union of \(L_{\mathrm{layers}}\) overlay graphs to canonical 2D-grid positions, followed by \(R\) syndrome cycles in which each chromatic color of \(G_T\) is loaded into one of the stacked AOL planes and fired in parallel. The protocol is stated as Algorithm 3 and illustrated in Figure 2.

None

4.2 Amortization theorem↩︎

The shift-based decomposition is simplest when \(H\) is quasi-cyclic. Each chromatic color of \(G_T\) is implementable as a single axis-aligned translation on the 2D embedding, giving a simple shift pattern to each AOL plane. For non-QC codes (e.g., HGP from random biregular bases), chromatic colors are arbitrary matchings rather than shifts. By König’s theorem [41] (see also Vizing [42] and [43]), \(\chi'(G_T) = \Delta(G_T) = 2\delta_c\), being constructible in polynomial time by repeated bipartite matching on the \(\Delta\)-regular extension [44]. Theorem 6’s \(\lceil \chi'/L_{\mathrm{layers}}\rceil\) bound holds. Computing optimal coloring and storing \(\chi'\) arbitrary AOL trap patterns (vs.a single shift template) is an offline precomputation. Per-cycle wall-clock comparisons across QC and non-QC families are reported in Sec. 5.5. The mechanism mirrors Xu et al.’s product coloration but exploits multi-layer parallelism in the application phase.

4.3 Tightened analytical bound for \(T_{\mathrm{Valiant}}(G_{\text{union}})\)↩︎

Courtney [12] gives an analytical bound on \(T_{\mathrm{Valiant}}\) that is empirically loose by \(\sim 25\times\) for HGP code Tanner graphs (Sec. 5). The looseness has roughly equal contributions from the diameter bound and a generic Chernoff bound on edge congestion. Theorem 4 addresses the diameter bound and gives \(D_T= 2 D_{\mathrm{base}}\) rather than the generic \(O(\log N / \log(1/\beta))\). We conjecture a tightened Chernoff bound using the HGP path-decomposition structure:

The above conjecture’s constant (\(c \approx 1\)) comes from a Bernstein-type argument [45], [46] (bounded-difference methods [47] give a comparable tail) with the variance bound \(\mathrm{Var}(X_e) \leq \mathbb{E}[X_e]\) from negative association of permutation indicators [48], [49]. A constant \(c < 1\) may require a non-Bernstein technique (e.g., heat-kernel methods directly exploiting the spectrum-decomposition of Proposition 1).

We cast our focus to establish Conjecture 7 as a theorem conditioned on explicit hypotheses on routing structure. Hypotheses (H1) and (H3) are satisfied by HGP under the canonical 2D routing decomposition (Lemma 1 and the negative-association argument below). Hypothesis (H2) requires the per-source expectation to be \(O(1/|S_e|)\) rather than \(O(1)\). This requires a routing scheme with \(O(\log N)\) canonical paths via check-node bridges (discussed after Lemma 2). The conjecture as originally stated is strongly conditioned on H2, while a rigorous construction for HGP is left to future work.

The asymptotic constant \(3/2\) in \(\mathbb{P}(X_e \geq c \ln N) \leq N^{-3c/2}\) is the standard Bernstein constant for sums of bounded variables when the \(t/3\) term dominates the variance. If we use the Azuma–Hoeffding inequality (with \(1/2\) instead of \(1/3\) in the variance proxy), we find \[\mathbb{P}(X_e \geq c \ln N) \leq N^{-c^2/(2\mu_0)},\] quadratic for \(c \ln N \leq \mu_0\). In the asymptotic regime \(c \ln N \gg \mu_0\), the linear Bernstein bound dominates.

Lemma 2 gives \(\mu_0 = O(\sqrt{N})\) for the canonical 2D routing scheme, not satisfying hypothesis (H2)’s requirement \(\mu_0 = O(1)\). Substituting \(\mu_0 = O(\sqrt{N})\) into Equation 13 with \(t = c \ln N\) gives a bound that decays as \[\exp(-(c \ln N)^2 / O(\sqrt N + c \ln N)),\] useful only when \(c \ln N \gg \sqrt N\), i.e., for \(N \lesssim e^{O(\sqrt N)}\), failing to give \(O(\log N)\) routing depth bound asymptotically. Therefore Theorem 8 holds only conditionally on (H1)–(H3): hypothesis (H2) is not verified by canonical 2D routing for HGP.

Verifying (H2) for HGP would require a routing scheme whose canonical paths have length \(O(\log N)\) rather than \(O(\sqrt N)\). As an example, routing through check-node bridges exploiting the spectral expansion of \(G_T\). We have not constructed such a scheme rigorously and this remains the obstacle to strengthening Theorem 8. Numerical evidence (Sec. 5) shows \(T_{\text{Valiant}} \approx 0.5 \log_2 N\) in the tested regime \(N \in [10^2, 10^3]\). While this suggests that the desired routing scheme exists, it is no proof.

Regarding (H3), negative association of permutation indicators \(I_u^{(e)}\) under uniform \(\sigma\) is a standard fact: if any two indicators \(I_{u_1}^{(e)}, I_{u_2}^{(e)}\) are sub-additively coupled (intuitively, both being 1 forces specific values of \(\sigma\) on \(u_1\) and \(u_2\), restricting the permutation more than each individually), then their covariance is non-positive. Then, the Joag-Dev-Proschan [48] machinery applies, giving \[\mathrm{Var}\bigl(\sum I_u^{(e)}\bigr) \leq \sum \mathrm{Var}(I_u^{(e)}) \leq \sum \mathbb{E}[I_u^{(e)}] = \mathbb{E}[X_e].\]

If a routing scheme satisfying (H1)–(H3) is constructed for HGP, Eq. 12 would convert to the routing-depth bound, i.e. \(T_{\text{Valiant}}(G_T) \leq c \log_2 N\) for any \(c > 2/(3 \ln 2) \approx 0.46\) with high probability. Taking \(c = 1\) would give the conjectured constant. The empirical \(T_{\text{Valiant}} \approx 0.5 \log_2 N\) measurement (Sec. 5) is consistent with this range, suggesting a sufficient routing scheme exists. We leave its explicit construction (likely a check-node-bridge routing exploiting the spectral expansion of \(G_T\)) to future work.

5 Numerical Comparison↩︎

5.1 Methodology↩︎

We measure the number of parallel atom-rearrangement steps per syndrome extraction cycle, comparing both schemes on the Xu et al. [2] HGP code family from their Figure 3a. Related routing/architecture baselines for reconfigurable atom arrays include Constantinides et al. [9] and Zhou et al. [10]. Both schemes target the same hardware (2D AOD + \(L_{\mathrm{layers}}\) stacked AOL) and the same metric. Our results are reproducible from the codebase associated with this work, given in the data availability section.

To represent Xu et al.’s method we apply Eq. 2 (constant 8 rearrangement layers per cycle for \((3,4)\)-biregular HGP bases). We use Theorem 6 with \(T_{\mathrm{Valiant}}\) measured directly via Valiant routing on the union of \(L_{\mathrm{layers}}\) random \(d_0 = 8\)-regular graphs.

5.2 Empirical \(k_{\text{emp}}\) measurement↩︎

We measure the empirical Valiant routing constant \(k_{\text{emp}} := T_{\mathrm{Valiant}}/ \log_2 N\) on multi-layer overlay graphs, tabulated in Table 3. For \(L_{\mathrm{layers}}= 8\): \(k_{\text{emp}} \approx 0.554 \pm 0.032\) (5-seed mean \(\pm\) std across \(N \in [11{,}025, 100{,}000]\)). For \(L_{\mathrm{layers}}= 16\): \(k_{\text{emp}} \approx 0.514 \pm 0.022\). These are \(\sim 30\times\) tighter than the Courtney [12] bound’s \(\sim 21\) for the same \(L_{\mathrm{layers}}= 8\) case. Our measurements validate \(N\)-independence of \(k_{\text{emp}}\) directly over \(N \in [225, 100{,}000]\) (a span of \(\sim\!2.6\) decades). We do not claim validation beyond this range: the rows at \(N \geq 10^6\) in Table 5 are conjectured extrapolation, resting on the observed \(N\)-independence together with the asymptotic scaling of Theorem 6.

5.3 Head-to-head depth comparison↩︎

In a memory experiment (no logical gates between syndrome rounds), per-cycle cost dominates for the head-to-head with Xu et al.’s Algorithm 3, which itself reports a per-cycle count. Setup cost \(T_{\mathrm{Valiant}}(G_{\text{union}})\) is reported separately in Table 3 and is paid before the syndrome-cycle loop begins. For a memory experiment of \(R\) rounds, the total cost per cycle amortized over the run is \(\lceil \chi'/L_{\mathrm{layers}}\rceil + T_{\mathrm{Valiant}}/R \to \lceil \chi'/L_{\mathrm{layers}}\rceil\) for large \(R\).

5.4 Engineering-N comparison and asymptotic regime↩︎

Per-cycle step counts for both schemes are constant in \(N\). The setup cost \(T_{\mathrm{Valiant}}\) grows as \(k_{\text{emp}} \log_2 N\) but is paid only once per memory experiment. Table 5 reports both.

Both schemes have \(O(1)\) per-cycle cost in atom-array reconfiguration count. The constant for Xu et al. is \(2\delta_c = 8\) under their single-layer AOD architecture. The constant for ours is \(\lceil \chi'/L_{\mathrm{layers}}\rceil = \lceil 2\delta_c / L_{\mathrm{layers}}\rceil\), which decreases linearly in \(L_{\mathrm{layers}}\) until the cap \(\chi' = 2\delta_c\) is reached. For \(L_{\mathrm{layers}}\geq \chi' = 8\), the per-cycle cost is 1, providing an \(8\times\) improvement over Xu et al.’s per-cycle cost, constant in \(N\). The improvement is purely from L-plane parallelism in the AOL stack, an architectural feature absent from Xu et al.’s framework, which works according to presently existing quantum hardware. If their algorithm were extended to multi-layer AOL, it would also achieve \(\lceil 8/L_{\mathrm{layers}}\rceil\) per cycle, and in that head-to-head the two schemes tie on this metric. Our spectral framework’s separate contributions are (i) explicit chromatic-decomposition cost prediction \(\chi'(G_T) = 2\delta_c\) for any HGP/LP code via König’s theorem, applicable to both QC and non-QC families (König-optimal coloring gives \(\chi' = 2\delta_c\) in both cases; Sec. 5.5), and (ii) explicit characterization of \(T_{\mathrm{Valiant}}\) via \(\beta_{\mathrm{HGP}} = (1+\beta_\text{base})/2\) for rare cases where setup cost matters (e.g., active computation with frequent logical gates, where atoms cannot remain canonical between cycles).

These costs sit naturally against the recent routing lower bounds of Constantinides et al. [9], who prove that current single-plane parallel-AOD designs require \(\Omega(\sqrt{N}\log N)\) steps to realize general permutations, give a matching \(O(\sqrt{N}\log N)\) protocol, and show that a hardware upgrade reduces this to \(\Theta(\log N)\). Our one-time setup cost \(T_{\mathrm{Valiant}}= \Theta(\log N)\) leverages a constructed upgrate of multi-layer overlays. The per-syndrome-cycle cost is \(O(1)\) rather than \(O(\sqrt N \log N)\), since syndrome extraction reuses fixed canonical positions and never re-solves a general permutation after setup. At the architecture level, Zhou et al. [10] report a transversal reconfigurable-atom design whose runtime speedup scales with the code distance \(d\), being orthogonal to and composable with the per-cycle rearrangement savings analyzed here, which target atom-motion depth underlying each transversal layer rather than the logical-gate schedule.

5.5 Non-quasi-cyclic HGP codes: applicability of both algorithms↩︎

The amortization theorem (Theorem 6) gives a \(\lceil \chi'/L_{\mathrm{layers}}\rceil\) per-cycle bound under the QC hypothesis. For non-QC HGP codes (random biregular bases), chromatic colors are arbitrary matchings instead of axis-aligned shifts. In this section, we examine empirically whether the multi-layer-AOL advantage degrades, and whether Xu et al.’s Algorithm 3 retains applicability.

5.5.0.1 Xu et al.’s Algorithm 3 on non-QC.

Xu et al.’s Algorithm 1 (1D divide-and-conquer scrambling) takes an arbitrary target 1D permutation as input and does not require the input to be a cyclic shift. Their Algorithm 2 then composes Algorithm 1 with parallel CZ gates over the chromatic decomposition of the base bipartite graph. Algorithm 3 pipelines this across X and Z syndromes. None of these algorithmic steps require the base check matrix \(H\) to be quasi-cyclic. The \(2\delta_c = 8\) rearrangement layers per cycle is determined by König’s theorem on the base graph (max degree \(= \delta_c\)), independent of QC structure. The QC structure simplifies per-layer atom-motion trajectories (axis-aligned shifts admit short, parallel cubic-spline motion) without altering Algorithm 3’s applicability or layer count.

5.5.0.2 Our multi-layer scheme on non-QC.

The chromatic decomposition \(\chi'(G_T) = 2\delta_c\) holds by König’s theorem for any bipartite Tanner graph, QC or otherwise. The \(L_{\mathrm{layers}}\)-fold parallelism in the application phase requires \(\chi'\) pre-loaded AOL patterns, one per color. For QC bases, each pattern is a simple shift, expressible as a single AOD frequency-tone update. For non-QC bases each pattern is an arbitrary matching on the canonical 2D grid and requires an arbitrary multi-tone AOD configuration. This is pre-storable on modern neutral-atom architectures, which demonstrate pattern switching between distinct codes “without additional calibrations,” incurring only a one-time setup cost in computing and storing the patterns [50].

For both QC and non-QC HGP codes, \(\chi'(G_T) = \Delta(G_T) = 2\delta_c\) by König’s theorem. Optimal coloring is constructible in polynomial time with the standard algorithm: extend \(G_T\) to a \(\Delta\)-regular bipartite multigraph by adding fake edges between sub-\(\Delta\)-degree vertices (Hall’s theorem guarantees feasibility), then iteratively extract \(\Delta\) perfect matchings through repeated bipartite maximum matching, stripping fake edges from each color.

5.5.0.3 Findings.

We find that Xu et al.’s Algorithm 3 applies to non-QC HGP codes with no algorithmic modification. Layer count remains \(2\delta_c = 8\) for \((3,4)\)-biregular bases. Wall-clock per cycle is \(\approx 1.6\) ms across QC and non-QC at \(N \sim 10^3\)–\(10^4\) using the demonstrated \(\sim 200~\mu\)s short-range move. We achieve \(\chi' = 8\) in both cases via König-optimal coloring, retaining an \(8\times\) advantage (pure step-count) in the pessimistic atom-motion scenario and a \(\sim 50\)–\(300\times\) advantage in the pre-stored AOL scenario (Sec. 6.2). König-optimal coloring gives \(\chi' = 8\) regardless of QC structure. The non-QC cost is an offline preprocessing burden (computing the optimal coloring, generating \(\chi'\) AOL trap patterns) paid once per code and amortized across syndrome rounds, minimizing non-QC overhead.

6 Discussion and Future Work↩︎

6.1 Bravyi BB codes: direct measurement↩︎

The bivariate bicycle (BB) codes of Bravyi et al. [1] have Tanner graphs that decompose into two edge-disjoint planar subgraphs, forming a 2-layer overlay structure. Subsequent work develops their logical operators and fold-transversal gates [51], connectivity-lowering morphing circuits [52], matching decoders [53], modular architectures [54], and layouts of (generalized/coprime) bicycle codes on cold atoms [55], [56]. As previously stated, BB codes are constructed from two commuting circulant polynomials \[A(x,y), B(x,y) \in \mathbb{F}_2[x,y]/(x^l-1, y^m-1).\] Their routing-relevant Tanner graph spectrum is governed by the Fourier reduction of Theorem 5. The resulting \(\chi'\) and \(\beta_{\mathrm{BB}}\) values are collected in Table 8.

BB codes have \(\chi' = 6\) vs.\(\chi' = 8\) for \((3,4)\)-biregular HGP/LP, shifting down the saturation point of the multi-layer-AOL: \(L_{\mathrm{layers}}= 6\) AOL planes suffice to collapse per-cycle cost to a single pattern activation. Wall-clock improvement at \(L_{\mathrm{layers}}= 6\) is identical to the \(L_{\mathrm{layers}}= 8\) HGP/LP case, \(\approx 50\text{--}300\times\) versus Xu et al. [2] Algorithm 3 (Sec. 6.2). The trade-off is that BB codes have a smaller demonstrated code family than HGP/LP and lack the random-base flexibility we exploit in Sec. 3.5 for LP code search.

6.2 Wall-clock comparison on multi-layer 3D AOL↩︎

Our step-count comparison treats each reconfiguration uniformly, but Xu et al.’s atom rearrangements and our AOL pattern activations differ by more than an order of magnitude in wall time. The critical quantity is the per-cycle move time. Syndrome-cycle rearrangements are short-range data\(\leftrightarrow\)ancilla moves, whose demonstrated characteristic wall-clock is \(\tau_\text{move} \approx 200~\mu\)s (\(0.55~\mu\)m \(\mu\)s\(^{-1}\) cubic-velocity profile) [11], [39]; equivalently, AOD trap transfers with atom motion are \(50\)–\(100~\mu\)s over \(1\)–\(2~\mu\)m. The long-range \(3\) ms cubic-spline time (0.7 ms AOD trap transfer plus 2.3 ms trajectory; Xu Methods Eq. 7, a \(\sim\!500~\mu\)m sweep) applies only to the one-time full-array setup scrambling and to the Endres-2016-era rearrangement sweep [38], not to the per-cycle short-range move; importing it into the per-cycle term is the misattribution corrected here.

From Bluvstein et al. Methods [11], the demonstrated per-row Raman-AOD reprogramming time without atom motion is 5–8 \(\mu\)s per row, with “several 10s of \(\mu\)s for an arbitrary pattern of rotations.” The AWG synchronization jitter is \(<10\) ns, confirming electronics are not the bottleneck (Raman pulse duration is). For our scheme’s application phase, atoms remain canonical and only AOL frequency patterns change, so the relevant cost is the per-pattern reprogramming time \(\tau_\text{AOL} \in [5, 30]\) \(\mu\)s (\(\sim 30\) \(\mu\)s conservative midrange). We summarize the wall-clock comparison below: \[\begin{align} T_\text{Xu et al., cycle} &= 8 \times \tau_\text{move} = 8 \times 200\;\mu\text{s} \approx 1.6\;\text{ms} \\ T_\text{ours, cycle}\,(L_{\mathrm{layers}}\geq 8) &= 1 \times \tau_\text{AOL} \in [5, 30]\;\mu\text{s} \\ T_\text{ours, setup}/R &= T_{\mathrm{Valiant}}\times 3\;\text{ms} / R \end{align}\] The underlying per-layer physical ratio \(\tau_\text{move}/\tau_\text{AOL} \approx 200/[5\text{--}30] = 7\text{--}40\times\); combined with the \(\chi'=8\to1\) chromatic-layer collapse (an architectural feature of the AOL stack absent from single-layer AOD), the per-cycle advantage is \(1.6~\text{ms}/[5\text{--}30]~\mu\text{s} \approx \boldsymbol{50\text{--}300\times}\) in the canonical-position regime. A larger factor survives only where a per-cycle rearrangement genuinely requires full-array long-range transport. The setup cost contributes \(k_{\text{emp}} \log_2 N \cdot 3\) ms once per memory experiment (long-range moves, legitimately \(\sim 3\) ms each), which becomes negligible per cycle for \(R \gtrsim 10\), the considered regime of Xu et al.(memory threshold). Figure 4 visualizes the per-cycle wall-clock as a function of \(L_{\mathrm{layers}}\) for the four code families considered here.

6.2.0.1 Caveat: AOL crosstalk and L scaling.

Bluvstein et al.demonstrate up to \(\sim 80\) addressable gate sites in their entangling zone with “minimal two-qubit cross-talk” between sites [11]. Corresponding parallel two-qubit entangling-gate fidelity has advanced from \(99.5\%\) on up to 60 atoms in parallel [57] to a leakage-corrected \(0.9971(5)\) for the time-optimal Rydberg CZ gate (with \(0.999\) projected) [58], [59]. The maximum number of independently pre-stored AOL patterns that are simultaneously addressable without per-pattern recalibration is not quantified in the published work. We estimate \(L_{\mathrm{layers}}\lesssim 10\) with current hardware before AOD intermodulation overhead becomes significant. Scaling to \(L_{\mathrm{layers}}\geq 8\) for the speedup-saturating regime of \(\chi'/L_{\mathrm{layers}}= 1\) requires modest hardware extension. If multi-pattern operation costs \(f \in [3, 10]\times\) overhead per AOL switch, per-cycle wall-clock advantage decreases to \(\sim 5\)–\(100\times\).

6.2.0.2 Hardware assumptions.

The wall-clock advantage in this regime depends on two assumptions extrapolated from current \(\sim 80\)-site demonstrations [11]: (R2-A) No atom motion in the application phase, i.e., the \(\chi'\) CNOT layers are implemented as pure AOL pattern switches with no atom shuttling between switches, requiring the multi-layer AOL hardware to provide \(L_{\mathrm{layers}}\) independent, simultaneously-addressable pattern channels. (R2-B) AOL pattern reprogramming at \(L_{\mathrm{layers}}= 8\) operates in 5–30 \(\mu\)s per pattern; this is consistent with the 5–8 \(\mu\)s per row and “several 10s of \(\mu\)s for an arbitrary pattern” demonstrated by Bluvstein et al. Methods. This assumption is backed by demonstrated 3D-AOD hardware: Picard & Endres [37] report a three-dimensional acousto-optic deflector switching focus at 100 kHz (\(10~\mu\)s) with a \(2~\mu\)s rise time, and note that longitudinal-mode TeO\(_2\) crystals (\(4200\) m/s acoustic velocity) support \(>\!600\) kHz (\(\sim\!1.6~\mu\)s) switching, placing our assumed \(5\)–\(30~\mu\)s window squarely within measured 3D-AOD performance. Scaling beyond \(L_{\mathrm{layers}}\approx 10\) may still incur AOD intermodulation overhead requiring per-pattern recalibration.

6.3 Engineering recommendations by hardware generation↩︎

Table 9 translates per-cycle and setup costs derived above into per-generation design guidance for hardware groups building qLDPC architectures on neutral-atom platforms.

The most important practical message is that per-cycle advantage is a step-function in \(L_{\mathrm{layers}}\): zero at \(L_{\mathrm{layers}}= 1\), growing linearly to \(\chi'\) at \(L_{\mathrm{layers}}= \chi'\), then constant beyond. Hardware roadmaps may target \(L_{\mathrm{layers}}\in [6, 8]\) as the first regime where our scheme materially beats single-layer AOD on per-cycle wall-clock.

6.4 Limitations↩︎

Both schemes are \(O(1)\) per cycle in atom-array reconfiguration count. Setup costs for multi-layer AOL scheme presented here grow as \(O(\log N)\) but amortize over the rounds of a memory experiment. The per-cycle speedup is constant in \(N\), capped by \(\chi' = 2\delta_c\).

We predict wall-clock advantage at moderate \(N\), but this is heavily dependent on hardware assumptions. (R2-A and R2-B above) currently demonstrated only at \(L_{\mathrm{layers}}\leq 2\). Further, for non-quasi-cyclic HGP codes, the chromatic colors are arbitrary matchings rather than shifts. König-optimal coloring (constructible in polynomial time) gives \(\chi' = 2\delta_c\) for both QC and non-QC bases, so the per-cycle bound \(\lceil \chi'/L_{\mathrm{layers}}\rceil\) is unchanged. The cost stays offline, where \(\chi'\) arbitrary AOL trap patterns must be precomputed and stored, vs.one shift template for the QC case (Sec. 5.5).

With no 3D parallelism, per-cycle step count does not change. The \(L_{\mathrm{layers}}\times\) speedup materializes at \(L_{\mathrm{layers}}\geq 2\) and saturates at \(8\times\) for \(L_{\mathrm{layers}}\geq \chi' = 8\) on \((3,4)\)-biregular bases. Wall-clock advantage is amplified by the short-range atom-motion vs.AOL-reprogramming time ratio (200 \(\mu\)s vs.–30 \(\mu\)s per Bluvstein et al.Methods, a \(7\)–\(40\times\) per-layer ratio), giving the \(\sim 50\)–\(300\times\) per-cycle wall-clock advantage figure at \(L_{\mathrm{layers}}= 8\) (Sec. 6.2).

6.5 Future hardware directions↩︎

A genuine asymptotic wall-clock advantage of \(O(N^{1/4})\) over Xu et al. would emerge if the multi-layer overlay is implemented via photonic interconnects with \(O(\mu s)\) switching that is independent of physical atom-motion distance. The required hardware is far from current state of the art.

First, we would require a per-pair photonic-mediated entanglement rate \(\geq 333\) Hz at \(\geq 99\%\) fidelity. This target is substantially more attainable than current cavity-mediated two-atom operations (\(\sim\!52\%\) deterministic fidelity, rising to \(\sim\!76\%\) with error detection [62]) might suggest: cavity-coupled Yb proposals project a Bell-pair rate of \(1.0\times10^5\) s\(^{-1}\) at average fidelity \(\approx 0.999\) [60] (a theory estimate). Fault tolerance is compatible with nonlocal Bell-pair error as high as \(\sim 10\%\) without distillation [61], [63], with multiplexed Bell-pair rates in the 1–50 MHz range. The entanglement-rate requirement is met in such proposals, making the binding constraint be fidelity compounded with parallel channel count and integration scale, described below.

Second, we would need \(L_{\mathrm{layers}}= O(\log N) \approx 14\) parallel photonic channels per atom array (current: 1–2) [64], and networked integration across \(\geq 10^4\) atoms. Array sizes have advanced rapidly toward this scale: 6,100 coherent qubits with 12.6 s coherence [65] and continuous operation of a 3,000-qubit system [66] are now demonstrated, alongside 3D atom-array assembly [34] and 3D acousto-optic transport [35], [36].

Summarily, the binding gap is parallel channel count (\(1\)–\(2\) demonstrated vs.\(O(\log N)\approx 14\) required) and the integration of photonic links with qLDPC-scale arrays. As such, we frame this research as a long-term direction toward robust, industrial-scale fault-tolerant quantum computation rather than a near-term hardware target. The theoretical advantage if these capabilities materialize is \(T_\text{us}^\text{photonic}/T_\text{Xu et al.}^\text{AOD} = O(\log N / N^{1/4}) \to 0\) as \(N \to \infty\).

On a single-layer AOD architecture (no AOL stack), both schemes share the same \(\sim 8 \times 200~\mu\)s \(= 1.6\) ms per cycle (short-range moves), with the same constant. The multi-layer 3D AOL architecture is the regime where our scheme provides per-cycle improvement, scaling as \(L_{\mathrm{layers}}\) until the cap at \(\chi' = 8\) is reached.

A shifted-Cayley overlay analysis shows that a purely geometric construction with atom motion only cannot break the \(N^{1/4}\) wall-clock barrier, regardless of how the layers are designed, for two reasons. Dominant motion cost is the largest-shift layer, requiring full-array atom motion of distance \(\sim\!\sqrt{n} = N^{1/4}\) under constant-acceleration transport. The resulting union graph has spectral ratio \(\beta\) that grows toward \(1\) with \(N\) (\(\beta = 0.75\) at \(n=16\), rising to \(\beta = 0.89\) at \(n=512\)), so it is not asymptotically Ramanujan and the routing-depth bound of Eq. 1 does not itself reach \(O(\log N)\). Escaping the barrier therefore requires a switching mechanism whose cost is independent of physical motion distance, such as the photonic interconnects discussed above.

6.6 Future theory directions↩︎

Alongside the apparent gap in hardware demonstration, confirmation of Conjecture 7 would close the remaining \(\sim 5\times\) gap between our analytical bound and empirical measurement. We propose using a refined Chernoff bound that exploits the HGP path-decomposition structure (rows and columns are statistically independent under uniform permutation).

Theorem 8 holds conditionally on hypotheses (H1)–(H3). Hypotheses (H1) and (H3) are satisfied by the canonical row-then-column 2D routing scheme on HGP (Lemma 1 and the negative-association remark following Lemma 2). Hypothesis (H2) states that the per-source bound \(\mathbb{P}(I_u^{(e)} = 1) \leq p\) satisfies \(sp \leq \mu_0\) for an absolute constant \(\mu_0 = O(1)\). This is not satisfied by the canonical 2D scheme, where Lemma 2 gives \(\mu_0 = O(\sqrt{N})\) instead. Numerical observation of \(T_{\mathrm{Valiant}} \approx 0.5 \log_2 N\) at validated \(N\) up to \(10^5\) (Table 3) is consistent with the conclusion of Theorem 8 at constant \(c \approx 1\), which would follow from H2-satisfying canonical paths. We leave constructing such a scheme rigorously for future work.

We propose a plausible construction, as a check-node-bridge routing where each canonical path traverses \(O(\log N)\) check-node “bridge” edges chosen to exploit the spectral expansion of \(G_T\) (Proposition 1). Closing this problem would upgrade Theorem 8 from conditional to unconditional for HGP and would recover the \(\sim 5\times\) analytical-vs-empirical gap currently noted as Conjecture 7.

7 Conclusion↩︎

We present a closed-form characterization of the routing-relevant Tanner graph spectrum for HGP/LP qLDPC codes (\(\beta_{\mathrm{HGP}}= (1+\beta_{\mathrm{base}})/2\) and \(D_T= 2 D_{\mathrm{base}}\)), together with a structural decomposition of \(\mathrm{spec}(G_T)\) into product modes and boundary modes (Proposition 1). For multi-layer 3D AOL hardware we construct and numerically validate a routing protocol with per-syndrome-cycle depth \(T_{\mathrm{Valiant}}(G_{\text{union}}) + \lceil \chi'/L_{\mathrm{layers}}\rceil\) under a quasi-cyclic hypothesis (Theorem 6).

Classical simulation of both schemes on identical HGP and LP codes (spanning \((3,4)\)- and \((3,5)\)-biregular bases) shows that Xu et al.’s pipelined Algorithm 3 requires \(2\delta_c\) atom rearrangements per syndrome cycle (constant in \(N\), where \(\delta_c\) is the maximum degree of the base bipartite graph). Our multi-layer scheme requires \(\lceil 2\delta_c/L_{\mathrm{layers}}\rceil\) AOL pattern activations per cycle. Using Xu et al.’s \((3,4)\)-biregular parameters, the per-cycle step-count advantage at \(L_{\mathrm{layers}}\geq 8\) is \(8\times\), capped by \(\chi'(G_T) = 2\delta_c = 8\) (König’s theorem on the bipartite Tanner graph). In wall-clock terms, the ratio between the demonstrated \(\sim 200~\mu\)s short-range per-cycle atom move (Bluvstein et al.Methods [11], [39]) and 5–30 \(\mu\)s AOL pattern reprogramming, combined with the \(\chi'=8\to1\) layer collapse, yields a per-cycle wall-clock advantage of \(\sim 50\)–\(300\times\) in the memory-experiment regime (a \(7\)–\(40\times\) per-layer physical ratio \(\times\) the \(8\times\) chromatic collapse).

Summarily, we provide a closed-form spectral characterization of HGP/LP Tanner graphs serving as a code-design tool, with the diameter identity \(D_T= 2D_{\mathrm{base}}\) and ratio \(\beta_{\mathrm{HGP}}= (1+\beta_{\mathrm{base}})/2\). We recognize that the \(\chi'(G_T) = 2\delta_c\) chromatic decomposition admits \(L_{\mathrm{layers}}\)-fold parallelism on multi-layer 3D AOL hardware, with both schemes equally able to exploit this when reformulated. Though we give no hardware demonstration, we numerically validate that this multi-layer-AOL advantage is robust across QC and non-QC HGP/LP families. König-optimal coloring (polynomial-time constructible) gives \(\chi' = 2\delta_c\) for both QC and non-QC bases, so there is no per-cycle algorithmic non-QC penalty.

Data and code availability↩︎

All numerical results, together with the code that generates every figure and table in this work and the shifted-Cayley overlay sweep discussed in Sec. 6.5, are available in this Github repository. The author used Claude (Anthropic) to assist in drafting code comments and documentation for the codebase.

Competing interests↩︎

The author declares no competing interests.

8 Block-SVD of the HGP Tanner biadjacency↩︎

We prove Proposition 1 by an explicit singular-value decomposition of the qubit-to-check biadjacency \(B\) of \(\mathrm{HGP}[H,H]\).

8.0.0.1 Biadjacency block form.

Let \(H\) be \(m\times n\). The HGP code has qubit sectors \(\mathcal{Q}_0 = V\times V\) (\(\dim n^2\)) and \(\mathcal{Q}_1 = C\times C\) (\(\dim m^2\)), and check sectors \(\mathcal{X} = C\times V\) (\(\dim mn\), X-checks) and \(\mathcal{Z} = V\times C\) (\(\dim nm\), Z-checks). With the stabilizer matrices \(H_X = (H\otimes I_n \mid I_m\otimes H^{T})\) and \(H_Z = (I_n\otimes H \mid H^{T}\otimes I_m)\) (Tillich–Zémor [20]), the biadjacency \(B = (H_X^{T}\mid H_Z^{T})\), arranged as (qubit sector) rows \(\times\) (check sector) columns, is \[\label{eq:app-B} B = \begin{pmatrix} H^{T}\otimes I_n & I_n\otimes H^{T} \\[2pt] I_m\otimes H & H\otimes I_m \end{pmatrix},\tag{14}\] where the row blocks are \(\mathcal{Q}_0,\mathcal{Q}_1\) and the column blocks are \(\mathcal{X},\mathcal{Z}\).

8.0.0.2 The Gram matrix \(BB^{T}\).

Using the mixed-product rule \((A\otimes B)(C\otimes D) = (AC)\otimes(BD)\) throughout, the diagonal blocks are \[(BB^{T})_{00} = (H^{T}H)\otimes I_n + I_n\otimes(H^{T}H), \qquad (BB^{T})_{11} = (HH^{T})\otimes I_m + I_m\otimes(HH^{T}),\] and the off-diagonal block is, using \((H^{T}\otimes I_n)(I_m\otimes H^{T}) = H^{T}\otimes H^{T}\) and \((I_n\otimes H^{T})(H^{T}\otimes I_m) = H^{T}\otimes H^{T}\), \[(BB^{T})_{01} = (H^{T}\otimes I_n)(I_m\otimes H^{T}) + (I_n\otimes H^{T})(H^{T}\otimes I_m) = 2\,H^{T}\otimes H^{T}, \qquad (BB^{T})_{10} = 2\,H\otimes H .\] This is the factor of \(2\) quoted in the main text; it arises because both the \(\mathcal{X}\)- and \(\mathcal{Z}\)-check columns of \(B\) couple \(\mathcal{Q}_0\) to \(\mathcal{Q}_1\) identically.

8.0.0.3 Diagonalization.

Take the SVD \(H = \sum_{k=1}^{r}\sigma_k\, u_k w_k^{T}\) with orthonormal left/right singular vectors \(u_k\in\mathbb{R}^m\), \(w_k\in\mathbb{R}^n\), so \[Hw_k = \sigma_k u_k\text{ , }H^{T}u_k = \sigma_k w_k\text{ , }H^{T}H\,w_k = \sigma_k^2 w_k\text{ , }HH^{T}u_k = \sigma_k^2 u_k.\] Extend \(\{w_k\}\) to an orthonormal basis of \(\mathbb{R}^n\) by kernel vectors (\(\sigma=0\)) and \(\{u_k\}\) likewise by cokernel vectors. For an ordered pair \((i,j)\) with \(\sigma_i,\sigma_j>0\), the two-dimensional subspace \(\mathcal{S}_{ij} = \mathrm{span}\{\,w_i\otimes w_j\;(\in\mathcal{Q}_0),\;u_i\otimes u_j\;(\in\mathcal{Q}_1)\,\}\) is invariant under \(BB^{T}\): \[(BB^{T})_{00}(w_i\otimes w_j) = (\sigma_i^2+\sigma_j^2)\,w_i\otimes w_j, \qquad (BB^{T})_{01}(u_i\otimes u_j) = 2\,(H^{T}u_i)\otimes(H^{T}u_j) = 2\sigma_i\sigma_j\, w_i\otimes w_j,\] and symmetrically on \(\mathcal{Q}_1\). Hence \[BB^{T}\big|_{\mathcal{S}_{ij}} = \begin{pmatrix} \sigma_i^2+\sigma_j^2 & 2\sigma_i\sigma_j \\ 2\sigma_i\sigma_j & \sigma_i^2+\sigma_j^2 \end{pmatrix}, \qquad \text{with eigenvalues } (\sigma_i+\sigma_j)^2 \text{ and } (\sigma_i-\sigma_j)^2 .\] Thus \(B\) has singular values \(\sigma_i+\sigma_j\) and \(|\sigma_i-\sigma_j|\) (the product modes). If one factor is a kernel/cokernel direction (\(\sigma_j = 0\)), the coupling term \(2\sigma_i\sigma_j\) vanishes and \(w_i\otimes w_{j_0}\) (respectively \(u_i\otimes u_{j_0}\)) is an eigenvector of \(BB^{T}\) with eigenvalue \(\sigma_i^2\), i.e.a singular value \(\sigma_i\) of \(B\) (the boundary modes). If both factors are kernel/cokernel directions the eigenvalue is \(0\) (zero modes). These subspaces are mutually orthogonal and their dimensions sum to \(n^2+m^2 = \dim(\mathcal{Q}_0\oplus\mathcal{Q}_1)\), exhausting \(\mathrm{sv}(B)\).

Since \(\mathrm{spec}(A_{G_T}) = \{\pm\sigma : \sigma\in\mathrm{sv}(B)\}\cup\{0\}\), the Tanner adjacency spectrum is contained in \[\{\pm(\sigma_i\pm\sigma_j) : 1\le i,j\le r\}\;\cup\;\{\pm\sigma_k : 1\le k\le r\}\;\cup\;\{0\},\] being the multiset ?? , proving Proposition 1. The Perron value is \(2\sigma_1\) (pair \((1,1)\)), and when \(\sigma_1\) is simple it is the unique product mode equal to \(2\sigma_1\), which is used in the proof of Theorem 2.

References↩︎