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!
Quantum LDPC are usually categorised into one of two types:
A [[41,1,5]] surface code
[[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.
Belief propagation + ordered statisics decoding (BP+OSD) is a universal decoder for all* quantum LDPC codes
*that can be constructed from the hypergraph product...
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.
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?
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 $$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 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$.
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).
$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
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!