Source-linked AI summary
Parallel window decoding enables scalable fault tolerant quantum computation
Luka Skoric, Dan E. Browne, Kenton M. Barnes, Neil I. Gillespie, Earl T. Campbell
TL;DR
Existing sliding-window decoders can develop an exponential syndrome backlog as quantum computations grow, threatening scalable real-time error correction. This paper introduces parallel window decoding, which uses layered windows to achieve almost arbitrarily high decoding speed with polynomially scaling overhead, while numerical simulations show logical error rates comparable to global decoders.
Problem
Existing sliding-window decoders can develop exponential backlog growth, while rapid QEC cycle times make real-time decoding a practical scalability obstacle.
Method
The paper introduces parallel window decoding, which distributes decoding across layers and uses delayed classical feed-forward decisions to parallelize processing.
Results
Logical error rates for parallel window MWPM and global MWPM are within numerical error across tested code sizes and measurement rounds, while response time scales poly-logarithmically with computation size.
Takeaways & Limitations
With enough classical resources and polynomially scaling quantum resource overheads, parallel window decoding can achieve almost arbitrarily high decoding speed and address real-time scalability obstacles.
Takeaways & Limitations
Windows smaller than the code distance can permit adversarial failure mechanisms of weight (ω +1)/2 that are no longer correctly decoded.
Abstract
from arXiv · showhide
Large-scale quantum computers have the potential to hold computational capabilities beyond conventional computers for certain problems. However, the physical qubits within a quantum computer are prone to noise and decoherence, which must be corrected in order to perform reliable, fault-tolerant quantum computations. Quantum Error Correction (QEC) provides the path for realizing such computations. QEC continuously generates a continuous stream of data that decoders must process at the rate it is received, which can be as fast as 1 MHz in superconducting quantum computers. A little known fact of QEC is that if the decoder infrastructure cannot keep up, a data backlog problem is encountered and the quantum computer runs exponentially slower. Today's leading approaches to quantum error correction are not scalable as existing decoders typically run slower as the problem size is increased, inevitably hitting the backlog problem. That is: the current leading proposal for fault-tolerant quantum computation is not scalable. Here, we show how to parallelize decoding to achieve almost arbitrary speed, removing this roadblock to scalability. Our parallelization requires some classical feed forward decisions to be delayed, leading to a slow-down of the logical clock speed. However, the slow-down is now only polynomial in code size, averting the exponential slowdown. We numerically demonstrate our parallel decoder for the surface code, showing no noticeable reduction in logical fidelity compared to previous decoders and demonstrating the parallelization speedup.
A. Matching decoders
Matching decoders represent potential defects as graph vertices and potential errors as edges, then output correction edges for observed defects.
- A. Matching decoders: A matching decoder takes triggered defects as input and outputs a subset of graph edges representing a correction.Boundary defects ensure the defect set has even parity when errors trigger a single physical boundary defect.
- A. Matching decoders: The graph contains real or boundary defect vertices, while edges represent potential errors.
- A. Matching decoders: Matching decoding applies when each error triggers either a pair of defects or a single defect connected to a virtual boundary defect.
B. Sliding window decoding
Sliding window decoding processes syndrome data sequentially, committing only high-confidence corrections from older rounds. Artificial defects carry unresolved boundary information between windows, but the method has scalability and decoder-scope constraints.
- B. Sliding window decoding: Each sliding-window step decodes nW syndrome rounds, while only corrections in the older ncom-round commit region become final.The remaining rounds form a buffer for tentative corrections.
- B. Sliding window decoding: The window advances by ncom rounds, carrying artificial defects and unresolved buffer defects into the next decoding step.Artificial defects arise where tentative correction chains cross the commit–buffer boundary.
- B. Sliding window decoding: Sliding and parallel window decoding require an inner decoder that returns an approximately low-weight correction, such as UF or MWPM.Homology-based decoders may select a low-weight homology class but produce a high-weight representative, requiring additional modifications.
- B. Sliding window decoding: Choosing nbuf = ncom = d retains logical fidelity close to that of the global decoder in the reported numerical validation.The buffer suppresses failure mechanisms involving error chains extending beyond the window.
C. Parallel window decoding
Parallel window decoding distributes non-overlapping windows across concurrent workers and reconciles them through layered processing. Simulations report logical error rates comparable to global decoding and substantial speedup, with throughput increasing through classical parallel resources.
- C. Parallel window decoding: Parallel window decoding processes non-overlapping windows concurrently in layer A, then resolves inter-window artificial defects in layer B.Layer A commits high-confidence middle regions; layer B completes corrections between adjacent committed regions.
- C. Parallel window decoding: Layer-A windows use preceding and following buffers with nbuf = ncom = w and nW = 3w, with w set to d in the method.Layer-B windows use nW = 3d and require no buffers because neighboring corrections were resolved in layer A.
- C. Parallel window decoding: Global MWPM and parallel-window MWPM have logical error rates within numerical error across tested code sizes and measurement rounds.The same qualitative result is reported for UF-based decoders in the appendix.
- C. Parallel window decoding: Layer-B decoding starts after adjacent layer-A workers complete, while pipelining can keep decoding cores highly utilized.
- C. Parallel window decoding: With no parallelization overhead, syndrome throughput scales linearly with the number of parallel processes Npar.The two decoding layers together take 2τW, so sufficient processes are required for acquisition time to exceed decoding time.
- C. Parallel window decoding: Using Npar = 16 with MWPM produced greater than an order-of-magnitude decoding-speed increase in simulation.Software overhead caused some sub-linearity, especially for low-distance codes.
D. Resulting resource overheads
Parallel window decoding introduces latency tied to window decoding time, but its total response time scales polylogarithmically with computation size rather than exponentially.
- The decoder may lag behind newly measured syndrome data by nlag rounds, requiring a delay when window decoding is slow.The lag is nlag = Npar(ncom + nW) rounds.
- The total response time for k layers of T gates is approximately 2kτW, contrasting with the exponential response time associated with the backlog problem.
- If window decoding time scales polynomially with code size, the response time per T-gate layer scales polylogarithmically with algorithm depth and width.The stated scaling is τ = O(log(kW)^αβ).
- Logical clock time combines lattice-surgery time dτrd with the decoder response time τ.It is defined as τclock := dτrd + τ.
E. Extensions
The windowing framework extends beyond matching approximations and one-dimensional time windows, but smaller spatial or temporal windows introduce decoding trade-offs and possible distance limitations.
- Windowing can use non-matching inner decoders when error mechanisms cannot be decorrelated into graphical matching problems.Matching examples include MWPM and union-find, while some codes require non-matching decoders.
- Three-dimensional windows can constrain decoding problems in both space and time using a D + 1 layer construction.The minimum layer count depends on the colorability of the underlying tiling.
- Figure 4 compares global and parallel-window MWPM logical error rates and measures decoding frequency as parallel processes increase.
- Spatial windowing is needed during lattice-surgery merges to prevent the window decode time from increasing substantially.Smaller windows may reduce decoder runtime, but windows below code distance can permit lower-weight adversarial failures.
II. CONCLUSIONS
Parallel window decoding addresses syndrome-backlog scalability constraints while retaining simulated logical fidelity and scaling speed with additional classical resources.
- Parallel window decoding avoids the exponential backlog growth that occurs with sliding-window decoders on sufficiently large computations.This is especially relevant to superconducting devices with sub-microsecond QEC rounds.
- Existing acceleration approaches include lookup-table and dedicated-microarchitecture decoders, but their demonstrated scope or scalability remains limited.Lookup-table memory scales exponentially with qubit number, while one microarchitecture model required further validation in a real device.
- Parallel window decoding can achieve almost arbitrarily high decoding speed given sufficient classical resources and polynomially scaling quantum-resource overheads.
III. METHODS
The simulations use phenomenological Pauli noise and implement MWPM and union-find decoding with specified software and initialization procedures.
- The simulations use PyMatching for MWPM and a custom Python implementation for union-find on an AMD EPYC 7742 processor.
- Phenomenological Pauli noise assigns data and syndrome-measurement errors with probability p in each round.
- Timing experiments decode 8(Npar + 1)d rounds and average results over 5000 repetitions.The setup assumes Z-basis initialization and readout, with specified initial and final defect-boundary conditions.
Appendix A: Parallel window decoding in time and space
Parallelization extends from time windows to spatial regions by layering nonadjacent commit regions, with buffers protecting unresolved corrections. Colourings organize these regions into decoding layers, including for surface-code geometries.
- Spatial parallelization divides the decoding space into non-overlapping commit regions and assigns space-time coordinates to vertices and edges.
- A valid layer ordering can be obtained by colouring commit regions so same-colour regions are nonadjacent and separated by distance R.
- For surface-code decoding, a 2D hexagonal colouring can be extruded into three dimensions to represent the decoding geometry.
- With a processor limit Npar, additional colours can be used so each colour contains no more than Npar regions.
- Buffers include possible error locations within distance w of a commit region while excluding previously committed regions and preventing artificial defects there.
- In the hexagonal protocol, later layers use smooth boundaries where they meet resolved regions, and the final layer has no buffer regions.
Appendix B: Circuit-level variants noise and non-matching inner decoders
The parallel-window framework extends to circuit-level noise and non-matching decoding by incorporating diagonal hook-error edges and partitioning hyperedges into compatible commit regions.
- Circuit-level noise introduces hook errors represented by diagonal edges in an otherwise cubic decoding graph.
- For non-matching decoding, hyperedges list all defects triggered by an error and may contain more than two defects.
- Hyperedges can be partitioned into commit regions that share a layer when no vertex or defect belongs to hyperedges from both regions.
- The partition can use a hypergraph-derived distance metric or space-time regions, although non-topological codes may lack Euclidean localization.
- Buffer construction follows the matching case, but rough hyperedge boundaries require connections to a boundary vertex to permit artificial defects.
Appendix C: Numerical validation of decoder performance
Numerical tests validate sliding and parallel window decoding against global decoders, showing preserved logical performance and increased throughput with parallel resources, especially for larger codes.
- Sliding-window MWPM shows a negligible logical-fidelity drop for nW = 2d and ncom = d compared with global MWPM.
- Sliding-window decoding frequency decreases with code size as O(1/poly(d)) for both MWPM and UF, matching the observed data.
- Because sliding-window frequency decreases with code size, some distance eventually satisfies τW > ncomτrd, limiting scalability.
- Parallel window decoding with UF shows no significant increase in logical error rate and roughly linear throughput growth with Npar for large codes.
- The parallel decoder pipeline assigns syndrome data to blocks that process 3d rounds using specified rough time boundaries.
- Blocks exchange artificial defects and unresolved syndromes from their boundary rounds to neighboring blocks during cyclic processing.