PaperlayerView exact revision on arXiv

Source-linked AI summary

Temporal Degeneracy Limits Message Passing Decoding of QLDPC Codes Under Repeated Noisy Syndrome Measurements

Dimitris Chytas, Nithin Raveendran, Bane Vasić

arXiv:2610.31877v1quant-phcs.ITmath.IT

TL;DR

Repeated noisy syndrome measurements introduce temporal degeneracy into space-time decoding, complicating efficient decoding of QLDPC codes. The paper characterizes temporal codewords and the resulting local failures of isotropic message passing, then proposes syndrome-guided space-time anisotropic min-sum decoding. On the tested BB codes, the proposed approach shows threshold-like behavior and improved failure probabilities relative to MS with OSD post-processing.

  • Problem

    Repeated noisy syndrome measurements create temporal degeneracy in the space-time decoding graph, while efficient decoding is needed to use QLDPC codes at very low logical error rates.

    Source: §I · p. 2

  • Method

    The paper characterizes temporal-kernel generators and harmful degenerate patterns, then proposes space-time anisotropic min-sum decoding with syndrome-guided realizations.

    Source: §I · pp. 2–3

  • Results

    The proposed decoder shows threshold-like behavior across tested BB-code sizes and improved performance relative to MS followed by OSD.

    Source: §I · p. 3

  • Takeaways & Limitations

    Under the stated assumptions, local failures of isotropic flooding decoders depend on node degrees rather than minimum distance, motivating updates that break the relevant symmetries.

    Source: §I · p. 2

Abstract

from arXiv · show

Practical quantum computations can require logical error rates of $10^{-12}$ or lower. Quantum low-density parity-check (QLDPC) codes are promising candidates for reaching such rates with low qubit overhead, provided that their syndromes can be decoded efficiently. Repeated noisy syndrome measurements introduce temporal degeneracy into the space-time decoding graph. We characterize the temporal kernel, whose vectors have zero total data parity, and show that it is generated by elementary temporal codewords of weight $d_v+2$, where $d_v$ is the variable-node degree. For $(d_v,d_c)$-regular parity-check matrices with fixed degrees $d_v,d_c>2$ and girth greater than four, we derive counting bounds and construct degenerate error patterns of weight $(d_v+2)/2$ for even $d_v$ and $d_v+1$ for odd $d_v$, with multiplicity $\Theta(nr)$ in the blocklength $n$ and number of measurement rounds $r$. Under the isolation assumption, these patterns cause local failures of deterministic isotropic message-passing decoders under a flooding schedule. These failures depend on the node degrees rather than the minimum distance; for the bivariate bicycle (BB) codes considered, their weight is equal to four. Monte carlo simulations and fixed-weight importance sampling quantify harmful low-weight degenerate error patterns for the min-sum (MS) decoder beyond the isolation assumption. Motivated by the identified symmetries, we propose space-time anisotropic min-sum decoding with syndrome-guided realizations. Its complexity is linear in the number of Tanner graph edges for fixed maximum number of iterations and number of decoders. Numerical results on BB codes show threshold-like behavior acrossthe tested code sizes and improved failure probabilities relative to MS decoding with ordered statistics decoding post-processing.

I. INTRODUCTION

Repeated noisy syndrome measurements create temporal degeneracy that can limit iterative decoding independently of code distance. The paper characterizes this structure and its decoding failures, then motivates anisotropic decoding to break the relevant symmetries.

I. INTRODUCTION

  • QLDPC decoding is complicated by degeneracy: errors differing by a stabilizer can produce the same syndrome, and iterative decoding can struggle when equivalent patterns have equal weight and symmetric support.Repeated noisy measurements require decoding a consistent space-time error configuration, whereas code-capacity decoding assumes perfect syndrome measurements.Source: §I · pp. 1–2, A. Stabilizer formalism · p. 3

B. Phenomenological Noise Model

  • In the phenomenological noise model, data and syndrome errors are independent stochastic processes and recovery is idealized; conventionally, the last measurement round is assumed perfect, and decoding infers a consistent space-time error configuration.Source: §I · p. 2, B. Phenomenological Noise Model · p. 4

I. INTRODUCTION

  • Elementary temporal codeword generators have weight d_v + 2 and their embedded copies generate the temporal kernel, whose vectors have zero total data parity across rounds.Such codewords relate error patterns with the same overall data error.Source: §I · p. 2
  • Under symmetric initialization and isolation, degree- and girth-dependent symmetries cause local failures for deterministic isotropic flooding decoders, with harmful-pattern multiplicity scaling as Θ(nr).The reported weight depends on variable-node degree rather than minimum distance; for the cited BB codes, isotropic decoders fail on weight-4 patterns despite distances 12 and 18.Source: §I · p. 2
  • The paper derives decoder-agnostic upper bounds on locally minimum half-weight patterns and identifies constant-weight harmful families for regular matrices with fixed degrees greater than two and girth above four.The failures are described as arising from measurement-induced local symmetries rather than the code's algebraic construction.Source: §I · p. 2
  • BB-code results show threshold-like behavior across tested code sizes and improved performance over MS followed by OSD.For fixed iteration and ensemble budgets, the proposed decoder has complexity linear in the number of Tanner graph edges.Source: §I · p. 3

A. Stabilizer formalism

  • For a regular parity-check matrix, each column and row has fixed weight d_v and d_c, respectively.The minimum distance is the minimum nonzero Hamming weight among codewords.Source: A. Stabilizer formalism · p. 3
  • A CSS code uses two classical codes, and its X and Z errors can be decoded separately as binary problems using the opposite-type parity-check matrix.A Tanner graph represents a parity-check matrix as variable and check nodes connected wherever the matrix has a nonzero entry.Source: A. Stabilizer formalism · p. 3

III. EVALUATION OF TEMPORAL DEGENERACY

The section characterizes the temporal kernel first in a small base matrix and then for one variable node repeated across measurement rounds. It uses this structure to characterize and count locally minimum half-weight error patterns supported on temporal codewords.

A. Analysis of the base matrix

  • The base-matrix kernel has 2^(r-1)-1 nonzero vectors, with each vector's data part determined by its measurement part.For two ones in the measurement block, consecutive positions yield weight 4, while nonconsecutive positions yield weight 6.Source: A. Analysis of the base matrix · p. 5
  • Weight-3 minimal vectors form a basis of the base-matrix kernel, and lifting them yields weight-(d_v+2) temporal codeword generators.The base-matrix minimal vectors correspond to runs of ones; for a run of length k, there are r-k such vectors of weight k+2.Source: A. Analysis of the base matrix · p. 5

B. One variable node repeated in time

  • Lifting gives a bijection between the base-matrix kernel and the kernel for one repeated variable node, whose vectors are all temporal codewords.The weight-(d_v+2) vectors are minimum-weight temporal codewords and span this kernel, so adding rounds introduces no lower-weight minimal vectors.Source: B. One variable node repeated in time · p. 6
  • Temporal codewords relate error patterns with the same overall data error, so their equal-weight halves are equivalent corrections with the same syndrome.A decoder unable to choose between such halves fails even though either correction is valid.Source: B. One variable node repeated in time · p. 6
  • The number of locally minimum half-weight patterns depends on k and d_v, not on blocklength or code distance.For the illustrated weight-10 temporal codeword, the passage reports 200 qualifying weight-5 patterns.Source: B. One variable node repeated in time · pp. 7–8
  • Locally minimum half-weight patterns are restricted to a codeword's support and cannot be reduced by adding constituent generators.The comparison is among syndrome-equivalent errors formed by adding combinations of the specified generators.Source: B. One variable node repeated in time · p. 7

C. Harmful temporal degenerate error patterns

The section extends the local temporal-kernel characterization to the full space-time matrix and counts potentially harmful degenerate patterns under stated regularity and girth conditions. It identifies degree-dependent pattern weights and reports that their number grows as Θ(nr).

C. Harmful temporal degenerate error patterns

  • Every temporal codeword in the full space-time matrix is a sum of embedded weight-(d_v+2) temporal codeword generators.The temporal degeneracy is thereby characterized locally, independently of the particular code construction.Source: C. Harmful temporal degenerate error… · p. 8
  • For odd d_v and girth greater than four, every nonzero even-weight temporal codeword has weight at least 2d_v+2.Odd-weight generators cannot be split into equal halves; the smallest even-weight temporal codewords therefore support patterns of weight d_v+1, which is four when d_v=3.Source: C. Harmful temporal degenerate error… · p. 8
  • The number of these harmful-pattern incidences grows as Θ(nr), with matching-order lower bounds reported for the stated setting.Here n is blocklength and r is the number of measurement rounds.Source: C. Harmful temporal degenerate error… · p. 8
  • For even d_v, the counted locally minimum half-weight errors have weight (d_v+2)/2 under the theorem's regularity and girth conditions.The theorem concerns errors supported on minimum even-weight temporal codewords with nonzero measurement parts.Source: C. Harmful temporal degenerate error… · p. 8

D. Spatial-Temporal Degeneracy

Mixed spatial-temporal codewords combine a stabilizer in one round with a temporal codeword, so spatial and temporal degeneracy occur together. In the decoding analysis, automorphism-preserving isotropic message passing can fail locally on paired degenerate patterns under specified assumptions, motivating anisotropic updates.

D. Spatial-Temporal Degeneracy

  • Mixed spatial-temporal codewords are sums of a stabilizer placed in one round and a temporal codeword, combining spatial and temporal degeneracy.For the illustrated regular two-block code with d_v = 3 and girth greater than four, Fig. 8 depicts a weight-10 mixed codeword.Source: D. Spatial-Temporal Degeneracy · p. 9, Figure 8 · p. 9

IV. EFFECT OF TEMPORAL DEGENERACY ON ITERATIVE DECODING

  • With symmetric initialization and isolation, isotropic decoding preserves syndrome-label-preserving automorphisms, forcing related variable nodes to have equal hard decisions.The resulting symmetry prevents the decoder from matching either of the two complementary half-weight patterns on the temporal-codeword support.Source: §IV · pp. 10–11
  • Theorem 3 guarantees at least N even-degree patterns of weight (d_v+2)/2 or N odd-degree patterns of weight d_v+1 that cause local failures under its assumptions.The result applies to regular parity-check matrices with d_v > 2, girth greater than four, at least two rounds, deterministic isotropic decoding under flooding, and the isolation assumption.Source: §IV · pp. 10–11
  • The counted constant-weight degenerate patterns occur with multiplicity Θ(nr), but these bounds do not predict the full-graph logical error rate.The failure statement is scoped to regular codes of girth greater than four, d_v > 2, and the phenomenological noise model under isolation.Source: §IV · p. 11
  • Variable-node labeling can break the relevant symmetries when no label-preserving automorphism satisfies the failure condition, though symmetry breaking alone does not guarantee successful decoding.The paper leaves optimal decoding for the phenomenological noise model beyond its scope.Source: §IV · pp. 11–12

V. NUMERICAL RESULTS

The numerical-results section evaluates min-sum-based decoding for X errors and measurement errors on BB codes under a binary symmetric channel. It runs the algorithms for 100 iterations and specifies when a trial counts as a failure.

V. NUMERICAL RESULTS

  • The case study evaluates X-error and measurement-error decoding on BB codes using min-sum-based algorithms for 100 iterations.Both error types are independently introduced by a binary symmetric channel with crossover probability α.Source: §V · p. 12
  • A trial fails if no syndrome-consistent estimate is found or if the returned estimate has a total data residual outside the rowspace of HX.Source: §V · p. 12
  • The measurement-round count r includes r − 1 noisy syndrome rounds followed by one ideal syndrome round.Source: §V · p. 12

A. Space-time anisotropic min-sum decoding

Space-time anisotropic min-sum decoding assigns different update rules to selected data nodes to break symmetries associated with spatial and temporal degeneracy. In the reported BB-code comparison, it shows evidence of threshold-like behavior where isotropic min-sum does not, while some temporal symmetries remain.

A. Space-time anisotropic min-sum decoding

  • For the BB codes considered, each block has row weight three and each stabilizer induces a subdivided K3,3 graph, motivating separate anisotropic rules across blocks and rounds.Source: A. Space-time anisotropic min-sum… · p. 12
  • The decoder alternates which data block is flagged across rounds, while measurement nodes remain unflagged and use the standard MS update.The selected block alternates between consecutive rounds, with flags fixed throughout decoding iterations.Source: A. Space-time anisotropic min-sum… · p. 13
  • Space-time anisotropic MS shows evidence of threshold-like behavior, while isotropic MS shows none in the tested BB-code setting.The comparison uses phenomenological noise with one noisy measurement followed by an ideal one; decoding runs for 100 iterations.Source: A. Space-time anisotropic min-sum… · p. 13, Figure 9 · p. 13
  • The deterministic data coloring leaves automorphisms relating paired weight-4 patterns on weight-8 temporal codewords and weight-6 patterns on a weight-12 codeword.The latter example spans three rounds; repeating the coloring every two rounds gives all four data nodes identical colors.Source: A. Space-time anisotropic min-sum… · p. 13, Figure 10 · p. 13
  • These residual symmetries motivate coloring measurement variable nodes and a syndrome-guided extension of space-time anisotropic MS.Source: A. Space-time anisotropic min-sum… · p. 13

B. Low-weight error patterns and syndrome-guided decoding

Guided space-time anisotropic MS achieves the lowest logical error rates at low crossover probabilities in the tested BB-code comparisons, while low-weight tests expose both residual failures and their scope. The approach uses syndrome-guided measurement-node updates and has edge-linear complexity for fixed decoding budgets.

B. Low-weight error patterns and syndrome-guided decoding

  • For the constructed weight-four family on the full space-time graph, isotropic MS fails on 19,008/38,880 patterns at r = 2 and 93,312/171,072 at r = 5, versus 912 and 6,912 for anisotropic MS.For the separate weight-two family, isotropic MS fails on all 288 patterns at r = 2 and 1,152 at r = 5; anisotropic MS corrects every tested pattern.Source: B. Low-weight error patterns and… · p. 14
  • At αIS = 10^-3 and r = 2, space-time anisotropic MS corrects every tested pattern through weight three, while fixed-weight sampling estimates contributions from weights four through six.The sampling enumerates all supports where feasible and otherwise draws uniformly from supports of the specified weight; the reported partial sum excludes other weights.Source: B. Low-weight error patterns and… · p. 14
  • Syndrome-guided realizations assign node-dependent coefficients to active measurement nodes, adding coloring while retaining deterministic data-node coloring to help break residual temporal symmetries.Symmetry breaking alone does not guarantee successful decoding; realizations use the same initialization and stop at the first estimate matching the input space-time syndrome.Source: B. Low-weight error patterns and… · pp. 14–15

C. Comparison with OSD Post-Processing and Relay-BP

  • At low crossover probabilities, guided space-time anisotropic MS has the lowest logical error rates in both measurement-round settings, while Relay-BP-1 is comparable with a larger sequential budget.The guided ensemble uses ND = 9; Relay-BP-1 has a total iteration limit of 1000 across sequential legs.Source: C. Comparison with OSD Post-Processing… · p. 16, Figure 13 · p. 16
  • At α = 0.02 with four noisy rounds, increasing guided realizations from ND = 1 to ND = 99 lowers the logical error rate from 2.09 × 10^-4 to 2.58 × 10^-5.Each realization is limited to 100 iterations; the comparison also varies Relay-BP-1's total budget from 100 to 2,000 iterations.Source: Figure 14 · p. 16, C. Comparison with OSD Post-Processing… · p. 17

VI. CONCLUSIONS

  • For fixed iteration and ensemble budgets, guided decoding scales linearly with space-time Tanner-graph edges, and BB-code results show practical improvements over MS with OSD post-processing.Extending the techniques to circuit-level noise is identified as future work.Source: §VI · p. 17, C. Comparison with OSD Post-Processing… · p. 17

APPENDIX A PROOFS OF THE RESULTS IN SECTION III

The appendix supplies proof steps for the combinatorial counting and kernel results used earlier. It establishes minimality and basis properties, then connects kernel vectors across repeated measurements through a bijective lift.

A. Proof of Lemma 1

  • The counting proof partitions consecutive measurement ones into blocks, separates those blocks with zeros, and weights each configuration by its left- and right-block contributions.It then sums over the possible block counts and pairings to enumerate the vectors.Source: A. Proof of Lemma 1 · p. 17

B. Proof of Lemma 2

  • For a vector with k consecutive measurement ones and two data ones, the restricted matrix has k + 1 independent rows, so its rank is k + 1 and the vector is minimal.The proof establishes independence successively from the columns of the two data-part columns and the measurement-part block.Source: B. Proof of Lemma 2 · pp. 17–18

C. Proof of Lemma 3

  • The vectors c1,2_i are linearly independent and form a basis of ker(B), because their number equals the dimension of that kernel.Source: C. Proof of Lemma 3 · p. 18

D. Proof of Lemma 4

E. Proof of Corollary 1

  • The lifting map from ker(B) to ker(H(r)) is bijective: each lifted vector retains its data part and repeats the measurement coordinates.The proof identifies the measurement coordinates from cumulative data parities and verifies the final parity-check equation.Source: E. Proof of Corollary 1 · p. 18

F. Proof of Corollary 2

The proof identifies temporal codewords through the parity of their data coordinates, then derives necessary local constraints for counting half-weight patterns. Its counting bound scales linearly with the number of measurement rounds for fixed parameters.

F. Proof of Corollary 2

G. Detailed Proof of Theorem 1

  • The support of a concatenated temporal vector is the symmetric difference of its constituent supports, which yields local constraints on any locally minimum half-weight error pattern.The singleton-partition constraints are necessary but not sufficient.Source: G. Detailed Proof of Theorem 1 · pp. 19–20
  • The proof counts patterns satisfying the necessary singleton constraints by summing over admissible weight distributions, with a bound linear in r for fixed k and d_v.A contiguous vector spanning k rounds has r − k possible placements.Source: G. Detailed Proof of Theorem 1 · p. 20

H. Proof of Lemma 5

The proof constructs temporal kernel vectors from sequences of data bits with even total parity. It shows that the full temporal kernel is generated by embedded weight-(d_v + 2) temporal codewords.

H. Proof of Lemma 5

  • A temporal vector has zero total data parity, and its data sequence uniquely determines its measurement blocks through cumulative parity.The measurement blocks are given by z(t) = H(x(1) + ··· + x(t)).Source: H. Proof of Lemma 5 · pp. 20–21
  • Every temporal codeword in ker(H′) is generated by linear combinations of embedded weight-(d_v + 2) temporal codeword generators.The proof first relates embedded local syndrome contributions to the syndrome blocks of the full vector.Source: H. Proof of Lemma 5 · p. 21

I. Proof of Lemma 6

The proof bounds temporal-codeword weight by tracking data-parity transitions and the associated measurement contribution. For odd d_v, every nonzero even-weight temporal codeword D has weight at least 2d_v + 2.

J. Proof of Theorem 2

  • Each nonzero data coordinate in an intermediate vector g_t requires at least two parity transitions because the sequence begins and ends at zero.Those transitions contribute nonzero entries to adjacent data blocks.Source: §I · p. 21
  • The proof lower-bounds the measurement contribution at a selected time using the variable and check neighborhoods of the support of g_t.It relates the number of incident checks with odd overlap to the parity-check image of g_t.Source: §I · p. 21
  • For odd d_v, every nonzero even-weight temporal codeword D has weight w(D) ≥ 2d_v + 2.The measurement contribution is Ld_v, with L even and at least 2; the data part has even weight and at least two nonzero coordinates.Source: §I · pp. 21–22

J. Proof of Theorem 2

The proof counts locally minimum half-weight errors supported on minimum-weight even temporal codewords. Even d_v uses elementary generators directly, while odd d_v requires sums of two generators.

J. Proof of Theorem 2

  • For even d_v, each weight-(d_v + 2)/2 error supported on a weight-(d_v + 2) generator is locally minimum, with n(r − 1) generators.The proof counts incidences between these generators and their associated errors.Source: J. Proof of Theorem 2 · p. 22
  • For odd d_v, the generator has odd weight, so the proof instead considers minimum even temporal codewords of weight 2d_v + 2.These arise from two generators sharing and canceling either a data-variable coordinate or a measurement-variable coordinate.Source: J. Proof of Theorem 2 · p. 22
  • The odd-degree count combines the two shared-coordinate cases to bound incidences between minimum even temporal codewords and locally minimum weight-(d_v + 1) errors.The proof separately counts the same-data-variable case and the shared-check case, then summarizes their incidences.Source: J. Proof of Theorem 2 · p. 22

K. Proof of Lemma 7

The proof characterizes the kernel of Π through stabilizer shifts and temporal codewords. It concludes that temporal codewords are generated by embedded weight-(d_v + 2) generators.

K. Proof of Lemma 7

  • The kernel of Π is precisely the set of temporal codewords, and it is generated by embedded weight-(d_v + 2) temporal codeword generators.The proof adds a stabilizer placed in one data block to D, showing the resulting vector remains in ker(H′) and lies in ker(Π).Source: K. Proof of Lemma 7 · p. 23
  • The stabilizer shift Sh satisfies every detector equation because the underlying h is a stabilizer, so both D and Sh belong to ker(H′).Their sum T is used to establish the kernel characterization.Source: K. Proof of Lemma 7 · p. 23

APPENDIX B DETAILED PROOF OF THEOREM 3

The proof constructs balanced error supports with syndrome-label-preserving automorphisms that map each support to its complement. Under isolation, the resulting paired hard decisions prevent isotropic decoding from estimating those patterns.

APPENDIX B DETAILED PROOF OF THEOREM 3

  • For even d_v, the induced graph of the weight-(d_v + 2) generator is a subdivided K2,d_v, and the proof counts balanced supports on it.The counted supports include one of the two degree-d_v data nodes and half of the degree-2 measurement nodes.Source: Appendix B · pp. 23, 26
  • Under isolation, a syndrome-label-preserving automorphism maps each balanced support to its complement, forcing paired hard decisions and preventing an isotropic decoder from estimating either support.The proof constructs the automorphism by swapping a1 and a2 and pairing the selected and unselected nodes in B.Source: Appendix B · p. 23
  • For odd d_v, the proof considers weight-(2d_v + 2) temporal codewords formed by concatenating two generators, including cases sharing a data or measurement variable.It characterizes supports admitting complement-mapping automorphisms and uses them to establish decoder failures under isolation.Source: Appendix B · pp. 23–25
  • The enumeration counts distinct error supports: the data coordinates and occupied measurement intervals identify their supporting temporal codeword, while girth greater than four prevents ambiguous variable identification.The proof also separates the cases by their number of data coordinates, so supports from the two cases cannot coincide.Source: Appendix B · p. 26

Related papers

Loading 2610.31877v1…