Proof of a finite threshold for the union-find decoder

• URL: http://arxiv.org/abs/2602.20238v1
• Date: Mon, 23 Feb 2026 19:00:00 GMT
• Title: Proof of a finite threshold for the union-find decoder
• Authors: Satoshi Yoshida, Ethan Lake, Hayata Yamasaki,
• Abstract summary: We provide a proof of a finite threshold for the union-find (UF) decoder on the surface code under the circuit-level local error model.<n>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.<n>These results provide a solid theoretical foundation for the practical use of UF-based decoders in the development of fault-tolerant quantum computers.
• Score: 0.9558392439655014
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Approximate level-by-level maximum-likelihood decoding based on the Chase algorithm for high-rate concatenated stabilizer codes [0.0]
  It is essential to encode logical qubits using quantum error-correcting codes.<n>High-rated codes have attracted attention due to theoretical advances in fault-tolerant protocols.<n>We propose a general, high-performance decoder for high-rated stabilizer codes.
  arXiv  Detail & Related papers  (2026-01-26T18:04:29Z)
• Generalization Bounds for Transformer Channel Decoders [61.55280736553095]
  This paper studies the generalization performance of ECCT from a learning-theoretic perspective.<n>To the best of our knowledge, this work provides the first theoretical generalization guarantees for this class of decoders.
  arXiv  Detail & Related papers  (2026-01-11T15:56:37Z)
• Toward Uncertainty-Aware and Generalizable Neural Decoding for Quantum LDPC Codes [0.9453554184019106]
  Quantum error correction (QEC) is essential for scalable quantum computing.<n>We propose textbfQuBA, a Bayesian graph neural decoder that integrates attention to both dot-product and multi-head.<n>We further develop textbfSAGU textbf(Sequential Aggregate Generalization under Uncertainty), a multi-code training framework with enhanced cross-domain robustness.
  arXiv  Detail & Related papers  (2025-10-05T01:08:39Z)
• BF-Max: an Efficient Bit Flipping Decoder with Predictable Decoding Failure Rate [6.209770040937912]
  Bit-Flipping (BF) decoder is widely employed in post-quantum cryptographic schemes.<n>For security concerns, one must guarantee that the Decoding Failure Rate (DFR) is negligible.<n>We introduce a new version of the BF decoder, that we call BF-Max, characterized by the fact that in each iteration only one bit (the least reliable) is flipped.
  arXiv  Detail & Related papers  (2025-06-11T13:04:05Z)
• Linear Time Iterative Decoders for Hypergraph-Product and Lifted-Product Codes [3.8748565070264753]
  Quantum low-density parity-check (QLDPC) codes are prominent candidates for achieving fault-tolerant quantum computation.<n>Numerous studies advocate for the necessity of fast decoders to fully harness the capabilities of QLDPC codes.<n>However, empirical investigations indicate that such iterative decoders are susceptible to having a high error floor while decoding QLDPC codes.
  arXiv  Detail & Related papers  (2025-04-02T13:37:29Z)
• Testing the Accuracy of Surface Code Decoders [55.616364225463066]
  Large-scale, fault-tolerant quantum computations will be enabled by quantum error-correcting codes (QECC) This work presents the first systematic technique to test the accuracy and effectiveness of different QECC decoding schemes.
  arXiv  Detail & Related papers  (2023-11-21T10:22:08Z)
• Modular decoding: parallelizable real-time decoding for quantum computers [55.41644538483948]
  Real-time quantum computation will require decoding algorithms capable of extracting logical outcomes from a stream of data generated by noisy quantum hardware. We propose modular decoding, an approach capable of addressing this challenge with minimal additional communication and without sacrificing decoding accuracy. We introduce the edge-vertex decomposition, a concrete instance of modular decoding for lattice-surgery style fault-tolerant blocks.
  arXiv  Detail & Related papers  (2023-03-08T19:26:10Z)
• Deep Quantum Error Correction [73.54643419792453]
  Quantum error correction codes (QECC) are a key component for realizing the potential of quantum computing. In this work, we efficiently train novel emphend-to-end deep quantum error decoders. The proposed method demonstrates the power of neural decoders for QECC by achieving state-of-the-art accuracy.
  arXiv  Detail & Related papers  (2023-01-27T08:16:26Z)
• Neural Belief Propagation Decoding of Quantum LDPC Codes Using Overcomplete Check Matrices [60.02503434201552]
  We propose to decode QLDPC codes based on a check matrix with redundant rows, generated from linear combinations of the rows in the original check matrix. This approach yields a significant improvement in decoding performance with the additional advantage of very low decoding latency.
  arXiv  Detail & Related papers  (2022-12-20T13:41:27Z)
• A Practical and Scalable Decoder for Topological Quantum Error Correction with Digital Annealer [0.5658123802733283]
  We propose an efficient and scalable decoder for quantum error correction using Fujitsu Digital Annealer (DA) In particular, we implement the proposed DA decoder for the surface code and perform detailed numerical experiments for various code to see its performance and scalability. It is also shown that the DA decoder has advantages over the Union-Find (UF) decoder from a variety of perspectives including hardware implementation.
  arXiv  Detail & Related papers  (2022-03-29T07:48:51Z)
• Improved decoding of circuit noise and fragile boundaries of tailored surface codes [61.411482146110984]
  We introduce decoders that are both fast and accurate, and can be used with a wide class of quantum error correction codes. Our decoders, named belief-matching and belief-find, exploit all noise information and thereby unlock higher accuracy demonstrations of QEC. We find that the decoders led to a much higher threshold and lower qubit overhead in the tailored surface code with respect to the standard, square surface code.
  arXiv  Detail & Related papers  (2022-03-09T18:48:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.