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

Decoding color codes by projection onto surface codes

Nicolas Delfosse

Published Jan 16, 2014• 98 citations
arXivHTMLPDF

Abstract

We propose a general strategy to decode color codes, which is based on the projection of the error onto three surface codes. This provides a method to transform every decoding algorithm of surface codes into a decoding algorithm of color codes. Applying this idea to a family of hexagonal color codes, with the perfect matching decoding algorithm for the three corresponding surface codes, we find a phase error threshold of approximately $8.7%$. Finally, our approach enables us to establish a general lower bound on the error threshold of a family of color codes depending on the threshold of the three corresponding surface codes. These results are based on a chain complex interpretation of surface codes and color codes.

DOI
10.1103/physreva.89.012317

Related papers

Erasure decoding of two-dimensional color codes

Arun B. Aloshious, Pradeep Kiran Sarvepalli

The quantum erasure channel models phenomena such as loss or leakage of qubits. Using quantum codes, we can recover from such errors. In this paper, we are interested in studying the performance of two-dimensional color codes over the quantum erasure channel. Our approach makes use of the local equivalence between color codes and surface codes. We propose a variety of decoding algorithms for color codes over the erasure channel. First, we propose algorithms that decode by projecting the erasures on the color to surface codes. Then, instead of directly decoding on the color code or on the equivalent copies of surface codes, we decode jointly on the color code and the equivalent surface codes. We observe a threshold of 44.3% for the color code on the square octagonal lattice.

Physical Review A•Oct 14, 2019•6 citations

The correlated matching decoder for the 4.8.8 color code

Yantong Liu, Junjie Wu, Lingling Lao

Color codes present distinct advantages for fault-tolerant quantum computing, such as high encoding rates and the transversal implementation of Clifford gates. However, existing matching-based decoders for the color codes such as the restricted decoder (Kubica and Delfosse, 2023), suffer from limited decoding performance. Inspired by the global decoding insight of the unified decoder (Benhemou et al., 2023), this paper introduces a correlated decoder for the 4.8.8 color code, which improves upon the conventional restricted decoder by leveraging correlations between restricted lattices, and is derived by mapping the correlated matching decoder for the surface code onto the color code lattice. Analytical and numerical results show that the correlated decoder achieves higher thresholds than the restricted and unified decoders, while matching the performance of the unified decoder at very low physical error rates. Under the code capacity and phenomenological noise models, the estimated thresholds for the color code against bit-flip error are 10.38% and 3.13%, respectively. Furthermore, by applying the surface-color code mapping, the thresholds of 16.62% and 3.52% are obtained for the surface code against depolarizing noise.

quant-pharXiv:2511.13192•Science China Information Sciences•Nov 18, 2025•1 citation

Minimising surface-code failures using a color-code decoder

Asmae Benhemou, Kaavya Sahay, Lingling Lao +1 more

The development of practical, high-performance decoding algorithms reduces the resource cost of fault-tolerant quantum computing. Here we propose a decoder for the surface code that finds low-weight correction operators for errors produced by the depolarising noise model. The decoder is obtained by mapping the syndrome of the surface code onto that of the color code, thereby allowing us to adopt more sophisticated color-code decoding algorithms. Analytical arguments and exhaustive testing show that the resulting decoder can find a least-weight correction for all weight d/2 depolarising errors for even code distance d . This improves the logical error rate by an exponential factor O(2d/2) compared with decoders that treat bit-flip and dephasing errors separately. We demonstrate this improvement with analytical arguments and supporting numerical simulations at low error rates. Of independent interest, we also demonstrate an exponential improvement in logical error rate for our decoder used to correct independent and identically distributed bit-flip errors affecting the color code compared with more conventional color-code decoding algorithms.

arXiv:2306.16476•Quantum•Feb 17, 2025•6 citations

Efficient fault-tolerant decoding of topological color codes

Ashley M. Stephens

Topological color codes defined by the 4.8.8 semiregular lattice feature geometrically local check operators and admit transversal implementation of the entire Clifford group, making them promising candidates for fault-tolerant quantum computation. Recently, several efficient algorithms for decoding the syndrome of color codes were proposed. Here, we modify one of these algorithms to account for errors affecting the syndrome, applying it to the family of triangular 4.8.8 color codes encoding one logical qubit. For a three-dimensional bit-flip channel, we report a threshold error rate of 0.0208(1), compared with 0.0305(4) previously reported for an integer-program-based decoding algorithm. When we account for circuit details, this threshold is reduced to 0.00143(1) per gate, compared with 0.00672(1) per gate for the surface code under an identical noise model.

arXiv:1402.3037•Feb 13, 2014•47 citations

Graphical algorithms and threshold error rates for the 2d color code

David S. Wang, Austin G. Fowler, Charles D. Hill +1 more

Recent work on fault-tolerant quantum computation making use of topological error correction shows great potential, with the 2d surface code possessing a threshold error rate approaching 1\%. However, the 2d surface code requires the use of a complex state distillation procedure to achieve universal quantum computation. The color code of is a related scheme partially solving the problem, providing a means to perform all Clifford group gates transversally. We review the color code and its error correcting methodology, discussing one approximate technique based on graph matching. We derive an analytic lower bound to the threshold error rate of 6.25\% under error-free syndrome extraction, while numerical simulations indicate it may be as high as 13.3\%. Inclusion of faulty syndrome extraction circuits drops the threshold to approximately 0.10 \pm 0.01\%.

arXiv:0907.1708•Quantum Information and Computation•Sep 1, 2010•65 citations

Optimal Decoding with the Worm

Zac Tobias, Nikolas P. Breuckmann, Benedikt Placke

We propose a new decoder for "matchable'' qLDPC codes that uses a Markov Chain Monte Carlo algorithm - called the worm algorithm - to approximately compute the probabilities of logical error classes given a syndrome. The algorithm hence performs (approximate) optimal decoding, and we expect it to be computationally efficient in certain settings. The algorithm is applicable to decoding random errors for the surface code, the honeycomb Floquet code, and hyperbolic surface codes with constant rate, in all cases with and without measurement errors. The efficiency of the decoder hinges on the mixing time of the underlying Markov chain. We give a rigorous mixing time guarantee in terms of a quantity that we call the defect susceptibility. We connect this quantity to the notion of disorder operators in statistical mechanics and use this to argue (non-rigorously) that the algorithm is efficient for typical errors in the entire decodable phase. We also demonstrate the effectiveness of the worm decoder numerically by applying it to the surface code with measurement errors as well as a family of hyperbolic surface codes. For most codes, the matchability condition restricts direct application of our decoder to noise models with independent bit-flip, phase-flip, and measurement errors. However, our decoder returns soft information which makes it useful also in heuristic "correlated decoding'' schemes which work beyond this simple setting. We demonstrate this by simulating decoding of the surface code under depolarizing noise, and we find that the threshold for "correlated worm decoding'' is substantially higher than for both minimum-weight perfect matching and for correlated matching.

quant-pharXiv:2603.05428•Mar 6, 2026•4 citations
We propose a general strategy to decode color codes, which is based on the projection of the error onto three surface codes. This provides a method to transform every decoding algorithm of surface codes into a decoding algorithm of color codes. Applying this idea to a family of hexagonal color codes, with the perfect matching decoding algorithm for the three corresponding surface codes, we find a phase error threshold of approximately 8.78.7%8.7. Finally, our approach enables us to establish a general lower bound on the error threshold of a family of color codes depending on the threshold of the three corresponding surface codes. These results are based on a chain complex interpretation of surface codes and color codes.
The quantum erasure channel models phenomena such as loss or leakage of qubits. Using quantum codes, we can recover from such errors. In this paper, we are interested in studying the performance of two-dimensional color codes over the quantum erasure channel. Our approach makes use of the local equivalence between color codes and surface codes. We propose a variety of decoding algorithms for color codes over the erasure channel. First, we propose algorithms that decode by projecting the erasures on the color to surface codes. Then, instead of directly decoding on the color code or on the equivalent copies of surface codes, we decode jointly on the color code and the equivalent surface codes. We observe a threshold of 44.3% for the color code on the square octagonal lattice.
Color codes present distinct advantages for fault-tolerant quantum computing, such as high encoding rates and the transversal implementation of Clifford gates. However, existing matching-based decoders for the color codes such as the restricted decoder (Kubica and Delfosse, 2023), suffer from limited decoding performance. Inspired by the global decoding insight of the unified decoder (Benhemou et al., 2023), this paper introduces a correlated decoder for the 4.8.8 color code, which improves upon the conventional restricted decoder by leveraging correlations between restricted lattices, and is derived by mapping the correlated matching decoder for the surface code onto the color code lattice. Analytical and numerical results show that the correlated decoder achieves higher thresholds than the restricted and unified decoders, while matching the performance of the unified decoder at very low physical error rates. Under the code capacity and phenomenological noise models, the estimated thresholds for the color code against bit-flip error are 10.38% and 3.13%, respectively. Furthermore, by applying the surface-color code mapping, the thresholds of 16.62% and 3.52% are obtained for the surface code against depolarizing noise.
The development of practical, high-performance decoding algorithms reduces the resource cost of fault-tolerant quantum computing. Here we propose a decoder for the surface code that finds low-weight correction operators for errors produced by the depolarising noise model. The decoder is obtained by mapping the syndrome of the surface code onto that of the color code, thereby allowing us to adopt more sophisticated color-code decoding algorithms. Analytical arguments and exhaustive testing show that the resulting decoder can find a least-weight correction for all weight d/2 depolarising errors for even code distance d . This improves the logical error rate by an exponential factor O(2d/2) compared with decoders that treat bit-flip and dephasing errors separately. We demonstrate this improvement with analytical arguments and supporting numerical simulations at low error rates. Of independent interest, we also demonstrate an exponential improvement in logical error rate for our decoder used to correct independent and identically distributed bit-flip errors affecting the color code compared with more conventional color-code decoding algorithms.
Topological color codes defined by the 4.8.8 semiregular lattice feature geometrically local check operators and admit transversal implementation of the entire Clifford group, making them promising candidates for fault-tolerant quantum computation. Recently, several efficient algorithms for decoding the syndrome of color codes were proposed. Here, we modify one of these algorithms to account for errors affecting the syndrome, applying it to the family of triangular 4.8.8 color codes encoding one logical qubit. For a three-dimensional bit-flip channel, we report a threshold error rate of 0.0208(1), compared with 0.0305(4) previously reported for an integer-program-based decoding algorithm. When we account for circuit details, this threshold is reduced to 0.00143(1) per gate, compared with 0.00672(1) per gate for the surface code under an identical noise model.
Recent work on fault-tolerant quantum computation making use of topological error correction shows great potential, with the 2d surface code possessing a threshold error rate approaching 1\%. However, the 2d surface code requires the use of a complex state distillation procedure to achieve universal quantum computation. The color code of is a related scheme partially solving the problem, providing a means to perform all Clifford group gates transversally. We review the color code and its error correcting methodology, discussing one approximate technique based on graph matching. We derive an analytic lower bound to the threshold error rate of 6.25\% under error-free syndrome extraction, while numerical simulations indicate it may be as high as 13.3\%. Inclusion of faulty syndrome extraction circuits drops the threshold to approximately 0.10 \pm 0.01\%.
We propose a new decoder for "matchable'' qLDPC codes that uses a Markov Chain Monte Carlo algorithm - called the worm algorithm - to approximately compute the probabilities of logical error classes given a syndrome. The algorithm hence performs (approximate) optimal decoding, and we expect it to be computationally efficient in certain settings. The algorithm is applicable to decoding random errors for the surface code, the honeycomb Floquet code, and hyperbolic surface codes with constant rate, in all cases with and without measurement errors. The efficiency of the decoder hinges on the mixing time of the underlying Markov chain. We give a rigorous mixing time guarantee in terms of a quantity that we call the defect susceptibility. We connect this quantity to the notion of disorder operators in statistical mechanics and use this to argue (non-rigorously) that the algorithm is efficient for typical errors in the entire decodable phase. We also demonstrate the effectiveness of the worm decoder numerically by applying it to the surface code with measurement errors as well as a family of hyperbolic surface codes. For most codes, the matchability condition restricts direct application of our decoder to noise models with independent bit-flip, phase-flip, and measurement errors. However, our decoder returns soft information which makes it useful also in heuristic "correlated decoding'' schemes which work beyond this simple setting. We demonstrate this by simulating decoding of the surface code under depolarizing noise, and we find that the threshold for "correlated worm decoding'' is substantially higher than for both minimum-weight perfect matching and for correlated matching.