Decoding quantum color codes with MaxSAT

Abstract

In classical computing, error-correcting codes are well established and are ubiquitous both in theory and practical applications. For quantum computing, error-correction is essential as well, but harder to realize, coming along with substantial resource overheads and being concomitant with needs for substantial classical computing. Quantum error-correcting codes play a central role on the avenue towards fault-tolerant quantum computation beyond presumed near-term applications. Among those, color codes constitute a particularly important class of quantum codes that have gained interest in recent years due to favourable properties over other codes. As in classical computing, decoding is the problem of inferring an operation to restore an uncorrupted state from a corrupted one and is central in the development of fault-tolerant quantum devices. In this work, we show how the decoding problem for color codes can be reduced to a slight variation of the well-known LightsOut puzzle. We propose a novel decoder for quantum color codes using a formulation as a MaxSAT problem based on this analogy. Furthermore, we optimize the MaxSAT construction and show numerically that the decoding performance of the proposed decoder achieves state-of-the-art decoding performance on color codes. The implementation of the decoder as well as tools to automatically conduct numerical experiments are publicly available as part of the Munich Quantum Toolkit (MQT) on GitHub.

17 pages, 10 figures

References in corpus (26)

• Topological quantum memory
• Suppressing quantum errors by scaling a surface code logical qubit
• Topological Quantum Distillation
• Exponential suppression of bit or phase flip errors with repetitive error correction
• Stim: a fast stabilizer circuit simulator
• Quantum Error Correction: An Introductory Guide
• Confinement-Higgs transition in a disordered gauge theory and the accuracy threshold for quantum memory
• Demonstration of fault-tolerant universal quantum gate operations
• The XZZX Surface Code
• Decoding Across the Quantum LDPC Code Landscape
• Strong Resilience of Topological Codes to Depolarization
• Unfolding the color code
• Error Threshold for Color Codes and Random 3-Body Ising Models
• Tailoring surface codes for highly biased noise
• Decoding color codes by projection onto surface codes
• The cost of universality: A comparative study of the overhead of state distillation and code switching with color codes
• Advantages of versatile neural-network decoding for topological codes
• Cellular-automaton decoders for topological quantum memories
• Anyon condensation and the color code
• The boundaries and twist defects of the color code and their applications to topological quantum computation
• The MQT Handbook: A Summary of Design Automation Tools and Software for Quantum Computing
• Efficient Decoding of Topological Color Codes
• General tensor network decoding of 2D Pauli codes
• Fault-tolerant fermionic quantum computation based on color code
• A cellular automaton decoder for a noise-bias tailored color code
• New circuits and an open source decoder for the color code

Cited by in corpus (6)

• Color code decoder with improved scaling for correcting circuit-level noise
• Data-driven decoding of quantum error correcting codes using graph neural networks
• Low-overhead magic state distillation with color codes
• Magic Mirror on the Wall, How to Benchmark Quantum Error Correction Codes, Overall ?
• Qudit low-density parity-check codes
• On the interpretability of neural network decoders