Improved decoding algorithms for surface codes under independent bit-flip and phase-flip errors

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/2log n\)-time decoder is achievable for surface and toric codes, improving over the O\(n³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 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 NC, improving over the O\(n²\) algebraic complexity of Bravyi 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³\) 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.