Decoding quantum color codes with MaxSAT

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, <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>d</mml:mi><mml:mi>e</mml:mi><mml:mi>c</mml:mi><mml:mi>o</mml:mi><mml:mi>d</mml:mi><mml:mi>i</mml:mi><mml:mi>n</mml:mi><mml:mi>g</mml:mi></mml:math> 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mtext mathvariant="monospace">LightsOut</mml:mtext></mml:mrow></mml:math> 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mtext class="MJX-tex-mathit" mathvariant="italic">Munich Quantum Toolkit</mml:mtext></mml:mrow></mml:math> (MQT) on GitHub.