High-Girth QLDPC Codes from Circulant and Affine Permutation Matrices

Background

• Tanner graph girth is desirable but does not by itself determine quantum distance, which depends on undetectable errors outside the stabilizer group.CSS codes require orthogonal parity-check matrices, while QLDPC codes also seek sparsity, useful dimension, and distance.Source: §I · p. 1

Circulant construction

• The explicit circulant-based CSS QLDPC family has parameters [[6N, 2N + 2, 6]] for N = 31 and every N ≥ 37; orthogonality, rank, Tanner graph girth, and minimum distance are established analytically.Source: §I · p. 1
• When both check matrices have column weight two and row weight six, the construction attains the largest possible Tanner girth: Proposition 1 gives gX ≤2w for a nonzero HZ row of weight w.The restriction applies regardless of the circulant representation.Source: §I · p. 1

Polynomial construction

• The second construction uses a fixed commuting pair of matrix polynomials with circulant and affine permutation coefficients, and its orthogonality and row and column weights hold for every outer lift size.Ranks and distances for selected lift sizes are finite computational results and do not establish an asymptotic distance growth law.Source: §I · p. 1

A. Permutation Blocks

• All matrix sums are over F2, and P_f denotes the permutation matrix associated with a permutation f of Z_N.Source: A. Permutation Blocks · p. 1
• A circulant permutation matrix is C_s = P_{t→t+s}, while an affine permutation matrix is F_{a,b} = P_{t→at+b} with gcd(a, N) = 1.Source: A. Permutation Blocks · p. 1
• The component matrices satisfy C_s^T = C_-s and F_{a,b}C_s = C_{as}F_{a,b}.The second identity holds because both compositions send t to at+as+b.Source: A. Permutation Blocks · p. 1
• Shift subscripts and affine map values in these definitions are reduced modulo N.Source: A. Permutation Blocks · p. 1
• These component permutation matrices are used to build the stabilizer matrices of a CSS code.Source: A. Permutation Blocks · p. 1

B. CSS Codes and Orthogonality Conditions

• The expanded check matrices have mX = NJX rows, mZ = NJZ rows, and n = NL columns, with one N × N permutation matrix per block.JX and JZ count block rows, while mX and mZ count individual binary checks.Source: B. CSS Codes and Orthogonality… · p. 2
• For square binary matrices, AB + BA = 0 is equivalent to AB = BA, and the orthogonality condition requires each input coordinate's output to occur an even number of times.The paper uses this commuting-pair condition for Construction II.Source: B. CSS Codes and Orthogonality… · p. 2
• Construction I uses a blockwise CSS orthogonality condition, while Construction II builds a commuting pair satisfying AB + BA = 0.In each construction, a fixed permutation pattern provides an algebraic orthogonality certificate before the lift size is chosen.Source: B. CSS Codes and Orthogonality… · p. 2

A. Case study: a fixed pattern and its incidence graphs

• Each check matrix has size 2N×6N, with row weight six, column weight two, and one permutation matrix in every block.A zero shift represents the identity permutation.Source: A. Case study: a fixed pattern and its… · p. 2
• Each qubit column represents an edge between checks, making the parity-check matrix the biadjacency matrix of a bipartite (2, 6)-regular Tanner graph on 2N vertices.The auxiliary incidence graph joins the two check rows touched by each qubit; each such edge corresponds to a two-edge path through that qubit in the Tanner graph.Source: A. Case study: a fixed pattern and its… · p. 2
• For N=31 or N≥37, the construction yields [[6N, 2N+2, 6]] CSS codes with check weight six, column degree two, Tanner girths 12, and check-matrix ranks 2N−1.Both check matrices have rank 2N−1.Source: A. Case study: a fixed pattern and its… · p. 2
• Even-multiplicity shift sums guarantee orthogonality for every N; connected incidence graphs and a graph isomorphism give both check ranks 2N−1 and k=2N+2.The X incidence graph is connected, and the Z rank follows from an isomorphism to the corresponding graph.Source: A. Case study: a fixed pattern and its… · pp. 2–3
• For N=31 and N≥37, distinct modular differences exclude parallel edges and 4-cycles, while the 2×r circulant bound fixes Tanner girth at 12.The difference argument gives girth at least 12,; the same proof applies to both auxiliary graphs.Source: A. Case study: a fixed pattern and its… · p. 3
• For every allowed N, a weight-six logical operator meets the incidence-graph lower bound d≥6, establishing exact quantum distance d=6.The constructed vector has weight six, has zero X syndromes, and is not in row(HZ).Source: A. Case study: a fixed pattern and its… · p. 3

B. Reusable conditions and the girth limitation

• n = 6N, k = 2N + 2, gX = gZ = 12, and d = 6 under the stated sufficient conditions.The conditions require even multiplicities in −b, −c, a−b, and a−c; a signed, shifted permutation relation between c−b and a; and distinct ordered differences av−aw with the stated gcd equal to one.Source: B. Reusable conditions and the girth… · p. 3
• With every HX column of weight two, a nonzero HZ row of weight w implies gX ≤ 2w; the analogous bound holds with X and Z interchanged.The proof associates each weight-w codeword in a 2 × n matrix with a 2w-cycle.Source: B. Reusable conditions and the girth… · p. 3
• Replacing CPMs with other permutations cannot raise either girth above twelve when column degree two and check weight six are retained.Classical prelifting can avoid a circulant girth bound, but it does not remove this additional CSS bound; a shortest cycle may be a stabilizer, so the bound does not upper-bound quantum distance.Source: B. Reusable conditions and the girth… · p. 3
• Changing only N gives listed realizations with rate 3 + 1/(3N) and minimum distance six.Table I lists the realizations; all distances are exact by Theorem 1.Source: B. Reusable conditions and the girth… · p. 3, Table I · p. 3

IV. MIXED CIRCULANT–AFFINE CONSTRUCTION

• The fixed base combines 24×24 circulant shifts with an affine permutation; commutation conditions select the blocks but do not establish a lower bound on quantum distance.The diagonal polynomial commutes with the circulant-coefficient blocks, while affine identities supply the off-diagonal commutation conditions.Source: §IV · pp. 3–4
• For every q≥2, AB=BA guarantees CSS orthogonality after lifting, giving length 96q and check matrices with 48q rows, row weight six, and column weight three.The lift preserves sums and products, so the polynomial commutation identity remains valid for every outer lift size.Source: §IV · p. 4
• The q=2 lift yields [[192, 16, 8]], with dX=dZ=8 and Tanner girth eight; completed support enumerations certify the exact distance.A weight-eight logical operator supplies the upper bound, while the enumerations exclude smaller even weights; odd column weight and girth eight rule out weight-two kernel vectors.Source: §IV · p. 4, Table II · p. 4
• The outer-lift table varies only q while keeping polynomial coefficients and exponents fixed; all listed checks have girth eight, and reported exact distances rely on completed enumerations.For each reported distance, the archived calculations exclude smaller even-weight logical operators and find a weight-d operator outside the stabilizer row space.Source: §IV · p. 4, Table II · p. 4
• The distance search tests zero-syndrome supports against the stabilizer row spaces and uses only symmetries preserving both spaces; an unfinished search stage gives no lower bound.It suffices to examine supports without a proper nonempty zero-syndrome subset, since such a subset or its complement would be a lighter logical operator.Source: §IV · pp. 4–5

• At N = 128, both codes have parameters [[768, 258, 6]], check weight six, column weight two in each check matrix, and Tanner graph girths gX = gZ = 12.The constructed matrices each have size 256 × 768 and rank 255.Source: §V · p. 5
• The code has 3840 weight-six logical supports on each CSS side, versus 4864 for the reference, a reduction of approximately 21.05%.Distinct binary supports are counted separately, without identifying operators that differ by a stabilizer; the comparison concerns minimum-weight operators, not higher-weight multiplicities or a proportional FER reduction.Source: §V · p. 5
• At p = 10^-3 and p = 5 × 10^-3, our code has lower measured FER than the reference under BP–OSD–10, RL–S, and RLMB.The RL decoders use T = 32 maximum iterations; the comparison keeps length, rate, minimum distance, check weight, and girth unchanged.Source: §V · p. 5, Figure 1 · p. 5

VI. STRUCTURAL LIMITATIONS AND CONCLUSION

• R = 1/3 + 1/(3N) for Construction I, while Construction II’s q=2 instance has 96 rows per matrix, rank 88, and R = 16/192.Construction I has column degrees (2, 2) and one dependency on each side; Construction II has (3, 3), with positive dimension arising entirely from row dependencies.Source: §VI · p. 5
• Distance six is constant for the first family, so its relative distance tends to zero as N grows despite increasing dimension and block length.Proposition 1 limits girth to twelve under the same column-degree and check-weight constraints; a shortest cycle alone does not determine quantum distance.Source: §VI · p. 5
• For every q >= 2, Theorem 2 proves orthogonality and weights for the mixed family, while its listed ranks, girths, and distances are finite calculations.A larger quantum distance for a different pattern requires every shorter kernel vector to lie in the corresponding stabilizer space.Source: §VI · p. 5
• The circulant pattern has a uniform proof of rate and distance, whereas the mixed polynomial base gives larger certified distances at selected lengths.Complete block descriptions specify the binary matrices without a separate orthogonality computation for each lift, and worked examples show how the algebra determines checks, ranks, and logical operators.Source: §VI · p. 5