Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1302.2669 · Physical Review A

Efficient Markov chain Monte Carlo algorithm for the surface code

Adrian Hutter, James R. Wootton, Daniel Loss

Published Feb 18, 2014• 77 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.89.022326

Related papers

Optimal Decoding with the Worm

Zac Tobias, Nikolas P. Breuckmann, Benedikt Placke

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.

quant-pharXiv:2603.05428•Mar 6, 2026•0 citations

Improved Methods for Determining Quantum Error Correcting Code Performance and Fault Tolerance

Michael Mullan, Matthew Weippert, Winton Brown

One of the central challenges in quantum error correction is determining the performance of a code in the low-error regimes needed to implement utility-scale computations. While performance at these error rates is not amenable to direct Monte Carlo simulation, it can be extrapolated from simulations at higher logical error rates, assuming the logical error rate scales predictably with increasing distance or decreasing physical error rate. However, the expected scaling depends sensitively on the minimum weight of uncorrectable error patterns. In many cases, the minimum weight is unknown since it depends not only on the theoretical code distance, but also on details of the implementation. Markov chain Monte Carlo (MCMC) methods, as adapted to quantum error correction by Bravyi and Vargo, provide a way to estimate logical failure rates in these low-error regimes via simulation. While offering significant gains over Monte Carlo, the described Metropolis algorithm makes small changes to the current logical failure patterns which results in slow convergence. In this paper, we argue that typical failure patterns include a large number of easily correctable errors that coexist alongside a malignant core. This observation motivates two new approaches to better evaluate code performance. First, we describe a pruning algorithm designed to obviate these correctable errors and focus on the problematic low-weight core. Second, we develop a novel family of Metropolis-Hastings algorithms, referred to as subregion MCMC. This technique is parameterized by the fraction of the error pattern that is resampled at each step, effectively interpolating between Monte Carlo and single step MCMC. We show that a judicious choice of this parameter results in far faster convergence than prior work.

quant-pharXiv:2607.27153•Jul 30, 2026•0 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

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

Rectangular surface code under biased noise

Jonghyun Lee, Joo Youn Park, Jun Heo

Abstract To date, the surface code has become a promising candidate for quantum error correcting codes because it achieves a high threshold and is composed of only the nearest gate operations and low-weight stabilizers. Here, we have exhibited that the logical failure rate can be enhanced by manipulating the lattice size of surface codes that they can show an enormous improvement in the number of physical qubits for a noise model where dephasing errors dominate over relaxation errors. We estimated the logical error rate in terms of the lattice size and physical error rate. When the physical error rate was high, the parameter estimation method was applied, and when it was low, the most frequently occurring logical error cases were considered. By using the minimum weight perfect matching decoding algorithm, we obtained the optimal lattice size by minimizing the number of qubits to achieve the required failure rates when physical error rates and bias are provided .

Quantum Information Processing•Jul 1, 2021•8 citations

Enhancing Fault-Tolerant Surface Code Decoding with Iterative Lattice Reweighting

Yi Tian, Yang Zheng, Xiaoting Wang +1 more

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 $\geq 17$ and physical error rates $\leq 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.

arXiv:2509.06756•Sep 8, 2025•0 citations
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 LLL, 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(L2)O({L}^{2})O(L2). 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 ppp, we present an efficient algorithm for which the logical error rate is suppressed as O((p/3)L/2)O({(p/3)}^{L/2})O((p/3)L/2) for p\ensuremath→0p\ensuremath{\rightarrow}0p\ensuremath→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.
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.
One of the central challenges in quantum error correction is determining the performance of a code in the low-error regimes needed to implement utility-scale computations. While performance at these error rates is not amenable to direct Monte Carlo simulation, it can be extrapolated from simulations at higher logical error rates, assuming the logical error rate scales predictably with increasing distance or decreasing physical error rate. However, the expected scaling depends sensitively on the minimum weight of uncorrectable error patterns. In many cases, the minimum weight is unknown since it depends not only on the theoretical code distance, but also on details of the implementation. Markov chain Monte Carlo (MCMC) methods, as adapted to quantum error correction by Bravyi and Vargo, provide a way to estimate logical failure rates in these low-error regimes via simulation. While offering significant gains over Monte Carlo, the described Metropolis algorithm makes small changes to the current logical failure patterns which results in slow convergence. In this paper, we argue that typical failure patterns include a large number of easily correctable errors that coexist alongside a malignant core. This observation motivates two new approaches to better evaluate code performance. First, we describe a pruning algorithm designed to obviate these correctable errors and focus on the problematic low-weight core. Second, we develop a novel family of Metropolis-Hastings algorithms, referred to as subregion MCMC. This technique is parameterized by the fraction of the error pattern that is resampled at each step, effectively interpolating between Monte Carlo and single step MCMC. We show that a judicious choice of this parameter results in far faster convergence than prior work.
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
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 XZZXXZZXXZZX 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.
Abstract To date, the surface code has become a promising candidate for quantum error correcting codes because it achieves a high threshold and is composed of only the nearest gate operations and low-weight stabilizers. Here, we have exhibited that the logical failure rate can be enhanced by manipulating the lattice size of surface codes that they can show an enormous improvement in the number of physical qubits for a noise model where dephasing errors dominate over relaxation errors. We estimated the logical error rate in terms of the lattice size and physical error rate. When the physical error rate was high, the parameter estimation method was applied, and when it was low, the most frequently occurring logical error cases were considered. By using the minimum weight perfect matching decoding algorithm, we obtained the optimal lattice size by minimizing the number of qubits to achieve the required failure rates when physical error rates and bias are provided .
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 (XXX) and phase-flip (ZZZ) 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 XXX and ZZZ 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\geq 17≥17 and physical error rates ≤0.001\leq 0.001≤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−1610^{-16}10−16, IRMWPM requires distance d=31d=31d=31, while standard MWPM needs d=50d=50d=50, implying a major reduction in qubit overhead.