Session M49: Decoders for Quantum Error Correction

A real-time, scalable, fast and highly resource efficient decoder for a quantum computer

Quantum computers promise to solve computing problems that are currently intractable using traditional approaches. This can only be achieved if the noise inevitably present in quantum computers can be efficiently managed at scale. A key component in this process is a classical decoder, which diagnoses the errors occurring in the system. If the decoder does not operate fast enough, an exponential slowdown in the logical clock rate of the quantum computer occurs. Additionally, the decoder must be resource-efficient to enable scaling to larger systems and potentially operate in cryogenic environments. Here we introduce the Collision Clustering decoder, which overcomes both challenges. We implement our decoder on both an FPGA and ASIC, the latter ultimately being necessary for any cost-effective scalable solution. We simulate a logical memory experiment on large instances of the leading quantum error correction scheme, the surface code, assuming a circuit-level noise model. The FPGA decoding frequency is above a megahertz, a stringent requirement on decoders needed for e.g. superconducting quantum computers. To decode an 881 qubit surface code it uses only 4.5% of the available logical computation elements. The ASIC decoding frequency is also above a megahertz on a 1057 qubit surface code, and occupies 0.06 mmsq area and consumes 8 mW of power. Our decoder is optimised to be both highly performant and resource efficient, while its implementation on hardware constitutes a viable path to practically realising fault-tolerant quantum computers.   

Demonstration of Real-Time Decoding in a Quantum Control Stack within 500 ns

The effectiveness of quantum error correction (QEC) is underpinned by the decoder, which in a universal fault-tolerant quantum computer has to run in real time, on an extremely tight schedule (e.g., microsecond timescale for superconducting qubits). So far, the QEC literature has predominantly focused on the QEC-code design and decoder accuracy. However, its real-time implementation is a critical milestone. First, real-time decoding requires a fast decoding algorithm running on suitable computational resources. A comprehensive review and perspective can be found in Battistel et al (arXiv:2303.00054). We identify the union-find Helios decoder by Liyanage et al (arXiv:2301.08419) as one of the most promising candidates. Second, real-time decoding requires communication of measurement results before the ones from the previous QEC cycle are generated, as well as low-latency communication of decoder outcome. In particular, to prove the feasibility of real-time decoding, it is necessary to demonstrate this using an FPGA (or ASIC) that is tightly integrated with the quantum control stack. While there have been previous implementations of standalone FPGA decoders, and numerous software decoders, there is a lack of demonstrations showcasing decoding within a quantum control stack. We adapt the union-find Helios decoder by Liyanage et al to run within 128 nanoseconds for a 3x3x3 surface code in an FPGA sequence processor and within 500 ns for the full round in the control stack. The decoding module is designed to seamlessly interface with the distributed communication network running over the backplane of the control system. This work is a milestone towards bringing real-time decoding to experimental reality. We envision a decoding platform to extend the available decoding set to other promising decoders.   

Multi-FPGA Union-Find Decoder for Surface Codes

A fault-tolerant quantum computer must have an accurate and real-time quantum error correction decoder. For superconducting qubits, the decoder should have an average throughput of around 1 us per measurement round with minimal latency to prevent a backlog of measurements from accumulating. The distributed Union-Find (UF) decoder by Liyanage et.al (arXiv:2301.08419) is a promising candidate with a sublinear average time complexity with regard to code distance (d). However, the resource usage of the decoder grows O(d3log(d)), thus the available resources in a single FPGA limit decoding large surface codes or performing multi-logical qubit operations such as lattice surgery.

We map the Helios architecture proposed to run the decoder to a custom multiple-FPGA system with a hybrid tree-grid topology. We demonstrate for the first time a decoder that is not constrained by resources and can run across multiple FPGAs. We show the validity of the decoder design and the multi-FPGA system by decoding large surface code blocks with (d>20) lattice surgery faster than the rate of measurement. Given the prevalence of multi-FPGA systems in contemporary quantum control setups, we anticipate that our approach is a promising candidate for practical real-time QEC for fault-tolerant quantum computing.   

Scaling Hardware-Based Quantum Error Correction via a Multi-Context Approach

The theory of quantum error correction is well understood, though its practical implementation remains challenging. This is due to the low-latency requirements for the classical computations that are required to carry out the quantum error correction. Recent advancements have shown that it is possible to meet these requirements for surface codes using algorithms implemented in FPGA hardware [1]. While it has been shown that the execution time of the algorithm scales favorably with increasing physical qubit numbers, the hardware ressource consumption grow to the third power, limiting the maximum number of qubits that can be used.

Here we present a way to reduce hardware ressource consumption by using a multi-context approach, trading hardware ressources for execution time. By saving some state of the error decoder in memory, we avoid time consuming network connections, which would otherwise be required to overcome the limitations of a single FPGA chip. The technique we are presenting is developed with our own approach to the Union-Find algorithm in mind [2], but is sufficiently general to be used with all algorithms which work on decoder graphs with limited connectivity.

[1] N. Liyanage et al., Scalable quntum error correction for surface codes using FPGA (IEEE FCCM, Marina Del Rey, CA, USA 2023)

[2] M. Heer el al., Novel union-find-based decoders for scalable quantum error correction on systolic arrays (IEEE IPDPSW, St. Petersburg, FL, USA 2023)   

Correlated decoding of logical qubit algorithms with transversal gates

Quantum error correction is essential to perform reliable quantum computation at scale. Recent experiments have realized error-corrected quantum algorithms on a multi-qubit logical processor, crucially relying on the use of transversal gates. Here we observe that the performance of such algorithms can be substantially improved by accounting for physical error propagation during transversal gates and decoding the logical qubits jointly. We find that this correlated decoding significantly improves the thresholds of both Clifford and non-Clifford transversal entangling gates, and we explore several decoders offering different computational runtimes and accuracies. We then apply correlated decoding to deep logical circuits with noisy syndrome extraction and find that significantly higher fidelities can be reached by utilizing this technique to reduce the number of rounds of noisy syndrome extraction per gate. This correlated decoding technique offers key advantages in early fault-tolerant computation, as well as the possibility for reduction in the spacetime cost of deep circuit logical algorithms.   

Hypergraph Minimum-Weight Parity Factor Decoder for QEC

Minimum-Weight Perfect Matching (MWPM) decoder on graphs has been widely used for decoding errors in the surface code and shows high performance when noise is not correlated. However, it cannot effectively decode correlated noise or decode general codes where a single error produces multiple syndromes. In these cases, the decoding problem reduces to finding the Minimum-Weight Parity Factor (MWPF) on hypergraphs. In this work, we introduce and implement an approximate MWPF decoder on hypergraphs. We test the performance of the decoder for decoding correlated noise on the surface code and find that the decoding accuracy drastically improves compared to that of the MWPM decoder. Most importantly, it shows almost linear average time complexity given a sufficiently low physical error rate.   

Decoding surface-code experiments with a recurrent neural network decoder

Quantum error correction offers a way to reach the low error rates needed to perform useful computations at the expense of an increase in the qubit overhead. A more accurate decoder leads to better logical performance, which can substantially reduce this overhead. Neural network decoders are particularly promising since they do not require any prior information about the physical noise.

In this talk, we explore the performance of such a decoder on both simulated data and the data from the recent surface code experiment performed in [Google Quantum AI, Nature 614, 676–681 (2023)]. This decoder typically outperforms perfect-matching decoders as it can better deal with errors leading to multiple syndrome defects, such as Y errors. When applied to the experimental data, we show that this decoder achieves logical error rates approaching those obtained using an approximate maximum-likelihood decoder. We demonstrate the flexibility of such a decoder by providing the soft information available in the analog readout of transmon qubits and show that this can further decrease the logical error rate.   

Scalable Graph Neural Network Decoders for Quantum LDPC Codes

Decoding quantum low density parity checks (QLDPC) codes shares similarities with the decoding of classical LDPC codes. In general, QLDPC decoding requires post-processing which is a time consuming procedure. Neural network (NN) decoders, with their constant time execution, have also been proposed for QLDPC codes. However, their training is very time consuming and once trained, a NN decoder cannot extrapolate (ie. train on a lower distance, and use it for larger distances) and can only be used on that particular code distance on which it was trained on. We present a novel graph-NN decoder which is trained on the Tanner graph of the QLDPC code. We benchmark our decoder on depolarizing noise and decode surface QECCs of distance 3, 5 and 7. We illustrate the extrapolation capabilities of our graph-NN decoder, and present numerical evidence that it achieves thresholds comparable to decoders using belief propagation combined with ordered statistics post-processing.   

A fast renormalization-group tensor-network decoder for planar quantum low-density parity-check codes

We present a fast and Bayes-optimal-approximating tensor network decoder for planar quantum

LDPC codes based on the tensor renormalization group algorithm, originally proposed

by Levin, and Nave. By precomputing the renormalization group flow for the null syndrome,

we need only recompute tensor contractions in the causal cone of the measured syndrome at the

time of decoding. This allows us to achieve an overall runtime complexity of O(pnχ6) where p is

the depolarizing noise rate, and χ is the cutoff value used to control singular value decomposition

approximations used in the algorithm. We apply our decoder to the surface code in the code capacity

noise model and compare its performance to the original matrix product state (MPS) tensor network

decoder introduced by Bravyi, Suchara, and Vargo. The MPS decoder has a p-independent runtime

complexity of O(nχ3) resulting in significantly slower decoding times compared to our algorithm in

the low-p regime.   

Fast and accurate decoder for the XZZX code using simulated annealing

The XZZX code is a variant of the surface code to incorporate biased noise in realistic quantum device. Although, as decoders of surface codes, minimum-weight perfect matching (MWPM) algorithm is widely used, it can take into account only X (bit-flip) and Z (phase-flip) errors, not Y (bit-flip and phase-flip) errors. To handle Y errors appropriately, Markov chain Monte Carlo (MCMC) decoders and matrix product state (MPS) decoders have been researched, and however, these decoders are too slow. For the XZZX code, we formulate decoding as energy minimization problem of Ising model, and apply simulated annealing (SA) to solve them. Specifically, to prepare an initial configuration of SA, we propose to employ recovery chains obtained by a greedy matching decoder, which brings us fast convergence of SA. By numerical simulation for code capacity noise model where only data qubits suffer errors, we confirmed that our SA decoder is more accurate than the MWPM decoder. Furthermore, our SA decoder attained the accuracy, equivalent to the optimal decoder formulated by integer programming. By comparing decoding times of our SA decoder, the decoder by the integer programming, and the MPS decoder, we confirmed that our SA decoder is fastest if parallelized. This result implies a possibility of the combination of our greedy matching and SA decoders in quantum error correction.   

Hardness results for decoding the surface code with Pauli noise

Real quantum computers will be subject to complicated, qubit-dependent noise, instead of simple noise such as depolarizing noise with the same strength for all qubits. We can do quantum error correction more effectively if our decoding algorithms take into account this prior information about the specific noise present. This motivates us to consider the complexity of surface code decoding where the input to the decoding problem is not only the syndrome-measurement results, but also a noise model in the form of probabilities of single-qubit Pauli errors for every qubit.

In this setting, we show that Maximum Probability Error (MPE) decoding and Maximum Likelihood (ML) decoding for the surface code are NP-hard and #P-hard, respectively. We reduce directly from SAT for MPE decoding, and from #SAT for ML decoding, by showing how to transform a boolean formula into a qubit-dependent Pauli noise model and set of syndromes that encode the satisfiability properties of the formula. We also give hardness of approximation results for MPE and ML decoding. These are worst-case hardness results that do not contradict the empirical fact that many efficient surface code decoders are correct in the average case (i.e., for most sets of syndromes and for most reasonable noise models). These hardness results are nicely analogous with the known hardness results for MPE and ML decoding of arbitrary stabilizer codes with independent X and Z noise.