Preprint at arXiv:2005.07016

Download our code from: https://github.com/quantumgizmos/bp_osd

Logical state $|\psi \rangle_L$ subject to error: $E|\psi \rangle_L$

Code stablisers measured $S\in \mathcal{S}$ to get syndrome, $s$

Goal: find the best recovery operation $\mathcal{R}$ given the syndrome $s$

Decoder output applied to logical state: $\mathcal{R}E|\psi \rangle_L$

Success if: $\mathcal{R}E \in \mathcal{S}$ so that $\mathcal{R}E|\psi \rangle_L=|\psi \rangle_L$

Full cycle must take place before qubits decohere

(Estimated that) a full-scale quantum computer will output syndrome info. at rates of $Tb.s^{-1}$

=> An efficient decoding algorithm is essential!

$$\left[ \begin{matrix}
X&I&X&I&X&X&I&I\\I&X&I&X&X&X&I&I\\X&I&X&I&I&I&X&X\\I&X&I&X&I&I&X&X\\Z&Z&I&I&Z&I&Z&I\\Z&Z&I&I&I&Z&I&Z\\I&I&Z&Z&Z&I&Z&I\\I&I&Z&Z&I&Z&I&Z
\end{matrix}\right]$$
Stabilisers of the [[8,2,2]] Toric code

- In QEC, it is desirable to limit the number of interactions each qubit is subject to: more interactions mean more potential errors!
**Low density parity check**(LDPC) codes have stabilisers tables with row & column weights upper bounded by a constant.- Eg. the Toric code is a quantum LDPC code with row & column weights upper bounded by 4.

$$\left[ \begin{matrix}
X&I&X&I&X&X&I&I\\I&X&I&X&X&X&I&I\\X&I&X&I&I&I&X&X\\I&X&I&X&I&I&X&X\\Z&Z&I&I&Z&I&Z&I\\Z&Z&I&I&I&Z&I&Z\\I&I&Z&Z&Z&I&Z&I\\I&I&Z&Z&I&Z&I&Z
\end{matrix}\right]$$
Stabilisers of the [[8,2,2]] Toric code

Quantum LDPC are usually categorised into one of two types:

- Eg. the surface & toric codes
- Highly structured
- Nearest-neighbour interactions
- Poor encoding rate

- Good encoding rates.
- Typically require arbitrary qubit-qubit connectivity

- Eg. the surface & toric codes
- Highly structured
- Nearest-neighbour interactions
- Poor encoding rate

A [[41,1,5]] surface code

- Good encoding rates.
- Typically require arbitrary qubit-qubit connectivity

[[N,K,D]] | Code rate, K/N |
---|---|

[[400,16,6]] | 0.04 |

[[625,25,8]] | 0.04 |

[[900,36,10]] | 0.04 |

Code parameters of a family of finite-rate random QLDPC codes

A [[81,16,4]] random QLDPC code

We propose a class of "semi-topoligical" codes that exist between topological and random QLDPC codes.

- Eg. the surface & toric codes
- Highly structured
- Nearest-neighbour interactions
- Poor encoding rate

codes

- More logical qubits than surface/toric codes
- Fewer long-range interactions than random QLDPC codes

- Good encoding rates.
- Typically require arbitrary qubit-qubit connectivity

- More logical qubits than surface/toric codes
- Fewer long-range interactions than random QLDPC codes

- Mininum weight perfect matching (MWPM) near optimal for surface and Toric codes
- Belief propagation + ordered statistics decoding (BP+OSD)

- Small set-flip (SSF) decoder for expander codes [Grospellier & Krishna 2018]
- Belief propagation (BP) + SSF [Grospellier et al. 2020]
- Belief propagation + ordered statistics decoding (BP+OSD) [Panteleev & Kalachev 2019]

Belief propagation + ordered statisics decoding (BP+OSD) is a universal decoder for all* quantum LDPC codes

*that can be constructed from the hypergraph product...

- Classical LDPC codes & belief propagation decoding
- Why standard belief propagation fails in the quantum setting
- Ordered statistics post-processing
- BP+OSD decoding across the quantum LDPC landscape

- 1948: Shannon calculated bounds on the maximum rate of lossless transmission along noisy communication channels.
- 1963: Gallager proposed that
**low density parity check**(LDPC) codes could achieve performance at the Shannon-limit. However, LDPC codes were impractical to implement at the time: there was no efficient decoder! - 1996: Mackay & Neal demonstrated that LDPC codes could be efficiently decoded using a statistical inference technique known as
**belief propagation**(BP). - Today: LDPC codes decoded using BP are some of the best performing classical coding protocols. eg. they are used in the new 5G protocol.

For codewords $\mathbf{c}$ and parity check matrix $H$, the syndrome equation is $$\mathbf{s}=H(\mathbf{c}+\mathbf{e})=H\mathbf{e}$$

Decoder goal is to find the mininum-weight estimate $\mathbf{e}_{\rm MW}$ given $\mathbf{s}$ $$\mathbf{e}_{\rm MW} \mapsto \text{ARGMAX}_\mathbf{e} \ P(\mathbf{e}|\mathbf{z})$$

For uniformly distributed error models, we can express this as a marginalisation problem on each bit: $$P_1(e_i) = \sum\nolimits_{\sim e_i } P(e_1,e_2,e_i=1,e_3,...,e_n|\mathbf{s})$$

Exhaustive bit-wise decoding $$P(e_1) = \sum_{e_2} \sum_{e_3} ...\sum_{e_n} P(e_1e_2...e_n|s)$$

**Belief propagation**: computation of marginals is simplified by exploiting structure of probability distribution so that repeated sums are avoided
\begin{eqnarray}
P(e_i) = \sum_{e_2} \sum_{e_3} ...\sum_{e_n}P(e_1e_2...e_n|s)=&\\
\sum_{e_4} \sum_{e_5} ...&\sum_{e_n} f(e_4...e_n|s)...\sum_{e_2} f(e_2|s) \sum_{e_3}f(e_1,e_2,e_3|s)
\end{eqnarray}

The specific form of the factorisation is determined via the code's **factor graph** (the adjacency matrix of the parity check matrix). The pre-computed sums are referred to as **messages**.

- Soft decisions (error probabilities) are iteratively updated by passing messages between nodes.
- For tree-like graphs, BP converges within a number of iterations less than or equal to the block length.

The stabilizers of a CSS code can be represented with a binary matrix of the form

$$H=\left(\begin{array}{@{} c|c @{}} H_X&0\\\hline 0&H_Z \end{array}\right)$$Assuming an error model with uncorrelated X/Z errors, the bit- and phase components of a CSS codes can be decoded as separate decoding problems. eg. the syndrome equation for phase-flips:

$$\mathbf{s}_z=H_X\mathbf{e}_z$$Can we use BP to solve this decoding problem?

A [[13,1,3]] surface code

Quantum degeneracy: due to superposition, there is often more than one mininum-weight solution. eg

$$ \ket{\psi}_L = \frac{1}{\sqrt{2}}\left(\ket{00} +\ket{11}\right) $$ $$ \color{red}{X_1}\ket{\psi}_L = \frac{1}{\sqrt{2}}\left(\ket{\color{red}{1}0} +\ket{\color{red}{0}1}\right) $$For the above, there are two equally viable recovery operations $\mathcal{R}_1=X_1$ and $R_2=X_2$:

$$ \mathcal{R}_1\color{red}{X_1}\ket{\psi}_L =\mathcal{R}_2\color{red}{X_1}\ket{\psi}_L = \ket{\psi}_L $$- Ordered statistics decoding (OSD) is a post-processing routine that can be called when BP fails to converge (ie. when $H\mathbf{e}_{\rm BP} \neq \mathbf{s}$).
- OSD was first proposed in the classical setting by Fossorier and Lin (1995), as a technique for lowering the error floor of classical LDPC codes.
- Panteleev and Kalachev (2019) have recently shown that a BP+OSD decoder works surprisingly well for decoding random quantum LDPC codes. See their QEC19 talk here.

$$
H=\left(\begin{matrix}
0&1&0&0&1&0\\
0&0&1&0&0&1\\
1&0&0&1&0&0\\
1&0&0&0&1&1
\end{matrix}\right)
$$

We want to solve the decoding problem: $$s=He$$

Q: Can we solve by matrix inversion? $$e=H^{-1}s$$

Q: No. $H$ does not have full-column rank

However, we can invert a full-rank sub-matrix of $H_S\subset H$. Eg. $$H_S=\left(\begin{matrix} 1&0&0&1\\ 0&1&0&0\\ 0&0&1&0\\ 0&0&0&1 \end{matrix}\right) $$

A solution $\mathbf{e}$ can then be found $\mathbf{e}=H_S^{-1}s$.

Problem: there are many ways of choosing $H_S$ involving different bits.

- The OSD algorithm uses the soft-decision output of BP to find the 'best' full column-rank submatrix $H_S$.

- Mininum weight perfect matching (MWPM) near optimal for surface and Toric codes
- Belief propagation + ordered statistics decoding (BP+OSD)

- Small set-flip (SSF) decoder for expander codes [Grospellier & Krishna 2018]
- Belief propagation (BP) + SSF [Grospellier et al. 2020]
- Belief propagation + ordered statistics decoding (BP+OSD) [Panteleev & Kalachev 2019]

The hypergraph product: a method for constructing a CSS code $H_{\rm CSS}$ from any pair of classical codes $H_1$ and $H_2$ [Tillich and ZĂ©mor 2014]

**Construction** Given any two classical codes $H_1$ ($[n_1,k_1,d_1]$) and $H_2$ ($[n_2,k_2,d_2]$), we can define a CSS code with the following $H_X$ and $H_Z$ components
\begin{equation*}\label{eq:hgp_h}
\begin{split}
H_X=( \ H_1 \otimes I_{n_2} \ | \ I_{m_1} \otimes H_2^T \ ){\rm,}\\
H_Z = (\ I_{n_1} \otimes H_2 \ | \ H_1^T \otimes I_{m_2} \ )\rm.
\end{split}
\end{equation*}

**Note**: The CSS commutivity constraint $H_XH_Z^T=0$ is satisfied for all $H_1$ and $H_2$.

Base codes: $$H_1=\left(\begin{matrix} 1&1 \end{matrix}\right)$$ $$H_2=\left(\begin{matrix} 1&1 \end{matrix}\right)$$

Hypergraph product code \begin{eqnarray*} H_X =( \ H_1 \otimes I_{n_2} \ | \ I_{m_1} \otimes H_2^T \ )\\=\left(\begin{array}{@{} cccc|c @{}} 1&0&1&0&1\\ 0&1&0&1&1 \end{array}\right) \end{eqnarray*} \begin{eqnarray*} H_Z =(\ I_{n_1} \otimes H_2 \ | \ H_1^T \otimes I_{m_2} \ )\\=\left(\begin{array}{@{} cccc|c @{}} 1&1&0&0&1\\ 0&0&1&1&1 \end{array}\right) \end{eqnarray*}

The hypergraph product of the [6,2,4] spoke code with the [2,1,2] repetition code.

This semi-topoligical code has three distinct surface code patches coupled by a small number of long range interactions (far fewer than in a random QLDPC code).

- Start with the factor graph of classical code
- Augment each edge with a length-n section of repettion code
- Take the hypergraph product of the augmented code with itself
- The resultant semi-topological code will have $\lambda^2$ surface code patches, where $\lambda$ is the number of edges in the original factor graph.

$g$ | $\mathcal{C}_H^{*g}$ | $(\mathcal{C}_H^{*g})^T$ | $\mathcal{HGP}(\mathcal{C}_H^{*g})$ | $R$ | $\bar{w}$ |
---|---|---|---|---|---|

0 | $[3,2,2]$ | $[2,1,1]$ | $[[13,5,2]]$ | $0.385$ | $5.00$ |

1 | $[9,2,6]$ | $[8,1,8]$ | $[[145,5,6]]$ | $ 0.0345$ | $4.25$ |

2 | $[15,2,10]$ | $[14,1,14]$ | $[[421,5,10]]$ | $0.0119$ | $4.14$ |

3 | $[21,2,14]$ | $[20,1,20]$ | $[[841,5,14]]$ | $0.00595$ | $4.10$ |

9 | $[57,2,38]$ | $[56,1,56]$ | $[[6385,5,38]]$ | $0.000783$ | $4.04$ |

__Main takeaways__

- BP+OSD is an extremely versatile decoder for quantum codes
- Our numerics imply BP+OSD is a useful decoder for all quantum codes that can be constructed using the hypergraph product
- If you are looking for a good decoder for a quantum LDPC code, you should give BP+OSD a try.

Code | BP | BP+OSD |
---|---|---|

Toric | N/A | $9.9\pm0.2\%$ |

Semi-topological | N/A | $9.7\pm0.2\% $ |

Random | $6.5\pm0.1\%$ | $7.1\pm0.1 \% \ $ |

Download our open-source implemenation of BP+OSD: https://github.com/quantumgizmos/bp_osd. Try it out on your favourite quantum error correction codes!