Compare Papers

Paper 1

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

Louay Bazzi

Year

2026

Journal

arXiv preprint

DOI

arXiv:2601.00972

arXiv

2601.00972

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.

Open paper

Paper 2

Fast surgery for quantum LDPC codes

Nouédyn Baspin, Lucas Berent, Lawrence Z. Cohen

Year

2025

Journal

arXiv preprint

DOI

arXiv:2510.04521

arXiv

2510.04521

Quantum LDPC codes promise significant reductions in physical qubit overhead compared with topological codes. However, many existing constructions for performing logical operations come with distance-dependent temporal overheads. We introduce a scheme for performing generalized surgery on quantum LDPC codes using a constant number of rounds of syndrome measurement. The merged code in our scheme is constructed by taking the total complex of the base code and a suitably chosen homomorphic chain complex. We demonstrate the applicability of our scheme on an example multi-cycle code and assess the performance under a phenomenological noise model, showing that fast surgery performs comparably to standard generalized surgery with multiple rounds. Our results pave the way towards fault-tolerant quantum computing with LDPC codes with both low spatial and temporal overheads.

Open paper