Session K71: Quantum LDPC Codes and Decoders

Parallel window decoding enables scalable fault tolerant quantum computation

Quantum Error Correction (QEC) continuously generates a stream of syndrome data that contains information about the errors in the system. Decoders must process this syndrome data at the rate it is received, otherwise a data backlog problem [Terhal 2015] is encountered and the quantum computer runs exponentially slower. The leading fault-tolerant approaches to quantum computation are not scalable since decoders typically run slower as the code distance is increased. Inevitably, they reach a maximum code distance where the backlog problem and exponential slowdown arise. Superconducting quantum computers can perform QEC rounds in sub-1us time, and so this fundamental problem is also a serious practical concern and an enormous engineering challenge. Here, we present a methodology that parallelizes most decoders and achieves almost arbitrary syndrome processing speed, removing this roadblock to scalability. Our parallelization requires some classical feedback decisions to be delayed, leading to a slow-down of the logical clock speed. However, the slow-down is now polynomial in code size and so an exponential slowdown is averted. We demonstrate our parallelization speed-up using a software implementation, combining it with both union-find and minimum weight perfect matching. Furthermore, we show that parallel window decoding imposes no noticeable reduction in logical fidelity compared to an un-windowed decoder. Finally, we discuss how the same methodology can be implemented in online hardware decoders.   

Maximum likelihood decoders of stabilizer codes under device noise using tensor networks

Quantum error correcting (QEC) codes promise arbitrary suppression of logical errors as the size of the code increases. This tradeoff between physical resources and error suppression makes the prospect of scalable quantum computing possible. Decoders play a key role in QEC protocols. They infer what class of logical error is most likely to have occurred during a computation based on information coming from a few sparse measurements performed on the system and a model of the underlying error mechanisms. Decoding is in principle a hard classical problem, and heuristics have been developed to decode efficiently in practice. In this talk I will present our latest advances in close-to-optimal decoding of stabilizer codes using device-level error models and tensor networks. In addition, I will present the results of our tensor network decoder applied to Google’s quantum processors. These results were recently used to support the first ever experimental demonstration of error suppression using the surface code.   

Minimising failures for the surface code using a color-code decoder

The development of practical and high-performance decoding algorithms reduces the resource cost of fault-tolerant quantum computing by decreasing the physical overhead that is needed for quantum error correction to reach a target logical error rate. Here we propose a matching decoder for the surface code that is specialised to correct depolarising noise. The decoder is obtained by mapping the syndrome of the surface code onto that of the color code, thereby allowing us to use high-performance color-code decoding algorithms. Analytical arguments and exhaustive testing show that the resulting decoder can find a least-weight correction for almost all weight (d+1) / 2 depolarising errors where d is the code distance. This improves the logical error rate by a factor that is exponential in d compared with decoders that deal with bit flips and dephasing errors separately. We demonstrate this improvement with numerical simulations at low error rates. Of independent interest, we also numerically demonstrate an exponential improvement in logical error rate for our color-code decoder against an independent and identically distributed bit-flip noise model compared with the restriction decoder; a well-studied type of matching decoder for the color code.   

Real-time algorithmic decoding

The ability to perform quantum error correction in real-time is essential for large-scale fault tolerant quantum computations. The process of decoding quantum error correction syndromes relies on a classical co-processor, performing a decoder procedure to produce corrections. Determining these corrections quickly is crucial for running logical algorithms, as they must be determined within the coherence time of the logical qubits. Furthermore, these decoders become increasingly computationally complex as the distance of the quantum error correcting code grows, creating a tradeoff between speed and performance. Here we present on the first demonstration of a real-time algorithmic decoder on a quantum error correction code. Utilizing the unique capabilities of Quantinuum’s System Model H1 machine, we perform fast and scalable decoding on the surface code. These results mark a step forward in benchmarking fast, scalable, and real-time decoding strategies.  

    

Real-Time Decoding for Fault-Tolerant Quantum Computing: Towards higher decoding speed and lower communication latency

Real-time decoding at the logical clock speed will be essential for universal fault-tolerant quantum computers. However, the short QEC cycle (<1 microsecond for superconducting qubits) poses enormous challenges. We examine the two issues that need to be addressed to overcome that: decoding speed and communication latency. We illustrate a review of current efforts on decoder algorithms and perspectives for the next few years aimed at achieving sufficient speed while maintaining good accuracy. In particular, we discuss the challenges at the level of the algorithm itself, its applicability (quantum memory, lattice surgery), the software stack, computational resources (FPGA/ASIC), as well as codesign across these aspects.

To address the communication-latency issue, Qblox proposes and implements a distributed control-stack architecture where measurement outcomes and Pauli-frame updates are shared within a few hundreds of nanoseconds. This architecture includes and interfaces to a specialized module for running user-defined decoding algorithms.   

Advances in decoding schemes for Surface codes

Quantum error correction (QEC) is an invaluable ingredient in any strategy that pursues the construction of reliable quantum computers. QEC Codes define methods through which to arrange the available qubits into subsets of noise-protected qubits. Surface codes and quantum low density parity check codes (QLDPC) are promising candidates to implement QEC strategies in near future quantum computers. The aim of this presentation is to showcase the recent developments we have made (in Tecnun) on the topic of decoding schemes for the aforementioned families of codes. This includes considering independent and non-identically distributed (i.ni.d.) noise present in state-of-the-art quantum processors and tailoring the decoding algorithms to this specific type of noise [1]. In addition, we will discuss different decoders for surface codes based on the MWPM and BP algorithms for i.i.d. unbiased and biased noise (Z-noise is predominant). We will introduce and explain our modifications to these decoders and we will show how the thresholds of the surface codes improve significantly when such decoders are applied under both i.i.d. and i.ni.d. noise.

[1] de Martí i Olius et al. Performance of surface codes in realistic quantum hardware. arXiv: 2203.15695 (2022).   

Three-dimensional subsystem codes from two-dimensional topological codes

Fault-tolerant protocols and quantum error correction (QEC) are essential to building reliable quantum computers from imperfect components that are vulnerable to errors. Optimizing the resource and time overheads needed to implement QEC is currently a pressing challenge. Certain quantum error correcting codes have the single-shot error correction property, i.e., one round of parity-check measurements suffices to perform reliable QEC even in the presence of measurement errors. Three-dimensional (3D) topological subsystem codes are one class of codes with the single-shot error correction property. Examples from this class include the gauge color code and the 3D subsystem toric code. 

We provide a new perspective on 3D topological subsystem codes in terms of 2D topological codes. Our perspective clarifies the origin of the Gauss law for gauge flux, and through this the origin of the single-shot property. Furthermore, our perspective shows how the 3D subsystem toric code can be naturally generalized to Abelian quantum double models, and suggests the possibility of further generalization. We numerically investigate the perfomance of the generalized 3D subystem toric codes, finding evidence that the single-shot property is present in the entire family. We discuss Hamiltonian models for the 3D subsystem toric code, and argue that the most natural Hamiltonians are gapless.     

Union–find quantum decoding without union–find

The union–find decoder is a leading algorithmic approach to the correction of quantum errors on the surface code, achieving code thresholds comparable to minimum-weight perfect matching (MWPM) with amortised computational time scaling near-linearly in the number of physical qubits. This complexity is achieved via optimisations provided by the disjoint-set data structure. We demonstrate, however, that the behaviour of the decoder at scale underutilises this data structure, and that improvements and simplifications can be made to architectural designs to reduce resource overhead in practice.   

Fusion Blossom: Parallel MWPM Algorithm for QEC

Minimum-Weight Perfect Matching (MWPM) decoders are widely used for quantum error correction (QEC) decoder due to their high accuracy and polynomial time complexity. Existing MWPM decoders, however, have insufficient throughput for superconducting qubits, which require almost one million measurement rounds per second. We report an MWPM algorithm of almost linear complexity given the rare and randomly distributed local quantum errors. We also report a parallel implementation of this algorithm, called Fusion Blossom [1], which leverages parallel computing resources to further improve the throughput.  We report the decoding speed on a d=21 CSS surface code with phenomenological noise model p=0.5% and 1e5 measurement rounds. On a 64-core machine, Fusion Blossom improves the throughput by 41x and achieves an average decoding time of 0.7 us per measurement round or 58 ns per non-trivial measurement. Importantly, Fusion Blossom can support even larger code distances by using more parallel computing resources available from a cluster of computers. Fusion blossom is open-source and implemented in the Rust programming language, with a Python package “fusion-blossom” [2]. It supports arbitrary user-defined decoding graphs and embeds a 3D visualization tool.

[1] https://github.com/yuewuo/fusion-blossom

[2] https://pypi.org/project/fusion-blossom/

    

Distributed Union-Find Decoder and Its FPGA-based Implementation for Scalable Quantum Error Correction

A fault-tolerant quantum computer must decode and correct errors faster than they appear.  The Union-Find (UF) decoder is promising with an average time complexity slightly higher than O(d³), substantially better than the more accurate MWPM decoders. We report a distributed version of the UF decoder that exploits parallel computing resources to further speed up. Given O(d³) parallel computing resources, the distributed UF decoder has an average time complexity of O(log(d)), without considering communication cost between the parallel resources. We design Helios, a scalable architecture that organizes parallel computing resources into a hybrid tree-grid structure and report an FPGA-based implementation of Helios and the distributed UF decoder. Using Xilinx’s cycle-accurate simulator, we show that the average decoding time of our implementation grows sublinearly with regard to d, up 15, with phenomenological noise model p=0.1%. We also confirm the decoding time with a Xilinx ZC106 FPGA for d up to 7: the FPGA does not have enough resources to support d>7 but achieves an average decoding time of 830 ns for d=7. We will also report our ongoing implementation effort using a network of seven Xilinx FPGAs, with a goal to support d=13.   

Improving belief propagation performance for quantum error correcting codes by degeneracy-reducing transformations

Due to its linear complexity and good error correction ability, iterative belief propagation (BP) decoder is widely used for decoding classical low-density-parity-check (LDPC) error correction codes.  However, for quantum LDPC codes, BP fails often, mainly because it cannot deal with small-weight trapping sets associated with degeneracy.  Decoding failure probability can be reduced by orders of magnitudes using, e.g., serial update schedules or otherwise breaking the symmetry, but this does not eliminate the trapping sets completely.  To address the problem, we consider BP decoding of codes specially modified to reduce the degeneracy.  The transformation amounts to a partial summation over the stabilizer group generators, adding variable nodes to account for the correlations induced.  In the spin-model language, it is a well-known star-polygon transformation used to construct marginal spin probability distributions.  We combine exact transformations with correlation-reducing approximations to optimize BP success probability and performance.