Classical algorithms for decoding and error correction

[dsvandet]

Generally speaking, let's begin by solving decoding problems in a channel model. Here we are given a Pauli noise model and a subsystem code. The noise is applied to the n qubits of the code and we compute an ideal syndrome. The generating set of the stabilizer group may be overcomplete. Given the syndrome, the task is to return a corrective Pauli operator. Each decoding algorithm aims to achieve a particular objective, such as finding the minimum weight correction or the maximum-likelihood correction, etc.

The practical decoding problem that we eventually must solve corrects noise generated by quantum circuits during computations. We will work up to this, beginning with specific families of codes for which a closely related problem has already been solved.

Several software projects have already implemented algorithms for decoding and error correction.

(list the relevant projects here)

(try to clarify language; decoding, error correction, syndrome processing, ...)

Error correction by reduction to a matching problem

Problem: Suppose a stabilizer code has the property that every single qubit error violates at most two stabilizer generators. Given a syndrome of this code, find a corrective Pauli operator of minimum weight.

Several software packages already exist that solve this problem.

• Higgott, PyMatching, https://pymatching.readthedocs.io/en/latest/
• Qiskit Ignis topological_codes

(list other important decoding algorithms)

Problem: Construct decoding graphs for surface codes. For more general codes, could return a hypergraph where each hyperedge represents the set of events (stabilizer or flag measurements) that are triggered by a single fault (suggested by Ted Yoder)

For codes where a single error triggers exactly two events (or sets of independent pairs) this is done by the GraphDecoder in topological_codes.