Refined Belief-Propagation Decoding of Quantum Codes with Scalar Messages

We consider the syndrome-based decoding. Consider an $[N,K]$ classical binary linear code defined by an $M\times N$ parity-check matrix $H\in\{0,1\}^{M\times N}$ (not necessarily of full rank) with $M\geq N-K$. Upon the reception of a noisy codeword disturbed by an unknown error $E=(E_{1},E_{2},\dots,E_{N})\in\{0,1\}^{N}$, syndrome measurements (defined by rows of $H$) are performed to generate a syndrome vector $z\in\{0,1\}^{M}$. The decoder is given $H$, $z$, and an a priori distribution $\boldsymbol{p}_{n}=(p_{n}^{(0)},p_{n}^{(1)})$ for each $E_{n}$ to infer an $\hat{E}$ such that the probability $P(\hat{E}=E)$ is as high as possible.²²2 Giving $\boldsymbol{p}_{n}$ can be according to a channel model [5] or even a fixed distribution (useful if the channel parameter is unknown) [38]. Here, we uses the former case since it usually has a better performance. BP decoding is done by updating each $\boldsymbol{p}_{n}$ as an a posterior distribution $\boldsymbol{q}_{n}=(q_{n}^{(0)},q_{n}^{(1)})$ and inferring $\hat{E}=(\hat{E}_{1},\hat{E}_{2},\dots,\hat{E}_{N})$ by $\hat{E}_{n}=\operatorname*{arg\,max}_{b\in\{0,1\}}q_{n}^{(b)}$. This is done by doing an iterative message-passing on the Tanner graph defined by $H$.

The Tanner graph corresponding to $H$ is a bipartite graph consisting of $N$ variable nodes and $M$ check nodes, and there is an edge $(m,n)$ connecting check node $m$ and variable node $n$ if entry $H_{mn}=1$. Let $H_{m}$ be row $m$ of $H$. An example Tanner graph of $H=\left[\begin{smallmatrix}1&1&0\\ 1&1&1\end{smallmatrix}\right]$ is shown in Fig. 1.

For the iterative message-passing, there will be a variable-to-check message $d_{n\to m}$ and a check-to-variable message $\delta_{m\to n}$ passed on edge $(m,n)$. Let ${\cal N}(m)=\{n:H_{mn}=1\}$ and ${\cal M}(n)=\{m:H_{mn}=1\}$. (And we will write things like ${\cal M}(n)\setminus\{m\}$ as ${\cal M}(n)\setminus m$ to simplify the notation.) Assume that every $\delta_{m\to n}=0$ initially. An iteration is done by:

• •

  $d_{n\to m}$ is computed by $\{\delta_{m^{\prime}\to n}:m^{\prime}\in{\cal M}(n)\setminus m\}$ with $\boldsymbol{p}_{n}$,

• •

  $\delta_{m\to n}$ is computed by $\{d_{n^{\prime}\to m}:n^{\prime}\in{\cal N}(m)\setminus n\}$ with $z_{m}$,

• •

  $\boldsymbol{q}_{n}$ is computed by $\{\delta_{m\to n}:m\in{\cal M}(n)\}$ with $\boldsymbol{p}_{n}$.

The messages $d_{n\to m}$ and $\delta_{m\to n}$ will be denoted, respectively, by $d_{mn}$ and $\delta_{mn}$ for simplicity. The message-passing is usually done with a parallel schedule, referred to as parallel BP₂ (cf. [39, Algorithm 1], which has $d_{mn}$ and $\delta_{mn}$ as likelihood differences (LDs) and is due to MacKay and Neal [3, 4, 5]).

The message-passing can also be done with a serial schedule, referred to as serial BP₂ [39, Algorithm 2]. We compared parallel/serial BP₂ by decoding a $[13298,3296]$ code in [39, Figs. 4 and 5], showing that serial BP₂ has a better convergence within limited iterations (as expected in [32, 33, 34]).

The computation in parallel/serial BP₂ can be substantially simplified and represented by simple update rules, corresponding to weight-2 and weight-3 rows. These simple rules can in turn be extended to define the general rules [9, Sec. V-E]. Consider $H=\left[\begin{smallmatrix}1&1&0\\ 1&1&1\end{smallmatrix}\right]$ as in Fig. 1. Recall that we denote $P(E_{1}=0)=p_{1}^{(0)}$ and $P(E_{1}=1)=p_{1}^{(1)}$. Let $E_{2}+E_{3}$ be a super bit indexed by $\{2,3\}$. Then we have the representation $P(E_{2}+E_{3}=0)=p_{\{2,3\}}^{(0)}$ and $P(E_{2}+E_{3}=1)=p_{\{2,3\}}^{(1)}$. By Bayes rule and some derivations, we can update the (conditional) distribution of $E_{n}$, say $n=1$, by:

We will use the notation based on Pauli operators $\left\{I=\left[\begin{smallmatrix}1&0\\ 0&1\end{smallmatrix}\right],X=\left[\begin{smallmatrix}0&1\\ 1&0\end{smallmatrix}\right],Y=\left[\begin{smallmatrix}0&-i\\ i&0\end{smallmatrix}\right],Z=\left[\begin{smallmatrix}1&0\\ 0&-1\end{smallmatrix}\right]\right\}$ [41], and consider $N$-fold Pauli operators with an inner product

which has an output 0 if the inputs commute and an output 1 if the inputs anticommute. (This is mathematically equivalent to mapping $\{I,X,Y,Z\}^{\otimes N}\to$ GF(4)^N with a Hermitian trace inner-product to the ground field GF(2) [17]). It suffices to omit $\otimes$ in the following discussion. An unknown error will be denoted by $E=E_{1}E_{2}\cdots E_{N}\in\{I,X,Y,Z\}^{N}$.

There will a check matrix $S\in\{I,X,Y,Z\}^{M\times N}$ used to generate a syndrome $z\in\{0,1\}^{M}$. Consider a simple example $S=\left[\begin{smallmatrix}S_{11}&S_{12}&I\\ S_{21}&S_{22}&S_{23}\\ \end{smallmatrix}\right]$, where there are five non-identity entries. For simplicity, fix it as $S=\left[\begin{smallmatrix}X&Y&I\\ Z&Z&Y\\ \end{smallmatrix}\right]$ and the other cases can be handled similarly. The Tanner graph (with generalized edge types $X,Y,Z$) of the example $S$ is shown in Fig. 2.

For decoding quantum codes, we are to update an initial distribution $\boldsymbol{p}_{n}=(p_{n}^{I},p_{n}^{X},p_{n}^{Y},p_{n}^{Z})$ of $E_{n}$ as an updated (conditional) distribution $\boldsymbol{q}_{n}=(q_{n}^{I},q_{n}^{X},q_{n}^{Y},q_{n}^{Z})$. Again (as in Sec. II-B) assume that the syndrome is a zero vector and we are to update the distribution of $E_{n}$ with $n=1$. By Bayes rule and some derivations, we have:

An $[[N,K]]$ stabilizer code is a $2^{K}$-dimensional subspace of $\mathbb{C}^{2^{N}}$ fixed by the operators (not necessarily all independent) defined by a check matrix $S\in\{I,X,Y,Z\}^{M\times N}$ with $M\geq N-K$. Each row $S_{m}$ of $S$ corresponds to an $N$-fold Pauli operator that stabilizes the code space. The matrix $S$ is self-orthogonal with respect to the inner product (6), i.e., $\langle S_{m},S_{m^{\prime}}\rangle=0$ for any two rows $S_{m}$ and $S_{m^{\prime}}$. The code space is the joint-($+1$) eigenspace of the rows of $S$. The vectors in the (multiplicative) rowspace of $S$ are called stabilizers [41].

It suffices to consider discrete errors like Pauli errors per the error discretization theorem [41]. Upon the reception of a noisy coded state suffered from an unknown $N$-qubit error $E\in\{I,X,Y,Z\}^{N}$, $M$ stabilizers $\{S_{m}\}_{m=1}^{M}$ are measured to determine a binary error syndrome $z=(z_{1},z_{2},\dots,z_{M})\in\{0,1\}^{M}$ using (6), where

Given $S$, $z$, and an a priori distribution ${\boldsymbol{p}}_{n}=(p_{n}^{I},p_{n}^{X},p_{n}^{Y},p_{n}^{Z})$ for each $E_{n}$ (e.g., let ${\boldsymbol{p}}_{n}=(1-\epsilon,\,\epsilon/3,\,\epsilon/3,\,\epsilon/3)$ for a depolarizing channel with error rate $\epsilon$), a decoder has to estimate an $\hat{E}\in\{I,X,Y,Z\}^{N}$ such that $\hat{E}$ is equivalent to $E$, up to a stabilizer, with a probability as high as possible. (The solution is not unique due to the degeneracy [27, 42].)

For decoding quantum codes, the neighboring sets are ${\cal N}(m)=\{n:S_{mn}\neq I\}$ and ${\cal M}(n)=\{m:S_{mn}\neq I\}$. Let $E|_{{\cal N}(m)}$ be the restriction of $E=E_{1}E_{2}\cdots E_{N}$ to ${\cal N}(m)$. Then $\langle E,S_{m}\rangle=\langle E|_{{\cal N}(m)},S_{m}|_{{\cal N}(m)}\rangle$ for any $E$ and $S_{m}$.³³3 For example, if $S_{m}=IXZ$ and $E=E_{1}E_{2}E_{3}$, then
$E|_{{\cal N}(m)}=(E_{1}E_{2}E_{3})|_{{\cal N}(m)}=E_{2}E_{3}$ and $S_{m}|_{{\cal N}(m)}=XZ$. Then
$\langle E,S_{m}\rangle=\langle E_{1}E_{2}E_{3},IXZ\rangle=\left\langle E_{2}E_{3},XZ\right\rangle=\langle E|_{{\cal N}(m)},S_{m}|_{{\cal N}(m)}\rangle.$

A conventional BP₄ for decoding binary stabilizer codes is done as follows [27]. In the initialization step, every variable node $n$ passes the message $\boldsymbol{q}_{mn}=(q_{mn}^{I},q_{mn}^{X},q_{mn}^{Y},q_{mn}^{Z})$ $={\boldsymbol{p}}_{n}$ to every neighboring check node $m\in{\cal M}(n)$.

• •

  Horizontal Step: At check node $m$, compute $\boldsymbol{r}_{mn}=(r_{mn}^{I},r_{mn}^{X},r_{mn}^{Y},r_{mn}^{Z})$ and pass $\boldsymbol{r}_{mn}$ as the message $m\to n$ for every $n\in{\cal N}(m)$, where $\forall~{}W\in\{I,X,Y,Z\}$,

  $${r_{mn}^{W}=\sum_{E|_{{\cal N}(m)}:~{}E_{n}=W,\atop\left\langle E|_{{\cal N}(m)},S_{m}|_{{\cal N}(m)}\right\rangle=z_{m}}\left({\prod_{n^{\prime}\in{\cal N}(m)\setminus n}q_{mn^{\prime}}^{E_{n^{\prime}}}}\right).}$$

• •

  Vertical Step: At variable node $n$, compute $\boldsymbol{q}_{mn}=(q_{mn}^{I},q_{mn}^{X},q_{mn}^{Y},q_{mn}^{Z})$ and pass $\boldsymbol{q}_{mn}$ as the message $n\to m$ for every $m\in{\cal M}(n)$, where

  $${q_{mn}^{W}=a_{mn}\,p_{n}^{W}\prod_{m^{\prime}\in{\cal M}(n)\setminus m}r_{m^{\prime}n}^{W}}$$

  with $a_{mn}$ a chosen scalar to let $\sum_{W\in\{I,X,Y,Z\}}q_{mn}^{W}=1$.

At variable node $n$, it also computes $q_{n}^{W}=p_{n}^{W}\prod_{m\in{\cal M}(n)}r_{mn}^{W}$ to infer $\hat{E}_{n}=\operatorname*{arg\,max}_{W\in\{I,X,Y,Z\}}q_{n}^{W}$. The horizontal and vertical steps are iterated until an estimated $\hat{E}=\hat{E}_{1}\hat{E}_{2}\cdots\hat{E}_{N}$ is valid or a maximum number of iterations is reached.

For a variable node, say variable node 1, and its neighboring check node $m$, we know from (10) that

Given the value $\langle E_{n},S_{mn}\rangle$ of (a possible) $E_{n}\in\{I,X,Y,Z\}$ and some $S_{mn}\in\{X,Y,Z\}$, we will know that $E_{n}$ commutes or anticommutes with $S_{mn}$, i.e., either $E_{n}\in\{I,S_{mn}\}$ or $E_{n}\in\{X,Y,Z\}\setminus S_{mn}$. Consequently, the passed message should indicate more likely whether $E_{n}\in\{I,S_{mn}\}$ or $E_{n}\in\{X,Y,Z\}\setminus S_{mn}$. In other words, the message from a neighboring check will tell us more likely whether the error $E_{1}$ commutes or anticommutes with $S_{m1}$. This suggests that a BP decoding of stabilizer codes with scalar messages is possible and we provide such an algorithm in Algorithm 1, referred to as parallel BP₄ (the same as [39, Algorithm 3]). Note that the notation $r_{mn}^{(\langle W,S_{mn}\rangle)}$ is simplified as $r_{mn}^{\langle W,S_{mn}\rangle}$.

It can be shown that Algorithm 1 has exactly the same output as the conventional BP₄ (as outlined in Sec. III-A). In particular, Algorithm 1 has a check-node efficiency 16-fold improved from the conventional BP₄.

Similar to the classical case, we can consider running Algorithm 1 with a serial schedule, referred to as serial BP₄ (cf. [39, Algorithm 4]). Using serial BP₄ may prevent the decoding oscillation (as an example based on the $[[5,1,3]]$ code in [39, Fig. 7]) and improve the empirical performance (e.g., for decoding a hypergraph-product code [39, Fig. 8]).