Efficient Belief Propagation Decoder for Color Codes

We present a low complexity belief propagation-based decoder for the color code family with early numerical evidence to suggest comparable performance to the concatenated minimum weight perfect matching decoder. The color code provides benefits such as the transversal implementation of Clifford gates but lacks an efficient message passing decoder for depolarizing noise. This difficulty arises because its Tanner graph contains dense, short loops and high connectivity, which hinder local message passing. To overcome this, we generalize the graph dilution method–previously developed for the square lattice of the surface code–to the hexagonal lattice of color codes, enabling belief propagation to operate reliably on the restricted lattice. We also provide a lower bound on the worst-case error-correcting capability for decoding on the diluted color codes. To the best of our knowledge, our algorithm is the first local message passing approach comparable to the concatenated minimum weight perfect matching decoder for the color codes.