Decoding Across the Quantum LDPC Code Landscape

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

Preprint at arXiv:2005.07016

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

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?

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

    BP and the surface code: example 1

    Threshold Plot: BP Decoding of the Toric 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 $$

    BP and the surface code: example 2

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

    Threshold Plot: BP+OSD decoding of the Toric code

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

    Semi topological codes from the hypergraph product

    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: \begin{equation} [[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. \end{equation}

    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

    1. Start with the factor graph of classical code
    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.

    BP+OSD Decoding of semi-topological codes

    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!