pith. machine review for the scientific record. sign in

arxiv: 2602.20238 · v2 · submitted 2026-02-23 · 🪐 quant-ph

Recognition: 1 theorem link

· Lean Theorem

Proof of a finite threshold for the union-find decoder

Satoshi Yoshida , Ethan Lake , Hayata Yamasaki
Authors on Pith no claims yet

Pith reviewed 2026-05-15 20:10 UTC · model grok-4.3

classification 🪐 quant-ph
keywords union-find decodersurface codefinite thresholdfault toleranceerror clusteringquantum error correctionlocal stochastic noisegreedy decoder
0
0 comments X

The pith

The union-find decoder achieves a finite threshold on the surface code under circuit-level local stochastic noise.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that the union-find decoder for surface codes has a positive error threshold, meaning logical errors can be suppressed to arbitrarily low levels below some nonzero physical error rate. This matters because the decoder is fast and empirically strong, but lacked a rigorous guarantee that it supports fault tolerance outside simulated regimes. The authors introduce a refined error-clustering framework that separates clusters with larger buffers than earlier methods, giving analytical control over decoder behavior. The same framework also bounds the parallel runtime and establishes a threshold for the simpler greedy decoder.

Core claim

We prove a finite threshold for the union-find decoder on the surface code under the circuit-level local stochastic error model. By extending prior error-clustering techniques to allow substantially larger buffers between clusters, we obtain analytical control over the decoder's output, showing that below a positive error rate the probability of logical failure vanishes with code distance. The framework additionally yields a quasi-polylogarithmic upper bound on the average runtime of a parallel implementation and proves a finite threshold for the greedy decoder.

What carries the argument

Refined error-clustering framework that separates error clusters by substantially larger buffers than prior methods

If this is right

  • Below the threshold the logical error rate falls exponentially with code distance.
  • A parallel implementation of the union-find decoder has average runtime at most quasi-polylogarithmic in code size.
  • The same clustering argument proves a finite threshold for the greedy decoder.
  • The results supply a theoretical foundation for deploying union-find-based decoders in fault-tolerant quantum hardware.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The larger-buffer clustering technique could be adapted to prove thresholds for other surface-code decoders that rely on local corrections.
  • Numerical extraction of the explicit threshold value from the framework would allow direct comparison with simulated performance.
  • The runtime bound suggests the decoder remains efficient even for code distances needed in large-scale quantum algorithms.
  • Extensions to non-local or correlated error models may follow by adjusting the buffer construction inside the clustering step.

Load-bearing premise

The refined error-clustering framework can separate error clusters by substantially larger buffers than prior methods, thereby enabling analytical control over the behavior of the UF decoder.

What would settle it

A direct calculation or Monte Carlo simulation showing that, at any positive error rate, error clusters cannot be separated by the claimed buffer sizes with probability that tends to one as code size grows, or that the logical failure rate fails to decrease exponentially with distance below some nonzero rate.

Figures

Figures reproduced from arXiv: 2602.20238 by Ethan Lake, Hayata Yamasaki, Satoshi Yoshida.

Figure 1
Figure 1. Figure 1: FIG. 1. Illustration of a rotated surface code with distance [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2. The logical error can happen only if the extended UF [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3. (a) Illustration of the distance chain in Eq. ( [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: FIG. 4. An example of error locations where the greedy [PITH_FULL_IMAGE:figures/full_fig_p012_4.png] view at source ↗
read the original abstract

Fast decoders that achieve strong error suppression are essential for fault-tolerant quantum computation (FTQC) from both practical and theoretical perspectives. The union-find (UF) decoder for the surface code is widely regarded as a promising candidate, offering almost-linear time complexity and favorable empirical error suppression supported by numerical evidence. However, the lack of a rigorous threshold theorem has left open whether the UF decoder can achieve fault tolerance beyond the error models and parameter regimes tested in numerical simulations. Here, we provide a rigorous proof of a finite threshold for the UF decoder on the surface code under the circuit-level local stochastic error model. To this end, we develop a refined error-clustering framework that extends techniques previously used to analyze cellular-automaton and renormalization-group decoders, by showing that error clusters can be separated by substantially larger buffers, thereby enabling analytical control over the behavior of the UF decoder. Using this guarantee, we further prove a quasi-polylogarithmic upper bound on the average runtime of a parallel UF decoder in terms of the code size. We also show that this framework yields a finite threshold for the greedy decoder, a simpler decoder with lower complexity but weaker empirical error suppression. These results provide a solid theoretical foundation for the practical use of UF-based decoders in the development of fault-tolerant quantum computers, while offering a unified framework for studying fault tolerance across these practical decoders.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The manuscript claims to prove a finite threshold for the union-find (UF) decoder on the surface code under the circuit-level local stochastic error model. It develops a refined error-clustering framework extending prior cellular-automaton and renormalization-group techniques by separating error clusters with substantially larger buffers, thereby granting analytical control over UF cluster growth and union operations. The paper also derives a quasi-polylogarithmic upper bound on the average runtime of a parallel UF decoder and shows that the same framework yields a finite threshold for the simpler greedy decoder.

Significance. If the central clustering argument holds, the result would be significant: it supplies the first rigorous threshold theorem for the UF decoder, a decoder already valued for its near-linear runtime and strong empirical performance. Establishing fault tolerance under the circuit-level model would provide a theoretical foundation for deploying UF-based decoders in fault-tolerant quantum computation and would unify the analysis of several practical decoders within one framework. The additional quasi-polylogarithmic runtime bound is a concrete practical contribution.

major comments (1)
  1. [Abstract / refined error-clustering framework] Abstract (refined error-clustering framework): the claim that substantially larger buffers separate clusters and thereby control UF behavior is load-bearing for the finite-threshold result. Under the circuit-level local stochastic model, gate-induced error propagation can produce effective long-range correlations within a single time step. The manuscript must supply an explicit calculation showing that the probability of a UF union operation bridging the chosen buffer still decays exponentially in distance; without this bound, the separation guarantee does not automatically imply the threshold.
minor comments (1)
  1. [Abstract] The abstract states a 'quasi-polylogarithmic' runtime bound but does not define the precise polylog factors or the parallel model used; a short clarification in the introduction would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their thorough reading, positive evaluation of the significance of the result, and constructive feedback on the refined error-clustering framework. We address the major comment below and will revise the manuscript to strengthen the presentation of the key probabilistic bound.

read point-by-point responses

  1. Referee: Abstract (refined error-clustering framework): the claim that substantially larger buffers separate clusters and thereby control UF behavior is load-bearing for the finite-threshold result. Under the circuit-level local stochastic model, gate-induced error propagation can produce effective long-range correlations within a single time step. The manuscript must supply an explicit calculation showing that the probability of a UF union operation bridging the chosen buffer still decays exponentially in distance; without this bound, the separation guarantee does not automatically imply the threshold.

    Authors: We agree that an explicit bound on the bridging probability is essential for rigor under the circuit-level model. The manuscript already derives this in the proof of the main threshold theorem (Section 4), where the buffer size is chosen proportionally to the logarithm of the code distance to absorb single-time-step propagation from CNOT and measurement errors. The local stochastic error model is used to bound the probability that a cluster grows across the buffer by a factor of at most (O(p))^{buffer/2}, which decays exponentially in the buffer distance even after accounting for the finite-range correlations induced by gates. To make this calculation more self-contained and address the referee's concern directly, we will add a dedicated lemma (new Lemma 4.3) that isolates the union-operation probability and provides the explicit exponential decay estimate with all constants tracked. revision: yes

Circularity Check

0 steps flagged

Refined clustering extends external prior techniques; no reduction of threshold to fitted input or self-definition

full rationale

The derivation introduces a refined error-clustering framework that extends techniques from prior CA/RG decoder analyses by establishing larger buffer separations. This is presented as enabling analytical control over UF behavior under the circuit-level local stochastic model, with an explicit quasi-polylog runtime bound derived from the separation guarantee. No equation or step reduces the threshold existence to a parameter fitted from the target UF performance itself, nor does any central claim rest on a self-citation chain that is unverified outside the paper. Self-citations to clustering methods are present but serve only as starting points for the new buffer-size extension, which is independently argued. The proof chain therefore remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The proof rests on the local stochastic error model and the new clustering separation guarantee; no free parameters or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption Circuit-level local stochastic error model
    Standard assumption for realistic quantum noise; invoked to define the error distribution under which the threshold holds.

pith-pipeline@v0.9.0 · 5540 in / 1110 out tokens · 39702 ms · 2026-05-15T20:10:08.505038+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

83 extracted references · 83 canonical work pages · 15 internal anchors

  1. [1]

    Proof.We show this lemma by induction onk

    any level-kextended UF cluster ˜Ct stops growing before merging with other level-k ′(k′ ≥k)extended UF clusters; 2.m k ≤ dk+1 2fk . Proof.We show this lemma by induction onk. Fork= 0, any level-0 clusterChas diameter at mostd 0 + 1, and buffer at leastb 0 −1 =f 0(b0 −1)> d 0 + 1. Therefore, any level-0 extended UF cluster ˜Ct stops growing before merging ...

    work page

  2. [2]

    B. M. Terhal, Quantum error correction for quan- tum memories, Rev. Mod. Phys.87, 307 (2015), arXiv:1302.3428

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  3. [3]

    A. A. Kovalev and L. P. Pryadko, Fault tolerance of quantum low-density parity check codes with sublin- ear distance scaling, Phys. Rev. A87, 020304 (2013), arXiv:1208.2317

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  4. [4]

    Fault-Tolerant Quantum Computation with Constant Overhead

    D. Gottesman, Fault-Tolerant Quantum Computation with Constant Overhead, Quantum Info. Comput.14, 1338–1372 (2014), arXiv:1310.2984

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  5. [5]

    Fawzi, A

    O. Fawzi, A. Grospellier, and A. Leverrier, Constant overhead quantum fault-tolerance with quantum ex- pander codes, in2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)(2018) pp. 743–754, arXiv:1808.03821

    work page arXiv 2018

  6. [6]

    Yamasaki and M

    H. Yamasaki and M. Koashi, Time-Efficient Constant- Space-Overhead Fault-Tolerant Quantum Computation, Nat. Phys.20, 247 (2024), arXiv:2207.08826

    work page arXiv 2024

  7. [7]

    Tamiya, M

    S. Tamiya, M. Koashi, and H. Yamasaki, Fault-tolerant quantum computation with polylogarithmic time and constant space overheads, Nat. Phys.22, 27 (2025), arXiv:2411.03683

    work page arXiv 2025

  8. [8]

    Q. T. Nguyen and C. A. Pattison, Quantum fault tol- erance with constant-space and logarithmic-time over- heads, inProceedings of the 57th Annual ACM Sympo- sium on Theory of Computing, STOC ’25 (Association for Computing Machinery, New York, NY, USA, 2025) p. 730–737

    work page 2025

  9. [9]

    Takada and H

    Y. Takada and H. Yamasaki, Doubly-polylog-time- overhead fault-tolerant quantum computation by a polylog-time parallel minimum-weight perfect matching decoder, arXiv:2503.13601 (2025)

    work page arXiv 2025

  10. [10]

    Fault-Tolerant Quantum Computation With Constant Error Rate

    D. Aharonov and M. Ben-Or, Fault-Tolerant Quantum Computation with Constant Error Rate, inProceedings of the twenty-ninth annual ACM symposium on Theory of computing(1997) pp. 176–188, arXiv:quant-ph/9906129

    work page internal anchor Pith review Pith/arXiv arXiv 1997

  11. [11]

    Knill, R

    E. Knill, R. Laflamme, and W. H. Zurek, Resilient Quan- tum Computation, Science279, 342 (1998), arXiv:quant- ph/9702058

    work page arXiv 1998

  12. [12]

    Aliferis, D

    P. Aliferis, D. Gottesman, and J. Preskill, Quantum accuracy threshold for concatenated distance-3 codes, Quantum Info. Comput.6, 97–165 (2006), arXiv:quant- ph/0504218

    work page arXiv 2006

  13. [13]

    Topological quantum memory

    E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, Topo- logical quantum memory, J. Math. Phys.43, 4452 (2002), arXiv:quant-ph/0110143

    work page internal anchor Pith review Pith/arXiv arXiv 2002

  14. [14]

    A. G. Fowler, Proof of Finite Surface Code Thresh- old for Matching, Phys. Rev. Lett.109, 180502 (2012), arXiv:1206.0800

    work page internal anchor Pith review Pith/arXiv arXiv 2012

  15. [15]

    Analytic and numerical demonstration of quantum self-correction in the 3D Cubic Code

    S. Bravyi and J. Haah, Quantum Self-Correction in the 3D Cubic Code Model, Phys. Rev. Lett.111, 200501 (2013), arXiv:1112.3252

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  16. [16]

    J. W. Harrington,Analysis of quantum error-correcting codes: Symplectic lattice codes and toric codes, Ph.D. the- sis, California Institute of Technology (2004)

    work page 2004

  17. [17]

    Cellular-automaton decoders for topological quantum memories

    M. Herold, E. T. Campbell, J. Eisert, and M. J. Kas- toryano, Cellular-automaton decoders for topological quantum memories, npj Quantum Inf.1, 15010 (2015), arXiv:1406.2338

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  18. [18]

    Cellular-automaton decoders with provable thresholds for topological codes

    A. Kubica and J. Preskill, Cellular-Automaton Decoders with Provable Thresholds for Topological Codes, Phys. Rev. Lett.123, 020501 (2019), arXiv:1809.10145

    work page internal anchor Pith review Pith/arXiv arXiv 2019

  19. [19]

    Vasmer, D

    M. Vasmer, D. E. Browne, and A. Kubica, Cellular au- tomaton decoders for topological quantum codes with noisy measurements and beyond, Sci. Rep.11, 2027 (2021), arXiv:2004.07247

    work page arXiv 2027

  20. [20]

    Balasubramanian, M

    S. Balasubramanian, M. Davydova, and E. Lake, A lo- cal automaton for the 2D toric code, arXiv:2412.19803 (2024)

    work page arXiv 2024

  21. [21]

    Lake, Fast offline decoding with local message-passing automata, arXiv:2506.03266 (2025)

    E. Lake, Fast offline decoding with local message-passing automata, arXiv:2506.03266 (2025)

    work page arXiv 2025

  22. [22]

    Lake, Local active error correction from simulated con- finement, arXiv:2510.08056 (2025)

    E. Lake, Local active error correction from simulated con- finement, arXiv:2510.08056 (2025)

    work page arXiv 2025

  23. [23]

    Panteleev and G

    P. Panteleev and G. Kalachev, Degenerate quantum LDPC codes with good finite length performance, Quan- tum5, 585 (2021), arXiv:1904.02703

    work page arXiv 2021

  24. [24]

    Roffe, D

    J. Roffe, D. R. White, S. Burton, and E. Camp- bell, Decoding across the quantum low-density parity- check code landscape, Phys. Rev. Res.2, 043423 (2020), arXiv:2005.07016

    work page arXiv 2020

  25. [25]

    Decoding Small Surface Codes with Feedforward Neural Networks

    S. Varsamopoulos, B. Criger, and K. Bertels, De- coding Small Surface Codes with Feedforward Neural Networks, Quantum Sci. Technol.3, 015004 (2017), arXiv:1705.00857

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  26. [26]

    Davaasuren, Y

    A. Davaasuren, Y. Suzuki, K. Fujii, and M. Koashi, General framework for constructing fast and near- optimal machine-learning-based decoder of the topolog- ical stabilizer codes, Phys. Rev. Res.2, 033399 (2020), arXiv:1801.04377

    work page arXiv 2020

  27. [27]

    Bausch, A

    J. Bausch, A. W. Senior, F. J. Heras, T. Edlich, A. Davies, M. Newman, C. Jones, K. Satzinger, M. Y. Niu, S. Blackwell,et al., Learning high-accuracy error de- coding for quantum processors, Nature635, 834 (2024), 13 arXiv:2310.05900

    work page arXiv 2024

  28. [28]

    A. Y. Kitaev, Fault-tolerant quantum computation by anyons, Ann. Phys.303, 2 (2003), arXiv:quant- ph/9707021

    work page arXiv 2003

  29. [29]

    A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, Surface codes: Towards practical large-scale quantum computation, Phys. Rev. A86, 032324 (2012), arXiv:1208.0928

    work page internal anchor Pith review Pith/arXiv arXiv 2012

  30. [30]

    Google Quantum AI, Suppressing quantum errors by scaling a surface code logical qubit, Nature614, 676 (2023), arXiv:2207.06431

    work page arXiv 2023

  31. [31]

    Bluvstein, S

    D. Bluvstein, S. J. Evered, A. A. Geim, S. H. Li, H. Zhou, T. Manovitz, S. Ebadi, M. Cain, M. Kalinowski, D. Hangleiter,et al., Logical quantum processor based on reconfigurable atom arrays, Nature626, 58 (2024), arXiv:2312.03982

    work page arXiv 2024

  32. [32]

    Google Quantum AI and Collaborators, Quantum error correction below the surface code threshold, Nature638, 920 (2025), arXiv:2408.13687

    work page arXiv 2025

  33. [33]

    T. He, W. Lin, R. Wang, Y. Li, J. Bei, J. Cai, S. Cao, D. Chen, K. Chen, X. Chen,et al., Experimental Quan- tum Error Correction below the Surface Code Threshold via All-Microwave Leakage Suppression, Phys. Rev. Lett. 135, 260601 (2025)

    work page 2025

  34. [34]

    Higgott, Pymatching: A python package for decoding quantum codes with minimum-weight perfect matching, ACM Transactions on Quantum Computing3, 1 (2022), arXiv:2105.13082

    O. Higgott, Pymatching: A python package for decoding quantum codes with minimum-weight perfect matching, ACM Transactions on Quantum Computing3, 1 (2022), arXiv:2105.13082

    work page arXiv 2022

  35. [35]

    Higgott and C

    O. Higgott and C. Gidney, Sparse blossom: correcting a million errors per core second with minimum-weight matching, Quantum9, 1600 (2025), arXiv:2303.15933

    work page arXiv 2025

  36. [36]

    Wu and L

    Y. Wu and L. Zhong, Fusion Blossom: Fast MWPM De- coders for QEC, in2023 IEEE International Conference on Quantum Computing and Engineering (QCE), Vol. 1 (IEEE, 2023) pp. 928–938, arXiv:2305.08307

    work page arXiv 2023

  37. [37]

    Y. Wu, N. Liyanage, and L. Zhong, Micro blossom: Accelerated minimum-weight perfect matching decoding for quantum error correction, inProceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Vol- ume 2(2025) pp. 639–654, arXiv:2502.14787

    work page arXiv 2025

  38. [38]

    Delfosse and N

    N. Delfosse and N. H. Nickerson, Almost-linear time de- coding algorithm for topological codes, Quantum5, 595 (2021), arXiv:1709.06218

    work page arXiv 2021

  39. [39]

    A simple decoder for topological codes

    J. Wootton, A Simple Decoder for Topological Codes, Entropy17, 1946 (2015), arXiv:1310.2393

    work page internal anchor Pith review Pith/arXiv arXiv 1946

  40. [40]

    Barber, K

    B. Barber, K. M. Barnes, T. Bialas, O. Bu˘ gdaycı, E. T. Campbell, N. I. Gillespie, K. Johar, R. Rajan, A. W. Richardson, L. Skoric,et al., A real-time, scalable, fast and resource-efficient decoder for a quantum computer, Nat. Electron.8, 84 (2025), arXiv:2309.05558

    work page arXiv 2025

  41. [41]

    Liyanage, Y

    N. Liyanage, Y. Wu, S. Tagare, and L. Zhong, FPGA-based Distributed Union-Find Decoder for Sur- face Codes, IEEE Trans. Quantum Eng.5, 1 (2024), arXiv:2406.08491

    work page arXiv 2024

  42. [42]

    Maurya, T

    S. Maurya, T. Maurer, M. B¨ uhler, D. Vandeth, and M. E. Beverland, FPGA-tailored algorithms for real-time decoding of quantum LDPC codes, arXiv:2511.21660 (2025)

    work page arXiv 2025

  43. [43]

    Holmes, M

    A. Holmes, M. R. Jokar, G. Pasandi, Y. Ding, M. Pe- dram, and F. T. Chong, Nisq+: Boosting quantum com- puting power by approximating quantum error correc- tion, in2020 ACM/IEEE 47th annual international sym- posium on computer architecture (ISCA)(IEEE, 2020) pp. 556–569, arXiv:2004.04794

    work page arXiv 2020

  44. [44]

    Y. Ueno, M. Kondo, M. Tanaka, Y. Suzuki, and Y. Tabuchi, QECOOL: On-Line Quantum Error Correc- tion with a Superconducting Decoder for Surface Code, in2021 58th ACM/IEEE Design Automation Conference (DAC)(IEEE, 2021) pp. 451–456, arXiv:2103.14209

    work page arXiv 2021

  45. [45]

    W. Liao, Y. Suzuki, T. Tanimoto, Y. Ueno, and Y. Tokunaga, WIT-Greedy: Hardware System Design of Weighted ITerative Greedy Decoder for Surface Code, in Proceedings of the 28th Asia and South Pacific Design Automation Conference(2023) pp. 209–215

    work page 2023

  46. [46]

    Improved HDRG decoders for qudit and non-Abelian quantum error correction

    A. Hutter, D. Loss, and J. R. Wootton, Improved HDRG decoders for qudit and non-Abelian quantum error correction, New J. Phys.17, 035017 (2015), arXiv:1410.4478

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  47. [47]

    E. M. Reingold and R. E. Tarjan, On a Greedy Heuristic for Complete Matching, SIAM Journal on Computing10, 676 (1981)

    work page 1981

  48. [48]

    G´ acs, Reliable computation with cellular automata, J

    P. G´ acs, Reliable computation with cellular automata, J. Comput. Syst. Sci.32, 15 (1986)

    work page 1986

  49. [49]

    G´ acs, Reliable cellular automata with self- organization, J

    P. G´ acs, Reliable cellular automata with self- organization, J. Stat. Phys.103, 45 (2001), arXiv:math/0003117

    work page arXiv 2001

  50. [50]

    A. G. Fowler, Minimum weight perfect matching of fault- tolerant topological quantum error correction in average O(1) parallel time, Quantum Info. Comput.15, 145–158 (2015), arXiv:1307.1740

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  51. [51]

    Optimal Resources for Topological 2D Stabilizer Codes: Comparative Study

    H. Bombin and M. A. Martin-Delgado, Optimal re- sources for topological two-dimensional stabilizer codes: Comparative study, Phys. Rev. A76, 012305 (2007), arXiv:quant-ph/0703272

    work page internal anchor Pith review Pith/arXiv arXiv 2007

  52. [52]

    Delfosse and G

    N. Delfosse and G. Z´ emor, Linear-time maximum like- lihood decoding of surface codes over the quantum erasure channel, Phys. Rev. Res.2, 033042 (2020), arXiv:1703.01517

    work page arXiv 2020

  53. [53]

    Skoric, D

    L. Skoric, D. E. Browne, K. M. Barnes, N. I. Gillespie, and E. T. Campbell, Parallel window decoding enables scalable fault tolerant quantum computation, Nat. Com- mun.14, 7040 (2023), arXiv:2209.08552

    work page arXiv 2023

  54. [54]

    X. Tan, F. Zhang, R. Chao, Y. Shi, and J. Chen, Scalable surface-code decoders with parallelization in time, PRX Quantum4, 040344 (2023), arXiv:2209.09219

    work page arXiv 2023

  55. [55]

    Bomb´ ın, C

    H. Bomb´ ın, C. Dawson, Y.-H. Liu, N. Nickerson, F. Pastawski, and S. Roberts, Modular decoding: par- allelizable real-time decoding for quantum computers, arXiv:2303.04846 (2023)

    work page arXiv 2023

  56. [56]

    Horsman, A

    D. Horsman, A. G. Fowler, S. Devitt, and R. V. Meter, Surface code quantum computing by lattice surgery, New J. Phys.14, 123011 (2012)

    work page 2012

  57. [57]

    M. Cain, C. Zhao, H. Zhou, N. Meister, J. P. B. Ataides, A. Jaffe, D. Bluvstein, and M. D. Lukin, Correlated De- coding of Logical Algorithms with Transversal Gates, Phys. Rev. Lett.133, 240602 (2024), arXiv:2403.03272

    work page arXiv 2024

  58. [58]

    H. Zhou, C. Zhao, M. Cain, D. Bluvstein, N. Maskara, C. Duckering, H.-Y. Hu, S.-T. Wang, A. Kubica, and M. D. Lukin, Low-overhead transversal fault tolerance for universal quantum computation, Nature646, 303 (2025), arXiv:2406.17653

    work page arXiv 2025

  59. [59]

    M. Cain, D. Bluvstein, C. Zhao, S. Gu, N. Maskara, M. Kalinowski, A. A. Geim, A. Kubica, M. D. Lukin, and H. Zhou, Fast correlated decoding of transversal log- ical algorithms, arXiv:2505.13587 (2025)

    work page arXiv 2025

  60. [60]

    Delfosse, V

    N. Delfosse, V. Londe, and M. E. Beverland, Toward a Union-Find decoder for quantum LDPC codes, IEEE 14 Trans. Inf. Theory68, 3187 (2022), arXiv:2103.08049

    work page arXiv 2022

  61. [61]

    Tillich and G

    J.-P. Tillich and G. Z´ emor, Quantum ldpc codes with positive rate and minimum distance proportional to the square root of the blocklength, IEEE Transactions on Information Theory60, 1193 (2014)

    work page 2014

  62. [62]

    Leverrier, J.-P

    A. Leverrier, J.-P. Tillich, and G. Z´ emor, Quantum ex- pander codes, in2015 IEEE 56th Annual Symposium on Foundations of Computer Science(2015) pp. 810–824

    work page 2015

  63. [63]

    Panteleev and G

    P. Panteleev and G. Kalachev, Quantum ldpc codes with almost linear minimum distance, IEEE Transactions on Information Theory68, 213 (2022)

    work page 2022

  64. [64]

    Bravyi, A

    S. Bravyi, A. W. Cross, J. M. Gambetta, D. Maslov, P. Rall, and T. J. Yoder, High-threshold and low- overhead fault-tolerant quantum memory, Nature627, 778 (2024)

    work page 2024

  65. [65]

    Panteleev and G

    P. Panteleev and G. Kalachev, Asymptotically good quantum and locally testable classical ldpc codes, inPro- ceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022 (Association for Computing Machinery, New York, NY, USA, 2022) p. 375–388

    work page 2022

  66. [66]

    Leverrier and G

    A. Leverrier and G. Zemor, Quantum Tanner codes , in2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)(IEEE Computer Society, Los Alamitos, CA, USA, 2022) pp. 872–883

    work page 2022

  67. [67]

    Dinur, M.-H

    I. Dinur, M.-H. Hsieh, T.-C. Lin, and T. Vidick, Good quantum ldpc codes with linear time decoders, inPro- ceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023 (Association for Computing Machinery, New York, NY, USA, 2023) p. 905–918

    work page 2023

  68. [68]

    Chan and S

    T. Chan and S. C. Benjamin, Actis: A Strictly Lo- cal Union–Find Decoder, Quantum7, 1183 (2023), arXiv:2305.18534

    work page arXiv 2023

  69. [69]

    McEwen, D

    M. McEwen, D. Bacon, and C. Gidney, Relaxing hard- ware requirements for surface code circuits using time- dynamics, Quantum7, 1172 (2023), arXiv:2302.02192. [69]https://github.com/quantumlib/Stim/blob/ 3ed7ffc7bc00e999dd950a3527a41d636b9ff37b/doc/ getting_started.ipynb(2026). ACKNOWLEDGMENTS EL and HY discussed part of this work during the KIAS workshop ...

    work page arXiv 2023

  70. [70]

    16 RX RZ RX RX RX RZ RZ RZ MX MZ MX MX MX MZ MZ MZ FIG

    Reset step: Reset the states of the measurement qubits⃗ r fX in|+⟩and⃗ r fZ in|0⟩for allf X ∈F X andf Z ∈F Z. 16 RX RZ RX RX RX RZ RZ RZ MX MZ MX MX MX MZ MZ MZ FIG. S1. Syndrome extraction circuit for the surface code with distanced= 3, where time flows from left to right. RX and RZ represent the reset operations to|+⟩and|0⟩, respectively. MX and MZ repr...

    work page

  71. [71]

    CNOT steps: Apply the CNOT gates in the following ordering: ( CNOT⃗ rfX ,⃗ rfX +⃗ eLT ∀fX ∈F bulk X ⊔F x=d−1 X CNOT⃗ rfZ +⃗ eLT ,⃗ rfX ∀fZ ∈F bulk Z ⊔F y=0 Z ,(S6) ( CNOT⃗ rfX ,⃗ rfX +⃗ eLB ∀fX ∈F bulk X ⊔F x=d−1 X CNOT⃗ rfZ +⃗ eRT ,⃗ rfX ∀fZ ∈F bulk Z ⊔F y=0 Z ,(S7) ( CNOT⃗ rfX ,⃗ rfX +⃗ eRT ∀fX ∈F bulk X ⊔F x=0 X CNOT⃗ rfZ +⃗ eLB ,⃗ rfX ∀fZ ∈F bulk Z ⊔F...

    work page

  72. [72]

    Measure the measurement qubits⃗ rfX inXbasis and⃗ r fZ inZbasis for allf X ∈F X andf Z ∈F Z, We repeat the syndrome extraction circuit fordtimes, and we write the measurement outcome of the measurement qubit⃗ rf in thei-th syndrome extraction circuit as mf,i ∈ {0,1}(S11) forf∈F X ⊔F Z andi∈[d]. We define the detectors ˆm f,i ∈ {0,1}by ˆmf,i := ( mf,0 (i= ...

    work page

  73. [73]

    The distancedist(v, v ′)between two verticesv, v ′ ∈Vis defined by the length of the shortest path connectingv andv ′

    work page

  74. [74]

    The line graphL(G)is defined by a graph whose set of vertices is given byE, and the set of edges is given by {(e, e′)∈E 2 |eande ′ are adjacent in the graphG}.(S17)

    work page

  75. [75]

    The distancedist(e, e ′)between two edgese, e ′ ∈Eis defined by the distance betweeneande ′ in the line graph L(G)

    work page

  76. [76]

    The distance between two subsets of edgesC, C ′ ⊂Eis defined by dist(C, C′) := min e∈C,e′∈C′ dist(e, e′).(S18)

    work page

  77. [77]

    The set of edges within a distancerof an edgeeis denoted byB e(r), i.e., Be(r) :={e ′ |dist(e, e ′)≤r}.(S19)

    work page

  78. [78]

    S2)).LetG= (V, E)be a graph, andN⊂E be a subset of edges

    The diameter of a subsetC⊂Eof edges is defined by diam(C) := max e,e′∈C dist(e, e′).(S20) Definition S3(Isolation and clustering of edges in graphs (see also Fig. S2)).LetG= (V, E)be a graph, andN⊂E be a subset of edges

    work page

  79. [79]

    Two edgese, e ′ ∈Nare called(r, R)-isolated ife ′ /∈Be(R)\B e(r), and otherwise called(r, R)-linked

    work page

  80. [80]

    An edgee∈Nis called(r, R)-isolated inNifeande ′ are(r, R)-isolated with alle ′ ∈N

    work page

Showing first 80 references.