Belief propagation reduces quantum error decoding search effort
Belief Propagation-Informed Tesseract Decoding of Quantum LDPC Codes
Information Theory
Summary
Quantum computers need to correct errors quickly to work well, but complex decoding methods can take too long as error rates or system size grow. The authors present a way to use a faster, simpler method called belief propagation to guide the more precise decoding search, sometimes skipping it completely. This approach keeps error correction nearly as accurate while making the search process much faster, especially at low error rates. They tested it on several example quantum codes and found it greatly reduced the work needed without hurting performance.
What this means in practice
- •For quantum hardware engineers: Speed up error decoding in quantum processors by integrating belief propagation to reduce search complexity without losing accuracy.
- •For quantum software developers: Implement belief propagation-informed decoders to efficiently manage error correction in quantum computing simulations and development tools.
Authors
Sana Javed, Francisco Garcia-Herrero, Bane Vasić, Mark F. Flanagan
Abstract
In quantum error correction, the decoder must estimate the errors from the measurement data accurately and fast enough to avoid a backlog. Search-based decoders such as Tesseract achieve high accuracy by finding a minimum-weight set of error events with an A* search, but their search effort grows rapidly with the physical error rate and the code size. To reduce this search effort while maintaining a logical error rate close to that of Tesseract, we propose a belief propagation (BP)-guided modification of the Tesseract decoder for quantum low-density parity-check (LDPC) codes. Damped sum-product BP is applied to the triggered detectors before the Tesseract search. If the detectors triggered by the BP hard decision match the triggered detectors, this hard decision is accepted directly, and the Tesseract search is skipped. Otherwise, the BP marginal probability estimates, weighted by a trust coefficient, modify the search priority, while the path cost keeps the channel-prior weights so that the decoding objective is unchanged. The framework also supports BP-based initialization, in which selected BP decisions form the starting point of a residual search whose signed-cost objective allows incorrect initial decisions to be removed. A node-exploration limit bounds this residual search; if the limit is reached, the decoder falls back to the BP-guided search on the original triggered detector set. The method is evaluated on the [[72,12,6]], [[90,8,10]], and [[144,12,12]] bivariate bicycle codes under circuit-level noise. With BP-based initialization and a global trust coefficient, the number of Tesseract search nodes expanded is reduced by up to more than two orders of magnitude at low physical error rates, while the logical error rate remains close to that of Tesseract.