Topological quantum codes are favored because they allow suitable qubit layouts for practical implementation. An N-qubit topological code can be decoded by minimum-weight perfect matching (MWPM) with complexity O(poly(N)). Recently it is shown that various quantum codes, including topological codes, can be decoded by an adapted belief propagation with memory effects (denoted MBP) with complexity almost linear in N. In this paper, we show that various two-dimensional topological codes, CSS or non-CSS, regardless of the layout, can be decoded by MBP, including color codes and a family of twisted XZZX codes. We will comprehensively compare these codes in terms of code efficiency and decoding performance, assuming perfect error syndromes.
Topological quantum codes are favored because they allow suitable qubit layouts for practical implementation. An N-qubit topological code can be decoded by minimum-weight perfect matching (MWPM) with complexity O(poly(N)). Recently it is shown that various quantum codes, including topological codes, can be decoded by an adapted belief propagation with memory effects (denoted MBP) with complexity almost linear in N. In this paper, we show that various two-dimensional topological codes, CSS or non-CSS, regardless of the layout, can be decoded by MBP, including color codes and a family of twisted XZZX codes. We will comprehensively compare these codes in terms of code efficiency and decoding performance, assuming perfect error syndromes.
Quantum error correction (QEC) is critical for scalable fault-tolerant quantum computing. Topological codes, such as the toric code, offer hardware-efficient architectures but their Tanner graphs contain many girth-4 cycles that degrade the performance of belief-propagation (BP) decoding. For this reason, BP decoding is typically followed by a more complex second stage decoder such as minimum-weight perfect matching. These combined decoders achieve a remarkable performance, albeit at the cost of increased complexity. In this paper we propose two key improvements for the decoding of toric code. The first one is replacing the BP decoder by a neural BP decoder, giving rise to the neural belief-matching decoder which substantially decreases the average decoding complexity. The main drawback of this approach is the high cost associated with the training of the neural BP decoder. To address this issue, we impose a convolutional architecture on the neural BP decoder, enabling weight sharing across the spatially homogeneous structure of the code's factor graph. This design allows a model trained on a modest-size topological code to be directly transferred to much larger instances, preserving decoding quality while dramatically lowering the training burden. Our numerical experiments on toric-code lattices of various sizes demonstrate that this technique does not result in a noticeable loss in performance.
Fault tolerance is a prerequisite for scalable quantum computing. Architectures based on 2D topological codes are effective for near-term implementations of fault tolerance. To obtain high performance with these architectures, we require a decoder which can adapt to the wide variety of error models present in experiments. The typical approach to the problem of decoding the surface code is to reduce it to minimum-weight perfect matching in a way that provides a suboptimal threshold error rate, and is specialized to correct a specific error model. Recently, optimal threshold error rates for a variety of error models have been obtained by methods which do not use minimum-weight perfect matching, showing that such thresholds can be achieved in polynomial time. It is an open question whether these results can also be achieved by minimum-weight perfect matching. In this work, we use belief propagation and a novel algorithm for producing edge weights to increase the utility of minimum-weight perfect matching for decoding surface codes. This allows us to correct depolarizing errors using the rotated surface code, obtaining a threshold of 17.76 ± 0.02 % . This is larger than the threshold achieved by previous matching-based decoders ( 14.88 ± 0.02 % ), though still below the known upper bound of ∼ 18.9 % .
Efficient decoding is essential for the practical realization of fault-tolerant quantum computers. We study the computational complexity of minimum-weight decoding for topological quantum codes. For surface codes under the depolarizing channel, we consider Minimum-Weight decoding, which seeks a minimum-weight Pauli error consistent with both the X- and Z-syndromes. For color codes under independent X- and Z-error models, we consider Separate Minimum-Weight decoding.
Assuming P=NP, we establish polynomial additive inapproximability gaps for these problems. Specifically, for the toric code and the 4.8.8 color code on the torus, there exists a constant c>0 such that no polynomial-time algorithm can always produce a solution whose weight is within cN1/14 of the optimum, where N is the number of qubits, unless P=NP. For the planar surface code, we obtain an Ω(N1/18) gap. Our inapproximability results use Håstad's hardness of approximation for MAX-3SAT.
Our reduction develops a general, modular framework for embedding logical constraints into coupled primal--dual join problems on a lattice. A key ingredient is a localization argument that controls unintended interactions between different parts of the construction.
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 nonzero code-capacity and circuit-level thresholds in the specified noise models. We further numerically study a variant optimized for practically relevant BB codes and observe performance comparable to that of belief propagation with ordered statistics decoding (BP-OSD). We also study the code-capacity threshold for the hexagonal color code as a proof of concept. Our results indicate that graph-matching decoders are a viable approach to decoding BB codes and other TTI codes.
In order to build a large scale quantum computer, one must be able to correct errors extremely fast. We design a fast decoding algorithm for topological codes to correct for Pauli errors and erasure and combination of both errors and erasure. Our algorithm has a worst case complexity of O ( n α ( n ) ) , where n is the number of physical qubits and α is the inverse of Ackermann's function, which is very slowly growing. For all practical purposes, α ( n ) ≤ 3 . We prove that our algorithm performs optimally for errors of weight up to ( d − 1 ) / 2 and for loss of up to d − 1 qubits, where d is the minimum distance of the code. Numerically, we obtain a threshold of 9.9 % for the 2d-toric code with perfect syndrome measurements and 2.6 % with faulty measurements.
Two-dimensional topological translationally invariant (2D TTI) stabilizer codes lie at the heart of fault-tolerant quantum computation, but using them requires solving the decoding problem. Minimum-weight decoding of these codes was recently shown to be NP-hard, even in basic settings, such as the color code with Pauli Z errors and the toric code with Pauli X, Y and Z errors. Here, we prove that minimum-weight decoding of 2D TTI codes nonetheless admits a polynomial-time approximation scheme (PTAS), i.e., for any constant ε>0, a recovery operator of weight within a multiplicative factor of 1+ε of the minimum can be found in polynomial time. Our approach builds on Arora's PTAS for Euclidean problems, such as the traveling salesman problem, and applies when decoding can be cast in terms of point-like excitations connected by string-like errors. It therefore extends beyond two dimensions, covering certain higher-dimensional topological codes and quantum memories, including the toric code with phenomenological or circuit-level noise.