Source-linked AI summary
Quantum LDPC codes with positive rate and minimum distance proportional to n^{1/2}
Jean-Pierre Tillich, Gilles Zemor
TL;DR
Quantum LDPC codes with fixed non-zero rate previously had only logarithmic known minimum-distance growth, while stronger-distance constructions faced structural constraints. The paper constructs quantum CSS LDPC codes from classical LDPC parity-check matrices and proves square-root blocklength distance at fixed rate, with further rate improvement possible.
Problem
The paper targets the limited minimum-distance growth available for quantum LDPC codes with non-vanishing rate, alongside construction and orthogonality difficulties.
Method
The paper constructs quantum CSS LDPC codes from flexible pairs of binary LDPC parity-check matrices, including identical classical codes.
Results
A family of classical asymptotically good LDPC codes with fixed rate yields quantum LDPC codes with fixed rate and minimum distance proportional to the square root of blocklength.
Takeaways & Limitations
The construction provides quantum LDPC codes combining non-zero asymptotic rate with square-root minimum-distance growth, and the rate can be improved while preserving that distance.
Abstract
from arXiv · showhide
The current best asymptotic lower bound on the minimum distance of quantum LDPC codes with fixed non-zero rate is logarithmic in the blocklength. We propose a construction of quantum LDPC codes with fixed non-zero rate and prove that the minimum distance grows proportionally to the square root of the blocklength.
1 Introduction
The paper addresses the difficulty of constructing quantum LDPC codes with both non-vanishing rate and growing minimum distance. It introduces a flexible construction from classical LDPC parity-check matrices, achieving square-root minimum-distance scaling and allowing further rate improvement.
- 1 Introduction: Efficient quantum decoding matters because decoding time can create computation and error-suppression delays during active stabilization.The paper also motivates quantum LDPC codes through the role of degeneracy in correcting different error patterns with the same syndrome.
- 1 Introduction: Existing quantum LDPC constructions with non-vanishing rate and bounded row weight have minimum distance that is bounded or not known to grow.Surface-based constructions provide logarithmically growing distance, while toric codes have square-root distance but fixed dimension and zero asymptotic rate.
- 1 Introduction: The construction uses a pair of parity-check matrices from binary LDPC codes without requiring the underlying classical codes to be mutually orthogonal.The resulting quantum code is in the CSS class, but the two classical codes may be chosen flexibly, including C1 = C2.
- 1 Introduction: N = n^2 +(n−k)^2, dimension k^2, and quantum minimum distance d are obtained from a full-rank [n, k, d] classical LDPC code.The stabilizer row weights have the form i + j, using the corresponding row and column weights of the classical parity-check matrix.
- 1 Introduction: A family of classical asymptotically good LDPC codes with fixed rate yields quantum LDPC codes with fixed rate and minimum distance proportional to the square root of blocklength.The rate can be improved further while preserving the same minimum distance.
2 Basic facts about CSS codes and Tanner graphs
This section introduces CSS and LDPC-code terminology through binary-code pairs, sparse parity-check matrices, and Tanner graphs. It also specifies the quantum minimum distance and the stabilizer-matrix representation.
- 2 Basic facts about CSS codes and Tanner graphs: CSS quantum codes are described by binary codes CX and CZ satisfying CZ⊥ ⊂ CX.Their quantum minimum distance is defined using vectors in CZ that are outside CX⊥.
- 2 Basic facts about CSS codes and Tanner graphs: The quantum minimum distance is dQ = min{|x| : x ∈ CZ \ CX⊥}.The code protects a quantum subspace whose dimension is called the quantum dimension kQ.
- 2 Basic facts about CSS codes and Tanner graphs: A Tanner graph for H is bipartite, with variable nodes corresponding to columns, check nodes corresponding to rows, and edges marking entries hij = 1.This graph supports decoding of the associated classical LDPC code.
- 2 Basic facts about CSS codes and Tanner graphs: A quantum CSS code is LDPC when both CX and CZ have sparse parity-check matrices HX and HZ.The pair (HX, HZ) is also called the stabilizer or quantum parity-check matrix, and its rows are stabilizer generators.
- 2 Basic facts about CSS codes and Tanner graphs: Figure 1 depicts a two-dimensional torus formed by identifying opposing sides of an outer square.The torus is used later as the geometric basis for the toric code.
3 The toric code and its generalization
The section develops a graph-product generalization of the toric code that preserves the CSS orthogonality structure and relates quantum distance to classical code properties. For a single toric-code example, duality gives dimension 2 and minimum distance m.
- The toric code: The cycle code CX is defined by the vertex-edge incidence matrix, while cocycles are the rows and their span’s elements.The second matrix HZ uses 4-cycle face-edge incidence, making its row space a subspace of CX.
- The toric code: 2, and the toric quantum code has minimum distance m.Duality equates the relevant minimum weights for CX and CZ, so the distance calculation applies to both error types.
- The toric code: The toric code is built from a product of two length-m cycles, with qubits identified with the graph’s edges.Its graph has m^2 vertices, each joined to four neighbors, and 2m^2 edges.
- Graph-product generalization: 4-cycles in the product graph ensure that X- and Z-type checks sharing one variable node share a second, giving orthogonality.The construction is presented as a graph-product formulation while retaining a connection to the hypergraph viewpoint.
- Graph-product generalization: The proposed generalization uses Tanner-graph products, assigning CX checks to C1 × V2 and CZ checks to V1 × C2.Their union forms the edge set of the bipartite product graph, and the resulting pair (CX, CZ) defines a CSS code.
4 Dimension of the CSS code Q(G1 × G2) and relationship with product codes
The construction relates the CSS code Q(G1 × G2) to product and transpose-product codes, yielding explicit dimension formulas and flexible degree distributions. Its Tanner-graph design preserves CSS validity while allowing sparse constructions with adjustable degree structure.
- CSS validity: Two shared neighbors, or none, make each X-check row orthogonal to each Z-check row, so the construction satisfies the CSS condition.The common-neighbor count is even in both cases: zero when an adjacency is absent and two when both adjacencies hold.
- Degree structure: The product Tanner graphs have flexible degree distributions, which can potentially support quantum LDPC codes with improved iterative-decoding performance.The degree distributions are determined from the component graphs’ degree statistics rather than being fixed to one specific structure.
- Product-code construction: The product construction defines G1 ×X G2 and G1 ×Z G2 using complementary check-node sets, producing the classical codes CX and CZ.Their combined edge sets form the product graph, and the associated codes are used to define the quantum code.
- Relationship with product codes: The hypergraph product is the Tanner graph of the product code, linking the constructed quantum code to standard product-code dimension formulas.This relationship is established through the product-code definition and the corresponding Tanner-graph proposition.
- Dimension: The quantum dimension is derived from the dimensions of C1, C2 and their transpose codes, and Q(G × G) always has positive dimension for any non-trivial code.The transpose operation exchanges variable and check nodes, while its code dimension enters the quantum-dimension calculation.
5 Minimum distance
The paper derives the quantum minimum distance from the minimum distances of two component codes and their transpose codes. This establishes the distance behavior needed for positive-rate quantum LDPC constructions, including square-root scaling when suitable classical families are chosen.
- Distance formula: dQ is governed by d1, d2, dT_1, and dT_2, with the exact expression determined by which component and transpose codes are nontrivial.The theorem treats cases using the convention that a code containing only the zero word has minimum distance ∞.
- Asymptotic consequence: Choosing component codes with linear minimum distance yields quantum minimum distance proportional to the square root of blocklength, while suitable rates give linear quantum dimension and sparse checks.The construction therefore produces quantum LDPC families combining growing distance, nonzero asymptotic rate, and LDPC parity checks.
- Lower-bound strategy: Classical-code distance bounds alone fail for these LDPC CSS codes because their sparse parity-check matrices already contain constant-weight rows.Since orthogonal classical codes are contained in the corresponding codes, such bounds cannot exceed the parity-check row weight.
- Lower bound: The lower-bound proof shows that sufficiently low-weight codewords in CX or CZ must belong to the orthogonal code and therefore cannot represent nontrivial quantum codewords.The argument uses the full CSS distance definition rather than separate lower bounds on the classical code distances.
- Tightness: Suitable codewords attaining the lower bound are constructed from minimum-weight words of the component codes, proving the stated quantum-distance expression.For example, a word x = x1 × {y} has weight d1 and is shown to lie in CX but outside CZ⊥ under the stated assumptions.
6 Comparison with other constructions of quantum codes based on binary linear codes
The construction turns two classical binary LDPC codes into a quantum LDPC code without requiring the CSS containment constraint, while retaining favorable dimension and distance properties compared with generalized Shor codes.
- Construction versus CSS and Shor codes: The construction produces a quantum code from classical binary codes C1 and C2 without requiring C2⊥ ⊂ C1.It yields a quantum LDPC code when both input codes are classical LDPC codes.
- Construction versus CSS and Shor codes: The resulting code has parameters [[n1n2 + r1r2, k1k2, min(d1, d2)]].
- Comparison with generalized Shor codes: The construction shares the generalized Shor code’s dimension and minimum distance while using an additional r1r2 term in the length.
- Comparison with generalized Shor codes: Sparse input parity-check matrices yield sparse HX and HZ, unlike the generalized Shor construction when C1 has large minimum distance.The Shor construction cannot produce quantum LDPC families with nonconstant minimum distance under that condition.