PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum LDPC and High-Rate CSS Codes from Fair-Density Parity-Check Codes

Hessam Mahdavifar

arXiv:2609.01181v1cs.IT

TL;DR

The paper addresses how to construct finite-length qLDPC codes with sparse stabilizers, useful distances, and analytically accessible logical structure. It sparsifies structured FDPC parity-check matrices and combines them with hypergraph products. The resulting codes cover finite-length rate–distance–weight tradeoffs and high-rate CSS scaling, while FDPC weight distributions support erasure-channel ML analysis.

  • Problem

    qLDPC design must satisfy sparse stabilizers and exact commutation while seeking nonvanishing rate and growing distance.

  • Method

    The paper sparsifies FDPC parity-check matrices and uses them as components in hypergraph-product constructions.

  • Results

    The constructions provide finite-length qLDPC codes with controlled parameters and high-rate qFDPC codes satisfying R_Q = 1 − O(1/loglog N), D = Ω(N^1/4), and stabilizer weight O(log N loglog N).

  • Takeaways & Limitations

    Analytical FDPC weight distributions characterize low-weight logical multiplicities and support ML logical-error estimates over the quantum erasure channel.

  • Takeaways & Limitations

    The ML weight-distribution connection relies on known erasure locations and does not generally determine degenerate ML coset probabilities for standard Pauli channels.

Abstract

from arXiv · show

We construct quantum LDPC (qLDPC) and high-rate CSS codes from our recently introduced classical fair-density parity-check (FDPC) codes. To this end, we introduce a structured sparsification of FDPC parity-check matrices, which reduces their check weights while preserving the underlying combinatorial structure and distance guarantees. Combined with the hypergraph-product construction, this yields finite-length qLDPC codes with analytically controlled blocklength, dimension, certified distance, and stabilizer weight. For quantum blocklengths $N<10^5$, the constructions introduced here span guaranteed rates from approximately $0.35\%$ to $25.8\%$ and certified quantum distances from $12$ to $69$, with stabilizer weights between $8$ and $16$. In the large-blocklength regime, allowing the FDPC order and sparsified check weight to scale moderately with blocklength yields a family of high-rate CSS codes, which we refer to as quantum FDPC (qFDPC) codes, with rate $R_Q$ and minimum distance $D$ satisfying \[ R_Q = 1-O\left(\frac{1}{\log\log N}\right), \ \ D=Ω(N^{1/4}), \] and stabilizer weight $O(\log N\log\log N)$. Finally, the analytically available FDPC weight distribution provides explicit information about the logical operators of the resulting hypergraph-product codes. Over the quantum erasure channel, this structure yields rigorous first-order maximum likelihood (ML) expressions and a higher-order weight-distribution approximation to the ML logical block error probability. This enables estimation of finite-length operating points and the onset of the error-floor regime. To the best of our knowledge, beyond surface-code-type constructions, this is the first finite-rate qLDPC framework to provide both finite-length certified minimum-distance information and an analytical characterization of low-weight logical multiplicities.

I. INTRODUCTION

qLDPC construction must reconcile sparse stabilizer measurements with exact X–Z commutation, while retaining useful rate and distance. This work instead starts from structured classical FDPC codes, sparsifies their checks, and combines them with hypergraph products to obtain analytically controlled quantum constructions.

  • I. INTRODUCTION: qLDPC codes require sparse X- and Z-type stabilizers that satisfy the exact commutation condition HXHZ^T = 0.This constraint creates the central difficulty in designing quantum LDPC codes.
  • I. INTRODUCTION: The hypergraph-product construction established qLDPC codes with positive rate and minimum distance proportional to the square root of quantum blocklength.Later constructions achieved stronger distance scaling, including linear-distance asymptotically good qLDPC families.
  • I. INTRODUCTION: The paper begins with FDPC codes whose column weight, row weight, graph structure, and weight distribution are analytically controlled.It then derives ensemble-average weight distributions and probabilistic minimum-distance guarantees before quantum construction.
  • I. INTRODUCTION: Structured sparsification replaces moderately dense FDPC checks with lower-weight checks while preserving controlled column weight and the parent code’s minimum-distance guarantee.The sparsified components retain an analytically accessible weight distribution for the finite-length ensembles studied.
  • I. INTRODUCTION: Hypergraph products of sparsified FDPC codes yield finite-length qLDPC codes with analytically controlled blocklength, dimension, certified distance, and stabilizer weight.A separate scaling regime produces high-rate CSS codes with R_Q → 1, D = Ω(N^1/4), and polylogarithmic stabilizer weight.
  • I. INTRODUCTION: The FDPC weight distribution also supports rigorous first-order ML expressions and higher-order approximations for logical block error probability on the quantum erasure channel.These analyses estimate finite-length operating points and the onset of the error-floor regime.

C. Fair-Density Parity-Check Codes

FDPC codes provide structured classical components with explicit weight behavior and controlled sparsity properties. Higher-order analysis and check splitting supply the distance guarantees and lower-weight matrices needed for the paper’s quantum constructions.

  • C. Fair-Density Parity-Check Codes: The base FDPC matrix has length n = q^2, column weight 2, row weight q, rank 2q − 1, and minimum distance 4.Its columns correspond to weight-2 vectors whose nonzero indices differ by an odd number.
  • C. Fair-Density Parity-Check Codes: An order-s FDPC code stacks s independently permuted base-matrix copies, giving row weight q and column weight 2s.Layer and cross-layer dependencies produce at least 2s − 1 independent row dependencies.
  • C. Fair-Density Parity-Check Codes: FDPC codes offer explicit high-rate structure, controlled row and column weights, analytically tractable minimum-distance behavior, and an explicit weight distribution.These properties motivate their use as structured components for quantum constructions.
  • C. Fair-Density Parity-Check Codes: The paper derives exact arbitrary-order ensemble-average weight distributions using the FDPC graph representation and the MacWilliams identity.This extends earlier analysis focused particularly on order 2.
  • C. Fair-Density Parity-Check Codes: The base FDPC code is the cycle space of the complete bipartite graph K_q,q, enabling explicit weight-enumerator analysis through its cut-space dual.The graph interpretation identifies codewords with edge sets having even degree at every vertex.
  • C. Fair-Density Parity-Check Codes: For constant order s ≥ 3, the ensemble has rate R = 1 − O(1/q) and admits codes with minimum distance d_min = Ω(√n).When s = Θ(log q), the minimum distance remains Ω(q) = Ω(√n) while the rate retains the stated high-rate scaling.
  • C. Fair-Density Parity-Check Codes: The order-2 case requires separate analysis because the available first-moment bound does not yield a growing minimum-distance guarantee.Order-2 ensemble-average weight results remain valid, but the cited higher-order argument is stated only for s ≥ 3.

B. Sparsification of FDPC Codes

Sparsification splits each high-weight FDPC check into lower-weight checks while preserving column participation and the parent code’s distance guarantee. This interpolates between high-rate FDPC codes and bounded-degree LDPC families, with explicit random-sparsification weight-distribution analysis.

  • q = √n: order-s FDPC matrices have fixed column weight 2s but growing row weight, enabling rates that approach one.Keeping both row and column weights bounded instead yields rates bounded away from one.
  • Each weight-q check is partitioned into q/L disjoint checks of weight L, preserving column weight 2s and inheriting the parent code’s minimum-distance guarantee.The resulting code is a subcode of the parent FDPC code.
  • L > 2s fixed: sparsification produces (2s, L)-regular LDPC codes, while growing L retains a rate approaching one with reduced row density.Thus, check splitting explicitly interpolates between high-rate FDPC and conventional regular LDPC constructions.
  • dmin(eCs) < d | Hs: random sparsification can further suppress low-weight configurations, although evaluating the bound requires parent-code overlap profiles.The analysis uses independent uniform partitions of each parent check’s support and first-moment bounds on post-sparsification codewords.
  • General random-sparsification bounds require detailed overlap profiles, motivating an order-2 specialization with explicitly available post-sparsification weight distributions.This specialization is used for the later finite-length constructions.

C. A Special Case: Order-2 Sparsified FDPC Codes

The structured order-2 construction partitions each FDPC layer into disjoint smaller complete-bipartite blocks, yielding exact weight enumerators and explicit rate–check-weight tradeoffs. Examples show substantial row-weight reductions alongside guaranteed-rate reductions.

  • q = ℓL: each sparsified layer decomposes into ℓ^2 disjoint blocks, each corresponding to a copy of K_L,L.The one-layer code is therefore a direct combination of independent base FDPC codes on disjoint coordinate sets.
  • W_L(z): evaluating the base-code weight enumerator gives the exact weight enumerator of one structured sparsified layer.Each of the ℓ^2 copies has dimension (L − 1)^2.
  • A uniformly random relative permutation between the two sparsified layers defines the order-2 ensemble used for the explicit weight-distribution analysis.The resulting parity-check matrix has row weight L and column weight 4.
  • q = 15, L = 5: row weight falls from 15 to 5, column weight remains 4, and the guaranteed rate changes from at least 168/225 to at least 63/225.The sparsified ensemble is a (4, 5)-regular LDPC code.
  • q = 32, L = 8: row weight falls from 32 to 8, while the guaranteed rate changes from at least 899/1024 to at least 544/1024.The resulting parity-check matrix is (4, 8)-regular.

IV. QUANTUM CSS CODES FROM FDPC AND SPARSIFIED FDPC CODES

FDPC and sparsified FDPC matrices serve as classical components in asymmetric hypergraph-product constructions, combining controlled sparsity with inherited distance guarantees. The resulting CSS parameters are explicit and allow rate–distance tradeoffs through the second component.

  • L-sparsification reduces FDPC row weight in a controlled manner while preserving the classical code’s distance guarantee after redundant rows are removed.The sparsified kernel is a subcode of the parent kernel, so dA is at least the parent-code distance.
  • An arbitrary second full-row-rank classical code provides flexibility for controlling quantum dimension and distance, including the symmetric FDPC choice.The FDPC component supplies structured sparsity and the inherited distance guarantee.
  • N = nnB + rArB, K = kAkB, and D = min{dA, dB} for the HGP CSS code built from HA and HB.These formulas give analytically controlled blocklength, dimension, and minimum distance.
  • Stabilizer weights are bounded using the component check weights, with the resulting CSS code’s X- and Z-stabilizer weights controlled by the HGP construction.The construction specifically combines sparsified FDPC checks with a second classical parity-check matrix.

B. Quantum FDPC Codes

Symmetric hypergraph products of sparsified FDPC codes define qFDPC codes whose parameter scaling can produce high rate, polynomial distance, and polylogarithmic stabilizer weight. An asymmetric FDPC–repetition variant adds finite-length flexibility and an explicit logical-operator connection.

  • A qFDPC code is the symmetric HGP CSS code using an L-sparsified order-s FDPC code for both classical components.The unsparsified FDPC construction is recovered when L = q.
  • s and L control distinct properties: s governs parent-FDPC distance behavior, while L controls sparsification rate loss and, with s, stabilizer weight.Joint scaling of these parameters yields high-rate CSS codes with polynomially growing distance.
  • L = q retains the same probabilistic distance scaling but makes stabilizer weight polynomial in quantum blocklength; sparsification reduces it to polylogarithmic growth.This reduction trades part of the original FDPC construction’s excess rate for lower stabilizer weight.
  • Improved asymptotic distance scaling for the sparsified ensemble remains open because the current bound uses only the parent FDPC minimum-distance guarantee.The additional parity constraints’ potential suppression of low-weight codewords is not exploited in the theorem.
  • The asymmetric FDPC–repetition construction adds a finite-length blocklength–distance tradeoff and exactly characterizes one Pauli sector’s logical classes through FDPC codewords.This connects the FDPC weight distribution to ML performance over the quantum erasure channel.

V. WEIGHT DISTRIBUTION AND ML PERFORMANCE ON THE QUANTUM ERASURE CHANNEL

The section develops maximum-likelihood erasure analysis by connecting FDPC weight enumerators to classical and hypergraph-product quantum decoding. Known erasure locations make the resulting finite-length bounds computable from analytically available ensemble-average weight distributions.

  • The analysis transfers FDPC weight-distribution results to hypergraph-product logical operators and derives a first-order ML error approximation.
  • Each qubit is independently erased with probability p, and the decoder is given the erased locations.
  • For CSS codes, decoding a fixed erased set reduces to analyzing the corresponding erased-column submatrices of H_X and H_Z.
  • The classical weight enumerator gives the expected number of codewords consistent with unerased observations and yields an explicit finite-length erasure bound.
  • Analytically available ensemble-average FDPC weight distributions make the averaged finite-length bound computable.

B. Logical weight distribution of quantum FDPC codes

This section characterizes logical classes in qFDPC–Rep hypergraph-product codes through the FDPC component code. The classical weight distribution exactly determines minimum physical weights and therefore the distribution of Z-logical classes.

  • HGP logical operators admit line representatives whose structure is determined by codewords of the classical component codes.
  • The qFDPC–Rep family characterizes the minimum weight within each logical equivalence class, rather than only selected logical representatives.
  • Proposition 10 establishes an isomorphism between Z-logical classes and the FDPC component code C_A.
  • Under this correspondence, the logical class associated with a in C_A has minimum physical weight exactly wt(a).
  • The FDPC weight distribution therefore gives the minimum physical weight of every logical equivalence class, and its ensemble average transfers to the qFDPC–Rep ensemble.

C. First-order approximation of the ML probability of error

The section derives first-order ML erasure probabilities for HGP codes from minimum-weight logical operators and classical component weight distributions. The resulting expressions identify both the leading erasure exponent and its multiplicity-dependent coefficient.

  • ML decoding can fail logically only when the erased qubits support a nontrivial logical operator.
  • At erasure weight D_Z, each minimum-weight logical support creates one binary ambiguity and conditional ML error probability 1/2; smaller erasure sets cannot cause such a Z-sector failure.
  • For full-coordinate-support components, the HGP sector distances satisfy D_Z = d_A and D_X = d_B.
  • For symmetric qFDPC codes with d >= 4, distinct X- and Z-logical supports make the two sector contributions add at first order.
  • The first-order qFDPC ML error is determined by the classical minimum-distance term, while minimum-weight multiplicity determines its coefficient.
  • The weight-distribution connection relies on known erasure locations and does not generally determine degenerate ML coset probabilities on standard Pauli channels.

VI. FINITE-LENGTH QLDPC CONSTRUCTIONS FROM FDPC COMPONENTS

This section constructs finite-length qLDPC families from sparsified FDPC components and studies their parameter tradeoffs under bounded stabilizer weight. It also uses the complete FDPC weight distribution for higher-order ML estimates, while explicitly noting approximation limits.

  • A. Constructions with stabilizer weight up to 10: The finite-length constructions trade quantum blocklength, dimension, certified distance, and stabilizer weight rather than optimizing one parameter alone.
  • A. Constructions with stabilizer weight up to 10: Two construction classes have maximum stabilizer weight at most 10: symmetric sim-FD qLDPC codes and FD–Rep qLDPC codes.
  • A. Constructions with stabilizer weight up to 10: For order-2 sparsified FDPC components, row weight is L and column weight is 4, determining the sim-FD stabilizer-weight expression.
  • A. Constructions with stabilizer weight up to 10: The stabilizer constraint w_stab <= 10 permits L <= 6 for sim-FD and L <= 8 for FD–Rep constructions, with N < 10^5.
  • A. Constructions with stabilizer weight up to 10: The WD approximation retains all line-logical contributions at weights appearing in the complete FDPC distribution, rather than only the minimum-weight term.
  • A. Constructions with stabilizer weight up to 10: The approximation sets terms below the certified component distance to zero but retains unconditional ensemble-average coefficients above it.
  • A. Constructions with stabilizer weight up to 10: Conditioning on the certified-distance event can increase any retained ensemble-average coefficient by at most a factor of two.
  • A. Constructions with stabilizer weight up to 10: The WD approximation matches rigorous first-order ML terms but omits logical operators outside the line family and overlaps among distinct logical-erasure events.

A , r}, FD–Rep qLDPC. (69)

The section defines weight-distribution-based operating points and error-floor onset estimates for finite-length qLDPC constructions. It compares rates, certified distances, ML predictions, and the contributions of higher-weight logical operators.

  • Operating-point definitions: pWD_ML(ε) is the physical erasure probability where the weight-distribution approximation predicts logical block error probability ε.The reported pWD_ML(10^-12) values probe an ultralow-error regime and, together with another operating point, indicate predicted low-error steepness.
  • Error-floor onset: pEF marks the transition to a regime where the leading minimum-distance contribution becomes dominant over higher-weight contributions.At p = pEF, the leading retained contribution at Dcert accounts for one half of the weight-distribution approximation.
  • Finite-length regimes: 11% rate is achieved by the (q, L) = (12, 6) sim-FD construction with stabilizer weight 10, while FD–Rep examples reach Dcert = 69 with stabilizer weight 8–10.These examples illustrate distinct finite-length rate-oriented and distance-oriented regimes under N < 10^5 and wstab ≤ 10.
  • Error-floor onset: 7.4×10^-4, 1.3×10^-6, 5.5×10^-10, and below 10^-16 are the estimated error-floor-onset probabilities for Dcert values 16, 22, 29, and 42, respectively.The onset moves rapidly toward lower logical block error probabilities as certified distance increases.
  • ML operating points: 0.256 to 0.098 is the predicted change in pWD_ML for the (q, L) = (12, 6) sim-FD code when the target logical block error probability decreases from 10^-6 to 10^-12.For larger-distance FD–Rep codes, the two operating points are closer, while higher-weight line-logical terms can contribute substantially.
  • Logical-weight effects: Higher-weight FDPC line logicals can become significant at larger erasure probabilities when repetition determines the certified distance.The complete FDPC weight distribution therefore supplies finite-length information beyond certified distance and leading multiplicity.

B. Constructions with moderately relaxed stabilizer weight

Moderately relaxing stabilizer weight and selecting HGP components independently expands the finite-length rate–distance design space. The resulting constructions provide higher rates, certified distances, and weight-distribution-based operating-point information within bounded stabilizer weights.

  • Rate–weight tradeoffs: 23% guaranteed rate is obtained by sim-FD qLDPC codes when stabilizer weight is increased to 12.The construction is part of the moderately relaxed regime with 11 ≤ wstab ≤ 16.
  • FD–FD constructions: 25.8% guaranteed rate is achieved by the (16, 8)×(18, 9) FD–FD construction with stabilizer weight 13 and Dcert = 12.Choosing the two FDPC components independently provides additional rate–distance flexibility.
  • FD–FD constructions: 25.8% to 4.0% guaranteed rates span the FD–FD examples as Dcert increases from 12 to 24 within N < 10^5.Their estimated error-floor onset shifts from roughly 10^-4 toward the 10^-9–10^-10 range for distance-18 examples.
  • FD–Rep tradeoffs: 1.1% to 2.3% guaranteed rate accompanies increasing L from 9 to 14 in FD–Rep qLDPC codes, while stabilizer weight rises from 11 to 16.Across the same sequence, Dcert decreases from 38 to 25.
  • Design controls: Rates above 20% are possible without changing the underlying FDPC construction or abandoning bounded-weight stabilizers.The tables identify sparsification parameter L and HGP component choice as finite-length design controls.
  • Framework scope: The framework combines finite-length weight distributions, probabilistic distance guarantees, and sparsification mechanisms to produce sim-FD, FD–FD, and FD–Rep qLDPC families.These families exhibit tradeoffs among rate, certified distance, blocklength, and stabilizer weight.
  • Open directions: Deterministic sparsification and permutation choices, sharper good-distance characterization, and practical Pauli-noise decoder evaluation remain open directions.BP-OSD, BPGD, and MBBP-LD are identified as possible decoder starting points.
Loading 2609.01181v1…