Ambiguity Clustering: an accurate and efficient decoder for qLDPC codes

Compared to the surface code, error correction schemes based on quantum low-density parity check (qLDPC) codes can allow more logical information to be encoded in significantly fewer physical qubits. The downsides are that syndrome extraction involves more complicated circuits; we can't directly apply the well-developed theory of computation in the surface code using lattice surgery; and we lose access to fast and accurate matching-based decoders. Slow decoding is problematic in the short term because it constrains theoretical research into qLDPC codes, and in the medium term because syndrome data produced by a quantum computer must be processed at the same rate it is generated.

The state of the art decoder for general qLDPC codes this time last year was OSD, which after a fast initial message passing step (belief propagation) solves a linear algebra problem (worst case cubic complexity) then performs a global search which heuristically should scale exponentially to maintain accuracy on large problems. Here we introduce Ambiguity Clustering (AC), an algorithm which seeks to divide the measurement data into clusters that are decoded locally and independently. We benchmark AC on IBM's bivariate bicycle codes and obtain up to a 25x speedup over OSD, with no reduction in logical fidelity. Our single-threaded CPU implementation of AC decodes the 144-qubit Gross code in 135us per round of syndrome extraction under 0.3% circuit level noise, already fast enough to keep up with neutral atom and trapped ion systems.