PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum LDPC Codes with Almost Linear Minimum Distance

Pavel Panteleev, Gleb Kalachev

arXiv:2012.04068v2cs.ITquant-ph

TL;DR

The paper addresses the challenge of constructing quantum LDPC codes with substantially larger minimum distance. It introduces lifted products and combines quasi-cyclic constructions, expander methods, and chain-complex products to obtain quantum codes with almost linear distance, larger-dimension trade-offs, and a related classical-code result.

  • Problem

    Known quantum LDPC constructions had limited minimum-distance scaling, motivating constructions with larger distance while retaining low-density structure.

  • Method

    The paper introduces lifted product codes, using quasi-cyclic matrices, expander-based arguments, and products with classical LDPC codes and chain complexes.

  • Results

    The construction gives quantum LDPC codes with dimension Θ(log N) and distance Θ(N/log N), and families with dimension Ω(N^α log N) and distance Ω(N^(1−α/2)/log N) for 0≤α<1.

  • Takeaways & Limitations

    Lifted products provide a broad class of CSS codes, including several known quantum LDPC constructions, while the same results yield classical quasi-cyclic LDPC codes with linear distance and circulant size Ω(N/log N).

Abstract

from arXiv · show

We give a construction of quantum LDPC codes of dimension $Θ(\log N)$ and distance $Θ(N/\log N)$ as the code length $N\to\infty$. Using a product of chain complexes this construction also provides a family of quantum LDPC codes of distance $Ω(N^{1-α/2}/\log N)$ and dimension $Ω(N^α\log N)$, where $0 \le α< 1$. We also introduce and study a new operation called lifted product, which naturally generalizes the product operations for quantum codes and chain complexes. Moreover, as a simple byproduct of our results on quantum codes, we obtain a new result on classical codes. We show that for any fixed $R < 1$ there exists an asymptotically good family of classical quasi-cyclic LDPC codes of rate at least $R$ with, in some sense, optimal circulant size $Ω(N/\log N)$ as the code length $N\to\infty$.

I. INTRODUCTION

The paper constructs quantum LDPC codes with almost linear minimum distance and develops lifted products to increase dimension or generalize code constructions. It also derives asymptotically good classical quasi-cyclic LDPC codes with near-optimal circulant size.

  • Lifted product codes generalize hypergraph product codes and encompass several established QLDPC families.The paper also extends the lifted product operation from codes to chain complexes.
  • The construction uses carefully chosen low-density quasi-cyclic matrices, b=1+x, expander codes, and a distance-balancing product with classical LDPC codes.The proof’s main technical tool is the expander-code framework; the product increases dimension while reducing distance.
  • Quantum LDPC codes with dimension Θ(log N) and distance Θ(N/log N) exist as N→∞.This is stated as the paper’s first main result.
  • Classical quasi-cyclic LDPC codes can have distance Θ(N) and circulant size Ω(N/log N), with this size described as optimal in some sense.The construction applies for any fixed design rate below one.
  • For every 0≤α<1, quantum LDPC codes exist with dimension Ω(N^α log N) and distance Ω(N^(1−α/2)/log N).The α=0 case recovers the first family’s parameters.

Lifted Product Codes

Lifted product codes generalize hypergraph product codes by lifting matrix coefficients to suitable algebras, while also extending to chain complexes. The construction supports comparisons among LP, fiber-bundle, and hypergraph product families.

  • Lifted Product Codes: Lifted product codes generalize hypergraph product codes and include many well-known quantum LDPC code families.They were introduced as a more general form of generalized hypergraph product codes.
  • Lifted Product Codes: The construction starts from Tanner graphs with shift lifts and forms CSS parity-check matrices over a commutative algebra.For cyclic lifts, the coefficient ring is R_ℓ = F2[x]/(x^ℓ−1).
  • Lifted Product Codes: Fig. 2 compares LP, fiber-bundle, and hypergraph product codes by minimum distance and dimension as N grows, up to polylogarithmic factors.The comparison is presented on logarithmic scales.
  • Lifted products of chain complexes: The lifted-product operation extends to chain complexes through a tensor product over a commutative algebra, then views the result over F2.Its boundary map is ∂A ⊗ idB + idA ⊗ ∂B.

A. Classical codes

This section defines classical linear codes and introduces the related CSS quantum-code framework. It specifies parity-check representations, duality, equivalence, dimension, and minimum-distance notions.

  • Classical codes: A linear [n,k]q code is a k-dimensional subspace of Fnq, with rate k/n and length n.Its codewords are vectors in the subspace.
  • Classical codes: The minimum distance d(C) is the minimum Hamming weight of a nonzero codeword, and [n,k,d]q records the code parameters.For a zero-dimensional code, the convention is d(C) = ∞.
  • Classical codes: A classical code can be represented as the row space of a generator matrix or the kernel of a parity-check matrix.The generator and parity-check matrices satisfy GHT = 0.
  • Quantum CSS codes: A CSS quantum code is defined by two classical codes whose parity-check matrices have mutually orthogonal rows.The quantum dimension is determined by the associated pair of classical codes.
  • Quantum CSS codes: CSS codes have Z- and X-type minimum distances, with quantum minimum distance equal to the smaller one.Degenerate codewords correspond to stabilizers, while quotient-space codewords represent logical operators.

C. Classical and quantum LDPC codes

LDPC codes are defined by sparse parity-check matrices and represented through Tanner graphs. The section extends these ideas to quantum CSS codes and to algebraic lifts represented by block matrices.

  • C. Classical and quantum LDPC codes: An LDPC code has a parity-check matrix whose row and column weights remain bounded by a constant as code length grows.Its Tanner graph represents variables by v-nodes and checks by c-nodes.
  • C. Classical and quantum LDPC codes: A quantum LDPC code is a CSS code with sparse parity-check matrices HX and HZ.Its Tanner graph contains qubit nodes and X- and Z-check nodes.
  • Lifted product: The lifted-product framework generalizes several known quantum codes and provides dimension estimates for important special cases.The paper uses a special case to construct quantum LDPC codes with almost linear distance.
  • Algebraic representations: Matrices over a finite-dimensional algebra can be converted into binary block matrices, allowing algebraic code descriptions to define binary linear codes.For group algebras, the block representation uses permutation matrices for group elements.
  • Algebraic representations: For abelian groups, group-algebra matrices use a commutative ring; cyclic groups yield quasi-cyclic matrices represented over F2[x]/(x^ℓ−1).The corresponding lift size is the circulant size ℓ.

A. Generalized bicycle (GB) codes

Generalized bicycle codes motivate lifted products by enforcing CSS orthogonality through commuting matrices. Lifted products extend hypergraph products from binary matrices to commuting matrix-ring elements while retaining CSS structure.

  • Generalized bicycle codes: CSS orthogonality is a major obstacle for random-like quantum LDPC constructions, motivating structured generalized bicycle codes.Binary circulant matrices commute automatically, ensuring the required orthogonality condition.
  • Lifted product codes: Lifted product codes generalize generalized bicycle and hypergraph product codes by replacing binary coefficients with elements of a finite-dimensional F2-algebra.The ring elements are represented by binary block matrices.
  • Lifted product codes: Element-wise commuting matrices define valid lifted product CSS codes through block parity-check matrices B(HX) and B(HZ).The mixed-product formula establishes the needed orthogonality relation.
  • Connections: Hypergraph product codes remain a special case of lifted products when R = F2, while generalized bicycle codes arise from 1 × 1 matrix-ring inputs.This places both constructions within one algebraic framework.
  • Parameters: Lifted product length is N = ℓ(nAmB + nBmA), while its general dimension lacks a simple formula.Special cases permit dimension lower bounds from row counting and rank conditions.

E. Quasi-cyclic and quasi-abelian LP codes

Quasi-cyclic and quasi-abelian lifted products use commutative rings to control block-matrix density. They can be built from classical QC LDPC codes and include concrete finite-length examples.

  • Ring-based constructions: Commutative rings make lifted product matrices element-wise commuting and allow density control through weight matrices.The quasi-cyclic case uses Rℓ, while the quasi-abelian case uses group algebras F2G.
  • Construction: Classical QC LDPC codes provide the building blocks for QC LP codes and offer many examples with strong parameters.The paper illustrates this with a [155, 64, 20] code of circulant size ℓ = 31.
  • Example: An 8-limited QC LP code constructed from the [155, 64, 20] example has parameters [[1054, 140, d]].Extensive BP-OSD simulations found no non-degenerate codeword of weight below 20.
  • Symmetries: Conjugation preserves the relevant QC or QA structure, while exchanging the roles of HX and HZ relates LP(A, B) to LP(A*, B*).The resulting codes are permutation equivalent under these transformations.
  • Relation to prior codes: QC LP codes are permutation equivalent to a special case of hyperbicycle codes.The correspondence is obtained by setting χ = 1 in the cited hyperbicycle construction.

F. Special case of QC LP codes

The special QC LP construction evaluates ring elements at roots of irreducible factors to connect lifted products with finite-field codes. For b = 1 + x, the dimension formula simplifies substantially.

  • Context: The construction generalizes earlier GHP terminology while covering both odd and general lift sizes.The paper notes an alternative proof for odd ℓ.
  • Setup: QC LP codes in this case use an irreducible factor b of x^ℓ − 1 and a matrix A over Rℓ.The polynomial b is treated as a 1 × 1 matrix over Rℓ.
  • Finite-field reduction: Evaluation ϕb(u) = u(β) maps Rℓ to the finite field Fq, where β is a root of b and q = 2^deg b.The map extends elementwise to vectors and matrices.
  • Dimension: The dimension of LP(A, b) is determined through the dimensions of finite-field codes obtained by evaluating A and AT at β.The lemma also identifies β within Fq ≅ R(b).
  • Special case: For b = 1 + x, dim LP(A, 1 + x) = dim C(A(1)) + dim C(AT(1)).Here β = 1 and the associated cyclic code is the [ℓ, 1, ℓ] repetition code.

IV. EXPANDERS

The expander section supplies the graph-theoretic tools used to construct quasi-cyclic matrices with large lift sizes and favorable expansion. It also supports asymptotically good classical QC LDPC families.

  • Purpose: Proposition 1 constructs quasi-cyclic matrices with very large lift sizes and good expansion properties.This construction is used for the paper’s main quantum-code result.
  • Classical codes: The expander construction yields asymptotically good classical quasi-cyclic LDPC families with close-to-optimal lift size.The result is stated as Corollary 1.
  • Expander graphs: An expander graph is characterized by sufficiently small second-largest adjacency eigenvalue.Expander codes combine such graphs with a small linear code.
  • Expansion bound: For an (n, w, λ)-expander and |S| ≤ αn, Lemma 2 bounds the internal edges of S.The proof uses the expander mixing lemma and counts each internal edge twice in E(S, S).

B. Expanding binary matrices

The section constructs quasi-cyclic matrices whose binary expansions, together with their transposes, satisfy expansion properties under explicit graph and component-code conditions. A Tanner-code and lift construction then yields sparse QC matrices with controlled dimensions and lift sizes.

  • Expansion properties: A binary matrix is (α, β)-expanding when every vector of weight at most αn maps to a vector of weight at least β times larger.For parity-check matrices, this expansion implies a minimum-distance lower bound; the same definition extends to QC matrices through their binary block expansions.
  • Existence result: For every ε ∈ (0, 1), suitable constants yield a w-limited QC matrix A with m ≤ εwn such that A and A^T are both (α, β)-expanding.The construction uses suitable regular expanders, random shift lifts, and a component code selected using the Gilbert–Varshamov bound.
  • Tanner-code construction: Tanner codes assign bits to graph edges and impose a local code constraint at each vertex, producing a w-limited parity-check matrix when 2r < w.The resulting matrix has 2rn rows and wn columns, with each row and column weight bounded by w.
  • QC lifting: Shift lifts convert Tanner codes into QC codes, with circulant blocks encoding edge shifts and preserving the relevant expansion structure.The lifted graph gives a QC parity-check matrix over R_ℓ, and its binary block matrix is the lifted Tanner parity-check matrix.
  • Expansion proof: Sufficient graph expansion and large minimum distances for C0 and C0⊥ make both the Tanner parity-check matrix and its transpose expanding.Lemma 3 assumes a (2n, w, λ)-expander with λ < δw, d(C0) ≥ δw, and d(C0⊥) ≥ δw.

C. Asymptotically good QC LDPC codes with large lift sizes

The section establishes asymptotically good classical QC LDPC codes with large lift sizes and shows that linear distance constrains the lift size to the same N/log N scale. This makes the constructed lift size optimal in the stated sense.

  • Construction: For any R < 1, there exists a family of classical QC LDPC codes with rate at least R, distance Ω(N), and lift size Ω(N/log N).The construction applies the expanding-matrix proposition with n = ⌈γ ln ℓ⌉ and ε = 1 − R.
  • Optimality: Thus the achieved lift size Ω(N/log N) is optimal in this sense for QC LDPC codes and more broadly for quasi-abelian LDPC codes with linear minimum distance.The corresponding upper bound is stated as lift size at most O(N/log N).
  • Lift-size limitation: When m < n, a weight-matrix bound prevents the minimum distance of a QC code from growing with the lift size if the block-weight pattern is fixed.The bound depends only on the weight matrix W, not on ℓ.
  • Square case: The fixed-weight upper bound no longer applies when m = n, where the minimum distance can grow linearly with the lift size.The section gives an explicit square-matrix example illustrating this distinction.
  • Optimality: For w-limited matrices with w ≥ 2 and linear distance, the construction implies ℓ = O(N/log N) when m < n.The argument combines the distance assumption d ≥ αN with n = Ω(log N).

V. LP CODES WITH ALMOST LINEAR DISTANCE

The section proves almost-linear distance for lifted-product quantum codes by combining expansion of a QC matrix and its transpose with a case analysis of codewords. Applied to a suitable matrix A, this yields distance Θ(N/log N) and dimension Θ(log N).

  • Proof strategy: The proof combines a lower bound for special QC LP codes with the expanding-matrix results to establish QLDPC codes with almost linear distance.The lifted product LP(A, 1 + x) is the quantum-code construction analyzed in the section.
  • Distance bound: For A and A^T both (α, β)-expanding, LP(A, 1 + x) has d(Q) ≥ γℓ, with stronger bounds for dZ or dX when the corresponding base-code dimension vanishes.The proposition gives dZ(Q) ≥ γℓn if dim C(A^T(1)) = 0 and dX(Q) ≥ γℓm if dim C(A(1)) = 0.
  • Main construction: The construction from Proposition 1 gives N = ℓ(wn + m), n = Θ(log N), and K = Θ(log N), while Proposition 2 supplies d(Q) ≥ γℓ.Since ℓ is Θ(N/log N), the lower bound becomes almost linear in N.
  • Main construction: An explicit non-degenerate codeword has weight ℓ, yielding d(Q) ≤ ℓ and therefore d(Q) = Θ(ℓ) = Θ(N/log N).The upper bound uses a standard basis vector outside the column space of the base matrix transpose.

VI. CONCLUSION

The paper concludes that lifted product codes yield quantum LDPC families with almost linear distance and scalable dimension, while also encompassing a broad class of CSS codes and extending to chain complexes.

  • Θ(log N) dimension and Θ(N/log N) distance are achieved by a family of lifted product QLDPC codes.
  • Ω(N^α log N) dimension and Ω(N^(1−α/2)/log N) distance are obtained for 0 ≤ α < 1.
  • Ω(N/log N) circulant size accompanies classical QC LDPC codes with any design rate and distance Θ(N).
  • The lifted product class includes CSS codes such as hypergraph product, bicycle, and Haah’s cubic codes.
  • For some linear-dimension lifted product codes, only an O(N/log N) upper bound on distance is currently known, leaving matching-distance questions open.
  • The lifted product operation extends from codes to chain complexes and naturally generalizes their tensor product.

APPENDIX A RING OF CIRCULANTS

The appendix identifies circulant matrices with a quotient polynomial ring and decomposes that ring into component rings, enabling lifted product codes to be analyzed componentwise.

  • ℓ×ℓ circulant matrices over F2 correspond to the quotient ring R_ℓ = F2[x]/(x^ℓ−1).
  • When ℓ is odd, x^ℓ−1 factors into irreducible polynomials over F2, and R_ℓ decomposes into a direct product of finite fields.
  • For general ℓ = 2^eℓ′ with ℓ′ odd, the factorization and Chinese remainder theorem produce a direct-product decomposition of R_ℓ.
  • Matrices over the ring decompose through component homomorphisms, so LP(A,B) corresponds one-to-one with component codes.
  • The component correspondence preserves codeword degeneracy and supports dimension calculations from the component hypergraph product codes.
  • For odd lift size, semisimplicity gives finite-field components, and the quasi-abelian lifted product dimension is computed by summing weighted component dimensions.

APPENDIX C LIST OF SYMBOLS AND ABBREVIATIONS

The appendix defines notation for vectors, finite fields, cyclic structures, rings, matrices, and the principal classical and quantum code constructions used throughout the paper.

  • ℓ denotes lift size or circulant size, while R_ℓ denotes the quotient ring F2[x]/(x^ℓ−1).
  • F_q denotes a finite field with q elements, S_n the permutations of [n], and C_n the cyclic group of order n.
  • C^⊥ denotes the dual code, C(H) the code with parity-check matrix H, and ker A and im A the kernel and image of a linear map.
  • HP(A,B) denotes a hypergraph product code, LP(A,B) a lifted product code, and QLDPC a quantum low-density parity-check code.
  • Q* denotes a quantum code with swapped C_Z and C_X, while Q ∼ Q′ denotes permutation-equivalent codes.
Loading 2012.04068v2…