In quantum computing, quantum error correction techniques are essential to render quantum sys-
tems sufficiently robust to noise and capable of performing useful digital algorithms. One particularly
simplified and widely studied noise model is the quantum erasure channel, in which qubits can
independently at random be sent to the maximally-mixed state, undergoing a random Pauli error to be
determined upon syndrome measurement, and with the decoder being aware of the erasure positions.
Although simplified, the erasure channel provides valuable insights for analyzing the performance
of quantum codes and decoding algorithms, which can prove useul for more realistic noise models.
Moreover, some physical platforms can transform their native errors into erasures, which greatly
simplifies the task of syndrome decoding.
In both the classical and quantum settings, the erasure decoding problem admits a maximum-
likelihood decoder based on Gaussian elimination. However, its cubic complexity becomes prohibi-
tive for large systems, and the same approach is not applicable to more realistic channels, which has
motivated the development of iterative decoding algorithms with lower computational complexity at
the expense of some loss in decoding performance. Among those are message-passing algorithms
such as belief propagation (BP), which has many variations and can be applied to different noise
models, including in the quantum setting. For the erasure channel, the simplest form of BP is the
peeling decoder.
The peeling decoder iteratively solves a linear system by solving equations with a single unknown
variable, potentially giving rise to new single-variable equations, until it completely solves the era-
sure or reaches a stopping set, for which no such single-variable equations remain. In the context
of classical LDPC codes, the peeling decoder performs well, but in the quantum setting the very
presence of low-weight stabilizers hinders its performance by inducing small stopping sets.
To counter this issue, peeling variants such as pruning were proposed, along with BP variants
such as BP with Guided Decimation. Building on the idea of the VH decoder introduced in for
HGP codes, the cluster peeling decoder was proposed in generalizing the idea to the broader class
of CSS codes, and providing a mechanism to balance runtime complexity and decoding performance
by tuning a parameter.
In a similar fashion, this work aims to adapt the Maxwell decoder to the quantum CSS case, by
introducing guessing mechanisms to the peeling and pruned-peeling decoders. The resulting decoder
attains maximum likelihood performance, with complexity no larger than that of Gaussian elimina-
tion. By limiting the number of available guesses, one can obtain a linear time decoder, in exchange
for some of the decoding performance.

Collaboration avec François-Marie Le Régent et Anthony Leverrier