Source-linked AI summary
Breaking the Orthogonality Barrier in Quantum LDPC Codes
Kenta Kasai
TL;DR
Quantum LDPC constructions face a tension between regular, large-girth Tanner graphs and the orthogonality required by CSS codes, which can create structural distance limits. The paper controls commutativity with permutation-matrix structure and imposes orthogonality only on active components. It constructs a girth-8, (3,12)-regular code achieving FER as low as 10^-8 at 4% depolarizing-channel error with BP and post-processing.
Problem
CSS orthogonality constraints can reduce girth and impose structural distance upper bounds when enforced together with regularity.
Method
The construction uses controlled commutativity, active-only orthogonality, and staged post-processing to avoid low-weight latent logical operators.
Results
The constructed girth-8, (3,12)-regular [[9216,4612, ≤48]] code achieves FER as low as 10^-8 on the depolarizing channel at 4% error probability.
Takeaways & Limitations
The design provides a regular quantum LDPC construction with large girth while avoiding the conventional distance limitation induced by parent-matrix orthogonality.
Takeaways & Limitations
The reported instance is rate-near-one-half, and only the latent part of its distance is currently certified; non-latent logical operators are bounded through performed searches.
Abstract
from arXiv · showhide
Classical low-density parity-check (LDPC) codes are a widely deployed and well-established technology, forming the backbone of modern communication and storage systems. It is well known that, in this classical setting, increasing the girth of the Tanner graph while maintaining regular degree distributions leads simultaneously to good belief-propagation (BP) decoding performance and large minimum distance. In the quantum setting, however, this principle does not directly apply because quantum LDPC codes must satisfy additional orthogonality constraints between their parity-check matrices. When one enforces both orthogonality and regularity in a straightforward manner, the girth is typically reduced and the minimum distance becomes structurally upper bounded. In this work, we overcome this limitation by using permutation matrices with controlled commutativity and by restricting the orthogonality constraints to only the active part of the construction, while preserving regular check-matrix structures. This design circumvents conventional structural distance limitations induced by parent-matrix orthogonality, and enables the construction of quantum LDPC codes with large girth while avoiding latent low-weight logical operators. As a concrete demonstration, we construct a girth-8, (3,12)-regular $[[9216,4612, \leq 48]]$ quantum LDPC code and show that, under BP decoding combined with a low-complexity post-processing algorithm, it achieves a frame error rate as low as $10^{-8}$ on the depolarizing channel with error probability $4 \%$.
1 Introduction
Quantum LDPC codes cannot directly inherit classical girth and regularity principles because CSS orthogonality constraints can reduce girth and impose structural distance bounds. This work controls commutativity locally and restricts orthogonality to the active construction, yielding a concrete regular code with strong decoding performance.
- CSS orthogonality has no classical counterpart and, when combined straightforwardly with regularity, typically reduces girth and induces structural distance upper bounds.
- Deleting parity-check rows preserves commutation but weakens stabilizer constraints, enlarges the code space, and does not generally preserve distance.
- The proposed design controls commutativity of submatrices, enforces orthogonality only on the active part, and prevents deleted rows from becoming low-weight logical operators.
- The construction provides a girth upper bound under commutativity requirements and explicitly constructs a code attaining that bound.
- The demonstrated (3,12)-regular [[9216,4612, ≤48]] code reaches FER as low as 10^-8 at 4% depolarizing-channel error using BP with low-complexity post-processing.
2 Problem setting: low-weight logical operators induced by check-row removal
The conventional parent-matrix construction can turn low-weight latent rows into logical operators after row deletion, structurally limiting minimum distance. The proposed design instead makes low-weight latent rows non-orthogonal to the active matrices while preserving active CSS orthogonality.
- The conventional construction starts with orthogonal parent matrices, then deletes internal rows to form active matrices and adjust the code rate.
- Parent orthogonality constrains latent rows and can degrade minimum distance by making low-weight latent rows logical operators.
- The minimum distance is dmin = min{dX, dZ}, where dX and dZ are defined through nontrivial logical operators in the corresponding CSS spaces.
- The proposed design enforces non-orthogonality between low-weight latent rows and the opposite active matrix, including low-weight linear combinations.
- Latent-based distance quantities upper bound dmin, so the design aims to make these bounds as large as possible.
3 Method of matrix design
The construction uses block-circulant permutation-matrix parents while enforcing orthogonality only on active rows. Localized commutativity preserves active CSS orthogonality but leaves selected active–latent interactions nonzero, avoiding automatic low-weight logical operators.
- Parent-matrix design: Generalized Hagiwara–Imai codes use block-circulant permutation-matrix parent pairs whose products depend only on block-index differences.The parent matrices are built from permutation blocks, yielding sparse regular structures and difference-indexed interaction matrices.
- Active orthogonality: Active orthogonality HXH_Z^T = 0 is enforced without requiring the full parent matrices to be orthogonal.The active matrices are the top J block rows, while latent rows remain available for controlling distance-related structure.
- Localized commutativity: Commutativity is restricted to a difference set ∆, making the corresponding interaction matrices Ψr vanish for active block-row differences.If Fu and G_{r-u} commute for every relevant u, then Ψr = 0; this supplies a sufficient condition for active orthogonality.
- Latent non-orthogonality: The construction requires L ≥ 4J to preserve nonzero active–latent interactions under the standard top-J-row choice.When L < 4J, ∆ covers all residues, so active orthogonality also annihilates mixed active–latent blocks.
- Latent non-orthogonality: A nonzero interaction Ψr outside ∆ is necessary to prevent latent rows from becoming automatically orthogonal to the active matrices.This condition targets low-weight latent rows and combinations that could otherwise enter the logical-operator space.
- Girth limitation: Under the required commutativity conditions, each active Tanner graph contains an 8-cycle, establishing a structural short-cycle limitation.The result applies for even L with 3 ≤ J ≤ L/2 and the standard top-J active-row choice.
4 Method of Matrix Construction
The matrix-construction procedure searches affine permutation blocks that satisfy localized commutativity while avoiding short cycles. It uses algebraic fixed-point tests and adaptive backtracking as an offline design process.
- Sequential search: The construction sequentially selects permutation blocks satisfying both the commutation table and active short-cycle constraints.Backtracking is used when a candidate fails, and trial allocation is adjusted using recent success rates.
- Affine permutation blocks: Affine permutation matrices use maps fi(x) = aix + bi and gj(x) = cjx + dj over ZP.The corresponding matrices Fi and Gj instantiate the APM–LDPC blocks.
- Commutativity tests: Affine-permutation commutativity reduces to congruence conditions involving the linear and translation parameters.After choosing ai and cj, the remaining constraints become linear congruences in bi and dj.
- Implementation scope: The search is an offline design step rather than part of encoding or decoding.For fixed J and L, the expensive checks are finite congruence and fixed-point tests.
- Short-cycle tests: Short-cycle detection checks fixed points of composite affine maps instead of enumerating the Tanner graph.The composite map has the form Σ(x) = Ax + B, providing an algebraic test for candidate cycles.
5 Method of Decoding
Decoding combines joint BP with staged post-processing for rare stalls. The stages target trapping sets, flip histories, and reliability-based candidate supports, while the reported performance reflects several interacting design choices.
- Belief propagation: Joint BP preserves correlation between X and Z error components on the depolarizing channel.The formulation is equivalent to four-state BP after relabeling the local Pauli states.
- Post-processing trigger: Post-processing is triggered for stalled BP instances with at most 20 unsatisfied checks.The procedure uses ETS-library, FHD, and OSD stages on small-residual cases.
- OSD stage: OSD uses BP reliabilities to choose a candidate support and is reserved for residual syndromes that remain small.A binary search selects the minimum solvable support size while preserving uniqueness.
- Design interaction: Finite-length performance reflects the interaction of girth, degree distribution, APM search, trapping-set filtering, and lift size.The present instance uses a (3, 12)-regular profile, and the measured result should not be attributed to one isolated ingredient.
- FHD stage: FHD forms a candidate support from variables that flipped during BP and solves a local linear correction.The correction is applied on the neighborhood of the flip-history support as a heuristic for trapping-set stalls.
- ETS stage: The ETS library targets harmful b = 2 elementary trapping sets precomputed from the Tanner graph.Each library entry stores a variable set and its pair of odd check nodes.
6 Results
The concrete instance specializes the framework to J = 3, L = 12, and P = 768, using explicit block parameters and active orthogonality conditions. Its construction is evaluated through distance bounds and frame-error performance.
- Concrete instance: J = 3, L = 12, and P = 768 define the smallest constructed instance reported in the section.The instance instantiates the general theory and sequential construction before evaluating distance and frame-error rate.
- Block structure: The parent matrices have a 6 × 12 block-circulant structure for the J = 3 construction.Each block row is a cyclic shift of the preceding row.
- Interaction matrices: The (0, 1) parent-product block is expressed as a sum of F_iG_j and G_iF_j terms and equals Ψ1.This illustrates how the block-circulant products reduce to interaction matrices indexed by differences.
- Active orthogonality: The active difference indices are ∆ = {0, 1, 2, 4, 5}, leaving r = 3 available for nonzero interaction.For active indices i and k in {0, 1, 2}, r = (k − i) mod 6 lies in this set.
6.2 Design goal and commutation table
The construction preserves active orthogonality while deliberately relaxing parent orthogonality, using controlled noncommutativity to avoid low-weight logical operators and harmful trapping-set structures.
- Design goal: Active orthogonality is enforced by setting Ψr = 0 for r ∈ ∆ while retaining Ψ3 ≠ 0.This relaxes parent orthogonality and keeps the latent part from automatically becoming orthogonal to the active part.
- Commutation table: The illustrative commutation table makes all pairs commute except (0, 3) and (1, 2), yielding Ψ3 = F0G3 + G3F0 + F1G2 + G2F1.All other Ψr are zero under this pattern.
- Commutation table: Allowing noncommuting pairs (F0, G3) and (F1, G2) avoids the trapping sets produced by a single noncommuting pair.The minimal design generated many (a, b = 2) ETSs from connected length-8 cycles and associated low-weight logical operators.
- Generalized active sets: For J = 3 and L = 12, choosing S = {0, 2, 4} reduces |∆S| to 3 from 5 under the standard choice.The smaller difference set leaves more indices r ∉ ∆S available for nonzero Ψr and may support shorter constructions.
6.3 Affine permutation construction and choice of P
The paper constructs a girth-8 (3,12)-regular code from affine permutations over Z768, with cycle enumeration quantifying the resulting short-cycle structure.
- Affine permutation construction: The construction uses P = 768 = 3 × 2^8 because the required affine-permutation commutation pattern cannot occur when P is a prime power.Each permutation has the form x ↦ ax + b on ZP with gcd(a, P) = 1.
- Affine permutation construction: The resulting Tanner graph has girth 8, with no 4- or 6-cycles.The construction is a (3,12)-regular code based on the parameters listed in Table 1.
- Short-cycle counting: 18P = 13,824 lifted 8-cycles arise from the counted block pattern for J = 3 and L/2 = 6.The pattern uses ∆ = {0, 1, 2, 4, 5} and an intersection of shifted difference sets equal to {0, 1, 2}.
- Short-cycle counting: 60,512 X-side and 54,656 Z-side 8-cycles are enumerated in the constructed instance.The totals exceed the block-pattern lower bound because additional commuting pairs and specific affine-permutation parameters create extra cycles.
6.5 Trapping set library construction
The construction exhaustively enumerates dominant trapping-set patterns from 8-cycles and uses latent-space analysis to certify a latent distance of 48, while the full minimum distance remains only upper bounded.
- Trapping-set library construction: The trapping-set library exhaustively enumerates patterns formed from multiple length-8 cycles, rather than only structures observed during decoding.The library targets patterns dominant in initial BP stalls.
- Trapping-set library construction: For P = 768, the library contains 64 (6,2), 23 (12,2), and 48 (8,2) path4 trapping sets.The (6,2) counts are 48 X-side and 16 Z-side; the (12,2) and (8,2) path4 counts are exclusively X-side.
- Minimum-distance evaluation: The four permutation terms in Ψ3 have disjoint supports, yielding kernels generated by 192 disjoint weight-4 codewords.Each 4-point block is represented by [t] = {t, t + 192, t + 384, t + 576}.
- Minimum-distance evaluation: Explicit latent vectors lift to weight 48 and are nontrivial logical operators, proving d(lat)_X and d(lat)_Z are at most 48.The vectors are constructed from latent matrices and are outside the relevant dual spaces.
- Minimum-distance evaluation: Block compression proves d(lat)_X and d(lat)_Z are at least 48, so both latent distances equal 48.Compressed nonzero vectors have weight at least 12, and expansion multiplies weight by 4.
- Minimum-distance evaluation: The full minimum distance remains certified only as dmin ≤ 48 because lower bounds for non-latent logical operators are unavailable.Girth 8 supports BP performance and trapping-structure suppression but does not itself certify a CSS distance lower bound.
6.7 Frame error rate
Under BP decoding with post-processing, the constructed code reaches a frame error rate of 10^-8 at depolarizing-channel error probability 4%.
- Frame error rate: 10^-8 FER is reached at depolarizing-channel error probability 4% under BP decoding with post-processing.Each plotted point used at least 50 error events, with 95% confidence intervals.
6.8 Density evolution benchmark
A non-orthogonal random (3,12)-regular code pair provides a classical density-evolution benchmark for interpreting BP performance, despite not being a CSS code.
- Density evolution benchmark: The benchmark uses independently drawn non-orthogonal random (3,12)-regular HX, HZ matrices from the standard configuration-model ensemble.Because the pair is not a CSS code, it has no direct physical meaning but can estimate noise from syndromes.
6.9 Instance dependence
Waterfall behavior is expected to be relatively stable across instances, whereas error-floor behavior near 10^-8 depends strongly on instance selection and screening.
- Instance dependence: For fixed local degrees and girth constraints, the waterfall region is expected to be governed largely by local message-passing behavior.The concentration analogy supports limited instance-to-instance variation there, though it is not directly proved for the structured APM family.
- Instance dependence: Near FER 10^-8, an absolute FER difference of order 10^-8 is significant for evaluating the error floor.The same difference is essentially invisible on the logarithmic FER scale in the waterfall region.
- Instance dependence: The reported construction requires simulation-based screening and distance searches because admissible active-orthogonality conditions alone do not exclude small-distance or poor-error-floor mechanisms.Using only one non-commuting pair produced many harmful trapping sets and low-weight logical operators; two non-commuting pairs led to the reported instance.