Note on Belief Propagation
This work gives a detail description of Belief Propagation (BP) algorithm and several of its variations.
I description of binary BP decoder
The Belief Propagation (BP) algorithm can approximate the maginal probability of errors, giving the received bits or the syndrome. It is designed for factor graph. When the graph is a tree, it gives the exact marginal probability. There are several equivalent/approximate versions of it, let us start with the classical one.
BP decoder for classical binary codes:
A code is defined by a factor graph ( with assumed degree and) with variable nodes and check nodes . The message from variable to check is
The message from check to variable is
The initial condition is .
(To generalize it to nonbinary case, one only need to modify the parity check condition from matrix miltiplication to symplectic product. Everything else will be extended smoothly)
I.2 codeword-based, LLR-simplified
By rewriting the probabilities and messages in terms of the log-likelihood ratio
, , one can get the simplified message:
When , will be flipped.
In this simplified form, only one message need to be sent per edge, instead of two messages for 0 and 1 respectively. Hence, the complexity is reduced.
In classical case, the received bits was used, instead of the syndrome. In quantum case, there are no received bits, but only the syndrome. Hence, to get the formula in quantum case, one need to change it to a syndrome-based decoder.
Ref (MacKay and Mac Kay, 2003, chapter 47.2) show that the codeword-based BP decoder is equivalent to the following syndrome-based decoder
The initial condition is still .
The logic is that, the codeword-view calculate (the most-likely input codeword given the recieved vector ) and the syndrome-view calculate (the most-likely error given this syndrome ). Here should be an valid zero-syndrome input codeword; is the received vector; and is an error vector matching syndrome . Literally, these two marginal probability are describing the same event, thus should lead to the same result. Mathematically, one has to write it carefully and show they are isomorphic.
I.4 syndrome-based, LLR simplified
In a similar fashion of simplification, one can write the above equations into the log-likelihood-ratio form, then reach the following simple formula Liu and Poulin (2018)
The posterior log-likelihood ratio can be estimated as
This syndrome-based BP decoder can be used for quantum code as well. We first discuss the case of CSS codes, then the case of GF(4) codes.
I.5 discussion on quantum case
In CSS codes, one has . Say is the parity check matrix, then the only difference from a classical code with parity check matrix is that one need to check the decoded vector is an trivial error or not, that is, if it can be eliminated by rows of or not. Hence, the CSS code can use BP decoder directly with a post check.
In GF(4) code, the generator matrix satisfies , where . Here, one can just decode a classical code with parity check matrix , then check if it is a combination of rows of .
Note that, in both CSS codes and GF(4) codes, the correlation between X and Z errors are not considered. One way to consider the correlations is as following.
One can change the generator matrix from
The error changes from to , which satisfy . (Any single error will produce an even number of 1s in the vector. This is not the Pauli Y error, but simply a superposition of X and Z, mod 2.) This extra Y node contain the information that X and Z errors tend to appear or disapear in pair but not alone.
In this construction, we can just take the new parity check matrix as a classical binary code and use the basic BP decoder.
I.6 variation of BP
Finally, there are some optimization of BP decoder, including normalized and offset min-sum decoder Chen et al. (2005). Ref Panteleev and Kalachev (2019) says they are always using normalized offset min-sum decoder with mormalization factor .
Here I use to denote the check-to-variable messages for BP, min-sum, normalized min-sum, and off-set min-sum respectively. The relation on their sign and magnitute are
I.6.2 layered scheduling for updating rule
Ref Panteleev and Kalachev (2019) claim they used layered scheduling, which helped to eliminate the oscillating errors caused by the trapping sets. The criteria for how to choose the schedule is unclear for me yet.
I.6.3 enhanced feedback
Ref Wang et al. (2012) developed an optimization called Enhanced Feedback iterative BP decoder. In the second round of BP decoding, he locate the frustrated checks and some common qubits connected with them, then use the output probability to replace the input probability for those qubits. This approach is very similar to what I tried ( in the codeword-based LLR-simplified BP decoder for toric codes). The difference is that, I simply use the output probability (LLR vector) to replace the input probability for all qubits. I saw it fix all double errors on large-size (about 35x35) toric codes, but only tiny improvement in the numerics of small size (5, 7, 9, 11, 13). I am not sure about the reason on small size. there may be a bug in the program as well.
-  (2005) Improved min-sum decoding algorithms for irregular ldpc codes. In Proceedings. International Symposium on Information Theory, 2005. ISIT 2005., pp. 449–453. Cited by: §I.6.1.
-  (2018) Neural belief-propagation decoders for quantum error-correcting codes. arXiv preprint arXiv:1811.07835. Cited by: §I.4.
-  (2003) Information theory, inference and learning algorithms. Cambridge university press. Cited by: §I.3.
-  (2019) Degenerate quantum ldpc codes with good finite length performance. arXiv preprint arXiv:1904.02703. Cited by: §I.6.1, §I.6.2.
-  (2012) Enhanced feedback iterative decoding of sparse quantum codes. IEEE Transactions on Information Theory 58 (2), pp. 1231–1241. Cited by: §I.6.3.