Decoders for quantum error correction

Belief propagation + ordered statistics decoding (BP+OSD)

The belief propagation + ordered statistics decoder (BP+OSD) is a modified version of BP that works well for quantum LDPC codes. An advantage of the BP+OSD decoder is that it always returns a decoding that satisfies the syndrome equation.

The LDPC implementation of BP+OSD inherits from the ldpc.BpDecoder class. The setup is therefore very similar, with only two extra parameters to specify the osd_method and the osd_order. The LDPCv2 package now includes an implementation of the fast-solve algorithm for OSD_0, which terminates the Gaussian elimination as soon as the syndrome becomes linearly dependent on the columns elimianted up to that point.

An example is below:

[6]:

import numpy as np
import ldpc.codes
from ldpc import BpOsdDecoder

H = ldpc.codes.hamming_code(5)

## The
bp_osd = BpOsdDecoder(
            H,
            error_rate = 0.1,
            bp_method = 'product_sum',
            max_iter = 7,
            schedule = 'serial',
            osd_method = 'osd_cs', #set to OSD_0 for fast solve
            osd_order = 2
        )

syndrome = np.random.randint(size=H.shape[0], low=0, high=2).astype(np.uint8)

print(f"Syndrome: {syndrome}")
decoding = bp_osd.decode(syndrome)
print(f"Decoding: {decoding}")
decoding_syndrome = H@decoding % 2
print(f"Decoding syndrome: {decoding_syndrome}")

Syndrome: [1 0 1 1 1]
Decoding: [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0]
Decoding syndrome: [1 0 1 1 1]

Belief propagation + localized statistics decoding (BP+LSD)

The belief propagation + localized statistics decoder (BP+LSD) is a parallel inversion-based decoder for quantum LDPC codes (see our paper https://arxiv.org/abs/2406.???). Similar to OSD, the LSD algorithm solves the decoding problem through matrix inversion. However, matrix inversion is performed on local error clusters rather than over the entire parity check matrix. This considerably speeds up decoding relative to BP+OSD for large parity check matrices. Higher-order reprocessing, using either the ‘combination sweep’ or ‘exhaustive’ strategy can also be performed locally for each cluster.

An advantage of LSD (over OSD) is that the number of bp iterations (BpDecoder.max_iter) can be set to a small number (experiment with this, but we find ~30 usually suffices) without reducing runtime. The decoder then relies more on the post-processor, but this does not matter as the runtime of the LSD algorithm scales (roughly) with the error rate rather than the size of the parity check matrix (as is the case for BP+OSD).

The LDPC implementation of BP+LSD inherits from the ldpc.BpDecoder class. The setup is therefore very similar, with only two extra parameters to specify the lsd_method and the lsd_order. Note that for higher-order reprocessing, lsd_cs-w and osd_cs-w are not entirely equivalent, so expect some differences.

An example is below:

[7]:

import numpy as np
import ldpc.codes
from ldpc.bplsd_decoder import BpLsdDecoder

H = ldpc.codes.hamming_code(5)

## The
bp_osd = BpLsdDecoder(
            H,
            error_rate = 0.1,
            bp_method = 'product_sum',
            max_iter = 2,
            schedule = 'serial',
            osd_method = 'lsd_cs',
            osd_order = 2
        )

syndrome = np.random.randint(size=H.shape[0], low=0, high=2).astype(np.uint8)

print(f"Syndrome: {syndrome}")
decoding = bp_osd.decode(syndrome)
print(f"Decoding: {decoding}")
decoding_syndrome = H@decoding % 2
print(f"Decoding syndrome: {decoding_syndrome}")

Syndrome: [0 1 0 1 1]
Decoding: [0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
Decoding syndrome: [0 1 0 1 1]

Belief-find

The belief propagation + union-find decoder (belief-find) is an alternative to BP+OSD/LSD for decoding quantum LDPC codes. Belief-find first attempts to solve the decoding using belief propagation. If this fails, a union-find decoder is run as a post-processor using the output of BP to guide cluster growth. The LDPC package implements two versions of belief-find:

  1. Peeling belief-find. This approach uses a peeling decoder to solve the local decoding problem in each cluster. Peeling uinon-find is limited to decoding codes that have point like syndromes. e.g, the surface and toric codes. The peeling version of union-find decoder was first proposed by Delfosse & Nickerson in (https://arxiv.org/abs/1709.06218). Peeling belief-find was first proposed and implemented by Oscar Higgott (https://arxiv.org/abs/2203.04948).

  2. Cluster-inversion belief-find. This approach solves the local decoding problem on each cluster using matrix inverison. Cluster-inversion union find can be applied to any quantum LDPC code. Matrix inversion find was first proposed by Delfosse et al. (https://arxiv.org/abs/2103.08049), and later improved by Berent et al. (https://arxiv.org/abs/2209.01180).

The LDPC implementation of belief-find inherits from the ldpc.BpDecoder class.

An example of the cluster-inversion belief-find decoder is below:

[8]:

import numpy as np
import ldpc.codes
from ldpc import BeliefFindDecoder

H = ldpc.codes.hamming_code(5)

## The
bf = BeliefFindDecoder(
            H,
            error_rate = 0.1,
            bp_method = 'product_sum',
            max_iter = 7,
            schedule = 'serial',
            uf_method = "inversion", # Union-find clusters are solved by matrix inversion
            bits_per_step = 1 ## this is the number of bits by which clusters are expanded in each growth step
        )

syndrome = np.random.randint(size=H.shape[0], low=0, high=2).astype(np.uint8)

print(f"Syndrome: {syndrome}")
decoding = bf.decode(syndrome)
print(f"Decoding: {decoding}")
decoding_syndrome = H@decoding % 2
print(f"Decoding syndrome: {decoding_syndrome}")

Syndrome: [0 0 1 0 1]
Decoding: [0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
Decoding syndrome: [0 0 1 0 1]

The peeling version of belief-find can be activated by setting uf_method="peeling". This method only works for parity check matrix that yield point-like syndromes. An example of using peeling belief-find on the repetition code is show below:

[9]:

import numpy as np
import ldpc.codes
from ldpc import BeliefFindDecoder

H = ldpc.codes.ring_code(15)

## The
bf = BeliefFindDecoder(
            H,
            error_rate = 0.1,
            bp_method = 'product_sum',
            max_iter = 7,
            schedule = 'serial',
            uf_method = "peeling", # If uf_method is set to False, union-find clusters are solved using a peeling decoder
            bits_per_step = 1 ## this is the number of bits by which clusters are expanded in each growth step
        )


[10]:

error = np.random.randint(size=H.shape[0], low=0, high=2).astype(np.uint8)
syndrome = H@error % 2

decoding = bf.decode(syndrome)
print(f"Decoding: {decoding}")
decoding_syndrome = H@decoding % 2
print(f"Decoding syndrome: {decoding_syndrome}")

Decoding: [1 0 1 0 0 0 1 0 0 1 1 0 0 1 0]
Decoding syndrome: [1 1 1 0 0 1 1 0 1 0 1 0 1 1 1]