Quantum error correction has three parts:
- Encode logical information in a large number of physical qubits using some quantum code.
- Make careful repeated measurements that reveal information about the error state without collapsing the data.
- Decode the measurement results to work out the most likely error state.
We need to do all three for quantum error correction to work.
The surface code has efficient decoders (minimum weight perfect matching, union-find) but needs a lot of physical qubits to encode a single logical qubit with good protection against errors.
Recently, a whole raft of other qLDPC codes have been proposed with much lower overheads, but they don’t yet have good decoders.
What is a qLDPC code?
A quantum low-density parity check code is one which can be implemented by measuring only small sets of qubits, and not measuring any one qubit too often. For practical reasons, almost all quantum codes are LDPC, including the surface code, so when people talk about qLDPC codes they normally mean a code that beats the surface code in some particular way - often using far fewer qubits to protect the same amount of information.
The standard qLDPC decoder is Roffe’s implementation of Panteleev and Kalachev’s BP-OSD. BP-OSD is generic enough to work for any qLDPC code but can be slow: in one experiment it took an hour and twenty-two minutes to decode 10,000 sets of measurement data. So, we wrote a new decoder that can do the same job in 34 seconds.
BP-OSD struggles on large problems because it tries to solve the problem all in one go. Ambiguity Clustering instead breaks it into manageable separated chunks that can be solved independently.
Ambiguity Clustering is a drop-in replacement for BP-OSD. In tests on IBM’s recent bivariate bicycle codes, we saw up to a 150x speedup at a realistic 0.3% circuit-level error rate. We can decode IBM’s Gross code on a laptop in 280μs per round of measurements, already fast enough to keep up with neutral atom and ion trap systems.
More details in our arXiv paper ‘Ambiguity Clustering: an accurate and efficient decoder for qLDPC codes’.
Ambiguity Clustering is also available in our analytics tool, QEC Explorer.
by Ben Barber and Stasiu Wolanski