PaperlayerView exact revision on arXiv

Source-linked AI summary

Asymptotically Good Quantum and Locally Testable Classical LDPC Codes

Pavel Panteleev, Gleb Kalachev

arXiv:2111.03654v2cs.ITquant-ph

TL;DR

The paper asks whether constant-rate classical and quantum LDPC codes with linear distance can be obtained, and whether the classical codes can also be locally testable. It uses lifted products of expander codes over non-abelian groups and proves asymptotically good quantum LDPC families, alongside asymptotically good classical LDPC families with constant-query and constant-soundness local testability.

  • Problem

    The paper addresses open conjectures on asymptotically good quantum LDPC codes and classical locally testable codes with constant rate, locality, and normalized minimum distance.

  • Method

    The construction uses lifted products of expander codes over non-abelian groups, with a product-expansion condition on the local codes.

  • Results

    The paper proves asymptotically good quantum LDPC families and asymptotically good classical LDPC families that are locally testable with constant query and soundness parameters.

  • Takeaways & Limitations

    The results give affirmative answers to the qLDPC and classical locally testable code conjectures within the stated construction and assumptions.

  • Takeaways & Limitations

    The local codes used in the expander constructions are explicit only in the broader sense that their constant-size instances are obtained probabilistically.

Abstract

from arXiv · show

We study classical and quantum LDPC codes of constant rate obtained by the lifted product construction over non-abelian groups. We show that the obtained families of quantum LDPC codes are asymptotically good, which proves the qLDPC conjecture. Moreover, we show that the produced classical LDPC codes are also asymptotically good and locally testable with constant query and soundness parameters, which proves a well-known conjecture in the field of locally testable codes.

Introduction

The paper addresses open conjectures by constructing constant-rate classical and quantum LDPC codes through lifted products over non-abelian groups. It proves asymptotically good quantum LDPC families and classical codes that are also locally testable with constant parameters.

  • Motivation: Classical and quantum locally testable codes are sought with constant locality, constant rate, and constant normalized minimum distance.The quantum version remains open even without local testability, as the qLDPC conjecture asks for constant rate and normalized minimum distance.
  • Classical result: For every R ∈ (0, 1/2) and finite field Fq, an explicit family of classical LDPC codes has k ⩾ Rn and d = Θ(n), with constant locality and soundness.This establishes constant rate, constant normalized minimum distance, and constant-query local testability for the classical family.
  • Quantum result: For every R ∈ (0, 1) and finite field Fq, an explicit family of quantum LDPC codes has k ⩾ Rn and d = Θ(n).The result gives an affirmative answer to the qLDPC conjecture, although local testability is not claimed for these quantum codes.
  • Decoding: The classical constructions admit a linear-time bit-flipping decoder for errors up to a constant fraction of n, whereas a corresponding quantum decoder remains conjectural.The proposed quantum decoder would be a variant of small-set-flip decoding.
  • Method: The construction uses lifted products of expander codes over non-abelian groups, with product-expansion required for the proof.The lifted product generalizes tensor and hypergraph product constructions and is formulated using chain complexes over group algebras.
  • Classical local testability: The second homology groups of the constructed complexes yield asymptotically good classical LDPC codes that are locally testable with constant query and soundness parameters.This byproduct resolves an important conjecture in locally testable codes.

1.1 Chain complexes

The section connects chain complexes to classical and quantum CSS codes through boundary maps, kernels, quotients, and homology groups. These homological descriptions encode code length, dimension, and distance.

  • Classical codes: A 2-term chain complex identifies the kernel of its boundary map with a classical linear code.The 1-chain space represents bits, while the 0-chain space represents parity checks.
  • Quantum CSS codes: A 3-term chain complex identifies with a quantum CSS code whose X- and Z-check matrices are derived from consecutive boundary maps.The X-check matrix is ∂1, while the Z-check matrix is the transpose of ∂2.
  • Quantum CSS codes: The quantum code length equals the dimension of the 1-chain space, while its dimension equals the first homology dimension.Specifically, H1(C) = ker ∂1 / im ∂2.
  • Quantum CSS codes: Quantum minimum distance can be expressed through the 1-systolic and 1-cosystolic distances of the chain complex and its dual.These are quotient-space distances associated with H1(C) and H1(C*).

1.2 Lifted product

The lifted product forms a tensor product chain complex from two free module complexes over an algebra, especially a group algebra. Its basis and boundary map yield a corresponding CSS-code description and connect to earlier product constructions.

  • Definition: The lifted product of two free module chain complexes is their tensor product complex over an associative algebra R.For noncommutative R, the first complex is a right R-module and the second is a left R-module.
  • Definition: The lifted product is a based chain complex whose distinguished basis consists of elements a · r · b.Here a and b come from the distinguished module bases and r from a fixed basis of R.
  • Relations to prior constructions: The lifted product specializes to known product constructions, including the product construction and hypergraph product in stated parameter regimes.When R = Fq it gives the product construction; when m = n = 1 it gives the hypergraph product.
  • Group-algebra construction: For two classical codes invariant under free group actions, their parity-check matrices define 2-term complexes whose lifted product is A ⊗R B.The construction uses the group algebra R = FqG.
  • Boundary map: The tensor-product boundary acts on a · g · b by applying the boundary from each factor with the graded sign (−1)i.The two component maps are described separately as ∂A⊗G id and id⊗G ∂B.
  • Relations to prior constructions: The G-lifted product permits dual complexes and is a special case of the balanced product, while the current work adds non-abelian examples based on double-covers of Cayley graphs.The dual reverses left and right module actions, enabling A ⊗G B* for right G-modules.

1.3 Expander graphs and lifts

This section introduces spectral expansion, graph lifts, and voltage assignments used to build the graphs underlying the constructions. Cayley graphs and their double-covers provide explicit non-abelian lift examples.

  • Expander graphs: A d-regular graph is an (n, d, λ)-expander when its largest absolute nontrivial adjacency eigenvalue is at most λ.The graph eigenvalues are ordered λ1 ≥ ··· ≥ λn, and λ(Γ) = max(|λ2|, |λn|).
  • Expander graphs: For d-regular graphs, a smaller second eigenvalue yields a larger Cheeger lower bound through h(Γ) ≥ 1/2(d − λ2(Γ)).The Alon–Boppana bound limits how small λ2 can be asymptotically.
  • Graph lifts: A G-lift replaces each base-graph vertex and edge with |G| replicas connected according to voltage-assigned group elements.Left and right derived graphs differ by whether the voltage multiplies on the left or right.
  • Graph lifts: The bipartite double-cover of a graph is a 2-lift whose second eigenvalue satisfies λ2(¯Γ) = λ(Γ).This construction assigns the non-identity element of C2 to every base edge.
  • Voltage assignments: Starting from bouquet or two-vertex base graphs, assigning generators to edges produces Cayley graphs or their double-covers.For the bouquet graph, the derived graph is Cay(G, S) when S is symmetric; the two-vertex construction yields the double-cover.
  • Examples: The construction uses small base graphs and finite groups to obtain non-abelian lifted graphs, including double-covers of Cayley graphs.The cited Ramanujan-family example uses Cayley graphs from PSL(Fq^2) and their bipartite double-covers.

1.4 Classical codes

This section reviews linear codes through their generator and parity-check matrices, standard parameters, duality, and permutation equivalence. It also extends the discussion from coordinate spaces to arbitrary based vector spaces.

  • Basic definitions: A linear [n, k]q code is a k-dimensional subspace of Fq^n, with rate k/n and minimum distance given by its least nonzero codeword weight.The parameters n and k are the length and dimension, respectively.
  • Matrix representations: A code can be represented either by a generator matrix through its row space or by a parity-check matrix through its kernel.The generator and parity-check matrices satisfy GH* = 0.
  • Duality: The dual of a linear [n, k]q code is an [n, n − k]q code under the standard scalar product.A generator matrix for a code serves as a parity-check matrix for its dual, and conversely.
  • Based vector spaces: The framework permits codes in arbitrary based n-dimensional Fq-vector spaces by identifying their distinguished bases with coordinate spaces.Subspaces of these based spaces inherit the linear-code terminology.
  • Equivalence: Two codes are permutation equivalent when a basis-preserving linear map sends one code to the other.Matrices are permutation equivalent when related by row and column permutations, which preserve kernel equivalence.

1.5 Expander codes

Expander codes are Tanner codes built from expander graphs, with local constraints imposed at vertices. The section describes their lifted Tanner-complex representation and its use in lifted-product code constructions.

  • Expander codes: Expander codes are Tanner codes obtained from expander graphs, with symbols assigned to edges and vertex neighborhoods constrained by a local code.A word belongs to the global code exactly when the incident-edge symbols at every vertex form a codeword of the local code.
  • Tanner complexes: A Tanner complex consists of an edge space and a vertex space connected by local boundary maps, defining a global code and vertex subcodes.The global code is ker ∂1, while the local subcodes are kernels of the vertex boundary maps.
  • Tanner complexes: When all local boundary matrices are equivalent to h, every local code is equivalent to ker h, denoted through the class T(Γ; h).This uniform local structure supports the expander-code formulation used later in the lifted constructions.
  • Lifted Tanner complexes: A G-lift of a graph induces a G-lifted Tanner complex whose boundary map acts on lifted vertices and edges and extends linearly.The lifted complex can be represented using tensor products over Fq and identified with the lifted graph's Tanner complex.
  • Lifted products: Because lifted Tanner complexes are right G-modules, they can be used in the lifted-product construction with local parity-check matrices.The construction fixes a Cayley graph and two parity-check matrices to define three-term chain complexes.
  • Construction outcomes: The first constructed complex yields asymptotically good quantum LDPC codes and classical LTCs, while the corresponding LTC rate is bounded above by 1/2.A related complex is conjectured to yield LTCs with rate arbitrarily close to 1; for local matrices h, h′ of size r × w, its rate is at least 1−4r/w.

1.6 Posets and incidence chain complexes

This section introduces incidence chain complexes and their cell posets, connecting combinatorial objects such as graphs and simplicial complexes to algebraic boundary maps.

  • Incidence complexes: An incidence chain complex has integer boundary matrices whose entries lie in {−1, 0, 1}, with basis elements interpreted as cells.The corresponding cell poset records which basis cells occur in the boundaries of others.
  • Cell posets: A cell poset is defined from a based chain complex by declaring a basis cell to cover another when the latter appears in its boundary support.The induced order captures the incidence relation among cells.
  • Cell posets: A graded poset has a rank function whose levels partition the elements, and the cell poset of a based chain complex is graded by cell dimension.The elements at the lowest and highest levels are minimal and maximal, respectively.
  • Incidence complexes: The boundary of a simplicial k-face is the signed sum of its codimension-one faces, extended linearly to all chains.The signs depend on the fixed vertex ordering, and the boundary matrices therefore have entries in {−1, 0, 1}.
  • Combinatorial interpretation: Graphs can be represented as two-level posets and simplicial complexes as subset-closed families, allowing both to be described through based incidence chain complexes.In characteristic 2, incidence signs can be ignored, so the cell poset alone determines the corresponding incidence complex.

1.7 Products of graphs and posets

Products of graphs and posets provide the combinatorial framework for lifted products, with group actions modifying incidence relations and grading.

  • Products of posets: The product poset X ×G Y is defined from quotient representatives, group elements, and covering relations inherited from either factor.Its rank is the sum of the ranks of the two factors when both posets are graded.
  • Products of graphs: For graphs, the ordinary product poset corresponds geometrically to the direct product, whose first two levels represent the Cartesian product graph.The group-indexed product has a balanced-product interpretation.
  • Products of graphs: The lifted Cartesian product of G-lifted graphs is the 1-skeleton of their group-indexed poset product and forms a |G|-fold cover of the standard Cartesian product.When G is abelian, this cover is regular and is itself a G-lift of the Cartesian product.
  • Lifted-product geometry: Elements of ˜X can be represented as triples x · g · y, with covering relations inherited from incidences in the lifted graph.This representation organizes the cells used to describe the lifted-product geometry.
  • Lifted-product geometry: The construction uses both a poset X = ˆΓ ×G ˆΓ* and a cell poset ˜X = ˆΓ ×G ˆΓ on the same underlying set but with different orders and rank functions.The dual factor gives the product poset used for the lifted-product complex, while the non-dual version supports a geometric interpretation.
  • Lifted-product geometry: The geometric cell poset ˜X has vertices, two edge types, and faces, while X has levels E↑, F ∪ V, and E→.The 1-skeleton Λ is formed from the vertices and edges of ˜X.

1.8 Local systems

Local systems assign vector spaces and compatible linear maps to the elements and order relations of a poset, producing chain complexes with locally varying coefficients.

  • Coefficient spaces: A direct-sum coefficient space represents chains as formal sums of cells with coefficients drawn from their corresponding local vector spaces.Distinguished bases on local spaces induce a basis for the whole chain space.
  • Local systems: A local system assigns a vector space F_x to each poset element and a linear map F_x→x′ for every relation x ⩾ x′, subject to composition compatibility.Equivalently, it can be viewed as a functor from the poset to vector spaces over Fq.
  • Chain complexes with local coefficients: Given an incidence complex and a local system, the chain space is the direct sum of local coefficient spaces, with a boundary map defined using incidence numbers and structure maps.The resulting boundary operator satisfies ∂^2 = 0.
  • Weights and supports: The framework distinguishes ordinary Hamming weight from block weight, which counts nonzero local coefficient blocks.Relative block weight and support can be restricted to a selected subset of cells.
  • Restricted boundary maps: Boundary maps can be restricted between subsets of cells by applying the global boundary and then projecting to the target subset.This supplies localized maps for analyzing selected portions of a chain complex.
  • Applications: Tanner complexes and lifted products can be represented using local systems, including the G-lifted product of two G-lifted Tanner complexes.In this terminology, Tanner complexes may also be called Tanner codes or identified with the global codes they define.

2 Proof of the main results

The proof combines local minimality, product expansion, and graph expansion to establish linear distances and local testability for lifted-product codes. These properties yield explicit asymptotically good classical and quantum LDPC families.

  • Local minimality: Local minimality extends prior simplicial-complex arguments to abstract cell complexes with local-system coefficients.The proof uses locally minimal chains as its central framework.
  • Local minimality: Locally minimal distance can differ from minimum cycle distance because minimum-weight cycles need not be locally minimal.For w-limited qLDPC codes, a boundary codeword can have weight at most w while failing local minimality.
  • Expansion: Product-expanding component codes and edge-expanding graphs control active elements in the lifted-product complex.The proof uses product expansion for local behavior and expansion of Λ and Λ2 for global behavior.
  • Expansion: A locally minimal 1-cycle of sufficiently small weight must vanish, because every labeled vertex is forced to be edge- or face-expanding and expansion yields a contradiction.Corollary 1 gives the two alternatives, while the subsequent counting argument forces the labeled set and active edges to be empty.
  • Distance bounds: Every non-zero locally minimal 1-cycle has weight at least a/2w, producing linear locally minimal distance in the chain complex.The bound follows by applying the expansion conditions to the lifted product A ⊗G B∗.
  • Theorems: For every R ∈(0, 1), explicit quantum LDPC families have parameters Jn, k ⩾Rn, d = Θ(n)Kq as n →∞.The dimension argument establishes k ⩾Rn, while the distance analysis supplies linear minimum distance.

Conclusions

The work proves the qLDPC conjecture by constructing asymptotically good quantum LDPC codes, and also derives asymptotically good locally testable classical LDPC codes. The construction uses lifted products, with non-abelian groups enabling linear minimum distance.

  • Conclusions: Asymptotically good quantum LDPC families prove the qLDPC conjecture.The codes have constant rate and normalized minimum distance.
  • Conclusions: The authors conjecture that a small-set-flip-like decoder could correct adversarial errors up to a constant fraction in linear time.
  • Conclusions: The quantum codes arise from the G-lifted product of two G-lifted Tanner codes.A non-abelian group G is used to obtain linear minimum distance.
  • Conclusions: The constructed chain complexes yield asymptotically good classical LDPC families that are locally testable with constant query and soundness parameters.Their second homology groups provide the classical codes.
  • Conclusions: The classical-code construction resolves an important conjecture in locally testable codes.
  • Conclusions: The proposed constructions are considered explicit, but their constant-size local codes are still obtained probabilistically.Finding an explicit construction of these local codes remains open, and it is unclear whether suitable MDS pairs satisfy the required product-expansion property.

A Chain complexes

This section introduces chain and cochain complexes, their homology and cohomology spaces, and their matrix representations. It also explains how dual complexes correspond to dual CSS codes.

  • A Chain complexes: A chain complex is a graded vector space with boundary maps whose consecutive composition is zero.The condition ∂² = 0 implies that boundaries are contained in cycles, enabling homology groups.
  • A Chain complexes: The i-th homology group is the quotient of i-cycles by i-boundaries.An n-term complex has length n.
  • A Chain complexes: A graph provides a 2-term chain-complex example with vertices in C_0, edges in C_1, and each edge mapped to the sum of its endpoints.
  • A Chain complexes: Dualizing a chain complex produces a cochain complex with coboundary maps satisfying δ² = 0.This defines cocycles, coboundaries, and cohomology groups.
  • A Chain complexes: With distinguished bases, boundary and coboundary maps become matrices, with the coboundary matrix equal to the transpose of the boundary matrix.
  • A Chain complexes: The dual chain complex of a CSS code reverses the roles of its X- and Z-check matrices.

B Lifted product of two classical codes

The lifted product generalizes the hypergraph product by replacing scalar matrix entries with matrix representations from an algebra. Using left and right regular representations permits non-commutative constructions when associativity ensures the required identities.

  • B Lifted product of two classical codes: The lifted product generalizes the hypergraph product and other constructions of quantum LDPC codes.
  • B Lifted product of two classical codes: Given classical parity-check matrices A and B, the hypergraph product produces a quantum CSS code with block parity-check matrices.The Z-check matrix is H_Z := [I_n_a ⊗ B^*, A^* ⊗ I_n_b].
  • B Lifted product of two classical codes: Replacing entries of A and B by ℓ × ℓ matrices creates enlarged block matrices over F_q.
  • B Lifted product of two classical codes: The lifted-product CSS checks are defined as Ĥ_X := [Â ⊗ I_m_b, −I_m_a ⊗ B̂] and Ĥ_Z := [I_n_a ⊗ B̂^*, Â^* ⊗ I_n_b].Each transposed block also transposes its ℓ × ℓ matrix blocks.
  • B Lifted product of two classical codes: The construction yields a well-defined CSS code exactly when every block from  commutes with every block from B̂.
  • B Lifted product of two classical codes: Associative algebras support the construction through right and left regular representations, including non-commutative group-algebra settings.For commutative algebras, the left and right representations coincide.

C Normed abelian groups

This section develops invariant metrics and norms on abelian groups, then extends them to quotient groups and subgroups. These constructions provide the distance and systolic-norm framework used later.

  • C Normed abelian groups: The framework assumes non-empty subsets have minimal distance, with singleton subsets assigned distance infinity.
  • C Normed abelian groups: An invariant metric on an abelian group is unchanged by translating both arguments by the same group element.
  • C Normed abelian groups: Invariant distances correspond to norms through d(x,y) = |x−y| and |x| = d(x,0).For vector spaces, the standard Hamming distance is an example.
  • C Normed abelian groups: The minimal distance of a subgroup can be expressed using the associated group norm.
  • C Normed abelian groups: A group norm induces a quotient norm metric on M/N, with coset norms determined by distance to the subgroup N.Canonical projection preserves distances to projected sets and relates coset weight to distance from N.
  • C Normed abelian groups: The quotient norm satisfies the norm axioms and gives the same distance as the quotient metric defined earlier.

D List of symbols and standard notations

This section defines notation for finite fields, matrices, linear maps, formal sums, graph lifts, lifted products, Tanner codes, and chain-complex structures.

  • Algebra and linear maps: Finite-field and linear-algebra notation includes Fq, matrix spaces Rm×n, the identity matrix In, kernels, images, and transposes or dual maps.These symbols establish the algebraic setting used throughout the paper.
  • Weights and formal sums: Formal-sum notation defines local-system coefficients, Hamming and block Hamming weights, norms, supports, and restrictions to subsets.The notation applies to elements of spaces of formal sums over finite sets.
  • Graphs and lifts: Graph notation includes group algebras, regular group lifts, adjacency matrices, graph squares, oriented edge sets, poset covers, and double covers of Ramanujan graphs.These definitions support the paper’s constructions from graphs and non-abelian groups.
  • Codes and chain complexes: Construction notation defines G-lifted products of complexes and posets, incidence numbers, Tanner codes, lifted Tanner codes, permutation equivalence, and cycle, boundary, homology, and locally minimal-distance spaces.Boundary-map restrictions are also specified for chain complexes over a field.
Loading 2111.03654v2…