Abstract
Quantum error correction (QEC) is considered essential for the development of scalable, fault-tolerant quantum computers in the medium- to long-term. By encoding quantum information across many physical qubits, carefully-designed measurements can be taken to gain limited knowledge as to errors which may have occurred in the system, known as the error syndrome, without causing quantum decoherence. In surface codes, qubits are arranged in a two-dimensional topological space, such as a torus or plane. In quantum low-density parity-check (qLDPC) codes, this is generalised to effectively arbitrary arrangements of qubits and syndrome checks.
This work studies decoders: the algorithms responsible for inferring error-correcting decisions from syndromes. In particular, the union–find decoder is studied in terms of its performance at scale. A simulation of a union–find decoding architecture is used to identify computational bottlenecks and propose improvements. In literature, it is assumed that the decoder runs in time scaling quadratically in the number of qubits under a naive implementation, but near-linearly when including two well-known optimisations. A key result is that, under independent and phenomenological noise models on surface codes, this complexity is strictly linear regardless of these optimisations. A supporting analytical argument is presented using percolation theory.
Generalisation of the decoding problem to qLDPC codes is also studied, with approaches broadly relying on Gaussian elimination to find appropriate solutions. A strategy is proposed which uses a novel online variant of the Gaussian elimination algorithm to solve this linear system incrementally on growing local clusters, with accompanying complexity analysis and empirical data demonstrating a reduction in runtime. An investigation into the use of metachecks is also presented, inspired by single-shot decoding, with implications for how such qLDPC decoders could be further improved.
