Decoding Across the Quantum LDPC Code Landscape
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
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.
What is the quantum LDPC code landscape?
What is the quantum LDPC code landscape?
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
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.
- 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
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
- 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]
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
- 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
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?
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
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
- 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]
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
- 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$ |
BP+OSD Decoding of semi-topological codes
Summary - decoding across the LDPC code landscape
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!