© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:2603.05428

Optimal Decoding with the Worm

Zac Tobias, Nikolas P. Breuckmann, Benedikt Placke

quant-phcond-mat.dis-nncond-mat.stat-mechSubmitted Mar 5, 2026• Announced Mar 6, 2026• 0 citations• Revised Mar 18, 2026 (v2)

v1 · Mar 5, 2026 v2 · Mar 18, 2026

Abstract

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.

Comments: 34 Pages, 14 figures

Related papers

Efficient Markov chain Monte Carlo algorithm for the surface code

Adrian Hutter, James R. Wootton, Daniel Loss

Minimum-weight perfect matching (MWPM) has been the primary classical algorithm for error correction in the surface code, since it is of low runtime complexity and achieves relatively low logical error rates [Phys. Rev. Lett. 108, 180501 (2012)]. A Markov chain Monte Carlo (MCMC) algorithm [Phys. Rev. Lett. 109, 160503 (2012)] is able to achieve lower logical error rates and higher thresholds than MWPM, but requires a classical runtime complexity, which is super-polynomial in $L$, the linear size of the code. In this work we present an MCMC algorithm that achieves significantly lower logical error rates than MWPM at the cost of a runtime complexity increased by a factor $O({L}^{2})$. This advantage is due to taking correlations between bit- and phase-flip errors (as they appear, for example, in depolarizing noise) as well as entropic factors (i.e., the numbers of likely error paths in different equivalence classes) into account. For depolarizing noise with error rate $p$, we present an efficient algorithm for which the logical error rate is suppressed as $O({(p/3)}^{L/2})$ for $p\ensuremath{\rightarrow}0$---an exponential improvement over all previously existing efficient algorithms. Our algorithm allows for tradeoffs between runtime and achieved logical error rates as well as for parallelization, and can be also used for correction in the case of imperfect stabilizer measurements.

arXiv:1302.2669•Physical Review A•Feb 18, 2014•77 citations

Error-rate-agnostic decoding of topological stabilizer codes

Karl Hammar, Alexei Orekhov, Patrik Wallin Hybelius +4 more

Efficient high-performance decoding of topological stabilizer codes has the potential to crucially improve the balance between logical failure rates and the number and individual error rates of the constituent qubits. High-threshold maximum-likelihood decoders require an explicit error model for Pauli errors to decode a specific syndrome, whereas lower-threshold heuristic approaches such as minimum-weight matching are error agnostic. Here we consider an intermediate approach, formulating a decoder that depends on the bias, i.e., the relative probability of phase-flip to bit-flip errors, but is agnostic to error rate. Our decoder is based on counting the number and effective weight of the most likely error chains in each equivalence class of a given syndrome. We use Metropolis-based Monte Carlo sampling to explore the space of error chains and find unique chains that are efficiently identified using a hash table. Using the error-rate invariance, the decoder can sample chains effectively at an error rate which is higher than the physical error rate and without the need for thermalization between chains in different equivalence classes. Applied to the surface code and the $XZZX$ code, the decoder matches maximum-likelihood decoders for moderate code sizes or low error rates. We anticipate that, because of the compressed information content per syndrome, it can be taken full advantage of in combination with machine-learning methods to extrapolate Monte Carlo--generated data.

arXiv:2112.01977•Physical Review A•Apr 25, 2022•9 citations

A Modified MWPM Decoding Algorithm for Quantum Surface Codes Over Depolarizing Channels

Yaping Yuan, Chung-Chin Lu

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

arXiv:2202.11239•Feb 23, 2022•2 citations

Preserving MWPM-Decodability in Fault-Equivalent Rewrites

Maximilian Schweikart, Linnea Grans-Samuelsson, Aleks Kissinger +1 more

Decoding a quantum error correction code is generally NP-hard, but corrections must be applied at a high frequency to suppress noise successfully. Matchable codes, like the surface code, exhibit a special structure that makes it possible to efficiently, approximately solve the decoding problem through minimum-weight perfect matching (MWPM). However, this efficiency-enabling property can be lost when constructing implementations for fault-tolerant gadgets such as syndrome-extraction circuits or logical operations. In this work, we take a circuit-centric perspective to formalise how the decoding problem changes when applying ZX rewrites to a ZX diagram with a given detector basis. We demonstrate a set of rewrites that preserve MWPM-decodability of circuits and show that these matchability-preserving rewrites can be used to fault-tolerantly extract quantum circuits from phase-free ZX diagrams. In particular, this allows us to build efficiently decodable, fault-tolerant syndrome-extraction circuits for matchable codes.

quant-pharXiv:2603.19522•Mar 23, 2026•0 citations

Improved quantum error correction using soft information

Christopher A. Pattison, Michael E. Beverland, Marcus Palmer Da Silva +1 more

The typical model for measurement noise in quantum error correction is to randomly flip the binary measurement outcome. In experiments, measurements yield much richer information - e.g., continuous current values, discrete photon counts - which is then mapped into binary outcomes by discarding some of this information. In this work, we consider methods to incorporate all of this richer information, typically called soft information, into the decoding of quantum error correction codes, and in particular the surface code. We describe how to modify both the Minimum Weight Perfect Matching and Union-Find decoders to leverage soft information, and demonstrate these soft decoders outperform the standard (hard) decoders that can only access the binary measurement outcomes. Moreover, we observe that the soft decoder achieves a threshold 25\% higher than any hard decoder for phenomenological noise with Gaussian soft measurement outcomes. We also introduce a soft measurement error model with amplitude damping, in which measurement time leads to a trade-off between measurement resolution and additional disturbance of the qubits. Under this model we observe that the performance of the surface code is very sensitive to the choice of the measurement time - for a distance-19 surface code, a five-fold increase in measurement time can lead to a thousand-fold increase in logical error rate. Moreover, the measurement time that minimizes the physical error rate is distinct from the one that minimizes the logical performance, pointing to the benefits of jointly optimizing the physical and quantum error correction layers.

arXiv:2107.13589•Jul 28, 2021•6 citations

Fast Bounds on Matching Decoder Soft Output for the Surface Code

Sumeet Shirgure, Siyuan Niu

Surface code decoders like Minimum Weight Perfect Matching (MWPM) can also be used to estimate or bound the probability of a logical failure conditioned on the error syndrome commonly called ``soft outputs''. Estimates like the complementary gap of a matching, or others like the ``cluster gap'' are used to produce high fidelity magic states via post-selection. They are also helpful in reducing the overhead of fault-tolerant computation via code concatenation schemes like yoked surface codes. In this work we provide techniques to tightly lower bound the complementary gap of a rotated surface code syndrome block and provide fast parallel algorithms for computing this lower bound efficiently. Our algorithms run in real time for the moderate distances and reasonable physical noise rates required by these applications. We achieve latencies of the order of one to tens of microseconds on sufficiently fast CPU cores.

•Nov 1, 2026•0 citations

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.

Minimum-weight perfect matching (MWPM) has been the primary classical algorithm for error correction in the surface code, since it is of low runtime complexity and achieves relatively low logical error rates [Phys. Rev. Lett. 108, 180501 (2012)]. A Markov chain Monte Carlo (MCMC) algorithm [Phys. Rev. Lett. 109, 160503 (2012)] is able to achieve lower logical error rates and higher thresholds than MWPM, but requires a classical runtime complexity, which is super-polynomial in

L

, the linear size of the code. In this work we present an MCMC algorithm that achieves significantly lower logical error rates than MWPM at the cost of a runtime complexity increased by a factor

O({L}^{2})

. This advantage is due to taking correlations between bit- and phase-flip errors (as they appear, for example, in depolarizing noise) as well as entropic factors (i.e., the numbers of likely error paths in different equivalence classes) into account. For depolarizing noise with error rate

p

, we present an efficient algorithm for which the logical error rate is suppressed as

O({(p/3)}^{L/2})

for $p\ensuremath{\rightarrow}0$---an exponential improvement over all previously existing efficient algorithms. Our algorithm allows for tradeoffs between runtime and achieved logical error rates as well as for parallelization, and can be also used for correction in the case of imperfect stabilizer measurements.

Efficient high-performance decoding of topological stabilizer codes has the potential to crucially improve the balance between logical failure rates and the number and individual error rates of the constituent qubits. High-threshold maximum-likelihood decoders require an explicit error model for Pauli errors to decode a specific syndrome, whereas lower-threshold heuristic approaches such as minimum-weight matching are error agnostic. Here we consider an intermediate approach, formulating a decoder that depends on the bias, i.e., the relative probability of phase-flip to bit-flip errors, but is agnostic to error rate. Our decoder is based on counting the number and effective weight of the most likely error chains in each equivalence class of a given syndrome. We use Metropolis-based Monte Carlo sampling to explore the space of error chains and find unique chains that are efficiently identified using a hash table. Using the error-rate invariance, the decoder can sample chains effectively at an error rate which is higher than the physical error rate and without the need for thermalization between chains in different equivalence classes. Applied to the surface code and the

XZZX

code, the decoder matches maximum-likelihood decoders for moderate code sizes or low error rates. We anticipate that, because of the compressed information content per syndrome, it can be taken full advantage of in combination with machine-learning methods to extrapolate Monte Carlo--generated data.

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

Decoding a quantum error correction code is generally NP-hard, but corrections must be applied at a high frequency to suppress noise successfully. Matchable codes, like the surface code, exhibit a special structure that makes it possible to efficiently, approximately solve the decoding problem through minimum-weight perfect matching (MWPM). However, this efficiency-enabling property can be lost when constructing implementations for fault-tolerant gadgets such as syndrome-extraction circuits or logical operations. In this work, we take a circuit-centric perspective to formalise how the decoding problem changes when applying ZX rewrites to a ZX diagram with a given detector basis. We demonstrate a set of rewrites that preserve MWPM-decodability of circuits and show that these matchability-preserving rewrites can be used to fault-tolerantly extract quantum circuits from phase-free ZX diagrams. In particular, this allows us to build efficiently decodable, fault-tolerant syndrome-extraction circuits for matchable codes.

The typical model for measurement noise in quantum error correction is to randomly flip the binary measurement outcome. In experiments, measurements yield much richer information - e.g., continuous current values, discrete photon counts - which is then mapped into binary outcomes by discarding some of this information. In this work, we consider methods to incorporate all of this richer information, typically called soft information, into the decoding of quantum error correction codes, and in particular the surface code. We describe how to modify both the Minimum Weight Perfect Matching and Union-Find decoders to leverage soft information, and demonstrate these soft decoders outperform the standard (hard) decoders that can only access the binary measurement outcomes. Moreover, we observe that the soft decoder achieves a threshold 25\% higher than any hard decoder for phenomenological noise with Gaussian soft measurement outcomes. We also introduce a soft measurement error model with amplitude damping, in which measurement time leads to a trade-off between measurement resolution and additional disturbance of the qubits. Under this model we observe that the performance of the surface code is very sensitive to the choice of the measurement time - for a distance-19 surface code, a five-fold increase in measurement time can lead to a thousand-fold increase in logical error rate. Moreover, the measurement time that minimizes the physical error rate is distinct from the one that minimizes the logical performance, pointing to the benefits of jointly optimizing the physical and quantum error correction layers.

Surface code decoders like Minimum Weight Perfect Matching (MWPM) can also be used to estimate or bound the probability of a logical failure conditioned on the error syndrome commonly called ``soft outputs''. Estimates like the complementary gap of a matching, or others like the ``cluster gap'' are used to produce high fidelity magic states via post-selection. They are also helpful in reducing the overhead of fault-tolerant computation via code concatenation schemes like yoked surface codes. In this work we provide techniques to tightly lower bound the complementary gap of a rotated surface code syndrome block and provide fast parallel algorithms for computing this lower bound efficiently. Our algorithms run in real time for the moderate distances and reasonable physical noise rates required by these applications. We achieve latencies of the order of one to tens of microseconds on sufficiently fast CPU cores.