PaperlayerView exact revision on arXiv

Source-linked AI summary

A matching decoder for bivariate bicycle codes

Kaavya Sahay, Dominic J. Williamson, Benjamin J. Brown

arXiv:2602.22770v2quant-ph

TL;DR

Decoding newly developed quantum error-correcting codes requires efficient methods for systems encoding many logical qubits with relatively few physical qubits. This paper uses toric-code equivalence and the cylinder trick to decode bivariate bicycle codes with matching, finding broad benchmark applicability and competitive performance after augmentation with belief propagation and over-matching.

  • Problem

    New LDPC quantum error-correcting codes require efficient and accurate decoders to support their operation.

  • Method

    The paper decodes bivariate bicycle codes with matching on code symmetries, using their equivalence to copies of the toric code and the cylinder trick to construct corrections.

  • Results

    Across gross, generalized toric, and directional BB-code families under code-capacity and phenomenological noise, augmented matching variants are competitive with state-of-the-art decoders.

  • Takeaways & Limitations

    Belief propagation, over-matching, and related subroutines substantially improve matching when bare symmetry matching fails, while retaining an efficient practical implementation.

  • Takeaways & Limitations

    The general use of code symmetries to produce a decoder remains unclear beyond settings where an overcomplete check matrix enables symmetry extraction.

Abstract

from arXiv · show

The discovery of new quantum error-correcting codes that encode several logical qubits into relatively few physical qubits motivates the development of efficient and accurate methods of decoding these systems. Here, we adopt the minimum-weight perfect matching algorithm, a subroutine invaluable to decoding topological codes, to decode bivariate bicycle codes. Using the equivalence of bivariate bicycle codes to copies of the toric code, we propose a method we call the `cylinder trick' to rapidly find a correction using matching on code symmetries. We benchmark our decoder on the gross code family, cyclic hypergraph-product codes, generalized toric codes, and recently proposed directional codes under code capacity and phenomenological noise models, demonstrating the general applicability of our protocol. For a subset of these codes, we find that our decoder can be significantly improved by augmenting matching with strategies including belief propagation and `over-matching', thus achieving performance competitive with state-of-the-art approaches.

I. INTRODUCTION

Bivariate bicycle codes extend decoding challenges to non-local LDPC quantum codes, while retaining a lattice structure related to copies of the toric code. The paper develops symmetry-based matching methods, benchmarks them across BB-code families, and augments them to address failures from large stabilizer supports and incomplete syndrome information.

  • Motivation: Non-local LDPC quantum error-correcting codes encode substantial quantum information into relatively few physical qubits, motivating efficient decoding algorithms.
  • Bivariate bicycle codes: Bivariate bicycle codes are translationally invariant lattice codes whose constant-sized stabilizers are translations of one another.
  • Decoder approach: The decoder exploits BB codes’ equivalence to copies of the toric code by formalizing their shared global structure as code symmetries.
  • Decoder approach: The cylinder trick interprets matching edges as error counts on a generating set of BB logical operators, enabling a correction consistent with the matching graph.
  • Decoder limitations: Bare matching can fail for errors of weight w ≪ d/2 because large-support stabilizers permit low-weight incorrect paths and symmetry matching omits some syndrome information.
  • Decoder improvements: Over-matching, classical decoders, and belief propagation recover many low-weight failures, making the best variants competitive with state-of-the-art methods at reduced time complexity.

B. Code symmetries

A code symmetry is a stabilizer subset whose product is identity, forcing every physical error to violate an even number of its stabilizers. BB-code symmetries are obtained algebraically and support matching-based decoding through generating sets and subsymmetries.

  • Definition: A code symmetry is a subset of stabilizers whose product is the identity, so every physical error violates an even number of its stabilizers.
  • Construction: BB-code symmetries can be found by Gaussian elimination, whose final row-reduction combinations produce stabilizer sums that add to zero.
  • Construction: Symmetries form an Abelian group under addition modulo 2, so linear combinations of symmetries are also valid symmetries.
  • Gross-code example: The gross code has six linearly independent symmetries, with a generating set obtained from distinct translations of one symmetry.

C. Subsymmetries

Subsymmetries identify error configurations that must produce even stabilizer-violation parity, enabling BB-code syndrome checks and classical decoding strategies within the code’s toric-code equivalence.

  • A subsymmetry is defined relative to an error subset whose errors always create even-parity stabilizer violations on that subsymmetry.
  • For BB codes, separate subsymmetries target errors confined to L qubits or R qubits.
  • The ΣL construction is insensitive to L-qubit errors, so such errors violate an even number of specified stabilizers; its meta-stabilizer detects violations of the subsymmetry.
  • Translations of ΣR generate linearly independent subsymmetries, and an example shows R-only errors respecting each subsymmetry while an L-qubit error violates two of them.
  • The code’s local structure and syndromes correspond to copies of the toric code under a finite-depth local unitary mapping, supporting symmetry-based decoding.
  • Translation actions can permute anyon types, with finite orders Rx and Ry defining an unfrustrated Rx × Ry unit cell where translations act trivially on anyons.

III. DECODER

The decoder constructs symmetry-specific matching graphs from stabilizer violations, applies minimum-weight pairing, and supplements matching when certain BB codes produce low-weight decoding failures.

  • The symatch decoder matches violated stabilizers within code symmetries, then uses the cylinder trick to obtain corrections from matching results.
  • For some BB codes, symatch fails on low-weight errors, motivating overcomplete-symmetry consistency checks and subsymmetry-based classical decoders.
  • MWPM pairs an even set of highlighted syndrome vertices along selected graph edges while minimizing total path length.
  • A correction can be extracted from the matched edge subset, and matching may also be implemented with clustering or union-find methods.
  • The symmetry graph represents each symmetry stabilizer as a vertex and connects stabilizer pairs violated by individual bit-flip errors.
  • Errors violating many symmetry stabilizers are represented by a complete set of pairwise edges, preserving the even-defect structure needed for matching.
  • Belief propagation can reweight symmetry-graph edges using the complete syndrome, including stabilizers outside the selected symmetry.
  • Matching on a weighted symmetry graph returns a minimum-total-weight pairing of the highlighted syndrome vertices.

B. The cylinder trick

The cylinder trick extracts logical operators from code symmetries and interprets matching parity as the logical-error information needed to construct a correction, including on small lattices via doubling.

  • Applying the cylinder trick to a symmetry extracts an associated logical operator and interprets matching results to find a correction for it.
  • A symmetry is divided into stabilizers supported on two disjoint cylinders, U and V, whose widths are large compared with stabilizer support.
  • The associated operator factors into boundary-supported components P1 and P2 that are well separated when M/2 ≫ r.
  • For a nontrivial anyon symmetry, the separated components are nontrivial logical operators, so one component can serve as the extracted logical operator.
  • A decoder estimates commutators between the error and generating logical operators, forms an initial correction, and appends a logical operator to match those commutators.
  • Matching determines the logical commutator from the parity of matched edges crossing between U and V, with even or odd parity corresponding to commuting or anticommuting errors.
  • The method does not require errors to violate only two symmetry stabilizers; higher-weight violations can be handled by decomposing matching hyperedges into pairwise edges.
  • When small codes lack cylinders much wider than stabilizer support, the code is doubled or recursively enlarged, decoded there, and folded back to recover logical information on the original code.

4. The basic symatch decoder

The symatch decoder matches on code symmetries and uses the cylinder trick to infer corrections for a generating set of logical operators. Redundant matching, classical decoding, and belief propagation address failures caused by short symmetry-graph loops and can improve logical error rates.

  • Decoder construction: The symatch decoder matches on each code symmetry to determine values for pairs of horizontal and vertical logical operators.For K independent symmetries, the code has k = 2K independent logical operators, and the cylinder trick identifies the corresponding operators.
  • Decoder construction: The cylinder trick interprets matching edges as the number of errors supported on logical operators, enabling a correction consistent with the matching graph.The resulting correction is constructed from matching outcomes on the symmetry graphs.
  • Over-matching: Over-matching uses 2K −1 non-trivial symmetries and consistency conditions to identify incorrect matching results.For three symmetries, the matching bits obey b1 ⊕ b2 ⊕ b1+2 = 0; violations detect a matching failure, and simplex coding can correct up to K/2 matching failures.
  • Over-matching: Over-matching offers little advantage when matching failures are perfectly correlated across constructed symmetries, except near weight d/2 ambiguities.The two-toric-code example shows that a failure on one symmetry also fails on the combined symmetry with certainty.
  • Subset-error preprocessing: For errors confined to one qubit subset, subsymmetry checks can certify a valid correction supported entirely on that subset before applying a fast classical decoder.The decoder accepts the classical correction when its weight is less than d/2 and otherwise falls back to matching.
  • Benchmark results: Across gross, generalized toric, cyclic hypergraph-product, and directional codes, bare symatch is distance-preserving for some instances but can fail below d/2 on others.For cases with dΣ < d, simplex-symatch slightly improves scaling, while belief-propagation edge reweighting makes symatch competitive with other LDPC decoders.

A. Phenomenological noise

Under phenomenological noise, the decoder is extended to spacetime detector symmetries and shows trends mirroring code-capacity results. Exhaustive low-weight tests reveal substantial gains from preprocessing, while runtime remains unmeasured and implementation-dependent.

  • Phenomenological noise: Phenomenological decoding replaces stabilizers with detectors over time and generalizes the cylinder trick by tracking symmetry-associated logical operators.Bare symatch and belief-symatch show trends mirroring the code-capacity results.
  • Low-weight failures: 20%-80% fewer low-weight errors cause failures with L/R preprocessing, outperforming BPOSD-CS10 in the tested regime.The comparison concerns exhaustively enumerated low-weight code-capacity errors on the gross code.
  • Low-weight failures: No listed decoder corrects all weight-5 = ⌊d/2⌋ errors in the exhaustive gross-code search.This bound persists despite the reported preprocessing and belief-propagation improvements.
  • Low-weight failures: Vertical logicals have consistently lower failure rates than horizontal logicals for symatch decoders.The authors attribute this asymmetry to the gross code’s small N dimension, which makes vertical torus wrapping easier.
  • Runtime overhead: Runtime overhead is not analyzed because current implementations serialize matching subroutines, use brute-force simplex decoding, and are mostly Python.The brute-force simplex step scales exponentially in K through the number of low-weight solutions.
  • Conclusion: The proposed decoder is reported to have competitive logical error rates and to avoid time-intensive ordered-statistics decoding used by BP-OSD.The conclusion presents this as an advantage for efficient practical implementation, while future work calls for parallelized runtime comparisons.

Appendix A: Bivariate bicycle codes in the check-matrix formalism

Appendix A formulates bivariate bicycle codes through stabilizers, check matrices, Pauli errors, and syndromes. It then extracts code symmetries by row-reducing an over-complete check matrix and reading null rows through the associated row operations.

  • Code formalism: Bivariate bicycle codes are CSS codes whose stabilizers use exclusively X or Z operators, and their check matrices separate these stabilizer types.The matrices H_X and H_Z must satisfy the CSS commutation condition.
  • Check matrices: A check matrix is a 2n×m binary matrix whose rows define stabilizer generators, with m ≥ n−k for n qubits and k encoded logical qubits.Each generator row can be partitioned into two n-component vectors describing its Pauli support.
  • Lattice representation: BB check matrices use cyclic-shift blocks to represent translations on a periodic M×N lattice.The cyclic-shift construction uses tensor products of one-dimensional shifts and identifies left and right qubits with horizontal and vertical lattice edges.
  • Lattice representation: The first and second MN columns encode stabilizer support on left and right qubits, respectively, while commuting X- and Z-check matrices define the code.The left and right qubits correspond to horizontal and vertical lattice edges.
  • Error syndrome and noise model: A Pauli error is represented by a binary vector containing its X and Z components, and the check matrix maps it to a syndrome.Syndrome entry s_j is one exactly when the j-th stabilizer generator is violated.
  • Finding symmetries: Gaussian elimination on an over-complete check matrix produces zero rows whose associated rows in Γ identify stabilizer subsets forming symmetries.For each all-zero row of the row-reduced matrix, the corresponding Γ row specifies which original generators belong to the symmetry.

Appendix B: Examples of code symmetries

The appendix constructs additional BB-code symmetries from translations and polynomial relations. These symmetries can be tiled across finite tori and include structures resembling those of HGP and color codes.

  • BB144 symmetries: The BB144 code has a 36-check generating symmetry whose translations generate further symmetry sets.These translated symmetries provide the starting point for constructing additional combinations.
  • BB144 symmetries: Linear combinations of the translated 36-check symmetries produce 32-check and 48-check symmetries resembling HGP and color-code structures.The 32-check and 48-check forms are used during simplex over-matching.
  • Infinite-code construction: For an infinite BB code, polynomial expressions generate Z-check symmetries on tori with periodic conditions x^Lx = 1 and y^Ly = 1.The construction assumes even translation orders for the relevant polynomial factors.
  • Infinite-code construction: The resulting symmetries are indexed by lattice translations and can be tiled over Lx × Ly regions to cover the infinite plane.This provides a systematic way to place the generated symmetry patterns across finite regions.

Appendix C: Toric code equivalence and topological defect networks

The appendix explains two-dimensional translation-invariant stabilizer codes through symmetry-enriched copies of the toric code and topological defect networks. It develops string-operator and commutation-matrix procedures that identify the equivalent toric-code copies and their translation structure.

  • Toric-code equivalence: Any 2DTI stabilizer-code family is equivalent to K copies of the toric code enriched by a Z×Z translation action.The enrichment accounts for system-size-dependent logical-qubit behavior beyond a fixed collection of independent toric codes.
  • Topological defect networks: The translation-enriched description forms a topological defect network whose unit-cell boundaries carry invertible domain walls coupling toric-code copies.Translations can permute anyons across these domain walls, producing the network representation.
  • Ground-space degeneracy: On an unfrustrated Rx × Ry torus, effective boundary conditions are untwisted and the code has 2K logical qubits, the maximum for any system size.The degeneracy pattern repeats after translation orders Rx and Ry.
  • Frustrated tori: On frustrated tori, boundary conditions relate multiple anyon types, so matching distances must account for corrections that pass through those boundaries.Local symmetry-satisfying neutral clusters are locally correctable, whereas more general neutral clusters may require boundary-crossing corrections.
  • Equivalence limitations: The toric-code equivalence may require a local unitary circuit of large constant depth before deformable stringlike logical operators become apparent.Some symmetry and logical-operator information can nevertheless be applied directly without performing that circuit.
  • Extensions and invariants: The same framework discusses boundary condensation, invariant-based copy counting, and translation actions extracted from string-operator braiding relations.The lattice S-matrix invariant is presented as a reliable alternative when topological entanglement entropy may contain spurious contributions.
  • String operators: The string-operator construction uses restricted check matrices on horizontal and vertical ribbons, with CSS assumptions assigning X type horizontally and Z type vertically.The resulting basis separates nontrivial string segments from stabilizer operators.
  • String operators: The number K of toric-code copies is obtained by diagonalizing the commutation matrix of horizontal and vertical string segments.Binary Smith normal form yields a diagonal identity block whose length equals the number of independent anticommuting string-segment pairs.

2. Translation action

Translation acts on string operators through matrices P_x and P_y, whose orders determine the minimal unfrustrated dimensions of the code. This structure makes finite tori equivalent to toric-code copies with twisted boundary conditions and supplies the string segments used by the decoder.

  • Translation action: Diagonalizing shifted commutation matrices determines the anyon-permutation actions P_x and P_y of horizontal and vertical translations.P_x is obtained by shifting vertical string operators horizontally; P_y is computed analogously.
  • Translation action: A torus of dimensions L_x × L_y is equivalent to n toric-code copies with boundary twists P_x^Lx and P_y^Ly.The twists correspond to anyons traversing the horizontal and vertical cycles.
  • Translation action: The orders R_x and R_y of P_x and P_y determine the width and height of the minimal unfrustrated unit cell.
  • Translation action: For equal check and qubit counts per unit cell, the number of logical qubits on a finite torus equals the number of independent global symmetries.Growing distance excludes local symmetries fully contained in constant-sized regions.
  • Translation action: The cylinder trick extracts fundamental string segments from unfrustrated symmetries, which are then used to construct decoupled toric-code symmetries.The construction uses an infinite cylinder of width R_x and diagonalizes string-segment commutation matrices.
  • Translation action: On frustrated tori, matching weights reflect the shortest operators connecting syndrome pairs rather than their geometric separation in the Tanner graph.

Appendix E: Correcting matching errors with a simplex encoding

The appendix treats matching outputs as potentially corrupted bits and uses algebraic relations among cylinder-derived logical operators to construct simplex-code checks. These checks identify inconsistent matching results, with a family of constraints whose support and validity are explicitly characterized.

  • Matching-result encoding: The cylinder trick maps each symmetry to a logical operator and each matching result b[v] to an estimated logical-operator bit.
  • Matching-result encoding: Relations among cylinder-derived logical operators induce modulo-2 constraints on the corresponding matching-result bits.
  • Check construction: An odd number of erroneous matching-result bits violates a check, allowing the checks to identify errors in the encoded results.
  • Check construction: The global check includes every nonzero vector, relying on the modulo-2 identity that the sum of vectors in Z_M is zero for M ≥ 2.
  • Check construction: Fixing up to K − 2 vector elements produces valid constraint checks because at least two free elements cause the relevant modulo-2 sums to vanish.
  • Check construction: Except for the all-zero constraint check, every check contains an even number of bits, whereas C[{0}] has odd support because the trivial bit is excluded.

2. Correcting the simplex code

The simplex correction procedure first constructs a valid codeword by satisfying checks in descending constraint weight, then searches equivalent codewords for a least-weight correction. The ordering preserves previously corrected checks while the final search explores 2^K alternatives.

  • Correction procedure: The matching-error bits form a simplex code with parameters [2^K−1, K, 2^K−1].
  • Correction procedure: An initial correction sets a bit whenever its check is violated, processing checks from constraint weight K − 2 down to 1.
  • Correction procedure: Descending constraint weight ensures each correction changes the targeted check without altering checks corrected earlier.
  • Correction procedure: If the all-zero check remains violated, flipping all currently assigned correction bits changes that check alone and satisfies the full check set.
  • Correction procedure: The procedure toggles among codewords by flipping correction bits indexed by sets with one fixed vector element, yielding 2^K candidate corrections.

Appendix F: Soft information

The soft-information analysis combines belief propagation, over-matching, and information passed between symmetry-specific matching subroutines. BP can leave only weight-5 errors for secondary correction after more than 500 iterations in BB144, while correlated symatching improves over unweighted simplex-symatching but remains less accurate than BP.

  • Belief propagation: Belief propagation updates error priors through Tanner-graph message passing and may converge incorrectly depending on its internal hyperparameters.
  • Belief propagation: For BB144, using over 500 BP iterations leaves only weight-5 errors for the secondary correction subroutine.
  • Correlated symatching: The authors characterize information passing between matching subroutines for bit-flip noise as a rudimentary exploration requiring further improvement.
  • Correlated symatching: The correlated strategy performs an initial matching round, suppresses corresponding edge weights across other symmetries, then rematches and applies simplex correction.
  • Correlated symatching: Correlated symatching improves over unweighted simplex-symatching, but BP provides greater overall accuracy on the gross code.
Loading 2602.22770v2…