Union–find quantum decoding without union–find

Abstract

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.

Sam J. Griffiths

PhD student of quantum computing and error correction