Source-linked AI summary
Generalized matching decoders for 2D topological translationally-invariant codes
Shi Jie Samuel Tan, Ian Gill, Eric Huang, Pengyu Liu, Chen Zhao, Hossein Dehghani, Aleksander Kubica, Hengyun Zhou, Arpit Dua
TL;DR
The paper asks whether the toric code’s efficient graph-matching decoding can extend to general 2D TTI codes, whose syndrome patterns can require hypergraph matching. It coarse-grains TTI codes into toric-code excitations, introduces two graph-matching decoders, and proves correction guarantees and non-zero thresholds while studying BB-code performance. The results support graph matching as a viable approach for BB and other TTI codes, although the demonstrated setting excludes measurement-error noise and has finite-size constraints.
Problem
General TTI codes can produce multi-defect syndrome patterns requiring generally NP-hard hypergraph matching, despite their equivalence to multiple toric codes and the practical need for efficient decoders.
Method
The decoders coarse-grain TTI codes into effective toric-code excitations and remove them with graph matching, using layer decoupling or local cell matching within coarse-grained unit cells.
Results
Both decoders correct errors up to a constant-fraction bound and yield non-zero code-capacity thresholds under i.i.d. bit-flip or phase-flip noise, with complexity tied to MWPM on the original lattice dimensions.
Takeaways & Limitations
Graph-matching decoding is a viable approach for practically relevant BB codes and other 2D TTI codes, with analytical guarantees and numerical evidence of competitive performance.
Takeaways & Limitations
The layer-decoupling decoder requires each toric-code sector to have distance at least 3 and its effective error rate below the toric-code threshold; the proposed approach also leaves measurement-error noise for future work.
Abstract
from arXiv · showhide
Two-dimensional topological translationally-invariant (TTI) quantum codes, such as the toric code (TC) and bivariate bicycle (BB) codes, are promising candidates for fault-tolerant quantum computation. For such codes to be practically relevant, their decoders must successfully correct the most likely errors while remaining computationally efficient. For the TC, graph-matching decoders satisfy both requirements and, additionally, admit provable performance guarantees. Given the equivalence between TTI codes and (multiple copies of) the TC, one may then ask whether TTI codes also admit analogous graph-matching decoders. In this work, we develop a graph-matching approach to decoding general TTI codes. Intuitively, our approach coarse-grains the TTI code to obtain an effective description of the syndrome in terms of TC excitations, which can then be removed using graph-matching techniques. We prove that our decoders correct errors of weight up to a constant fraction of the code distance and achieve non-zero code-capacity thresholds. We further numerically study a variant optimized for practically relevant BB codes and observe performance comparable to that of the belief propagation with ordered statistics decoder. Our results indicate that graph-matching decoders are a viable approach to decoding BB codes and other TTI codes.
1 Introduction
The paper motivates efficient decoders for 2D TTI quantum codes by leveraging their equivalence to multiple toric codes. It develops graph-matching decoders that coarse-grain general TTI codes and studies their practical relevance for BB codes.
- 2D TTI codes place qubits on a periodic square lattice with local parity checks whose range stays fixed as lattice size and code distance increase.
- Decoders must correct likely errors efficiently enough to avoid classical processing falling behind syndrome extraction.
- Color-code graph-matching decoders exploit unitary equivalence to the toric code, motivating the same question for other TTI codes.
- The paper develops graph-matching decoders for general TTI codes by combining polynomial representations, toric-code equivalence, and syndrome coarse-graining.
- The work includes analytical guarantees, practical BB-code simulations, and a paper structure covering two decoder constructions and their complexity and performance.
2 Overview
General 2D TTI codes pose a harder decoding problem than the toric code because single-qubit errors can create multiple excitations, leading to NP-hard hypergraph matching. This work uses the TTI–toric-code equivalence to coarse-grain syndromes into matching-decodable structures and establishes performance guarantees for two decoder constructions.
- Decoding problem: A decoder maps a measured syndrome to a Pauli correction, with practical designs needing to handle likely errors efficiently.The overview focuses on Z-error decoding for CSS codes, with X-error decoding analogous.
- Decoding problem: Toric-code errors create paired excitations, enabling efficient minimum-weight perfect matching on a weighted graph.Graph edges represent minimum-length strings connecting excitation endpoints.
- Decoding problem: General TTI codes can produce more than two excitations from one qubit error, turning decoding into generally NP-hard minimum-weight hypergraph matching.This breaks the simplest toric-code graph-matching formulation.
- Structural basis: The decoupling theorem states that, after coarse-graining, a topologically ordered 2D TTI code can be transformed by a constant-depth locality-preserving Clifford circuit into toric-code copies and trivial qubits.This supplies the structural basis for extracting toric-code-like decoding problems.
- Decoder approach: The proposed decoders coarse-grain TTI syndromes into toric-code-like sectors, decode those sectors by matching, and lift the resulting corrections back to physical qubits.The layer-decoupling decoder uses an algebraic change of basis, while the cell-matching decoder uses local transport within constant-size unit cells.
- Results and scope: Both decoders correct errors up to a constant-fraction bound tied to the coarse distance and yield non-zero code-capacity thresholds with MWPM-based asymptotic time complexity.The practical layer-decoupling performance depends on the chosen decoupling map, while MWPM-style primitives remain a concrete basis for more realistic noise models.
3 Preliminaries
The paper introduces the algebraic and coding-theoretic framework for 2D TTI codes, representing lattice translations and local stabilizer structure with bivariate Laurent polynomials. It also reviews CSS codes, chain complexes, distances, and parity-check matrices used throughout the decoding analysis.
- A CSS code separates X- and Z-type errors, checks, and distances through binary parity-check matrices.
- Quantum CSS codes are represented by three-term chain complexes whose boundary maps encode stabilizer checks and whose homology and cohomology capture logical operators and code distances.
- Laurent polynomials over F2[𝑥±1, 𝑦±1] represent finite translation-invariant stencils, with monomials 𝑥^i𝑦^j labeling lattice sites.
- 2D TTI codes place qubits on a periodic two-dimensional lattice with local, translationally invariant stabilizer checks.
- The Laurent-polynomial parity-check matrix uses an antipode operation that reverses translation directions when taking the dagger.
4 The layer-decoupling decoder for 2D TTI codes
The layer-decoupling decoder coarse-grains a 2D TTI code and transforms it into independent toric-code sectors plus trivial product states, decodes each sector by matching, and lifts the corrections back. Under stated finite-size conditions, the construction has correctness guarantees and matching-dominated complexity.
- Decoupling produces independent toric-code copies and trivial product states, with invertible transformations represented by polynomial matrices U and V.
- The decoder maps the measured syndrome into several toric-code sector syndromes, decodes each sector with matching, and lifts the sector corrections to the original code.
- The lifted correction is valid exactly when each sector correction satisfies the corresponding sector decoding condition.
- The decoder corrects adversarial errors up to a bound involving the toric-code distance and the maximum number of qubits disentangled with one original qubit.
- For local stochastic noise, decoding succeeds when w_max·p_max is below the corresponding toric-code matching threshold.
- The finite-size construction assumes lattice dimensions divisible by the coarse-graining parameter b, and its effective distance is reduced by a factor of b.
- The total runtime is dominated by decoding the toric-code sectors after the decoupling steps.
5 The cell-matching decoder for 2D TTI Codes
The cell-matching decoder locally coarse-grains 2D TTI codes into TC-like excitation sectors, matches the resulting pairs, and lifts the corrections back to the original code. The analysis establishes correctness under bounded-weight errors, stochastic thresholds, and matching-dominated runtime.
- Decoder construction: The cell-matching decoder flushes syndrome information into fixed basis subcells, producing point-like excitation pairs that can be matched on several TC-like coarse lattices.Local transport operators move excitations within each unit cell into the basis subcell; coarse matching edges lift to a physical correction.
- Unit cell construction: The decoder uses a constant-size coarse-graining determined by the code, with periodic lattices decomposed into b × b unit cells and a c × c basis subcell.The basis subcell contains a sparse basis of excitation types represented in the cokernel of the coarse-grained parity-check matrix.
- Decoder construction: Global physical syndromes yield even-cardinality excitation sets for every type, satisfying the parity condition required for matching on a torus.The even-parity constraint follows from the linearity of the flushing and coefficient-extraction maps.
- Correctness: Any decoder-induced logical failure must arise from a non-trivial homology class in at least one coarse excitation sector.If every sector residual is contractible, the lifted residual error is a Z-type stabilizer; the proof uses the lifting map and sector homology.
- Correctness: The decoder corrects adversarial errors up to a theorem-specified fraction of the code distance and, below the TC matching threshold, has logical-failure probability at most exp(−Ω(d_min)).Here d_min = d_TC = min{L_x/b, L_y/b}; the stochastic bound remains exponential after a union bound over the constant number of sectors.
- Complexity: The runtime is dominated by matching and scales as O(MATCHING(L_xL_y)) after summing over the excitation sectors.The number of sectors is r := dim(coker H), while the stated leading cost is matching over the lattice area.
6 Adapting the cell-matching decoder for small and intermediate code sizes
The section adapts cell-matching decoding to small and intermediate TTI code sizes, addressing coarse-graining failures in BB-code examples with specialized constructions. It reports heuristic numerical performance and implementation costs for these adaptations.
- Motivation: The standard gross and 24 × 24 gross lattices create distinct coarse-graining problems: unit-cell degeneration for the former and d_TC = 2 for the latter.The 24 × 24 construction is therefore insufficient to correct single-qubit errors through the induced toric-code matching instance alone.
- Adapted decoders: Two related adaptations target small lattices such as gross and two-gross codes and intermediate lattices such as the 24 × 24 gross code.The constructions are presented for BB examples but apply to general small and intermediate 2D TTI codes.
- Shared machinery: The method identifies syndrome equivalence classes using a chosen coker H basis, translation scales, short strings, and linear-system-based basis decomposition.Basis elements with smaller translation scales are preferred because they increase the effective distance of the matching graphs.
- Matching construction: Matching graphs group observed checks according to active basis components, while syndrome shifts can change the resulting graphs and matching outcomes without changing the decoding problem.The final correction uses local cancellation or chains of short strings between unit cells, depending on the matched pair locations.
- Size-dependent behavior: The small-size procedure succeeds because few error clusters can be identified, whereas the same strategy becomes ineffective for intermediate lattices as cluster counts increase.For intermediate codes, short-string pairing can still produce corrections without identifying every explicit error cluster.
- Numerical results and limitations: Matching performs relatively close to BP-OSD for the gross code, while the implementation currently lags BP-OSD in speed because of repeated decoding, cluster computation, and Python execution.The authors characterize the decoders as proof-of-concept adaptations and leave runtime optimization to future work.
7 Conclusions and future directions
The paper develops two graph-matching decoders for 2D TTI codes and reports analytical guarantees plus numerical evidence on BB codes. It identifies competitive performance and several directions for extending the approach.
- The work introduces layer-decoupling and cell-matching decoders that exploit the equivalence between 2D TTI codes and multiple toric codes.Cell matching locally flushes excitations within coarse-grained unit cells to better respect noise locality and avoid correlated errors.
- The authors establish analytical performance guarantees and numerically study practically relevant BB-code instances, including the gross code.
- The results indicate that graph-matching decoding can be competitive with belief-propagation-based decoders.
- Future work includes optimizing matching edge weights, incorporating measurement errors, and extending the approach to open-boundary lattices.The proposed optimization includes hybrid BP–graph-matching decoders, while noise extensions target phenomenological and circuit-level settings.
A Bivariate bicycle codes
Bivariate bicycle codes are a polynomially defined class of 2D TTI codes, represented on two periodic lattices and encompassing important examples such as the toric code. Their stabilizers, syndromes, and logical operators admit an algebraic module description.
- Code definition: BB codes are defined from two ℓ×m lattices using bivariate polynomials and are a specific class of 2D TTI codes.The paper focuses on BB codes embeddable in a 2D toric layout; toric and color codes can be viewed as BB-code instances.
- Polynomial representation: The qubits correspond to elements of R = F2[x^±1, y^±1]/⟨x^ℓ−1, y^m−1⟩, with stabilizers specified by a(x,y) and b(x,y).The relations impose periodicity through x^ℓ = 1 and y^m = 1.
- Stabilizer structure: The X- and Z-stabilizer groups are R-modules generated by (a,b) and (b*,a*), respectively.Each module contains polynomial multiples of its corresponding generator pair.
- Syndromes: A Z-error configuration represented by (f,g) produces an X syndrome described through the polynomial-check formalism and its associated ideal.The analogous Z syndrome for X errors is also represented by a polynomial ideal.
- Logical operators: Logical operators are characterized as quotient modules formed from syzygies modulo the corresponding stabilizer module.The paper gives separate quotient-module descriptions for Z and X logical operators.
- Example: The toric code is recovered as a BB-code special case with a(x,y) = 1 + x and b(x,y) = 1 + y.
B An algorithmic approach to decoupling 2D TTI codes
This section presents an algorithmic procedure for decoupling 2D TTI codes into independent toric-code copies and a trivial product state. The procedure uses coarse-graining and valid symplectic transformations to make the decoupling explicit.
- The section develops an algorithmic approach that decouples 2D TTI codes into independent copies of the toric code and a trivial product state.
- Decoupling treats two-dimensional topological codes as equivalent up to Clifford gates, simplifying their analysis.Bombín and Haah introduced the underlying decoupling perspective, while Haah provided an algorithmic coarse-graining proof for arbitrary 2D topological CSS codes with topological order.
- The section reviews Clifford operations, introduces coarse-graining, and identifies symplectic transformations suitable for decoupling.
- A modified decoupling algorithm is presented and illustrated with an example of the decoupling process.
B.1 Clifford Operations and Symplectic Group
Clifford operations preserve stabilizer-code structure and can be represented by symplectic matrices over F2. The section connects elementary Clifford gates to column operations on CSS-code matrices.
- Clifford gates preserve the structure of stabilizer codes and are represented by elements of Sp(2n,F2).The symplectic form encodes Pauli commutation relations.
- The symplectic group consists of 2n×2n matrices over F2 that preserve the symplectic form.It is a subgroup of the general linear group GL(2n,F2).
- Elementary symplectic operations correspond to column operations on the binary symplectic matrix of a CSS code.
- A CNOT adds specified columns across the matrix partitions, while a Hadamard swaps paired columns and a Phase gate adds one paired column to another.
B.2 Coarse-graining
Coarse-graining replaces the bivariate Laurent-polynomial ring with a smaller ring whose variables represent super-cell translations. A faithful matrix representation of the coarse-grained polynomials makes the code Hamiltonian’s interactions more transparent.
- Ring representation: The coarse-grained lattice groups multiple cells into a single super-cell, simplifying the analysis of the two-dimensional code.This grouping is motivated by the simpler interaction structure available for the toric code.
- Ring representation: Coarse-graining replaces R = F2[x^±1, y^±1] with R′ = F2[x^±b, y^±b] = F2[x′^±1, y′^±1], where b determines the super-cell size.Larger b produces larger super-cells and a more coarse-grained code.
- Matrix construction: A basis of b^2 monomials, ordered by powers of x and y, represents the degrees of freedom within each coarse-grained super-cell.The basis is explicitly listed as monomials x^i y^j with 0 ≤ i,j < b.
- Matrix construction: The generator matrices implement ordered x- and y-shifts of this basis, with boundary-crossing shifts represented by x′ and y′.The x and y actions are given separately by the displayed basis mappings.
- Matrix construction: Polynomial matrices are constructed from these generator matrices; for example, 1 + y + y^2 can be represented explicitly when b = 2.This faithful representation clarifies the interactions of the code Hamiltonian on the coarse-grained lattice.
B.3 Local Disentanglement and Stabilizer Relabeling via Symplectic Transformations
Symplectic row and column operations on the coarse-grained parity-check matrix correspond to local Clifford transformations, translations, CNOT gates, and stabilizer relabelings. These operations are used to decouple the code into toric-code copies and a trivial product state.
- Purpose: The transformations aim to decouple the coarse-grained code into independent copies of the toric code and a trivial product state.They perform local disentanglement and stabilizer relabeling on super-cells.
- Column operations: Column operations correspond to local Clifford transformations on physical qubits in the coarse-grained lattice.Because the matrix is symplectic, paired columns must be transformed together to preserve the symplectic form.
- Column operations: Swapping paired columns physically swaps corresponding qubits within every super-cell.The paired swap preserves the symplectic representation.
- Column operations: Multiplying a column by x′^j y′^k and its symplectic partner by x′^-j y′^-k translates the associated qubits across super-cells.The translation is by -j horizontal and -k vertical super-cell steps.
- Column operations: Adding one column to another, together with the required paired operation, implements a physical CNOT between qubits in each super-cell.The order of addition reflects how X and Z errors propagate through the CNOT.
- Row operations: Row swaps, monomial multiplication, and row additions relabel stabilizer checks without changing the stabilizer group.These are the valid row operations on the coarse-grained parity-check matrix.
B.4 Setting up for the Decoupling Algorithm
The decoupling algorithm requires sufficient structural conditions on the code, which are formulated using standard quantum error-correction language and related to prior abstract treatments.
- Decoupling conditions: The subsection states sufficient conditions for the decoupling algorithm and connects them to formulations by Haah and Bombín.The conditions are presented in standard quantum error-correction terminology.
B.4.1 Topological Order Condition
The topological-order setup uses the parity-check matrix, its associated chain complex, and the cokernel’s torsion structure to characterize logical operators and point-like excitations. The annihilator ideal captures which translations can move these excitations.
- Topological-order condition: Topological order requires the parity-check matrix to satisfy a condition in the infinite-lattice limit.This condition is expressed using H over R = F2[x^±1, y^±1].
- Parity-check representation: The maps H_X and H_Z send Pauli errors to violated stabilizer checks and are bundled into the parity-check, or excitation, map H.The parameters t and q count stabilizer-check descriptions and qubits per lattice site.
- Excitation structure: The cokernel of H represents excitation configurations modulo those attainable from Pauli errors.Physically equivalent excitation patterns differ by an element of im H.
- Homological formulation: The chain-complex condition ker H = im H† is equivalent to trivial first homology and, in the stated setting, exactness of the chain complex.The chain groups associate C0, C1, and C2 with X checks, qubits, and Z checks.
- Homological formulation: Exactness means no finite-support Pauli product forms a homologically nontrivial cycle on the infinite lattice, ensuring macroscopically large code distance.The passage states that coarse-graining replaces the base ring with R′ = F2[x^±b, y^±b].
- Excitation structure: The torsion submodule of coker H corresponds to point-like topological excitations that can be moved by finite-support Pauli operators.These excitation classes are invariant under Clifford transformations, stabilizer relabelings, and translations.
- Excitation mobility: The annihilator ideal consists of polynomials that kill every excitation class and encodes the mobility of point-like excitations.The associated string operators translate point charges along the x or y direction.
B.4.4 Sufficient Conditions for Decoupling
A suitable coarse-grained parity-check matrix enables local transformations that decouple a two-dimensional LTI CSS code into toric-code copies and a trivial product state. The number of toric-code copies is determined by the torsion submodule of the coarse-grained matrix’s cokernel.
- The decoupling conditions require a parity-check matrix H satisfying ker HΩ = im H† over F2[x±1, y±1].
- A transformed matrix H′ preserves im H†, satisfies ker H′Ω = im H′†, and has ker H′† = 0.
- The coarse-grained ring is R′ = F2[x±b, y±b], where b defines the super-cell translation scale.
- The annihilator ideal of coker H′ is generated by x^b−1 and y^b−1, enabling point-like excitations to move between corresponding super-cells.
- Local symplectic transformations disentangle H′ and relabel stabilizers into toric-code blocks plus a trivial product-state block.
- The number of independent toric-code copies is 1/2 dimF2 𝒯(coker H′), because each copy has two point-like excitation types, e and m.
C Layer-decoupling decoder lemmas and proofs
The layer-decoupling construction is formalized through chain maps and projections. These maps preserve the relevant differential relations while isolating individual toric-code and auxiliary summands.
- The triple φ = (φ2, φ1, φ0) defines a chain map between the original and decoupled chain complexes.
- The projections π(i) and πA are chain maps because they project onto summands of a direct-sum chain complex.
- The resulting corollary composes φ with the projections and differentials to establish the corresponding chain-map identities for the auxiliary sector.
D Computing short strings
Short strings are computed by partitioning the code into coarse rectangles, constructing local transfer matrices, and checking that candidate vectors form a quotient basis. Fixed transfer-matrix subspaces identify translationally repeated syndrome patterns.
- For the 24×24 gross code, monomial labels are partitioned into disjoint ℓ′×m′ rectangles on a coarse lattice.
- The gross-code construction yields ℓ′ = 3 = m′.
- Syndrome patterns in each rectangle are represented as vectors over F2^9 using a fixed ordering of its nine monomials.
- For each single-monomial excitation, a local error representative is searched for and assembled into a horizontal transfer matrix Ax.
- Vertical transfer matrices are constructed analogously, while eigenvectors of transfer matrices identify additional short strings; Ax and Ay need not coincide.
- Candidate quotient-basis elements are tested by appending their coefficient vectors to the ideal matrix and checking spanning and independence conditions.