Path: blob/main/qec101/Solutions/04_QEC_Decoders_Solution.ipynb
1143 views
QEC 101
Lab 4: Decoders
QEC is only effective if the codes utilized to flag errors can be interpreted to identify the errors to be fixed. This is the job of a decoder. Decoding is one of the most challenging yet critical aspects of QEC and finding good decoders is a major researcher objective in the field.
This lab introduces the basic concepts of decoding and frames why the problem is so difficult. In the later sections, you will then work through a number of exercises to implement a naive "brute force" decoder, train an AI decoder, and explore how GPUs can power advanced decoding algorithms like belief propagation with ordered statistics decoding.
Prerequisites: This is the 4th lab in the QEC series. If you are not familiar with the basics of classical or quantum error correction (EC), please complete "The Basics of Classical and Quantum Error Correction" first. It is also helpful to have completed "Stabilizers, the Shor Code, and the Steane Code" in which stabilizers and syndromes are introduced in detail. This notebook also walks you through building a Steane code implementation in CUDA-Q which is used again in this lab.
The list below outlines what you'll be doing in each section of this lab:
4.1 Understand what decoding is, why it is important, and what makes it so difficult
4.2 Explore Pauli frames and error tracking
4.3 Code a naive brute force decoder for the Steane Code
4.4 Train an AI decoder for the Steane Code
4.5 Experiment with NVIDIA's accelerated belief propagation decoder.
Terminology and notation you'll use:
decoders, decoding window, Pauli frames
most likely error decoding
AI decoding
Belief propagation and ordered statistics decoding
š» Just a heads-up: This notebook is designed to be run on an environment with a GPU. If you don't have access to a GPU, feel free to read through the cells and explore the content without executing them. Enjoy learning! ā
To get started, run the cells below to install the prerequisite libraries and then restart the kernel.
4.1 Decoding Decoded
Remember that a QEC round involves four main steps:
Encoding logical qubits and sending the system through a noisy channel, which is often just a duration of time where the qubits are exposed to potential sources of error
Measuring syndrome data
Decoding the syndrome to identify where an error occurred and what instructions to send to the QPU to fix the error
Correcting the error
The decoding step is very challenging and is considered one of the primary limitations for QEC. This is because decoding requires measurements on a QPU, data transfer to the supercomputer, decoding on the supercomputer, and then data transfer back to the QPU. The time available for this is called the decoding window and varies based on a number of factors such as the qubit modality, data transfer rates, and the volume of information that needs to be decoded.
The simulation below makes this more clear. First, set the time for the decoding window. All 50 syndromes must be decoded in this time, otherwise the QEC procedure fails. In many cases, syndromes vary in decoding difficulty, so this simulation samples random times from a normal distribution. Try changing the parameters of the distribution and see how this impacts the decoder's success rate.
Notice how even if a decoder is quite fast and can decode most of the syndromes in time, the worst-case scenario (i.e. hardest syndrome to decode) is usually the limiting factor.
Directly competing with speed is accuracy. If a decoder is inaccurate, errors will be missed or introduced each QEC round and will propagate to ruin the computation. High-distance codes are necessary for accuracy, but unfortunately introduce high-qubit overheads and make decoding much more challenging. Advances in QEC code design and low-latency integration between AI supercomputers and QPUs alleviate pressure on the decoding step, but it nevertheless remains the primary bottleneck of QEC.
4.2 Pauli Frames and Error Tracking
In practice, when errors are identified by the decoder, they are not immediately corrected but are tracked using a Pauli frame. The Pauli frame keeps track of the corrections classically and applies them later. This approach reduces the number of gate operations required to fix errors on the QPU, thereby protecting the encoded state from additional noise introduced by each correction gate. For instance, if a bit flip error occurs on qubit 1 in the first round and another bit flip error happens on the same qubit later, the two errors cancel each other out, eliminating the need for a correction
Often, codes are depicted using 3D images like the one below. In this case, each plane is a Steane code QEC round with flagged errors in purple. Each error is saved, and the list grows with future rounds. The final Paul frame, , is the list of corrections for the three bit flip errors that have occurred over all the rounds: two on qubit 1 and one on qubit 5. In the last step, the errors can be simplified, for example, , so only one of the three corrections, , needs to be applied. This is a rather trivial example, and often diagrams like this are used to depict more complex codes and their respective error pathways.
The dimension of time can also lend itself to more sophisticated decoding schemes. This is particularly important when measurement errors occur during the stabilizer checks. In this case, it might appear that a stabilizer flags when in fact the data qubits are fine. Multiple decoding rounds can demonstrate that the false stabilizer flag is a consequence of measurement error and not a true error, where other true errors would persist without correction. Such an approach is more powerful but requires decoding of much more complex syndromes. The diagram below demonstrates this concept with an example.
Notice how, in the first case, the decoder has kept track of a measurement error and is therefore making an incorrect syndrome in the final case. When decoding happens over time, the decoding task must not decode a 19-bit syndrome but is able to flag measurement errorsExercise 1:
The benefit of decoding in time is that the measurement errors can be factored into the decoding process. However, the tradeoff is that the decoding problem is much harder. When decoding in time, an effective parity check matrix must be constructed as an input to the decoder. In this exercise you will build for a two round Steane code that includes consistency checks to flag errors between the two time steps.
First, a few hints. Consider the dimensions. The number of columns still corresponds to the number of qubits, but, now we need to take into account the data qubits at time 0, the data qubits at time 1, and the three ancilla qubits used to measure syndromes between the two rounds.
Each time step will have the same three stabilizer checks, so should have six rows.
The top left block of and the bottom right block will be , where is the standard Steane code parity check matrix.
What do the middle three columns need to be for to be able to catch measurement errors?
Build , and then build an error vector of size 17 such that each entry is a 0 or a 1 if an error occurred on that qubit. Compute for a case with an error on data qubit 1 in the first time step, an error on data qubit 1 in the second time step only, and a measurement error. Note, it is best practice to assume that the decoder will not hanndle raw syndrome outputs, but the differences between he current set of measurements and the next round. For example, after preparation the syndrome 101 might be measured. If the next round produces the same stabilizer measurerments, the decoder would see 000 not 101. This syntax makes it much easier for decoders to handle data in more complex settings.
Looking at your results. Can you see how a measurement error can be detected in the the symdrome pattern? Note that the parity check matrix you created can only catch measurment errors on round 1. A round 2 measurement error would be missed unless you extenced the parity check matrix further.
4.3 Most Likely Error Decoding
So far, decoders have been presented as black boxes. In many cases that is sufficient. If you are developing or testing new codes, you might just use a state of the art decoder and not care how it works. In other cases, the opposite is true, and you might focus on developing and tuning a decoder to work well for a specific sort of QEC situation.
The rest of this lab will allow you to explore a number of different decoders ranging from conceptually simple to state of the art. You will interact with them in different ways, in certain cases you'll write the decoder from scratch and at other times you'll use the decoder out of the box.
The starting point is to consider a naive brute forced decoder that is conceptually simple yet sets the upper bound on decoder accuracy.
The steps of maximum likelihood decoding are as follows (considering only bitflip errors for simplicity):
Select a QEC code and encode a message in the codespace with data qubits.
Generate the bitstrings of length corresponding to all possible error situations.
For each , compute the syndrome as where is the code's parity check matrix.
Then, for each possible syndrome, list errors that could have produced the given syndrome.
Under each syndrome, order errors by their Hamming distance from the original message.
Finally, the decoder will receive a new syndrome, and then select the lowest Hamming distance error and apply the fix.
The assumption here is that, if errors are independent, cases with fewer errors are always more likely than those with more errors.
Notice, in Lab 2 when you coded the Steane code, we assumed a situation where one error occurs at a time, allowing your syndrome checks to fix errors. This is the same assumption made here. The problem with this approach is that it does not scale. There are errors that need to be computed a priori which is not possible for large codes. The sections below will consider more scaleable heuristics to overcome this issue.
Exercise 2:
Code the most likely error decoder for the Steane code below given the parity check matrix below. For each syndrome, print the associated length 7 bitstrings that produce that error, the Hamming distance from the baseline message (0000000), and the probability of that error.
4.4 AI Decoders
One way to circumvent the scaling challenges posed by the a brute force most likely error decoder is to use tools like AI. AI is fantastic at pattern recognition, runs very quickly, and can easily scale.
AI decoders also offer flexibility as they can be trained with simulated data or even trained on small-distance codes and, via transfer learning, be used to decode higher distance codes.
Recently, NVIDIA and QuEra announced a new transformed based decoder tested on magic state distillation circuits used by QuEra (A 35 qubit circuit with 5 Steane code logically encoded logical qubits). The decoder showed promise by outperforming the decoder used by QuEra in terms of speed and accuracy. Additionally, the AI decoder might have the potential to scale to code distances large enough for sufficiently low logical error rates.
Exercise 3:
You will now build a working AI decoder for the Steane code. The goal is to build something similar to the workflow in the image below.
This lab does not expect you to have experience coding AI models with tools like PyTorch, so you will focus on the data generation and learn how to prepare the data to train an AI decoder without worrying about details of the model. Follow the steps outlined below to complete the code.
The first step is to generate the training data. Take the Steane code circuit you coded in Lab 2, now with bitflip noise to each qubit after encoding. In this case, we can explore circuit-level noise based on simulated results rather than a contrived data set.
Create a data set of 1000 samples. To generate this, run cudaq.sample() 2000 times taking one shot each time. Output the measurements from the syndrome checks (without correcting any errors) and then measure all of the data qubits. Compute the parity of bits corresponding to the correct logical operator to determine the true logical state.
Save the syndromes and the logical states as two numpy arrays. This will be your data set.
Your data set will be split into a 2000 point training set and a 400 point test set to validate that the model worked. The inputs to the model will be syndrome data obtained from your simulations. The loss function will be a comparison between the predicted logical state of the model and the logical state you obtained from measuring the data qubits.
If you defined the arrays properly, the code below should preprocesses the data for you, splitting it into a training and test set, construct a simple neural network, define model setting, and train the model.
Each epoch is one trining loop through the entire data set. The model will then test the accuracy using the test set which was excluded from training at each epoch. The code is provided for the interested reader to see the details of the torch implementation, can also just be run as a black box. Do the plots below indicate the model improved as training progressed?
Training AI decoders is a very challenging task and must be used in the proper setting. For example, if the error rate in the training data is very low, The AI model could discover that it can produce pretty good results just by predicting no error each time. This sort of model does not learn anything about decoding! Thus, expert care must go into the fine-tuning and validation of AI decoders to ensure they are working properly. The steane code is rather simple and with only possible errors the training data can cover all possible errors. AI decoders in practice can only be trained on a subset of the possible errors, yet must be able to learn enough to decode with high enough accuracy.
Also note, that not matter how good the AI decoder is, it cannot overcome the fact that the Steane code is distance three.
Belief Propagation Decoding
Another state-of-the-art decoding method is belief propagation (BP). BP is a powerful technique borrowed from classical error correction that is highly flexible and can serve as a black box decoder for arbitrary QEC Codes. It is particularly useful for codes like quantum low-density parity check (qLDPC). All the user needs to do is provide a parity check matrix and then feed the decoder syndromes to decode.
NVIDIA created a GPU accelerated BP decoder which allows researchers to push QEC even further than before. This section will walk you through implementing BP and how to use NVIDIA's accelerated BP decoder.
At a high level, BP works by taking initial beliefs about each data qubit's physical error rate and, using syndrome measurements, iteratively update these beliefs to converge on a solution which provides a likelihood of an error occurring or not.
Though there are different variations of BP, one implementation is the following:
Initialize a log-likelihood ratio for each data qubit where is the physical error rate. If an error is unlikely, the quantity is positive and increases in magnitude the smaller is as errors are less likley.
, the message sent from each data qubit to a check qubit, is calculated based on the following equation: where includes all of the check qubits connected to data qubit excluding check qubit . That is, the check qubit is updated with beliefs the variable learned from the other check qubits it is connected to.
Similarly, is computed to compute the messages sent back to the variable qubits using where is all other variable nodes connected to excluding and is the value of the syndrome measurement for .
Finally, the final beliefs are computed as , summing the prior beliefs with the final messages sent to each variable node. From this a decision can be made where positive numbers indicate no error and negative an error, with the magnitudes related to confidence.
Ideally, BP will converge to a solution that agrees with the original syndrome and correct the error. If BP cannot converge, it means there is still significant uncertainty whether some of the bits have errors or not and postprocessing is necessary to refine the result. This will be discussed in the following section.
div style="background-color: #f9fff0; border-left: 6px solid #76b900; padding: 15px; border-radius: 4px;"> Exercise 4: Below is the start of a BP implementation for decoding the 5-qubit repetition code. Fill in the sections marked "TODO" to complete the code. Most of the BP loops are calculated for you. Make sure to review them and understand what is going on. Then, you will complete the code by fixing the code to calculate the final belief on each qubit and determine where errors occurred.
The 5-qubit repetition code is small, and easy to decode. If more than one error is present, the BPO decoder will fail, as the code distance is the primary constraint. However, with more complex codes, BP may complete, but not converge, meaning uncertainty remains on some of the bits and a logical error may occur due to its failure. Also, decoding large codes with orders of magnitude more variable and check nodes can become cumbersome.
NVIDIA's accelerated BP decoder, now part of the CUDA-Q QEC library, helps address this problem and parallelizes the BP algorithm. Examining your code above, it is not hard to see how the message calculations can be trivially parallelized, making them well suited for GPU acceleration.
Try running NVIDIA's accelerated BP decoder by running the code below which imports a data set of syndrome data from a large qLDPC code. How long did it take to decode 10 shots?
One of the reasons this algorithm can be accelerated is that it can be naturally parallelized. Do you see where that might happen?
The answer lies in the process of sending messages from syndrome qubits to data qubits, and vice versa. Each of these messages can be computed in parallel. This corresponds to performing operations that alternate across the rows and columns of a matrix, depending on which message is being sent. Each row and column can be treated independently, allowing for further parallelization within each row or column.
In benchmarks of large code instances, the NVIDIA decoder was up to 35x faster than the industry standard implementation for benchmarks run on the [144,12,12] code.
Batching
The performance can be enhanced ever further using batching. Batching means that a collection of syndromes are sent to the GPU and decoded simultaneously. This minimizes data transfer and allows the entire GPU to be working, reducing the average decoding time per shot.
Run the cells below to see the impact of batching when decoding 10000 syndromes. In the second cell, run_as_batched is set to True. How much faster is batching? Batching is most effective when decoding a large number of syndromes.
Ordered Statistics Decoding
Now, increase the error rate using a different data file from 0.1 % to 0.5 %. What happens to the logical error rate?
You should notice a very high logical error rate. Each of these logical error rates is a case where BP could not converge. Like any numerical solver, it is possible to increase iterations and perform a number of tricks to help BP, but some particularly difficult syndromes will not converge either way. To solve this, BP decoders are often paired with optional ordered statistics decoding (OSD) which performs post-processing to improve the result. Thus, you might often see a "BP+OSD" decoder.
The intuition behind OSD decoding is to solve for the errors directly using matrix inversion. That is, solving where is a vector with error locations, is the syndrome, and is the parity check matrix. The procedure cannot be performed with the original , so instead, a square matrix with columns of full-rank must be constructed from the columns of .
What makes this approach challenging is selecting the right columns. Many different solutions can be obtained with different column selections, but without guidance, this will likely result in a solution that is not of minimum weight and induce a logical error. Recall, for the most likely error decoder above, that valid errors with high weight are much less likely than low weight errors. Same idea here, but rather than computing all combinations, the OSD heuristic provides a clever way to search from a really good starting point that is the output of BP.
The output of BP assigns a probability of error to each data qubit. This naturally informs the reordering of the columns to rank from most to least likely to have an error. Next Gaussian elimination is performed on to determine the first full columns of full rank. These subcolumns are then inverted to get which is multiplied by to get the error result . The is then padded with zeros which results in a total error profile of .
Exercise 5:
The following exercise is based on a lecture by Joschka Roffe. Given the parity check matrix below and the probabilities of error from BP. Perform OSD manually and find the error profile that satisfies the syndrome. Note, all computations must be performed using mod 2 arithmetic. This can be accomplished using the galois library which creates a Galois field and allows all numpy operations to compute mod 2.
OSD guarantees an error pattern that satisfies the syndrome, but it is not necessarily a minimum weight solution nor avoids a logical error. In the exercise above, you performed OSD-0, or zero order OSD. To improve results, higher order OSD can be performed. Higher order OSD performs bitflips in the bits and checks if a lower weight solution can be found. Generally speaking, the order of the OSD determines how many bitflips are considered, but there is additional nuance not covered here.
Lower weight solutions are possible as bit flips in also impact the other bits in the subspace.
To summarize, syndromes are of varying difficulty. Easy syndromes are solved with BP, OSD-0 is used for moderate syndrome difficulties, and higher order OSD is used for the most challenging.
Try running the code below on the 10000 shot data set. See what happens when osd_method is set to 1 for OSD-0. Then try setting this variable to 3 to run a variant of higher order OSD. Does the logical error rate improve? How much more time does it take to perform higher order OSD?
Summary
After completing this notebook, you should now have an understanding for the challenges behind decoding. This begins with the brute force most likely error decoding which is incredibly inefficient. You now have experience using other techniques like AI and BP+OSD decoding to accelerated QEC decoding.