TejasviTomar
November 2026 · Preprint

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

Tejasvi Singh Tomar

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.

In plain words

The surface code protects data on quantum chips if their error rate is below a threshold. When bit flips occur independently and the checks themselves are error-free, simulations put the best correction method's threshold near 10.9%. But proven thresholds in this setting, including one by Dennis, Kitaev, Landahl and Preskill, stayed below 4%. This paper proves, without sampling, a threshold of at least 4.65% for the standard correction method on the rotated and unrotated codes. For the best method on the unrotated code, a proof and a pre-registered computer experiment certify a threshold of at least 10.2%. Under stated conditions, the chance of certifying such a bound when it is false is at most one in a billion.

A grid of grey dots split by thin lines into blocks of four by four dots. A thick square outlines nine blocks centred on a shaded block labelled c. A dashed square outlines the window of c and lies one dot outside the thick square on every side. A red rectangular loop extends from inside c to four dots past the right side of c. Another shaded block, in the top right corner of the grid, holds two red dots joined by a short red edge.
Figure 2. The auxiliary decoder of Section 5.1 on a part of a code far from its sides, with block side L = 4 and window radius R = 5, given by the formula R = (3/2)L − 1 of the registered program of Section 5.4; dots are checks and thin lines bound the blocks. The window W_c of block c (dashed) consists of the checks within ℓ∞ distance R of c; it reaches beyond N₁(c) (thick), the nine blocks at block distance at most 1 from c. Stage 1 computes a correction for each block from the syndrome in its window and keeps the edges that the block owns; the kept edges form C₀. A block is bad if the residual syndrome has a check in it (flagged; filled dots) or if a path of F = E ⊕ C₀ (red edges) inside N₁(c) joins it to a check at ℓ∞ distance at least L (long; the loop through c reaches distance L from c and makes c long, but it stays within distance 3 < L of the block to the right of c, which is good). Bad blocks are shaded.