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

Certified lower bounds on the optimal-decoding threshold of the surface code

Tejasvi Singh Tomar

Published Nov 5, 2026• 0 citations
Publisher

Abstract

Under independent bit flips, rigorous lower bounds on the threshold of the surface code from earlier work stay below 0.04, while numerical estimates place the optimal threshold near 0.109. By counting labelled failure paths with exact transfer-matrix certificates, we prove without sampling that every minimum-weight decoder has threshold at least 0.0465 on the planar and rotated codes. We then give statistical certificates that the optimal threshold of the planar code is at least 0.102 under bit flips and at least 0.02 under phenomenological noise. Each certificate bounds an auxiliary decoder that corrects each block from a window around it, and optimal decoding does at least as well. A deterministic lemma reduces the failure of the auxiliary decoder to rare bad blocks, whose probabilities are bounded by a pre-registered Monte Carlo experiment. The confidence holds under a binomial model of the counts and two tested properties of each decoding program. All these results are proved in the proof assistant Lean 4, the statistical ones with these conditions as hypotheses. The data, programs and certificates behind the paper are in the record 10.5281/zenodo.23994430, and its Lean proofs in the record 10.5281/zenodo.23994431.

DOI
10.5281/zenodo.23996236

Related papers

A matching threshold of 1.6×10⁻³ for the rotated surface code under circuit-level noise

Tejasvi Singh Tomar

We consider the rotated surface code of odd distance d with its standard syndrome-extraction circuit, under circuit-level depolarizing noise in which every gate, idle step, preparation and measurement fails independently with probability p, decoded by minimum-weight perfect matching with the log-likelihood weights of single faults. We prove that a memory experiment with T rounds fails with probability at most 0.061 (T+1)(d+1) λd/(1−λ), where λ = 0.999 (p/p**)9/25, for every p ≤ p** = 2×10−3. Hence the logical error rate per round decays exponentially in d for all p ≤ p**. Earlier rigorous thresholds for matching on surface-code circuits are 1.7×10−4, due to Dennis, Kitaev, Landahl and Preskill, and 7.4×10−4, due to Fowler. We keep their reduction of a failure to a weighted self-avoiding path in the decoding graph, but bound these paths by a local criterion for non-backtracking walks, which gives the threshold 1.04×10−3 in closed form. To reach 2×10−3 we use the minimality of the correction along the path, for a canonical choice among the minimum-weight corrections: labellings of short stretches of the path into error and correction edges that contradict this minimality are excluded, and the remaining labelled walks are counted with a potential function that is checked in exact arithmetic. For a leaner schedule with fused measure-and-reset steps the two arguments give 1.53×10−3 and 3×10−3, respectively. With error rates that depend on the type of operation, they certify exponential decay for error models built from the published component error rates of Quantinuum's Helios and H2 and of IBM's Heron r3 processor ibm_boston, mapped onto this circuit. All theorems are also proved in the proof assistant Lean 4. Any argument that bounds the failure probability by the probability of an increasing event, ours included, is limited by the smallest such event that contains all failures, and Monte Carlo estimates place the threshold of this event near 4×10−3 for this circuit. Changes from version 1: a third exclusion rule, which uses a canonical choice among the minimum-weight corrections, raises the certified thresholds to 2×10−3 for the standard schedule and 3×10−3 for the lean one and strengthens the certificates of the device error models. Lean 4 proofs of all theorems are new in this version. Programs, certificates, formal proofs and the outputs of all checks: doi:10.5281/zenodo.23485205. Mathematics Subject Classification (2020): 81P73; 94B35, 05C38, 68V05.

•Oct 19, 2026•0 citations

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

Louay Bazzi

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.

cs.ITCross-listedarXiv:2601.00972•IEEE International Symposium on Information Theory (ISIT)•Jan 6, 2026•1 citation

Representation Sensitivity in Rotated Surface-Code Decoding under Correlated Pauli Noise

Ba Thien Nguyen

Abstract We study decoder-representation sensitivity in simulated rotated surface-code Z-memory circuits with local spatially correlated XX pair events. At distance 3, ordinary minimum-weight perfect matching (MWPM) produced 4,610 versus 1,260 logical failures at p_corr = 10^-4 and 5,437 versus 2,239 at p_corr = 2 × 10^-4 on the same 500,000-shot samples using original-order versus canonical-sorted detector error models (DEMs). Across 50 additional seeded permutations per condition, failure counts varied widely. Canonical sorting tied for the minimum in this finite tested set; it is not claimed to be universally optimal. The ordering experiment reorders complete error instructions in a flattened DEM, preserving their probabilities and absolute detector and logical targets. PyMatching documents retaining the first-added logical-label set when parallel graph edges are merged; we therefore interpret the findings as a workflow-specific reproducibility result, not a newly discovered general software defect. At distances 5 and 7, correlation-aware MWPM had lower observed failure rates in all eight tested conditions, with six paired contrasts remaining significant after Bonferroni correction. An exact maximum-a-posteriori calculation gave a 0.2367% Bayes risk for the flattened-DEM distribution at p_corr = 10^-4; this is optimal for that modeled distribution only. This bounded classical simulation study proposes no new decoder, estimates no threshold, and provides no hardware evidence. Some historical source-to-result provenance remains incomplete, as disclosed in the manuscript. Code and evidence: https://github.com/tgiwn/QEC-surface-code-correlated-noise/tree/106d32e815c5f6009941afc36d3f65be7ecf35a3 Status: This is a preprint and has not undergone peer review.

•Oct 23, 2026•0 citations

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•4 citations

Exact results on finite size corrections for surface codes tailored to biased noise

Yinzi Xiao, Basudha Srivastava, Mats Granath

The code-capacity threshold of a scalable quantum error correcting stabilizer code can be expressed as a thermodynamic phase transition of a corresponding random-bond Ising model. Here we study the XY and XZZX surface codes under phase-biased noise, px=py=pz/(2η) , with η≥1/2 , and total error rate p=px+py+pz . By appropriately formulating the boundary conditions, in the rotated code geometry, we find exact solutions at a special disordered point, p=1+η−12+η−1≳0.5 , for arbitrary odd code distance d , where the codes reduce to one-dimensional Ising models. The total logical failure rate is given by Pf=34−14e−2dZartanh(1/2η) , where dZ=d2 and d for the two codes respectively, is the effective code distance for pure phase-flip noise. As a consequence, for code distances d≪η , and error rates near the threshold, the XZZX code is effectively equivalent to the phase-flip correcting repetition code over d qubits. The large finite size corrections for dZ<η also make threshold extractions, from numerical calculations at moderate code distances, unreliable. We show that calculating thresholds based not only on the total logical failure rate, but also independently on the phase- and bit-flip logical failure rates, gives a more confident estimate. Using this method for the XZZX code with a tensor-network based decoder and code distances up to d≈100 , we find that the thresholds converge to a single value at moderate bias ( η=30,100 ), at an error rate above the hashing bound.

arXiv:2401.04008•Quantum•Sep 11, 2024•7 citations

Minimising surface-code failures using a color-code decoder

Asmae Benhemou, Kaavya Sahay, Lingling Lao +1 more

The development of practical, high-performance decoding algorithms reduces the resource cost of fault-tolerant quantum computing. Here we propose a decoder for the surface code that finds low-weight correction operators for errors produced by the depolarising noise model. The decoder is obtained by mapping the syndrome of the surface code onto that of the color code, thereby allowing us to adopt more sophisticated color-code decoding algorithms. Analytical arguments and exhaustive testing show that the resulting decoder can find a least-weight correction for all weight d/2 depolarising errors for even code distance d . This improves the logical error rate by an exponential factor O(2d/2) compared with decoders that treat bit-flip and dephasing errors separately. We demonstrate this improvement with analytical arguments and supporting numerical simulations at low error rates. Of independent interest, we also demonstrate an exponential improvement in logical error rate for our decoder used to correct independent and identically distributed bit-flip errors affecting the color code compared with more conventional color-code decoding algorithms.

arXiv:2306.16476•Quantum•Feb 17, 2025•6 citations
Under independent bit flips, rigorous lower bounds on the threshold of the surface code from earlier work stay below 0.04, while numerical estimates place the optimal threshold near 0.109. By counting labelled failure paths with exact transfer-matrix certificates, we prove without sampling that every minimum-weight decoder has threshold at least 0.0465 on the planar and rotated codes. We then give statistical certificates that the optimal threshold of the planar code is at least 0.102 under bit flips and at least 0.02 under phenomenological noise. Each certificate bounds an auxiliary decoder that corrects each block from a window around it, and optimal decoding does at least as well. A deterministic lemma reduces the failure of the auxiliary decoder to rare bad blocks, whose probabilities are bounded by a pre-registered Monte Carlo experiment. The confidence holds under a binomial model of the counts and two tested properties of each decoding program. All these results are proved in the proof assistant Lean 4, the statistical ones with these conditions as hypotheses. The data, programs and certificates behind the paper are in the record 10.5281/zenodo.23994430, and its Lean proofs in the record 10.5281/zenodo.23994431.
We consider the rotated surface code of odd distance d with its standard syndrome-extraction circuit, under circuit-level depolarizing noise in which every gate, idle step, preparation and measurement fails independently with probability p, decoded by minimum-weight perfect matching with the log-likelihood weights of single faults. We prove that a memory experiment with T rounds fails with probability at most 0.061 (T+1)(d+1) λd/(1−λ), where λ = 0.999 (p/p**)9/25, for every p ≤ p** = 2×10−3. Hence the logical error rate per round decays exponentially in d for all p ≤ p**. Earlier rigorous thresholds for matching on surface-code circuits are 1.7×10−4, due to Dennis, Kitaev, Landahl and Preskill, and 7.4×10−4, due to Fowler. We keep their reduction of a failure to a weighted self-avoiding path in the decoding graph, but bound these paths by a local criterion for non-backtracking walks, which gives the threshold 1.04×10−3 in closed form. To reach 2×10−3 we use the minimality of the correction along the path, for a canonical choice among the minimum-weight corrections: labellings of short stretches of the path into error and correction edges that contradict this minimality are excluded, and the remaining labelled walks are counted with a potential function that is checked in exact arithmetic. For a leaner schedule with fused measure-and-reset steps the two arguments give 1.53×10−3 and 3×10−3, respectively. With error rates that depend on the type of operation, they certify exponential decay for error models built from the published component error rates of Quantinuum's Helios and H2 and of IBM's Heron r3 processor ibm_boston, mapped onto this circuit. All theorems are also proved in the proof assistant Lean 4. Any argument that bounds the failure probability by the probability of an increasing event, ours included, is limited by the smallest such event that contains all failures, and Monte Carlo estimates place the threshold of this event near 4×10−3 for this circuit. Changes from version 1: a third exclusion rule, which uses a canonical choice among the minimum-weight corrections, raises the certified thresholds to 2×10−3 for the standard schedule and 3×10−3 for the lean one and strengthens the certificates of the device error models. Lean 4 proofs of all theorems are new in this version. Programs, certificates, formal proofs and the outputs of all checks: doi:10.5281/zenodo.23485205. Mathematics Subject Classification (2020): 81P73; 94B35, 05C38, 68V05.
We study exact decoding for the toric code and for planar and rotated surface codes under the standard independent X/ZX/ZX/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(n3/2log⁡n)O(n^{3/2}\log n)O(n3/2logn)-time decoder is achievable for surface and toric codes, improving over the O(n3log⁡n)O(n^{3}\log n)O(n3logn) 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~111 for the toric code. This reduction enables the use of Lipton--Tarjan planar separator methods and implies that SMW decoding lies in NC\mathrm{NC}NC. For SMLC decoding, we show that the planar surface code admits an exact decoder with O(n3/2)O(n^{3/2})O(n3/2) algebraic complexity and that the problem lies in NC\mathrm{NC}NC, improving over the O(n2)O(n^{2})O(n2) 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(n3)O(n^{3})O(n3) 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.
Abstract We study decoder-representation sensitivity in simulated rotated surface-code Z-memory circuits with local spatially correlated XX pair events. At distance 3, ordinary minimum-weight perfect matching (MWPM) produced 4,610 versus 1,260 logical failures at p_corr = 10^-4 and 5,437 versus 2,239 at p_corr = 2 × 10^-4 on the same 500,000-shot samples using original-order versus canonical-sorted detector error models (DEMs). Across 50 additional seeded permutations per condition, failure counts varied widely. Canonical sorting tied for the minimum in this finite tested set; it is not claimed to be universally optimal. The ordering experiment reorders complete error instructions in a flattened DEM, preserving their probabilities and absolute detector and logical targets. PyMatching documents retaining the first-added logical-label set when parallel graph edges are merged; we therefore interpret the findings as a workflow-specific reproducibility result, not a newly discovered general software defect. At distances 5 and 7, correlation-aware MWPM had lower observed failure rates in all eight tested conditions, with six paired contrasts remaining significant after Bonferroni correction. An exact maximum-a-posteriori calculation gave a 0.2367% Bayes risk for the flattened-DEM distribution at p_corr = 10^-4; this is optimal for that modeled distribution only. This bounded classical simulation study proposes no new decoder, estimates no threshold, and provides no hardware evidence. Some historical source-to-result provenance remains incomplete, as disclosed in the manuscript. Code and evidence: https://github.com/tgiwn/QEC-surface-code-correlated-noise/tree/106d32e815c5f6009941afc36d3f65be7ecf35a3 Status: This is a preprint and has not undergone peer review.
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.
The code-capacity threshold of a scalable quantum error correcting stabilizer code can be expressed as a thermodynamic phase transition of a corresponding random-bond Ising model. Here we study the XY and XZZX surface codes under phase-biased noise, px=py=pz/(2η) , with η≥1/2 , and total error rate p=px+py+pz . By appropriately formulating the boundary conditions, in the rotated code geometry, we find exact solutions at a special disordered point, p=1+η−12+η−1≳0.5 , for arbitrary odd code distance d , where the codes reduce to one-dimensional Ising models. The total logical failure rate is given by Pf=34−14e−2dZartanh(1/2η) , where dZ=d2 and d for the two codes respectively, is the effective code distance for pure phase-flip noise. As a consequence, for code distances d≪η , and error rates near the threshold, the XZZX code is effectively equivalent to the phase-flip correcting repetition code over d qubits. The large finite size corrections for dZ<η also make threshold extractions, from numerical calculations at moderate code distances, unreliable. We show that calculating thresholds based not only on the total logical failure rate, but also independently on the phase- and bit-flip logical failure rates, gives a more confident estimate. Using this method for the XZZX code with a tensor-network based decoder and code distances up to d≈100 , we find that the thresholds converge to a single value at moderate bias ( η=30,100 ), at an error rate above the hashing bound.
The development of practical, high-performance decoding algorithms reduces the resource cost of fault-tolerant quantum computing. Here we propose a decoder for the surface code that finds low-weight correction operators for errors produced by the depolarising noise model. The decoder is obtained by mapping the syndrome of the surface code onto that of the color code, thereby allowing us to adopt more sophisticated color-code decoding algorithms. Analytical arguments and exhaustive testing show that the resulting decoder can find a least-weight correction for all weight d/2 depolarising errors for even code distance d . This improves the logical error rate by an exponential factor O(2d/2) compared with decoders that treat bit-flip and dephasing errors separately. We demonstrate this improvement with analytical arguments and supporting numerical simulations at low error rates. Of independent interest, we also demonstrate an exponential improvement in logical error rate for our decoder used to correct independent and identically distributed bit-flip errors affecting the color code compared with more conventional color-code decoding algorithms.