# Decoding Across the Quantum LDPC Code Landscape

Joschka Roffe, David R. White, Simon Burton & Earl T. Campbell

Preprint at arXiv:2005.07016

# The QEC Cycle

### Syndrome Extraction

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

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

### Decoding algorithm

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

### Recovery

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$

### QEC Cycle Clockspeed

Full cycle must take place before qubits decohere

### Decoding bottleneck

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

=> An efficient decoding algorithm is essential!

# Quantum LDPC Codes

$$\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 Codes

• 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

# What is the quantum LDPC code landscape?

Quantum LDPC are usually categorised into one of two types:

Topological codes

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

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

## Topological codes

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

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

## Random QLDPC codes

• 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

## Introducing: semi-topological codes

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

Topological codes

• Eg. the surface & toric codes
• Highly structured
• Nearest-neighbour interactions
• Poor encoding rate
Semi-topological
codes
• More logical qubits than surface/toric codes
• Fewer long-range interactions than random QLDPC codes
Random QLDPC codes

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

# Semi-topoligical codes

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

## Decoding across the quantum LDPC code landscape

Topological codes

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

?????????????????? ?????????????????? ??????????????????
• Belief propagation + ordered statistics decoding (BP+OSD)
• Random QLDPC codes

# Main result

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

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

# Talk Overview

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

# A brief history of classical LDPC coding

• 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.

# The classical decoding problem

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})$$

# The Belief propagation algorithm

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.

### Example: decoding the repetition code with BP

• 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.

# Belief propagation for quantum codes

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: Why standard BP fails for decoding quantum codes

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 post-processing

• 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.

## The BP+OSD Algorithm

$$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$.

# ...Back to the LDPC code landscape

## Decoding across the quantum LDPC code landscape

Topological codes

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

• Belief propagation + ordered statistics decoding (BP+OSD)
• Random QLDPC codes

# The hypergraph product

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*}

The resultant CSS code has paramaters: $$[[N=n_1n_2+m_1m_2,\ K=k_1k_2+k_1^Tk_2^T,\ D={\rm min}(d_1,d_2,d_1^T,d_2^T)]]\rm.$$

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

## Example: The surface code from the hypergraph product

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*}

## A simple semi-topological code: base codes

### A simple semi-topological code: taking the hypergraph product

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).

## A simple semi-topological code

### A general construction for semi-topological codes

2. Augment each edge with a length-n section of repettion code
3. Take the hypergraph product of the augmented code with itself
4. 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$
Code parameters for the family of semi-topological codes constructed by edge-augmenting the base code to the right.

# Summary - decoding across the LDPC code landscape

Main takeaways

1. BP+OSD is an extremely versatile decoder for quantum codes
2. Our numerics imply BP+OSD is a useful decoder for all quantum codes that can be constructed using the hypergraph product
3. 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 \% \$
Summary of numerical thresholds for three families of codes across the LDPC code landscape. The random codes were constructed by taking the hypergraph product of a family of finite-rate classical LDPC codes. More details in arXiv:2005.07016.

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