Local Probabilistic Decoding of a Quantum Code

Abstract

flip is an extremely simple and maximally local classical decoder which has been used to great effect in certain classes of classical codes. When applied to quantum codes there exist constant-weight errors (such as half of a stabiliser) which are uncorrectable for this decoder, so previous studies have considered modified versions of flip, sometimes in conjunction with other decoders. We argue that this may not always be necessary, and present numerical evidence for the existence of a threshold for flip when applied to the looplike syndromes of a three-dimensional toric code on a cubic lattice. This result can be attributed to the fact that the lowest-weight uncorrectable errors for this decoder are closer (in terms of Hamming distance) to correctable errors than to other uncorrectable errors, and so they are likely to become correctable in future code cycles after transformation by additional noise. Introducing randomness into the decoder can allow it to correct these "uncorrectable" errors with finite probability, and for a decoding strategy that uses a combination of belief propagation and probabilistic flip we observe a threshold of $\sim 5.5\%$ under phenomenological noise. This is comparable to the best known threshold for this code ($\sim 7.1\%$) which was achieved using belief propagation and ordered statistics decoding [Higgott and Breuckmann, 2022], a strategy with a runtime of $O(n^3)$ as opposed to the $O(n)$ ($O(1)$ when parallelised) runtime of our local decoder. We expect that this strategy could be generalised to work well in other low-density parity check codes, and hope that these results will prompt investigation of other previously overlooked decoders.

arXiv comment10 pages + 1 page appendix, 7 figures. Comments welcome.; v3 Published version

References in corpus (24)

• Fault-tolerant quantum computation by anyons
• Good Quantum Error-Correcting Codes Exist
• Topological quantum memory
• Quantum Error Correction for Quantum Memories
• Multiple Particle Interference and Quantum Error Correction
• Stabilizer Codes and Quantum Error Correction
• Confinement-Higgs transition in a disordered gauge theory and the accuracy threshold for quantum memory
• Degenerate Quantum LDPC Codes With Good Finite Length Performance
• Decoding Across the Quantum LDPC Code Landscape
• Single-shot fault-tolerant quantum error correction
• Fault-tolerant error correction with the gauge color code
• Quantum Expander Codes
• Single-shot error correction of three-dimensional homological product codes
• Cellular-automaton decoders with provable thresholds for topological codes
• Combining hard and soft decoders for hypergraph product codes
• Improved single-shot decoding of higher dimensional hypergraph product codes
• Cellular automaton decoders for topological quantum codes with noisy measurements and beyond
• Numerical study of hypergraph product codes
• Good Quantum LDPC Codes with Linear Time Decoders
• An efficient decoder for a linear distance quantum LDPC code
• Decoding quantum Tanner codes
• Non-Pauli Errors in the Three-Dimensional Surface Code
• On the iterative decoding of sparse quantum codes
• A Numerical Study of Bravyi-Bacon-Shor and Subsystem Hypergraph Product Codes

Cited by in corpus (4)

• Bias-tailored quantum LDPC codes
• Analog information decoding of bosonic quantum LDPC codes
• Single-shot and measurement-based quantum error correction via fault complexes
• Enhancing Quantum Memory Lifetime with Measurement-Free Local Error Correction and Reinforcement Learning