quant-ph — Quantum Physics

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

Contributed by Tejasvi Singh Tomar

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, with confidence $1-10^{-9}$ each, the optimal threshold of the planar code is at least $0.103$ under bit flips and at least $0.02$ under phenomenological noise. Each statistical certificate bounds the failure probability of an auxiliary decoder that divides the code into blocks and corrects each block using a window around it; optimal decoding does at least as well, so the bound also holds for optimal decoding. A deterministic lemma shows that the auxiliary decoder fails only if bad blocks, in which the window corrections leave a defect or a long residual path, form a sparse hierarchy that joins the two rough boundaries. This gives an explicit bound once every block is bad with probability below a limit, about $4\times10^{-4}$ under bit flips, and a pre-registered Monte Carlo experiment bounds these probabilities. The confidence rests on a binomial model of the counts of bad blocks and on two tested properties of each decoding program. All these results are proved in the proof assistant Lean 4, the statistical ones with the binomial model and the two properties as hypotheses.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.24048739