HEXAGONbeta

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

A mix of human-written and AI-generated textHuman understanding: all partsquant-ph — Quantum Physicscs.IT — Information Theorymath-ph — Mathematical Physicsmath.ST — Statistics Theory

Contributed by Tejasvi Singh Tomar ↗

Version 1 / Nov 12, 2026 / CC BY 4.0

Abstract

Under independent bit flips, rigorous lower bounds on the threshold of the surface code from earlier work stay below 0.040.04, while numerical estimates place the optimal threshold near 0.1090.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.04650.0465 on the planar and rotated codes. We then give statistical certificates that, with confidence 1−10−91-10^{-9} each, the optimal threshold of the planar code is at least 0.1030.103 under bit flips and at least 0.020.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×10−44\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

References

  1. C. Amoruso and A. K. Hartmann, Domain-wall energies and magnetization of the two-dimensional random-bond I sing model , Phys. Rev. B 70 (2004), 134425.
  2. Paul Balister, B é la Bollob á s, and Mark Walters, Continuum percolation with steps in the square or the disc , Random Structures Algorithms 26 (2005), 392--403.
  3. Roger L. Berger, Multiparameter hypothesis testing and acceptance sampling , Technometrics 24 (1982), 295--300.
  4. Sergey Bravyi and Jeongwan Haah, Analytic and numerical demonstration of quantum self-correction in the 3D C ubic C ode , 2011, arXiv:1112.3252.arXiv
  5. C. J. Clopper and E. S. Pearson, The use of confidence or fiducial limits illustrated in the case of the binomial , Biometrika 26 (1934), 404--413.
  6. Olivier Couronn é , New upper bound for the connective constant for square-lattice self-avoiding walks , 2022, arXiv:2211.16146.arXiv
  7. Leonardo de Moura and Sebastian Ullrich, The L ean 4 theorem prover and programming language , Automated Deduction -- CADE 28, Lecture Notes in Comput. Sci., Springer, 2021, pp. 625--635.
  8. Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill, Topological quantum memory , J. Math. Phys. 43 (2002), 4452--4505.
  9. Ilya Dumer, Alexey A. Kovalev, and Leonid P. Pryadko, Thresholds for correcting errors, erasures, and faulty syndrome measurements in degenerate quantum codes , Phys. Rev. Lett. 115 (2015), 050502.
  10. Jack Edmonds, Paths, trees, and flowers , Canad. J. Math. 17 (1965), 449--467.
Show all 36 referencesShow fewer references
  1. Michael E. Fisher, Statistical mechanics of dimers on a plane lattice , Phys. Rev. 124 (1961), 1664--1672.
  2. Austin G. Fowler, Proof of finite surface code threshold for matching , Phys. Rev. Lett. 109 (2012), 180502.
  3. Christophe Garban and Thomas Spencer, Continuous symmetry breaking along the N ishimori line , J. Math. Phys. 63 (2022), 093302.
  4. Alan George, Nested dissection of a regular finite element mesh , SIAM J. Numer. Anal. 10 (1973), no. 2, 345--363.
  5. Oscar Higgott, PyMatching : a P ython package for decoding quantum codes with minimum-weight perfect matching , ACM Trans. Quantum Comput. 3 (2022), no. 3, 1--16.
  6. Oscar Higgott and Craig Gidney, Sparse B lossom: correcting a million errors per core second with minimum-weight matching , Quantum 9 (2025), 1600.
  7. T. Horiguchi and T. Morita, Existence of the ferromagnetic phase in a random-bond I sing model on the square lattice , J. Phys. A 15 (1982), L75--L80.
  8. M. Kac and J. C. Ward, A combinatorial solution of the two-dimensional I sing model , Phys. Rev. 88 (1952), 1332--1337.
  9. P. W. Kasteleyn, The statistics of dimers on a lattice , Physica 27 (1961), 1209--1225.
  10. Sun Woo P. Kim and Max McGinley, Mixed-state topological order and error-correction thresholds in non- A belian codes: rigorous results , 2026, arXiv:2607.21706.arXiv
  11. A. Yu. Kitaev, Fault-tolerant quantum computation by anyons , Ann. Physics 303 (2003), 2--30.
  12. Alexey A. Kovalev and Leonid P. Pryadko, Fault tolerance of quantum low-density parity check codes with sublinear distance scaling , Phys. Rev. A 87 (2013), 020304(R).
  13. Aleksander Kubica and John Preskill, Cellular-automaton decoders with provable thresholds for topological codes , Phys. Rev. Lett. 123 (2019), 020501.
  14. Lin Lin, Jianfeng Lu, Lexing Ying, Roberto Car, and Weinan E, Fast algorithm for extracting the diagonal of the inverse matrix with application to the electronic structure analysis of metallic systems , Commun. Math. Sci. 7 (2009), no. 3, 755--777.
  15. Lin Lin, Chao Yang, Juan C. Meza, Jianfeng Lu, Lexing Ying, and Weinan E, SelInv ---an algorithm for selected inversion of a sparse symmetric matrix , ACM Trans. Math. Software 37 (2011), no. 4, 1--19.
  16. H. Nishimori, Internal energy, specific heat and correlation function of the bond-random I sing model , Progr. Theoret. Phys. 66 (1981), 1169--1181.
  17. Takuya Ohno, Gaku Arakawa, Ikuo Ichinose, and Tetsuo Matsui, Phase structure of the random-plaquette Z2{Z}_2 gauge model: accuracy threshold for a toric quantum memory , Nuclear Phys. B 697 (2004), 462--480.
  18. Manaka Okuyama and Masayuki Ohzeki, Existence of a phase transition in the one-dimensional I sing spin glass model with long-range interactions on the N ishimori line , J. Phys. A 59 (2026), 305204.
  19. Francesco Parisen Toldin, Andrea Pelissetto, and Ettore Vicari, Strong-disorder paramagnetic-ferromagnetic fixed point in the square-lattice ±J\pm J I sing model , J. Statist. Phys. 135 (2009), 1039--1061.
  20. Yan Ru Pei, Vertical and reentrant ferromagnetic boundaries below the N ishimori point , 2026, arXiv:2609.37479.arXiv
  21. Andr é P ö nitz and Peter Tittmann, Improved upper bounds for self-avoiding walks in Zd\mathbb{Z}^d , Electron. J. Combin. 7 (2000), R21.
  22. Oliver Riordan and Mark Walters, Rigorous confidence intervals for critical probabilities , Phys. Rev. E 76 (2007), 011110.
  23. The mathlib Community , The L ean mathematical library , Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs, ACM, 2020, pp. 367--381.
  24. Tejasvi Singh Tomar, A matching threshold of 2×10−32\times10^{-3} for the rotated surface code under circuit-level noise , Zenodo, 2026, https://doi.org/10.5281/zenodo.23725694.DOI
  25. Chenyang Wang, Jim Harrington, and John Preskill, Confinement- H iggs transition in a disordered gauge theory and the accuracy threshold for quantum memory , Ann. Physics 303 (2003), 31--58.
  26. Satoshi Yoshida, Ethan Lake, and Hayata Yamasaki, Proof of a finite threshold for the union-find decoder , 2026, arXiv:2602.20238.arXiv

Version history

  1. v1 · 42 pagesSubmitted by Tejasvi Singh TomarPublished on Zenodo: https://doi.org/10.5281/zenodo.24048739CurrentNov 12, 2026