We study exact decoding for the toric code and for planar and rotated surface codes under the standard independent \(X/Z\) noise model, focusing on Separate Minimum Weight (SMW) decoding and Separate Most Likely Coset (SMLC) decoding. For the SMW decoding problem, we show that an \(O(n^{3/2}\log n)\)-time decoder is achievable for surface and toric codes, improving over the \(O(n^{3}\log n)\) worst-case time of the standard approach based on complete decoding graphs. Our approach is based on a local reduction of SMW decoding to the minimum weight perfect matching problem using Fisher gadgets, which preserves planarity for planar and rotated surface codes and genus~\(1\) for the toric code. This reduction enables the use of Lipton--Tarjan planar separator methods and implies that SMW decoding lies in \(\mathrm{NC}\). For SMLC decoding, we show that the planar surface code admits an exact decoder with \(O(n^{3/2})\) algebraic complexity and that the problem lies in \(\mathrm{NC}\), improving over the \(O(n^{2})\) algebraic complexity of Bravyi \emph{et al.} Our approach proceeds via a dual-cycle formulation of coset probabilities and an explicit reduction to planar Pfaffian evaluation using Fisher--Kasteleyn--Temperley constructions. The same complexity measures apply to SMLC decoding of the rotated surface code. For the toric code, we obtain an exact polynomial-time SMLC decoder with \(O(n^{3})\) algebraic complexity. In addition, while the SMLC formulation is motivated by connections to statistical mechanics, we provide a purely algebraic derivation of the underlying duality based on MacWilliams duality and Fourier analysis. Finally, we discuss extensions of the framework to the depolarizing noise model and identify resulting open problems.
Comments
Updated discussion of open problems to reflect subsequent results on the complexity and approximability of minimum-weight decoding
We study exact decoding for the toric code and for planar and rotated surface codes under the standard independent (X/Z) noise model, focusing on Separate Minimum Weight (SMW) decoding and Separate Most Likely Coset (SMLC) decoding. For the SMW decoding problem, we show that an (O(n^{3/2}\log n))-time decoder is achievable for surface and toric codes, improving over the (O(n^{3}\log n)) worst-case time of the standard approach based on complete decoding graphs. Our approach is based on a local reduction of SMW decoding to the minimum weight perfect matching problem using Fisher gadgets, which preserves planarity for planar and rotated surface codes and genus~(1) for the toric code. This reduction enables the use of Lipton--Tarjan planar separator methods and implies that SMW decoding lies in (\mathrm{NC}). For SMLC decoding, we show that the planar surface code admits an exact decoder with (O(n^{3/2})) algebraic complexity and that the problem lies in (\mathrm{NC}), improving over the (O(n^{2})) algebraic complexity of Bravyi \emph{et al.} Our approach proceeds via a dual-cycle formulation of coset probabilities and an explicit reduction to planar Pfaffian evaluation using Fisher--Kasteleyn--Temperley constructions. The same complexity measures apply to SMLC decoding of the rotated surface code. For the toric code, we obtain an exact polynomial-time SMLC decoder with (O(n^{3})) algebraic complexity. In addition, while the SMLC formulation is motivated by connections to statistical mechanics, we provide a purely algebraic derivation of the underlying duality based on MacWilliams duality and Fourier analysis. Finally, we discuss extensions of the framework to the depolarizing noise model and identify resulting open problems.
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.
Topological quantum codes, such as toric and surface codes, are excellent candidates for hardware implementation due to their robustness against errors and their local interactions between qubits. However, decoding these codes efficiently remains a challenge: existing decoders often fall short of meeting requirements such as having low computational complexity (ideally linear in the code’s blocklength), low decoding latency, and low power consumption. In this paper we propose a novel bit-flipping (BF) decoder tailored for toric and surface codes. We introduce the proximity vector as a heuristic metric for flipping bits, and we develop a new subroutine for correcting degenerate multiple errors on adjacent qubits. Our algorithm has quadratic complexity growth and it can be efficiently implemented as it does not require operations on dynamic memories, as do state-of-art decoding algorithms such as minimum weight perfect matching or union find. The proposed decoder shows a decoding threshold of 7.5% for the 2D toric code and 7% for the rotated planar code over the binary symmetric channel.
Efficient and realistic error decoding is crucial for fault-tolerant quantum computation (FTQC) on near-term devices. While decoding is a classical post-processing task, its effectiveness depends on accurately modeling quantum noise, which is hardware-dependent. In particular, correlated bit-flip (X) and phase-flip (Z) errors often arise under circuit-level noise. We introduce the Iterative Reweighting Minimum-Weight Perfect Matching (IRMWPM) decoder, which systematically incorporates such correlations to enhance quantum error correction. Our method leverages fault-detection patterns to guide reweighting: correlated X and Z detection events are identified, and their conditional probabilities update weights on the primal and dual lattices. This iterative procedure improves handling of realistic error propagation in a hardware-agnostic yet noise-aware manner. We prove that IRMWPM converges in finite time while preserving the distance guarantee of MWPM. Numerical results under circuit-level noise show substantial improvements. For distances ≥17 and physical error rates ≤0.001, IRMWPM reduces logical error rates by over 20x with only a few iterations. It also raises the accuracy threshold from 1% to 1.16%, making it practical for near-term real-time decoding. Extrapolated estimates suggest that to reach logical error rate 10−16, IRMWPM requires distance d=31, while standard MWPM needs d=50, implying a major reduction in qubit overhead.
Quantum Surface codes are a kind of quantum topological stabilizer codes whose stabilizers and qubits are geometrically related. Due to their special structures, surface codes have great potential to lead people to large-scale quantum computation. In the minimum weight perfect matching (MWPM) decoding of surface codes, the bit-flip errors and phase-flip errors are assumed to be independent for simplicity. However, these two kinds of errors are likely to be correlated in the real world. In this paper, we propose a modification to MWPM decoding for surface codes to deal with the noises in depolarizing channels where bit-flip errors and phase-flip errors are correlated. With this modification, we obtain thresholds of 17% and 15.3% for the surface codes with mixed boundaries and the surface codes with a hole, respectively
Abstract Quantum error correction is essential for realizing fault-tolerant quantum computing, where both the efficiency and accuracy of the decoding algorithms play critical roles. In this work, we introduce the implementation of the Planar algorithm, a software framework designed for fast and exact decoding of quantum codes with a planar structure. The algorithm first converts the optimal decoding of quantum codes into a partition function computation problem of an Ising spin glass model. Then it utilizes the exact Kac–Ward formula to solve it. In this way, Planar offers the exact maximum likelihood decoding in polynomial complexity for quantum codes with a planar structure, including the surface code with independent code-capacity noise and the quantum repetition code with circuit-level noise. Unlike traditional minimum-weight decoders such as minimum-weight perfect matching (MWPM), Planar achieves theoretically optimal performance while maintaining polynomial-time efficiency. In addition, to demonstrate its capabilities, we exemplify the implementation using the rotated surface code, a commonly used quantum error correction code with a planar structure, and show that Planar achieves a threshold of approximately p uc ≈ 0.109 under the depolarizing error model, with a time complexity scaling of O(N 0.69), where N is the number of spins in the Ising model.
We propose a new decoder for "matchable'' qLDPC codes that uses a Markov Chain Monte Carlo algorithm - called the worm algorithm - to approximately compute the probabilities of logical error classes given a syndrome. The algorithm hence performs (approximate) optimal decoding, and we expect it to be computationally efficient in certain settings. The algorithm is applicable to decoding random errors for the surface code, the honeycomb Floquet code, and hyperbolic surface codes with constant rate, in all cases with and without measurement errors. The efficiency of the decoder hinges on the mixing time of the underlying Markov chain. We give a rigorous mixing time guarantee in terms of a quantity that we call the defect susceptibility. We connect this quantity to the notion of disorder operators in statistical mechanics and use this to argue (non-rigorously) that the algorithm is efficient for typical errors in the entire decodable phase. We also demonstrate the effectiveness of the worm decoder numerically by applying it to the surface code with measurement errors as well as a family of hyperbolic surface codes. For most codes, the matchability condition restricts direct application of our decoder to noise models with independent bit-flip, phase-flip, and measurement errors. However, our decoder returns soft information which makes it useful also in heuristic "correlated decoding'' schemes which work beyond this simple setting. We demonstrate this by simulating decoding of the surface code under depolarizing noise, and we find that the threshold for "correlated worm decoding'' is substantially higher than for both minimum-weight perfect matching and for correlated matching.