Actis: A Strictly Local Union-Find Decoder

Abstract

Fault-tolerant quantum computing requires classical hardware to perform the decoding necessary for error correction. The Union-Find decoder is one of the best candidates for this. It has remarkably organic characteristics, involving the growth and merger of data structures through nearest-neighbour steps; this naturally suggests the possibility of its realisation using a lattice of simple processors with nearest-neighbour links. In this way the computational load can be distributed with near-ideal parallelism. Here we show for the first time that this strict (rather than partial) locality is practical, with a worst-case runtime $\mathcal{O}(d^3)$ and mean runtime subquadratic in the surface code distance $d$. A novel parity-calculation scheme is employed which can simplify previously proposed architectures, and our approach is optimised for circuit-level noise. We compare our local realisation with one augmented by long-range links; while the latter is of course faster, we note that local asynchronous logic could negate the difference.

arXiv comment19 pages, 18 figures; link emulation code and raw data, rename definitions, make diagrams colourblind friendly, update acknowledgments

References in corpus (21)

• Fault-tolerant quantum computation by anyons
• Surface codes: Towards practical large-scale quantum computation
• Topological quantum memory
• Quantum Computing with Very Noisy Devices
• Interfacing spin qubits in quantum dots and donors - hot, dense and coherent
• A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
• Quantum computing with nearest neighbor interactions and error rates over 1%
• Fast Decoders for Topological Quantum Codes
• Towards practical classical processing for the surface code
• High threshold error correction for the surface code
• Linear-Time Maximum Likelihood Decoding of Surface Codes over the Quantum Erasure Channel
• Improved decoding of circuit noise and fragile boundaries of tailored surface codes
• Neural-Network Decoders for Quantum Error Correction using Surface Codes:A Space Exploration of the Hardware Cost-Performance Trade-Offs
• Parallel window decoding enables scalable fault tolerant quantum computation
• Fault-Tolerant Weighted Union-Find Decoding on the Toric Code
• Towards practical classical processing for the surface code: timing analysis
• Multi-path Summation for Decoding 2D Topological Codes
• Improved single-shot decoding of higher dimensional hypergraph product codes
• Exploiting Degeneracy in Belief Propagation Decoding of Quantum Codes
• A local pre-decoder to reduce the bandwidth and latency of quantum error correction
• Neural ensemble decoding for topological quantum error-correcting codes

Cited by in corpus (6)

• FPGA-based Distributed Union-Find Decoder for Surface Codes
• Local Clustering Decoder as a fast and adaptive hardware decoder for the surface code
• Union-find quantum decoding without union-find
• Minimising surface-code failures using a color-code decoder
• Union-Intersection Union-Find for Decoding Depolarizing Errors in Topological Codes
• Snowflake: A Distributed Streaming Decoder