Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1709.02154 · Quantum

Multi-path Summation for Decoding 2D Topological Codes

Ben Criger, Imran Ashraf

Published Oct 19, 2018• 46 citations
arXivHTMLPDF

Abstract

Fault tolerance is a prerequisite for scalable quantum computing. Architectures based on 2D topological codes are effective for near-term implementations of fault tolerance. To obtain high performance with these architectures, we require a decoder which can adapt to the wide variety of error models present in experiments. The typical approach to the problem of decoding the surface code is to reduce it to minimum-weight perfect matching in a way that provides a suboptimal threshold error rate, and is specialized to correct a specific error model. Recently, optimal threshold error rates for a variety of error models have been obtained by methods which do not use minimum-weight perfect matching, showing that such thresholds can be achieved in polynomial time. It is an open question whether these results can also be achieved by minimum-weight perfect matching. In this work, we use belief propagation and a novel algorithm for producing edge weights to increase the utility of minimum-weight perfect matching for decoding surface codes. This allows us to correct depolarizing errors using the rotated surface code, obtaining a threshold of 17.76 ± 0.02 % . This is larger than the threshold achieved by previous matching-based decoders ( 14.88 ± 0.02 % ), though still below the known upper bound of ∼ 18.9 % .

DOI
10.22331/q-2018-10-19-102

Related papers

Towards practical classical processing for the surface code: Timing analysis

Austin G. Fowler, Adam C. Whiteside, Lloyd C. L. Hollenberg

Topological quantum error-correction codes have high thresholds and are well suited to physical implementation. The minimum-weight perfect-matching algorithm can be used to efficiently handle errors in such codes. We perform a timing analysis of our current implementation of the minimum-weight perfect-matching algorithm. Our implementation performs the classical processing associated with an $n\ifmmode\times\else\texttimes\fi{}n$ lattice of qubits realizing a square surface code storing a single logical qubit of information in a fault-tolerant manner. We empirically demonstrate that our implementation requires only $O({n}^{2})$ average time per round of error correction for code distances ranging from 4 to 512 and a range of depolarizing error rates. We also describe tests we have performed to verify that it always obtains a true minimum-weight perfect matching.

arXiv:1202.5602•Physical Review A•Oct 12, 2012•49 citations

Achieving Thresholds via Standalone Belief Propagation on Surface Codes

Pedro Hack, Luca Menti, Francisco Lazaro +1 more

The standard approach to Belief Propagation (BP) decoding passes messages on the Tanner graph of the quantum error-correcting (QEC) code, and is known to lack a threshold for the surface code. We propose novel BP decoders that exchange messages on the decoding graph and obtain thresholds (both for code capacity and circuit-level noise) via standalone BP for the surface code under depolarizing noise. Our approach, similarly to the minimum weight perfect matching (MWPM) decoder, is applicable to any graphlike QEC code. The thresholds observed with our decoders are close to those obtained by MWPM. This result opens the path towards scalable hardware-accelerated implementations of MWPM-compatible decoders.

quant-pharXiv:2603.05381•Mar 6, 2026•0 citations

Decoding the surface code using graph neural networks

Moritz Lange

Quantum error correction is essential to achieve fault-tolerant quantum computation in the presence of noisy qubits. Among the most promising approaches to quantum error correction is the surface code, thanks to a scalable two-dimensional architecture, only nearest-neighbor interactions, and a high error threshold. Decoding the surface code, i.e. finding the most likely error chain given a syndrome measurement outcome is a computationally complex task. Traditional decoders rely on classical algorithms, which, especially for larger systems, can be slow and may not always converge to the optimal solution. This thesis presents a novel approach to decoding the surface code using graph neural networks. By mapping the syndrome measurements to a graph and performing graph classification, we find that the graph neural networks can predict the most likely error configuration with high accuracy. Our results show that the GNN-based decoder outperforms the classic minimum weight perfect matching (MWPM) decoder in terms of accuracy. With a phenomenological noise model with depolarizing noise and perfect syndrome measurements, our networks beat MWPM up to code-size 15 across all relevant error rates. Furthermore, the GNN is capable of surpassing MWPM under circuit-level noise up to code size 7. We also show that training the network on repetition code data from a recent experiment [Google Quantum AI, Nature 614, 676 (2023)] produces per-step error rates comparable to those achieved with a matching decoder specifically adapted to the error rates of the physical qubits. This indicates that graph neural network decoders are capable of learning the underlying error distribution on the qubits. Our findings advance the field of quantum error correction and provide a promising new direction for the development of efficient decoding algorithms.

•Oct 17, 2023•0 citations

Neural Belief-Matching Decoding for Topological Quantum Error Correction Codes

Luca Menti, Francisco Lázaro

Quantum error correction (QEC) is critical for scalable fault-tolerant quantum computing. Topological codes, such as the toric code, offer hardware-efficient architectures but their Tanner graphs contain many girth-4 cycles that degrade the performance of belief-propagation (BP) decoding. For this reason, BP decoding is typically followed by a more complex second stage decoder such as minimum-weight perfect matching. These combined decoders achieve a remarkable performance, albeit at the cost of increased complexity. In this paper we propose two key improvements for the decoding of toric code. The first one is replacing the BP decoder by a neural BP decoder, giving rise to the neural belief-matching decoder which substantially decreases the average decoding complexity. The main drawback of this approach is the high cost associated with the training of the neural BP decoder. To address this issue, we impose a convolutional architecture on the neural BP decoder, enabling weight sharing across the spatially homogeneous structure of the code's factor graph. This design allows a model trained on a modest-size topological code to be directly transferred to much larger instances, preserving decoding quality while dramatically lowering the training burden. Our numerical experiments on toric-code lattices of various sizes demonstrate that this technique does not result in a noticeable loss in performance.

quant-pharXiv:2603.21730•Mar 24, 2026•0 citations

Neural ensemble decoding for topological quantum error-correcting codes

Milap Sheth, Sara Zafar Jafarzadeh, Vlad Gheorghiu

Topological quantum error-correcting codes are a promising candidate for building fault-tolerant quantum computers. Decoding topological codes optimally, however, is known to be a computationally hard problem. Various decoders have been proposed that achieve approximately optimal error thresholds. Due to practical constraints, it is not known if there exists an obvious choice for a decoder. In this paper, we introduce a framework which can combine arbitrary decoders for any given code to significantly reduce the logical error rates. We rely on the crucial observation that two different decoding techniques, while possibly having similar logical error rates, can perform differently on the same error syndrome. We classify each error syndrome to the decoder which is more likely to decode it correctly using machine learning techniques. We apply our framework to an ensemble of minimum-weight perfect matching (MWPM) and hard-decision re-normalization-group decoders for the surface code in the depolarizing noise model. Our simulations show an improvement of 38.4%, 14.6%, and 7.1% over the pseudothreshold of MWPM in the instance of distance 5, 7, and 9 codes, respectively. Lastly, we discuss the advantages and limitations of our framework and applicability to other error-correcting codes. Our framework can provide a significant boost to error correction by combining the strengths of various decoders. In particular, it may allow for combining very fast decoders with moderate error-correcting capability to create a very fast ensemble decoder with high error-correcting capability.

arXiv:1905.02345•Physical Review A•Mar 23, 2020•25 citations

Topological blocking decoder for surface codes

Hyun-Woo Jung, Jeongseok Ha

Surface codes have gained widespread popularity as quantum error-correction codes due to their unique structural feature that encoders and decoders can be implemented by leveraging interactions between physically neighboring qubits. The implementational advantage of surface codes has driven extensive research into decoding algorithms for surface codes, aimed at improving error-rate performance and/or reducing decoding complexity. In this paper, we propose a low-complexity postprocessing algorithm that effectively resolves failures of a syndrome-based belief-propagation (SB-BP) decoder for surface codes. In particular, we carefully analyze the topological structure of surface codes and present a method for selecting reliable qubits, enabling efficient recovery operator identification through a simple syndrome matching technique with a lookup table. Furthermore, we present an efficient way to construct lookup tables tailored to the proposed postprocessing algorithm. Numerical results demonstrate that the proposed postprocessing algorithm requires substantially reduced complexity as compared to that of a competing postprocessing algorithm, the ordered statistics decoding in the depolarizing error model, while providing the same logical error-rate (LER) performance. It is also demonstrated that the combination of SB-BP decoding and the proposed postprocessing algorithm outperforms minimum weight perfect matching, a more computationally expensive decoding algorithm, in terms of LER and threshold at drastically reduced complexity.

Physical Review A•Apr 18, 2025•1 citation
Fault tolerance is a prerequisite for scalable quantum computing. Architectures based on 2D topological codes are effective for near-term implementations of fault tolerance. To obtain high performance with these architectures, we require a decoder which can adapt to the wide variety of error models present in experiments. The typical approach to the problem of decoding the surface code is to reduce it to minimum-weight perfect matching in a way that provides a suboptimal threshold error rate, and is specialized to correct a specific error model. Recently, optimal threshold error rates for a variety of error models have been obtained by methods which do not use minimum-weight perfect matching, showing that such thresholds can be achieved in polynomial time. It is an open question whether these results can also be achieved by minimum-weight perfect matching. In this work, we use belief propagation and a novel algorithm for producing edge weights to increase the utility of minimum-weight perfect matching for decoding surface codes. This allows us to correct depolarizing errors using the rotated surface code, obtaining a threshold of 17.76 ± 0.02 % . This is larger than the threshold achieved by previous matching-based decoders ( 14.88 ± 0.02 % ), though still below the known upper bound of ∼ 18.9 % .
Topological quantum error-correction codes have high thresholds and are well suited to physical implementation. The minimum-weight perfect-matching algorithm can be used to efficiently handle errors in such codes. We perform a timing analysis of our current implementation of the minimum-weight perfect-matching algorithm. Our implementation performs the classical processing associated with an $n\ifmmode\times\else\texttimes\fi{}n$ lattice of qubits realizing a square surface code storing a single logical qubit of information in a fault-tolerant manner. We empirically demonstrate that our implementation requires only O(n2)O({n}^{2})O(n2) average time per round of error correction for code distances ranging from 4 to 512 and a range of depolarizing error rates. We also describe tests we have performed to verify that it always obtains a true minimum-weight perfect matching.
The standard approach to Belief Propagation (BP) decoding passes messages on the Tanner graph of the quantum error-correcting (QEC) code, and is known to lack a threshold for the surface code. We propose novel BP decoders that exchange messages on the decoding graph and obtain thresholds (both for code capacity and circuit-level noise) via standalone BP for the surface code under depolarizing noise. Our approach, similarly to the minimum weight perfect matching (MWPM) decoder, is applicable to any graphlike QEC code. The thresholds observed with our decoders are close to those obtained by MWPM. This result opens the path towards scalable hardware-accelerated implementations of MWPM-compatible decoders.
Quantum error correction is essential to achieve fault-tolerant quantum computation in the presence of noisy qubits. Among the most promising approaches to quantum error correction is the surface code, thanks to a scalable two-dimensional architecture, only nearest-neighbor interactions, and a high error threshold. Decoding the surface code, i.e. finding the most likely error chain given a syndrome measurement outcome is a computationally complex task. Traditional decoders rely on classical algorithms, which, especially for larger systems, can be slow and may not always converge to the optimal solution. This thesis presents a novel approach to decoding the surface code using graph neural networks. By mapping the syndrome measurements to a graph and performing graph classification, we find that the graph neural networks can predict the most likely error configuration with high accuracy. Our results show that the GNN-based decoder outperforms the classic minimum weight perfect matching (MWPM) decoder in terms of accuracy. With a phenomenological noise model with depolarizing noise and perfect syndrome measurements, our networks beat MWPM up to code-size 15 across all relevant error rates. Furthermore, the GNN is capable of surpassing MWPM under circuit-level noise up to code size 7. We also show that training the network on repetition code data from a recent experiment [Google Quantum AI, Nature 614, 676 (2023)] produces per-step error rates comparable to those achieved with a matching decoder specifically adapted to the error rates of the physical qubits. This indicates that graph neural network decoders are capable of learning the underlying error distribution on the qubits. Our findings advance the field of quantum error correction and provide a promising new direction for the development of efficient decoding algorithms.
Quantum error correction (QEC) is critical for scalable fault-tolerant quantum computing. Topological codes, such as the toric code, offer hardware-efficient architectures but their Tanner graphs contain many girth-4 cycles that degrade the performance of belief-propagation (BP) decoding. For this reason, BP decoding is typically followed by a more complex second stage decoder such as minimum-weight perfect matching. These combined decoders achieve a remarkable performance, albeit at the cost of increased complexity. In this paper we propose two key improvements for the decoding of toric code. The first one is replacing the BP decoder by a neural BP decoder, giving rise to the neural belief-matching decoder which substantially decreases the average decoding complexity. The main drawback of this approach is the high cost associated with the training of the neural BP decoder. To address this issue, we impose a convolutional architecture on the neural BP decoder, enabling weight sharing across the spatially homogeneous structure of the code's factor graph. This design allows a model trained on a modest-size topological code to be directly transferred to much larger instances, preserving decoding quality while dramatically lowering the training burden. Our numerical experiments on toric-code lattices of various sizes demonstrate that this technique does not result in a noticeable loss in performance.
Topological quantum error-correcting codes are a promising candidate for building fault-tolerant quantum computers. Decoding topological codes optimally, however, is known to be a computationally hard problem. Various decoders have been proposed that achieve approximately optimal error thresholds. Due to practical constraints, it is not known if there exists an obvious choice for a decoder. In this paper, we introduce a framework which can combine arbitrary decoders for any given code to significantly reduce the logical error rates. We rely on the crucial observation that two different decoding techniques, while possibly having similar logical error rates, can perform differently on the same error syndrome. We classify each error syndrome to the decoder which is more likely to decode it correctly using machine learning techniques. We apply our framework to an ensemble of minimum-weight perfect matching (MWPM) and hard-decision re-normalization-group decoders for the surface code in the depolarizing noise model. Our simulations show an improvement of 38.4%, 14.6%, and 7.1% over the pseudothreshold of MWPM in the instance of distance 5, 7, and 9 codes, respectively. Lastly, we discuss the advantages and limitations of our framework and applicability to other error-correcting codes. Our framework can provide a significant boost to error correction by combining the strengths of various decoders. In particular, it may allow for combining very fast decoders with moderate error-correcting capability to create a very fast ensemble decoder with high error-correcting capability.
Surface codes have gained widespread popularity as quantum error-correction codes due to their unique structural feature that encoders and decoders can be implemented by leveraging interactions between physically neighboring qubits. The implementational advantage of surface codes has driven extensive research into decoding algorithms for surface codes, aimed at improving error-rate performance and/or reducing decoding complexity. In this paper, we propose a low-complexity postprocessing algorithm that effectively resolves failures of a syndrome-based belief-propagation (SB-BP) decoder for surface codes. In particular, we carefully analyze the topological structure of surface codes and present a method for selecting reliable qubits, enabling efficient recovery operator identification through a simple syndrome matching technique with a lookup table. Furthermore, we present an efficient way to construct lookup tables tailored to the proposed postprocessing algorithm. Numerical results demonstrate that the proposed postprocessing algorithm requires substantially reduced complexity as compared to that of a competing postprocessing algorithm, the ordered statistics decoding in the depolarizing error model, while providing the same logical error-rate (LER) performance. It is also demonstrated that the combination of SB-BP decoding and the proposed postprocessing algorithm outperforms minimum weight perfect matching, a more computationally expensive decoding algorithm, in terms of LER and threshold at drastically reduced complexity.