Joint decoding using Belief-Propagation

In this article, we take a first step from classical LDPC towards qLDPC. We discuss how channel information is fed into the decoder and how this impacts the decoding process. To this end, we first take a more detailed look at decoding for classical LDPC codes and then generalize to qLDPC.

The goal of classical Belief-Propagation (BP) decoding is to infer the most likely codeword given the information received from the channel. This includes measured channel output and knowledge about the channel's characteristics. For sake of clarity, let us assume that we transmit a codeword of length n using binary phase-shift keying (BPSK) modulation, which results in signalling n symbols over the channel. At the receiver, we learn about the transmitted signal by measuring the channel output at n predefined sampling instants.

The figure below shows a classical belief-propagation decoder with variable nodes, check nodes, and the connections between them. Each variable node represents one classical bit of the codeword, and each check node represents one parity-check equantion of the code's parity-check matrix. Each received value, y_1 to y_n, is fed into one of the variable nodes, along with information on the channel characteristics denoted by sigma. The key observation is that the n variable nodes are the entry point for all information obtained from the channel.

Decoding process summary:

• Preload: Feed variable node i with y_i and sigma (i=1:n).
• Pre-process: Using the preloaded information, each variable node infers its likelihood value.
• Run: Perform iterations until all checks are satisfied by a tentative binary quantization at the variable nodes, or until a maximum number of iterations is reached - whichever comes first.
• Readout: Read the estimated codeword as a binary quantization from the variable nodes. In case of systematic encoding it suffices to read out the subset containing the original information.

Let us now switch to qubits. For a moment we will assume that qubits can only have amplitude errors. This is not true as qubits also suffer from phase errors, but it allows us to focus on the important observation of this article: how feeding information the decoder needs to be adapted and how the decoding process itself changes when qubits are considered. Further, quantum error correction builds robustness on the stabilizer formalism, but we will continue to refer to parity checks for easier comparsion with the classical case.

Unlike with classical bits, qubits collapse when being measured. The details depend a lot on how we measure, but in general, we need to find another way of retrieving information at the receiver. Direct measuring of qubits is not an option, as QEC will be used at intermediate steps in quantum computing, or even continouosly, and hence the decoding process shall not interfere with the qubits.

In quantum error correction, we can observe qubits only indirectly. At the receiver, we prepare ancilla qubits and entangle them with the actual qubits of interest. Measurements will then be performed on those ancilla qubits. In the scope of LDPC, this can be understood as measurements providing information on the likelihood of a certain parity check being satisified. The picture below shows which decoder-relevant information is available from measurements when dealing with qubits.

Note that the channel statistics (sigma) are henceforth passed to the variable nodes. However, the received values y_1 to y_n are not available. Instead, only information on whether the checknodes are fulfilled is available from measurement of the ancilla qubits. We call this information z_1 to z_(n-k) and in this picture, we depict it as entering on the check-node side. Additionally, we feed the channel characteristics value sigma'. This value describes the channel stemming from errors during preparation and measurements of ancilla qubits. How can we pass z_1 to z_(n-k) such that the decoder can make good use of it? Assigning it to the check node, e.g. as a bias, would escalate these measurements to ground truth and keep the decoder from performing error correction. Instead, we need to augment the decoder with additional, special variable nodes which hold the parity-check information. This is shown in the figure below.

Observe in the figure that there are n-k additional variable nodes. They are special in the sense that there is one additional variable node for each parity-check node and that each additional variable node has exactly one connection with its corresponding parity-check node. The parity-check nodes continue to have their regular connections to the first n variable nodes. In other words, the degree of each parity-check node is increased by one due to its connection with the additional variable node. The information z_1 to z_n, which can be understood as a bias to the parity-check nodes, is fed into the augmented check nodes, along with \sigma'. This setup brings all available information into the decoder and allows for the decoder to correct errors within z_1 to z_n during the iterative decoding process.

Summary of the decoding process using qubits and the BP decoder with augmented variable nodes:

• Preload: Feed variable nodes i with sigma (i=1:n). Feed variable nodes j with z_j and sigma' (j=n+1:n+n-k).
• Pre-process: Variable node i (i=1:n) assumes the value 0 and sets the corresponding likelihood according to sigma. Variable nodes j (j=n+1:n+n-k) calculate their likelihoods according to z_j and sigma'.
• Run: Perform iterations until all checks are satisfied by a tentative binary quantization at the variable nodes, or until a maximum number of iterations is reached - whichever comes first.
• Readout: Read the most likely error pattern from variable nodes i (i=1:n).

It is important to note that in the case of qubits, the variable nodes do not hold a codeword, but an error pattern. Further processing of the qubits requires correction measures, or logging the errors in a Pauli frame.

Joint decoding is implemented in ldpc_dec, along with a simple binary symmetric channel (BSC) for qubits. Feel free to try it out.