A matching decoder for bivariate bicycle codes

Motivation

• Non-local LDPC quantum error-correcting codes encode substantial quantum information into relatively few physical qubits, motivating efficient decoding algorithms.Source: §I · p. 1

Bivariate bicycle codes

• Bivariate bicycle codes are translationally invariant lattice codes whose constant-sized stabilizers are translations of one another.Source: §I · p. 1

Decoder approach

• The decoder exploits BB codes’ equivalence to copies of the toric code by formalizing their shared global structure as code symmetries.Source: §I · p. 1
• 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.Source: §I · p. 1

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.Source: §I · p. 1

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.Source: §I · p. 1, Figure 1 · p. 2

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.Source: B. Code symmetries · p. 4

Construction

• BB-code symmetries can be found by Gaussian elimination, whose final row-reduction combinations produce stabilizer sums that add to zero.Source: B. Code symmetries · p. 4
• Symmetries form an Abelian group under addition modulo 2, so linear combinations of symmetries are also valid symmetries.Source: B. Code symmetries · p. 4

Gross-code example

• The gross code has six linearly independent symmetries, with a generating set obtained from distinct translations of one symmetry.Source: B. Code symmetries · p. 5

• A subsymmetry is defined relative to an error subset whose errors always create even-parity stabilizer violations on that subsymmetry.Source: C. Subsymmetries · p. 5
• For BB codes, separate subsymmetries target errors confined to L qubits or R qubits.Source: C. Subsymmetries · p. 5
• 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.Source: C. Subsymmetries · p. 5
• 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.Source: C. Subsymmetries · p. 5
• 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.Source: D. Equivalence between codes on a… · p. 5
• 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.Source: D. Equivalence between codes on a… · p. 6

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

• Applying the cylinder trick to a symmetry extracts an associated logical operator and interprets matching results to find a correction for it.Source: B. The cylinder trick · p. 7
• A symmetry is divided into stabilizers supported on two disjoint cylinders, U and V, whose widths are large compared with stabilizer support.Source: §1 · p. 7
• The associated operator factors into boundary-supported components P1 and P2 that are well separated when M/2 ≫ r.Source: §1 · pp. 7–8
• For a nontrivial anyon symmetry, the separated components are nontrivial logical operators, so one component can serve as the extracted logical operator.Source: §1 · p. 8
• A decoder estimates commutators between the error and generating logical operators, forms an initial correction, and appends a logical operator to match those commutators.Source: §2 · p. 8
• 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.Source: §2 · p. 8
• 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.Source: §2 · p. 8
• 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.Source: §3 · p. 8

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.Source: §4 · pp. 8–9
• 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.Source: §4 · p. 9

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.Source: C. Over-matching: the simplex-symatch… · p. 9
• 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.Source: C. Over-matching: the simplex-symatch… · p. 9

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.Source: D. Identifying L- and R-only errors… · pp. 9–10

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.Source: §IV · p. 10

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.Source: A. Phenomenological noise · pp. 10–11

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.Source: B. Exhaustive search for low-weight… · p. 11
• 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.Source: B. Exhaustive search for low-weight… · p. 11
• 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.Source: B. Exhaustive search for low-weight… · p. 11

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.Source: C. A comment on runtime overhead · p. 11

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.Source: §V · p. 11, C. A comment on runtime overhead · p. 11

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.Source: Appendix A · p. 15

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.Source: Appendix A · p. 15

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.Source: Appendix A · p. 15
• 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.Source: Appendix A · p. 15

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.Source: §1 · pp. 15–16

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.Source: §2 · p. 16

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.Source: Appendix B · p. 16
• 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.Source: Appendix B · p. 16

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.Source: §1 · p. 16
• 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.Source: §1 · p. 16

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.Source: Appendix C · pp. 16–17

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.Source: Appendix C · p. 17, Figure 10 · p. 17

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.Source: Appendix C · pp. 17–18

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.Source: Appendix C · p. 18

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.Source: Appendix C · p. 18

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.Source: Appendix C · p. 18, Appendix D · p. 18, §1 · p. 19

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.Source: Figure 11 · p. 18, Appendix D · p. 18, §1 · p. 19
• 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.Source: §1 · p. 19

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.Source: §2 · p. 19
• 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.Source: §2 · p. 19
• The orders R_x and R_y of P_x and P_y determine the width and height of the minimal unfrustrated unit cell.Source: §2 · p. 19
• 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.Source: §3 · p. 19
• 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.Source: §3 · p. 20
• On frustrated tori, matching weights reflect the shortest operators connecting syndrome pairs rather than their geometric separation in the Tanner graph.Source: §3 · p. 20

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.Source: §1 · p. 20
• Relations among cylinder-derived logical operators induce modulo-2 constraints on the corresponding matching-result bits.Source: §1 · pp. 20–21

Check construction

• An odd number of erroneous matching-result bits violates a check, allowing the checks to identify errors in the encoded results.Source: §1 · p. 21
• 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.Source: §1 · p. 21
• 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.Source: §1 · p. 21
• 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.Source: §1 · p. 21

Correction procedure

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

Belief propagation

• Belief propagation updates error priors through Tanner-graph message passing and may converge incorrectly depending on its internal hyperparameters.Source: §1 · pp. 22–23
• For BB144, using over 500 BP iterations leaves only weight-5 errors for the secondary correction subroutine.Source: §1 · p. 23

Correlated symatching

• The authors characterize information passing between matching subroutines for bit-flip noise as a rudimentary exploration requiring further improvement.Source: §2 · p. 23
• The correlated strategy performs an initial matching round, suppresses corresponding edge weights across other symmetries, then rematches and applies simplex correction.Source: §2 · p. 23
• Correlated symatching improves over unweighted simplex-symatching, but BP provides greater overall accuracy on the gross code.Source: §2 · p. 23