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:1202.5602 · Physical Review A

Towards practical classical processing for the surface code: Timing analysis

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

Published Oct 12, 2012• 49 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.86.042313

Related papers

Minimum weight perfect matching of fault-tolerant topological quantum error correction in average O(1) parallel time

Austin G. Fowler

Consider a 2-D square array of qubits of extent $L\times L$. We provide a proof that the minimum weight perfect matching problem associated with running a particular class of topological quantum error correction codes on this array can be exactly solved with a 2-D square array of classical computing devices, each of which is nominally associated with a fixed number $N$ of qubits, in constant average time per round of error detection independent of $L$ provided physical error rates are below fixed nonzero values, and other physically reasonable assumptions. This proof is applicable to the fully fault-tolerant case only, not the case of perfect stabilizer measurements.

arXiv:1307.1740•Quantum Information and Computation•Jan 1, 2015•86 citations

Multi-path Summation for Decoding 2D Topological Codes

Ben Criger, Imran Ashraf

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 % .

arXiv:1709.02154•Quantum•Oct 19, 2018•46 citations

Towards Practical Classical Processing for the Surface Code

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

The surface code is unarguably the leading quantum error correction code for 2D nearest neighbor architectures, featuring a high threshold error rate of approximately 1%, low overhead implementations of the entire Clifford group, and flexible, arbitrarily long-range logical gates. These highly desirable features come at the cost of significant classical processing complexity. We show how to perform the processing associated with an n×n lattice of qubits, each being manipulated in a realistic, fault-tolerant manner, in O(n2) average time per round of error correction. We also describe how to parallelize the algorithm to achieve O(1) average processing per round, using only constant computing resources per unit area and local communication. Both of these complexities are optimal.

arXiv:1110.5133•Physical Review Letters•May 1, 2012•208 citations

Fault-tolerance thresholds for the surface code with fabrication errors

James M. Auger, Hussain Anwar, Mercedes Gimeno-Segovia +2 more

The construction of topological error correction codes requires the ability to fabricate a lattice of physical qubits embedded on a manifold with a nontrivial topology such that the quantum information is encoded in the global degrees of freedom (i.e., the topology) of the manifold. However, the manufacturing of large-scale topological devices will undoubtedly suffer from fabrication errors---permanent faulty components such as missing physical qubits or failed entangling gates---introducing permanent defects into the topology of the lattice and hence significantly reducing the distance of the code and the quality of the encoded logical qubits. In this work we investigate how fabrication errors affect the performance of topological codes, using the surface code as the test bed. A known approach to mitigate defective lattices involves the use of primitive swap gates in a long sequence of syndrome extraction circuits. Instead, we show that in the presence of fabrication errors the syndrome can be determined using the supercheck operator approach and the outcome of the defective gauge stabilizer generators without any additional computational overhead or use of swap gates. We report numerical fault-tolerance thresholds in the presence of both qubit fabrication and gate fabrication errors using a circuit-based noise model and the minimum-weight perfect-matching decoder. Our numerical analysis is most applicable to two-dimensional chip-based technologies, but the techniques presented here can be readily extended to other topological architectures. We find that in the presence of $8%$ qubit fabrication errors, the surface code can still tolerate a computational error rate of up to $0.1%$.

arXiv:1706.04912•Physical Review A•Oct 12, 2017•39 citations

Enhancing Fault-Tolerant Surface Code Decoding with Iterative Lattice Reweighting

Yi Tian, Yang Zheng, Xiaoting Wang +1 more

Efficient and realistic error decoding is crucial for fault-tolerant quantum computation (FTQC) on near-term devices. While decoding is a classical post-processing task, its effectiveness depends on accurately modeling quantum noise, which is hardware-dependent. In particular, correlated bit-flip ($X$) and phase-flip ($Z$) errors often arise under circuit-level noise. We introduce the Iterative Reweighting Minimum-Weight Perfect Matching (IRMWPM) decoder, which systematically incorporates such correlations to enhance quantum error correction. Our method leverages fault-detection patterns to guide reweighting: correlated $X$ and $Z$ detection events are identified, and their conditional probabilities update weights on the primal and dual lattices. This iterative procedure improves handling of realistic error propagation in a hardware-agnostic yet noise-aware manner. We prove that IRMWPM converges in finite time while preserving the distance guarantee of MWPM. Numerical results under circuit-level noise show substantial improvements. For distances $\geq 17$ and physical error rates $\leq 0.001$, IRMWPM reduces logical error rates by over 20x with only a few iterations. It also raises the accuracy threshold from 1% to 1.16%, making it practical for near-term real-time decoding. Extrapolated estimates suggest that to reach logical error rate $10^{-16}$, IRMWPM requires distance $d=31$, while standard MWPM needs $d=50$, implying a major reduction in qubit overhead.

arXiv:2509.06756•Sep 8, 2025•0 citations

Fast fault-tolerant decoder for qubit and qudit surface codes

Fern H. E. Watson, Hussain Anwar, Dan E. Browne

The surface code is one of the most promising candidates for combating errors in large scale fault-tolerant quantum computation. A fault-tolerant decoder is a vital part of the error correction process---it is the algorithm which computes the operations needed to correct or compensate for the errors according to the measured syndrome, even when the measurement itself is error prone. Previously decoders based on minimum-weight perfect matching have been studied. However, these are not immediately generalizable from qubit to qudit codes. In this work, we develop a fault-tolerant decoder for the surface code, capable of efficient operation for qubits and qudits of any dimension, generalizing the decoder first introduced by Bravyi and Haah [Phys. Rev. Lett. 111, 200501 (2013)]. We study its performance when both the physical qudits and the syndromes measurements are subject to generalized uncorrelated bit-flip noise (and the higher-dimensional equivalent). We show that, with appropriate enhancements to the decoder and a high enough qudit dimension, a threshold at an error rate of more than $8%$ can be achieved.

arXiv:1411.3028•Physical Review A•Sep 8, 2015•62 citations
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×\else\texttimes\finn\ifmmode\times\else\texttimes\fi{}nn\ifmmode×\else\texttimes\fin 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.
Consider a 2-D square array of qubits of extent L×LL\times LL×L. We provide a proof that the minimum weight perfect matching problem associated with running a particular class of topological quantum error correction codes on this array can be exactly solved with a 2-D square array of classical computing devices, each of which is nominally associated with a fixed number NNN of qubits, in constant average time per round of error detection independent of LLL provided physical error rates are below fixed nonzero values, and other physically reasonable assumptions. This proof is applicable to the fully fault-tolerant case only, not the case of perfect stabilizer measurements.
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 % .
The surface code is unarguably the leading quantum error correction code for 2D nearest neighbor architectures, featuring a high threshold error rate of approximately 1%, low overhead implementations of the entire Clifford group, and flexible, arbitrarily long-range logical gates. These highly desirable features come at the cost of significant classical processing complexity. We show how to perform the processing associated with an n×n lattice of qubits, each being manipulated in a realistic, fault-tolerant manner, in O(n2) average time per round of error correction. We also describe how to parallelize the algorithm to achieve O(1) average processing per round, using only constant computing resources per unit area and local communication. Both of these complexities are optimal.
The construction of topological error correction codes requires the ability to fabricate a lattice of physical qubits embedded on a manifold with a nontrivial topology such that the quantum information is encoded in the global degrees of freedom (i.e., the topology) of the manifold. However, the manufacturing of large-scale topological devices will undoubtedly suffer from fabrication errors---permanent faulty components such as missing physical qubits or failed entangling gates---introducing permanent defects into the topology of the lattice and hence significantly reducing the distance of the code and the quality of the encoded logical qubits. In this work we investigate how fabrication errors affect the performance of topological codes, using the surface code as the test bed. A known approach to mitigate defective lattices involves the use of primitive swap gates in a long sequence of syndrome extraction circuits. Instead, we show that in the presence of fabrication errors the syndrome can be determined using the supercheck operator approach and the outcome of the defective gauge stabilizer generators without any additional computational overhead or use of swap gates. We report numerical fault-tolerance thresholds in the presence of both qubit fabrication and gate fabrication errors using a circuit-based noise model and the minimum-weight perfect-matching decoder. Our numerical analysis is most applicable to two-dimensional chip-based technologies, but the techniques presented here can be readily extended to other topological architectures. We find that in the presence of 88%8 qubit fabrication errors, the surface code can still tolerate a computational error rate of up to 0.10.1%0.1.
Efficient and realistic error decoding is crucial for fault-tolerant quantum computation (FTQC) on near-term devices. While decoding is a classical post-processing task, its effectiveness depends on accurately modeling quantum noise, which is hardware-dependent. In particular, correlated bit-flip (XXX) and phase-flip (ZZZ) errors often arise under circuit-level noise. We introduce the Iterative Reweighting Minimum-Weight Perfect Matching (IRMWPM) decoder, which systematically incorporates such correlations to enhance quantum error correction. Our method leverages fault-detection patterns to guide reweighting: correlated XXX and ZZZ detection events are identified, and their conditional probabilities update weights on the primal and dual lattices. This iterative procedure improves handling of realistic error propagation in a hardware-agnostic yet noise-aware manner. We prove that IRMWPM converges in finite time while preserving the distance guarantee of MWPM. Numerical results under circuit-level noise show substantial improvements. For distances ≥17\geq 17≥17 and physical error rates ≤0.001\leq 0.001≤0.001, IRMWPM reduces logical error rates by over 20x with only a few iterations. It also raises the accuracy threshold from 1% to 1.16%, making it practical for near-term real-time decoding. Extrapolated estimates suggest that to reach logical error rate 10−1610^{-16}10−16, IRMWPM requires distance d=31d=31d=31, while standard MWPM needs d=50d=50d=50, implying a major reduction in qubit overhead.
The surface code is one of the most promising candidates for combating errors in large scale fault-tolerant quantum computation. A fault-tolerant decoder is a vital part of the error correction process---it is the algorithm which computes the operations needed to correct or compensate for the errors according to the measured syndrome, even when the measurement itself is error prone. Previously decoders based on minimum-weight perfect matching have been studied. However, these are not immediately generalizable from qubit to qudit codes. In this work, we develop a fault-tolerant decoder for the surface code, capable of efficient operation for qubits and qudits of any dimension, generalizing the decoder first introduced by Bravyi and Haah [Phys. Rev. Lett. 111, 200501 (2013)]. We study its performance when both the physical qudits and the syndromes measurements are subject to generalized uncorrelated bit-flip noise (and the higher-dimensional equivalent). We show that, with appropriate enhancements to the decoder and a high enough qudit dimension, a threshold at an error rate of more than 88%8 can be achieved.