Asymptotically Good Quantum and Locally Testable Classical LDPC Codes

• The results resolve longstanding open problems because asymptotically good quantum LDPC codes were previously unavailable, while the classical construction achieves constant locality, rate, and normalized distance.The paper frames these problems as the qLDPC conjecture and the classical c3-conjecture.Source: Introduction · pp. 2–3
• For every R∈(0,1/2), the authors construct explicit classical (ω,s)-locally testable LDPC families with rate at least R and distance Θ(n).The locality ω and soundness s are universal constants, and the codes have parameters [n,k⩾Rn,d=Θ(n)]_q.Source: Introduction · p. 2
• For every R∈(0,1), they construct explicit quantum LDPC families with rate at least R and minimum distance Θ(n), proving the qLDPC conjecture.These codes have parameters ⟦n,k⩾Rn,d=Θ(n)⟧_q and are not necessarily locally testable.Source: Introduction · p. 3
• Product-expansion of the local codes and global small-set expansion of the underlying graph provide the ingredients for the distance and local-testability proofs.Random local-code pairs have product-expansion with high probability, while spectral expanders and their finite covers supply the required small-set expansion.Source: Introduction · pp. 5–6
• The construction uses lifted products of expander codes over non-abelian groups, generalizing tensor and hypergraph products through chain complexes over group algebras.The relevant complexes are A⊗_G B*; their classical and quantum codes arise from homology groups of the resulting three-term complex.Source: Introduction · pp. 3, 4, 6

1.1 Chain complexes

• Chain complexes of finite-dimensional vector spaces over Fq provide a common framework for defining classical and quantum codes with desired parameters.Source: §1.1 · p. 7
• A 2-term chain complex yields the classical linear code ker ∂1, with parity-check matrix H := ∂1.The 1-chain space Fq^n represents n bits, while the 0-chain space Fq^m represents m checks.Source: §1.1 · p. 7
• A 3-term chain complex yields a quantum CSS code Q = Q(HX, HZ) with HX := ∂1 and HZ := ∂∗2.The 1-cell space represents qubits, while 0-cells and 2-cells represent X-checks and Z-checks, respectively.Source: §1.1 · p. 7
• The quantum code length is n = dim Fq^n, and its dimension is dim H1(C) = ker ∂1 / im ∂2 = CX/C⊥2.Source: §1.1 · p. 7
• The minimum distance d(Q) is the smaller of the distances of H1(C) and its dual chain complex H1(C∗).These quotient-space distances use the quotient Hamming norm, minimizing the representative weight within each homology class.Source: §1.1 · p. 7
• The distances d(H1(C)) and d(H1(C∗)) are called the 1-systolic and 1-cosystolic distances, respectively.Source: §1.1 · p. 7

Definition

• The lifted product A ⊗_R B combines chain complexes that are free R-modules, with R-linear boundary maps and compatible left/right actions when R is noncommutative.Its k-chains are ⨁_{i+j=k} A_i ⊗_R B_j, and the boundary combines the two factor boundaries with the usual sign.Source: §1.2 · p. 8

Relation to prior constructions

• When R = F_q, the lifted product recovers the product construction, while m = n = 1 gives the hypergraph product, and R = F_2[x]/(x^ℓ−1) yields the hyperbicycle construction.These equivalences place the lifted product within a broader family of known quantum LDPC constructions.Source: §1.2 · p. 8

Group-algebra formulation

• For R = F_qG, freeness is equivalent to a free group action on the distinguished bases, and the product basis consists of elements a · g · b with boundary ∂(a · g · b) = (∂_A a) · g · b + (−1)^i a · g · (∂_B b).The construction is denoted A ⊗_G B and can be identified with a CSS code described by corresponding parity-check matrices.Source: §1.2 · p. 9

Relation to balanced products

• The G-lifted product is a free-action special case of the balanced product, producing a more regular structure than the general non-free-action construction.The current work also introduces new non-abelian lifted products based on double covers of Cayley graphs, which are similar but not equivalent to the cited horizontal subsystem codes.Source: §1.2 · p. 10

Expander graphs

• Tanner codes on spectral expander graphs were proposed as expander codes, and Ramanujan graphs or their double-covers later support lifted-product chain complexes with strong expansion properties.The resulting CSS codes connect these constructions to notions studied in high-dimensional expander theory.Source: §1.3 · pp. 10–11
• Spectral expansion of an n-vertex d-regular graph is quantified by λ(Γ)=max(|λ2|,|λn|), while smaller λ2 yields a larger Cheeger constant.The Alon–Boppana bound limits how small λ2 can be asymptotically, and Ramanujan graphs nearly attain this limit.Source: §1.3 · pp. 10–11

Graph lifts

• An ℓ-lift replaces every base-graph vertex and edge by ℓ replicas connected according to edge-specific permutations, while voltage assignments over a group G define the corresponding regular cover.The derived graph has vertices V(Γ)×G and connects lifted endpoints according to the assigned group element, with left and right conventions distinguished for non-abelian groups.Source: §1.3 · p. 11
• For cyclic groups, shift lifts include a double-cover whose second eigenvalue satisfies λ2(¯Γ)=λ(Γ), while sufficiently large random shift lifts preserve good expansion when the base graph expands.These lifts were used to construct quasi-cyclic expander codes whose parity-check matrix H and transpose H* both have good expansion properties.Source: §1.3 · p. 12

Group-based constructions

• The construction starts from small bouquet or multi-edge base graphs, assigns generators of a finite group G to edges, and yields Cayley graphs or their double-covers, including a (p+1)-regular bipartite G-lift with n=2|G| vertices.For Xp,q, the double-cover ¯Xp,q is a (p+1)-regular bipartite G-lift with n=2|G| vertices, and proves λ(Xp,q)≤2√p.Source: §1.3 · p. 12

• A linear [n, k]_q code is a k-dimensional subspace with length n, rate k/n, and minimum distance defined by the least weight of a nonzero codeword.When its minimum distance is d, the code is denoted [n, k, d]_q.Source: §1.4 · p. 13
• A classical linear code can be represented as the row space of a generator matrix G or the kernel of a parity-check matrix H, with GH∗ = 0 and ranks k and n − k, respectively.The code defined by H is written ker H.Source: §1.4 · p. 13
• The dual C⊥ of an [n, k]_q code is an [n, n − k]_q code, and generator and parity-check matrices exchange roles under duality.Source: §1.4 · p. 13
• The framework applies equally to subspaces of any based n-dimensional F_q-vector space by identifying its distinguished basis with F_q^n.This lets the paper treat such subspaces as linear codes and use the preceding terminology.Source: §1.4 · p. 13
• Two codes are permutation equivalent when a basis-preserving linear map maps one code to the other, while matrices are equivalent under row and column permutations.Matrix equivalence implies equivalence of their kernels.Source: §1.4 · p. 13

1.5 Expander codes

• Expander codes are Tanner codes built from expander graphs, represented through chain complexes with local boundary maps and local systems.The global Tanner code is the kernel of the boundary map, while each local subcode is the kernel of its corresponding local map.Source: §1.5 · p. 14
• G-lifting Tanner complexes via voltage assignments produces right G-modules that can be used in the lifted product construction.The lifted complex is defined on the G-lifted graph and retains the local-code structure induced by the parity-check matrix h.Source: §1.5 · p. 14
• The first of the constructed 3-term complexes is used to establish two asymptotically good families: quantum LDPC codes and classical LTCs.The resulting LTC rate is bounded above by 1/2 according to Theorem 1.Source: §1.5 · p. 15
• A related complex C′•( ¯Xw−1,t; h, h′) is conjectured to yield asymptotically good LTCs with rate arbitrarily close to 1.For local parity-check matrices h and h′ whose local-code rates approach 1, the resulting classical-code rate also approaches 1.Source: §1.5 · p. 15

Incidence chain complexes

• An incidence chain complex is a based chain complex whose boundary matrix entries lie in {−1, 0, 1}, with basis elements viewed as cells.The section focuses on coefficients over Z and Fq, and calls the corresponding basis elements cells.Source: §1.6 · pp. 15–17

Cell posets

• The cell poset orders basis cells through boundary incidence, with a covering relation generating the full partial order.For a based chain complex, c′ ≺ c exactly when c′ belongs to the support of ∂c; finite posets are determined by their covering relations.Source: §1.6 · pp. 15–16

Graded posets

• The cell poset of a based (co)chain complex is graded, with levels corresponding to cells of the same dimension.A graded poset has a rank function, and finite graded posets decompose into rank levels containing minimal and maximal elements at their extremes.Source: §1.6 · p. 16

Examples

• Simplicial complexes and graphs are graded-poset examples, with faces ranked by dimension and graph vertices and edges forming two incidence levels.Two-level posets also represent incidence systems, undirected multigraphs, and hypergraphs.Source: §1.6 · p. 16

Chain-complex representations

• The framework represents graphs, incidence systems, and simplicial complexes by based chain complexes over Z, generalizing these objects through integer boundary maps.For graphs, the boundary matrix is the zero–one incidence matrix; for simplicial complexes, boundaries use the alternating sum of faces after fixing a vertex order.Source: §1.6 · pp. 16–17

Incidence numbers

• Incidence numbers record signed cell incidences in the boundary map, while the condition ∂2 = 0 imposes relations among them.For incident cells x and x′, the coefficient [x : x′] lies in {−1, +1}; it is taken to be zero for non-incidences.Source: §1.6 · p. 17

1.7 Products of graphs and posets

• The lifted product X ×G Y is defined for finite posets with free group actions, using orbit representatives and covering relations, with an additive rank function for graded posets.When |G| = 1, the construction reduces to the ordinary product X × Y.Source: §1.7 · p. 17
• For graph lifts, the 1-skeleton ˆX ✷G ˆY is a |G|-fold cover of the Cartesian product X ✷Y, and is a G-lift when G is abelian.The construction corresponds geometrically to the balanced product of graphs.Source: §1.7 · pp. 17–18
• The construction uses ˜X = ˆΓ ×G ˆΓ as a three-level, two-dimensional complex with vertices, horizontal and vertical edges, and faces represented geometrically as squares.Its incidence relation supports stars and other sets of cells incident to specified elements.Source: §1.7 · p. 18
• The dual construction X = ˆΓ ×G ˆΓ∗ uses the same underlying set as ˜X but a different partial order and grading, matching the lifted product complex used in the main result.The proof also uses the 1-skeleton Λ := ˆΓ ✷G ˆΓ of ˜X.Source: §1.7 · pp. 18–19

Local systems

• A local coefficient system assigns vector spaces Fx to poset elements and compatible Fq-linear maps Fx→x′ whenever x ⩾ x′.Equivalently, it is a functor from the poset, viewed as a category, to Fq-vector spaces.Source: §1.8 · p. 19
• Given an incidence chain complex and local system F, C•(I; F) uses the direct-sum space FX with a boundary map satisfying ∂2 = 0.When FX is based, the resulting chain complex is also based.Source: §1.8 · p. 19
• The subsection defines standard Hamming weight, block weight wtX, restricted block weight wtS, support, and restriction notation for based complexes.Block weight counts nonzero coefficient spaces rather than individual field coordinates.Source: §1.8 · p. 20
• A Tanner complex for a graph assigns Fq to vertices and edges, with incidence maps given by boundary restrictions; G-lifted Tanner products admit the same local-system representation.The latter representation uses the poset ˆΓ ×G ˆΓ∗ introduced in Subsection 1.7.Source: §1.8 · p. 20

2.1 Local minimality

• Local minimality extends from F2-cohomology to abstract cell complexes with local systems, and bounds quantum-code distance through homological and cohomological distances.The framework also connects locally minimal distance to local testability of Z_i+1(C), while locally minimal distance need not equal the minimum distance of the cycle space.Source: §2.1 · pp. 20–21

2.2 Graph expansion

• An (n,w,λ)-expander is (λn/w, 2λ)-edge-expanding; G-lifts scale the parameter by |G|, while Γ2 inherits (a/w, 2λ^2(1+ln w))-edge-expansion.These lemmas yield Λ expansion Θ(w^1/2) and Λ2 expansion Θ(w ln w), which drive the contradiction for sparse locally minimal cycles.Source: §2.2 · pp. 22–24, §2.3 · p. 26

2.3 Proof outline

• If d_LM(1)(C) = Θ(n), then Z2(C) is locally testable and Q(C) has linear minimum distance; the proof rules out nonzero locally minimal cycles of weight o(n).The construction uses G-lifted Tanner codes and their lifted product complex, with suitable matrices chosen so the required product-expansion conditions hold.Source: §2.3 · p. 26
• The locally minimal distance satisfies LM(C) = Θ(n), matching the length scale of the resulting classical and quantum codes.The proof first shows any nonzero 1-cycle has weight Θ(n), then applies Lemma 1.Source: §2.3 · p. 27

2.4 Local expansion

• For d/3-minimal codewords, vanishing on sufficiently large row or column submatrices forces the entire codeword to vanish, yielding the local-expansion lemma.The argument uses information sets and minimality to show that a zero restriction on A × B implies x = 0 under the stated size conditions.Source: §2.4 · pp. 28–29

2.5 Global expansion

• The graph Λ is (a, 2λ)-edge-expanding, obtained by combining its horizontal and vertical subgraphs, each isomorphic to the base expanded graph.The corresponding graph Λ2 is also edge-expanding with parameters (a/2w, 8λ^2(ln w + 2)).Source: §2.5 · pp. 31–32
• If ∂c = 0, every face-active vertical edge is incident to at least d(ker h) active faces, and under additional weight and distance conditions every active edge touches a labeled vertex.These lemmas connect cycle activity to local code distance and graph expansion for a fixed locally minimal 1-cycle.Source: §2.5 · p. 32
• The local expansion argument converts s active faces around a vertex into s distinct length-2 neighbors in Λ2, establishing s-face expansion after active edges are shown to contain labeled vertices.The proof uses product expansion to obtain wt(f|A×B) ⩾s and Lemma 14 to label the incident active edges.Source: §2.5 · pp. 36–37
• Under the stated product-expansion and distance conditions, every labeled vertex is either m-edge-expanding or s-face-expanding.The conditions include βw ⩾4m + 3, d ⩾4m, and m ⩾max(4s/d, λ).Source: §2.5 · p. 37
• For a (s, 2m, β)-product-expanding pair (ker h, im h′∗) with βw ⩾ 4m+3, d = min(d(ker h), d(im h′∗)) ⩾ 4m, m ⩾ max(4s/d, 2λ′), s ⩾ 2λ′′, λ′ = 2λ, and λ′′ = 8λ2(ln w + 2), every locally minimal 1-cycle c with wtX(c) ⩽ a/2w is zero.The argument concludes that |L| = 0; because each active vertical edge contains labeled vertices, there are no active vertical edges, and hence c = 0.Source: §2.5 · pp. 37–38

2.6 Proof of the theorems

• When min(d(ker h), d(ker h′), d(im h∗), d(im h′∗)) ≥ d and conditions (12) hold, every non-zero locally minimal 1-cycle in A ⊗G B∗ has weight at least a/2w.Source: §2.6 · p. 38
• For every R ∈(0, 1/2) and finite field Fq, an explicit family of (ω, s)-locally testable classical LDPC codes has parameters [n, k ⩾Rn, d = Θ(n)]q.The constants s and ω are universal, and the family is asymptotic in n.Source: §2.6 · p. 39
• The associated classical code Z2(C) is (ω, s)-locally testable with ω := 2w and s := 2w−7/2.Its dimension satisfies k = dim Z2(C) ⩾ n − m ⩾ Rn.Source: §2.6 · p. 39
• The linear distance of Z2(C) follows from the component Tanner code’s expander-code distance, yielding d(T( X̄w−1,t, h)) = Θ(n) for sufficiently large w.The proof chooses w so that d(ker h) > λ2(X̄w−1,t).Source: §2.6 · p. 39
• For every R ∈ (0, 1) and finite field Fq, an explicit quantum LDPC family has parameters ⟨n, k ⩾ Rn, d = Θ(n)⟩q.The construction therefore has both linear rate and linear minimum distance.Source: §2.6 · p. 40
• For the quantum CSS code Q, the homological dimension obeys k = dim(H1(C)) > n − n(1 − R)/2 − n(1 − R)/2 = nR.The construction uses Q = Q(HX, HZ) with HX := ∂1 and HZ := ∂∗2.Source: §2.6 · p. 40

Main conclusions

• Asymptotically good quantum LDPC code families prove the well-known qLDPC conjecture.The authors conjecture that a decoder similar to small-set-flip decoding [26] (see also) could correct adversarial errors up to a constant fraction in linear time.Source: Conclusions · p. 40

Construction

• The quantum codes come from the G-lifted product of two G-lifted Tanner codes, using a non-abelian group G to obtain linear minimum distance.Using cyclic groups C_ℓ with ℓ = Θ(n / log n) instead gives parameters k = Θ(n) and d = Θ(n / log n), and explicit constructions follow from results on explicit C_ℓ-lifted expander graphs [58].Source: Conclusions · pp. 40–41

Classical codes

• The constructed chain complexes yield asymptotically good classical LDPC codes that are locally testable with constant query and soundness parameters, resolving an important conjecture.These classical codes arise from the second homology groups of the constructed complexes.Source: Conclusions · p. 41

Limitations and open problems

• The constructions are considered explicit, but their constant-size local codes currently rely on probabilistic methods, leaving fully explicit local codes as an open problem.Reed–Solomon codes are suggested as a possible option, though it is unclear whether suitable pairs satisfy the required product-expansion property.Source: Conclusions · p. 41

Future directions

• The methods may help establish locally testable qLDPC codes for the qLTC conjecture, which would imply the NLTS conjecture.A proposed candidate is a 5-term chain complex whose middle terms form a good qLDPC code and whose outer terms represent X- and Z-meta-checks; related complexes appear in single-shot decoding [60, Figure 1].Source: Conclusions · pp. 40–41

• A chain complex is a graded collection of vector spaces with boundary maps satisfying ∂i∘∂i+1 = 0, yielding cycles, boundaries, and homology groups Hi(C) = Zi(C)/Bi(C).The condition ∂² = 0 ensures every boundary is a cycle.Source: A Chain complexes · p. 46
• The work uses based bounded complexes, where distinguished basis elements are cells and only finitely many consecutive spaces are nonzero.A bounded complex has length t − s + 1, also called an n-term complex when its length is n.Source: A Chain complexes · p. 46
• A cochain complex is obtained by dualizing a chain complex, replacing boundary maps with coboundary maps δ satisfying δ² = 0 and defining cohomology analogously.Its cochains, cocycles, and coboundaries produce Hi(C) = Zi(C)/Bi(C).Source: A Chain complexes · p. 47
• With distinguished bases, boundary and coboundary maps are represented by matrices over Fq, with δi−1 equal to the transpose of ∂i.This coordinate representation identifies chain and cochain spaces with corresponding finite-dimensional vector spaces.Source: A Chain complexes · p. 47
• Under index reversal, the dual chain complex of a CSS code swaps HX and HZ, corresponding to the dual CSS code Q∗.The convention Ci = C−i lets a cochain complex also be viewed as a chain complex.Source: A Chain complexes · p. 47

B Lifted product of two classical codes

• The lifted product generalizes known qLDPC constructions by lifting the hypergraph product from scalar matrices to block-matrix representations.Given A and B, replacing their entries with ℓ×ℓ matrices produces block checks ˆHX and ˆHZ as in Equation (13).Source: B Lifted product of two classical codes · pp. 47–48
• The resulting matrices define a quantum CSS code LP(ˆA, ˆB) exactly when every block entry of ˆA commutes with every block entry of ˆB.A commutative matrix ring is sufficient, while the condition is also necessary for a well-defined CSS code.Source: B Lifted product of two classical codes · p. 48
• Associative, potentially noncommutative algebras still yield LP(A, B) by using right regular representations for A and left regular representations for B.Associativity ensures that the corresponding operators commute, so arbitrary matrices over the algebra produce the required CSS code.Source: B Lifted product of two classical codes · p. 48
• Toric code and Haah’s cubic code are lifted products over polynomial quotient rings, with lattice size L setting the parameter.They arise respectively as LP(1+x, 1+y) and LP(1+x+y+z, 1+xy+xz+yz).Source: B Lifted product of two classical codes · pp. 48–49
• Lifted products also apply to quasi-twisted codes, whose parameters can sometimes improve on quasi-cyclic and cyclic codes, motivating an open question about good quantum CSS codes.For an algebra R and matrix H over R, C(H) is quasi-twisted, or constacyclic when m=n=1; whether such inputs yield quantum CSS codes with good parameters remains open.Source: B Lifted product of two classical codes · p. 49

Normed abelian groups

• An abelian normed group has translation-invariant distance, with standard Hamming distance as an example on F_q^n.Invariant distances correspond one-to-one with norms via d(x,y)=|x−y| and |x|=d(x,0).Source: C Normed abelian groups · p. 49

Quotient norm metrics

• Quotienting a normed abelian group by a subgroup N induces a quotient norm metric on M/N.The quotient norm satisfies the norm axioms, and its distance agrees with the quotient metric construction.Source: C Normed abelian groups · pp. 49–50
• For subgroups containing N, the quotient subgroup’s minimal distance is inherited from the quotient metric and admits a simpler formula.The construction applies to C/N ⊆ M/N whenever N ⊆ C ⊆ M.Source: C Normed abelian groups · p. 50

Systolic norms

• Canonical projection preserves distances to quotient subsets and identifies coset norms with distances to N, enabling a systolic norm on M.For [x]=x+N, d([x],Y)=d(x,Y) and |[x]|=d(x,N).Source: C Normed abelian groups · p. 50

D List of symbols and standard notations

• Basic algebraic notation includes [n], finite fields Fq, matrix sets Rm×n, identity matrices In, kernels, images, transposes, and dual chain complexes.Source: D List of symbols and standard notations · p. 51
• Formal sums use coefficients in a local system, with wt(a) denoting Hamming weight and wtS(a) block Hamming weight relative to S.Source: D List of symbols and standard notations · p. 51
• The notation also specifies norms, supports, restrictions, group algebras, regular covers, graph adjacency and squares, oriented edges, poset covers, and Ramanujan double-covers.Source: D List of symbols and standard notations · p. 51
• Definitions cover G-lifted products, Tanner codes and their lifted variants, permutation equivalence, cycles, boundaries, homology, locally minimal distance, and restricted boundary maps.Source: D List of symbols and standard notations · p. 51