Explicit Abelian Lifts and Quantum LDPC Codes

1 Introduction

• The central problem is to construct expanding graphs with a prescribed symmetry group, namely H ≤ Aut(G).This question connects graph expansion and symmetry beyond the rigidity of many Cayley-graph constructions.Source: §1 · p. 3

Current Techniques

• Lifting preserves the base degree and, for abelian H, transfers H-symmetry to the lifted graph while random lifts preserve expansion with high probability.These properties motivate lifting as a route to larger structured expanders.Source: Current Techniques · pp. 4–5

1.1 Our Results and Techniques

• Explicit abelian lifts produce d-regular expanders with near-Ramanujan, small-relative-eigenvalue, or polylogarithmically weakened guarantees across sub-exponential and exponential lift sizes.The main construction applies to transitive abelian H and uses deterministic polynomial-time algorithms in the stated regimes.Source: §1.1 · pp. 5–6
• The construction extends Mohanty, O’Donnell and Paredes [MOP20] from 2-lifts to larger abelian lifts by compressing depth-first-search traversals of special trace-power walks.For larger lift sizes, the method replaces the counting approach that ceases to yield expansion with alternative encodings of the relevant walks.Source: §1.1 · p. 6
• The exponential-regime construction uses a simpler proof based on a converse of the expander mixing lemma, trading a logarithmic factor in the spectral guarantee for an accessible interpolation of lift-size exponents.It bridges the exponent range from exp(O(n/d^2)) to exp(O(nd)).Source: §1.1 · p. 6

1.2 Derandomized Quantum and Classical Codes

• The results derandomize Panteleev and Kalachev [PK21b] to give explicit quantum LDPC codes with almost linear distance and explicit quasi-cyclic LDPC codes with broad circulant-size choices.The paper also reports quantum codes with distance Ω(N^(1−α)) and dimension Θ(N^α), and quasi-cyclic codes with circulant size up to N/polylog(N).Source: §1.2 · p. 7

Further Directions

• The constructions are explicit but the paper leaves strongly explicit, near-linear-time, and efficiently implementable versions as further goals.This matters especially for quasi-cyclic codes used in practice.Source: Further Directions · p. 8
• The approach does not cover every intermediate lift-size regime or extend near-Ramanujan guarantees beyond the sub-exponential range.The paper identifies derandomizing lifts between 2^{n^Θ(1)} and 2^{O_d(n)} as an open direction.Source: §1.1 · p. 5, Further Directions · p. 8

Characters

• A character is a multiplicative map χ:H→C*, with the trivial character taking value 1 on every group element.For finite groups, character values have unit magnitude; all other characters are non-trivial.Source: §2 · p. 8

Group actions

• The group action is represented as a homomorphism ψ:H→Sym(ℓ), and the analysis assumes the image acts naturally on the ℓ labels.Only the induced permutation action matters for constructing the lift.Source: §2 · p. 8

Graph lifts

• An (H, ℓ)-lift replaces every base vertex with ℓ copies and each edge with matching edges determined by an element of H.The signing assigns s(u,v)∈H to each base edge, connecting (u,i) to (v,s(u,v)·i).Source: §2 · p. 8

Connectivity assumption

• Transitivity is required because a non-transitive abelian action produces disconnected lifts, preventing expansion.The important special case is the cyclic group H=Z_ℓ.Source: §2 · p. 8

Walk operators

• For each character, the signed non-backtracking operator B_s(χ) records χ(s(x,y)) on compatible directed-edge transitions that do not immediately backtrack.The signing extends to reversed edges by s(v,u)=s(u,v)^−1.Source: §2 · pp. 8–9

Spectral decomposition

• For abelian H, the lifted non-backtracking spectrum decomposes across character-indexed operators, with exactly one trivial character when H is transitive.The graph’s nontrivial spectral behavior can therefore be studied through these character components.Source: §2 · p. 9

3 Proof Strategy

• The trace-power method reduces bounding the lifted graph’s spectrum to counting singleton-free non-backtracking hikes on the base graph.Random signings eliminate walks containing singleton edges, leaving hikes in which every edge is traversed at least twice.Source: §3 · pp. 9–10
• The construction first encodes each hike’s traversed subgraph, then encodes the hike using that full hike graph and its locally tree-like structure.The hike graph has at most k edges and k + 1 vertices, enabling DFS-based encodings and segment descriptions.Source: §3 · pp. 10–11
• A generic DFS encoding yields at most n · d · (d −1)^k · 2^2k · k^O(k/g) hike encodings, supporting weaker expansion for larger lifts.Taking k approximately n^δ gives expansion O(sqrt(d)) for lift sizes up to 2^(n^δ), while weakening the guarantee reaches 2^(n^Theta(1)).Source: §3 · p. 11
• Near-Ramanujan bounds require compressing the DFS traversal because storing the full length-2m R/B string introduces an extra factor of 2.The compression exploits that most hike-graph vertices have degree 2 and stores extra recursive data only at the sparse degree-at-least-3 vertices.Source: §3 · pp. 11–12
• The union bound over ℓ−1 non-trivial characters forces walk lengths at least logarithmic in the lift size, while generalized ε-biased distributions replace random signings.The required pseudorandomness remains efficiently constructible because the error can be made smaller than n · d^2k for the relevant walk lengths.Source: §3 · p. 12
• The exact exponential lift regime uses a converse of the expander mixing lemma by Bilu and Linial rather than the preceding trace-power argument.This regime is treated separately because its proof is simpler than the sub-exponential and moderately exponential cases.Source: §3 · p. 12

4 A New Encoding for Special Walks

• The section counts singleton-free hikes in two stages: encoding possible hike graphs and then encoding hikes that realize each graph.Both encodings use traversal histories of depth-first search, with the second exploiting that hike graphs have few vertices of degree greater than 2.Source: §4 · p. 12, §4.1 · p. 13

4.1 Graph Encoding

• The DFS implementation traverses each edge at most twice, allowing the traversal history to recover the encoded graph unambiguously.The algorithm records recursive and backtracking steps while maintaining the DFS stack and visited-vertex order.Source: §4.1 · pp. 13–14
• GraphEnc reconstructs a subgraph from a start vertex, recursive-neighbor choices, and either a full R/B traversal string or a compact recursive-neighbor sequence.Backtracking needs no additional neighbor data because it pops the DFS stack.Source: §4.1 · p. 13

4.1.1 Counting the encodings

• For a fixed d-regular graph, the generic encoding counts connected subgraphs with at most k edges, while the sparse encoding sharply reduces the count when excess vertices are limited.The second bound uses that almost all degree-2 vertices contribute fixed recursive-neighbor information, leaving only the excess vertices to encode flexibly.Source: §4.1.1 · p. 15

4.2 Bounding Singleton Free Hikes

• Singleton-free hikes define connected hike graphs with at most two degree-one vertices, so their counts follow from the constrained subgraph bounds.The resulting bounds combine the number of possible hike graphs with the number of hikes realizing each graph.Source: §4.2 · pp. 16–17
• A bicycle-free graph permits at most (|V(H)|r)^ceil(2k/r) simple singleton-free k-hikes for a fixed hike graph H.The encoding records segment endpoints and signed cycle traversals within radius-r neighborhoods.Source: §4.2 · p. 16
• The resulting total singleton-free hike bound is obtained by combining the constrained graph count with the per-hike-graph encoding bound.The argument uses bicycle-free-radius estimates derived from earlier excess bounds.Source: §4.2 · pp. 16–17

5 Instantiation of The First Two Main Results

• The construction reduces the lifted graph’s spectral analysis to bounding signed non-backtracking operators for all non-trivial characters of the abelian lift group.A union bound over these characters combines the character-wise bounds into one signing with the required spectral gap.Source: §5.1 · pp. 17–18, §5.2 · p. 21

5.1 A Simple Generalization of The Trace Power Method in MOP

• ε-biased distributions suppress singleton-hike contributions because a singleton edge induces a non-trivial character whose expectation has magnitude at most the bias.This extends the pseudorandom-signing argument from Z2 to arbitrary finite abelian groups.Source: §5.1 · p. 18
• Lemma 5.3 assumes bias ν ≤ (nℓd^2)^−1 and states that every non-trivial character fails with probability at most 1/ℓ over D.Source: §5.1 · p. 18

5.2 The Instantiation

• The instantiation uses explicit Mohanty–O’Donnell–Paredes base expanders with large bicycle-free radius and Jalan–Moshkovitz biased distributions.Both ingredients are deterministic and polynomial-time constructible from the group generators and target parameters.Source: §5.2 · pp. 19–20
• Theorem 1.1 constructs a d-regular graph on Θ(nℓ) vertices in deterministic polynomial time for transitive abelian H ≤ Sym(ℓ) and ℓ ≤ exp(n^Θ(1)).The spectral guarantee is obtained by combining the trivial-character contribution, the non-trivial-character bounds, and the non-backtracking-to-adjacency conversion.Source: §5.2 · pp. 20–21
• The proof separates shorter-walk and longer-walk regimes: the first uses the singleton-free hike bound, while the second chooses k = log ℓ.The resulting parameter restrictions explain the allowable exponent in the lift size and the weaker expansion guarantee in the moderately exponential regime.Source: §5.2 · p. 20

6 Derandomizing Exponential Lifts

• Explicit exponential lifts are obtained by a simplified, mostly self-contained derandomization based on Bilu–Linial’s key lemma.The proof applies to abelian lifts and yields a spectral guarantee with logarithmic-factor loss.Source: §6 · p. 21, §6.2 · p. 22

6.1 The Setup and Construction

• Random-walk-generated signings use an expander on ℓ vertices, with a random starting point followed by dn−1 steps to produce lift labels.The construction uses O(log ℓ + (dn−1)log d′) random bits and extends to transitive abelian groups through an expander on |H| vertices.Source: §6.1 · p. 21
• Expander Hoeffding concentration bounds sums of centered real and imaginary character evaluations associated with subsets of base-graph edges.Corollary 6.3 applies the Markov-chain concentration theorem to the signing variables generated by the walk.Source: §6.1 · p. 22

6.2 A Simpler Lifting Proof

• The proof decomposes each character matrix into real symmetric matrices C and D, then bounds their Boolean Rayleigh quotients before recovering spectral bounds.Bilu–Linial’s discretization lemma converts Boolean-vector bounds into real spectral control up to logarithmic factors.Source: §6.2 · pp. 22–23
• Theorem 6.6 gives a deterministic construction of d-regular lifted graphs, and in particular provides explicit polynomial-time constructions when ℓ=exp(O(n)).The algorithm enumerates signings generated from an expander, computes the lifted-graph eigenvalue, and selects the best signing; Lemma 6.5 supplies the existence guarantee.Source: §6.2 · pp. 24–25

7 Explicit Quantum and Classical Codes

• The lifted-product construction starts from a d-regular (Zℓ,ℓ)-lift and applies the Panteleev–Kalachev framework to obtain quantum and classical codes.The construction uses a Tanner code T(G,C0), a cycle graph on ℓ vertices, and the lifted product LP(B,F).Source: §7 · p. 25
• The underlying Panteleev–Kalachev theorem requires sufficiently small ε, sufficiently large constant d, and a base code whose code and dual attain the Gilbert–Varshamov bound.Under these conditions, the Tanner code is good quasi-cyclic LDPC and the lifted product is LDPC with distance Θε,d(ℓ).Source: §7 · p. 25
• The original construction used uniformly random Zℓ signings, whereas the paper replaces them with explicit expanding lifts and thereby controls circulant size and quantum-code parameters.Constant degree is essential because code locality is essentially d and must remain constant for LDPC status.Source: §7 · p. 25
• Explicit polynomial-time constructions yield good quasi-cyclic LDPC codes with block length N and circulant size up to N/polylog(N).In the exponential-lift regime, the circulant size is Θ(N/log N).Source: §7 · pp. 25–26
• Explicit quantum LDPC codes achieve distance Ω(N^(1−α)) and dimension Θ(N^α) for every constant α>0.Choosing a polynomial-sized lift gives the stated distance and dimension parameters through the lifted-product construction.Source: §7 · pp. 25–26

A.1 Diagonalizing Non-backtracking Operator

• A signing induces a block non-backtracking walk matrix whose nonzero blocks are permutation representations of the signing labels.For the lifted graph, this block matrix exactly equals the generalized non-backtracking matrix BG(ρ).Source: §A.1 · p. 29
• Because H is abelian, its commuting permutation matrices are simultaneously diagonalizable by characters.The representation takes the form ρ(h)=F diag(χ1(h),…,χℓ(h))F−1.Source: §A.1 · p. 29
• The lifted non-backtracking spectrum is the union of the spectra of the character-specific non-backtracking matrices.For a transitive action, exactly one character is trivial.Source: §A.1 · pp. 29–30
• The appendix’s index permutation rearranges coordinates so the block-diagonal character decomposition is expressed in the lifted graph’s natural ordering.This is the role of the permutation T in the similarity transformation.Source: §A.1 · pp. 29–30

A.2 A Simple Consequence of Ihara-Bass

• The paper extends a claim from [MOP20] to general signings by mapping adjacency eigenvectors to non-backtracking eigenvectors.The constructed edge function g satisfies Bg=βg whenever β solves β²−αβ+(d−1)=0 for an adjacency eigenvalue α.Source: §A.2 · pp. 30–31
• The eigenvector correspondence remains valid in the signed case after incorporating the edge signing into the definition of g.The signed calculation gives Bg=βg using the signed adjacency entries.Source: §A.2 · pp. 30–31
• If the second non-backtracking spectral radius satisfies ρ2(B)≤λ/2 for λ>2√(d−1), then the adjacency spectral radius satisfies ρ2(A)≤λ.Consequently, λ(G) is bounded by twice the maximum relevant non-backtracking spectral scale.Source: §A.2 · p. 31

• DFS takes a connected graph and starting vertex as input, and outputs a traversal T together with step types σ.Source: B A Precise Implementation of DFS · p. 31
• The implementation colors all vertices green initially, then processes a green vertex by recoloring it yellow.Source: B A Precise Implementation of DFS · pp. 31–32
• For each eligible neighbor u that is not red and is not the parent, DFSRec recursively continues from u along edge (v,u).Source: B A Precise Implementation of DFS · p. 32
• Each edge is traversed exactly twice: first in a recursive step and later in a backtrack step.Source: B A Precise Implementation of DFS · pp. 31–32