# Fault-tolerant noise guessing decoding of quantum random codes

Diogo Cruz, Francisco A. Monteiro, André Roque, Bruno C. Coutinho This work
was supported in part by the European Union’s Horizon 2020 Research and
Innovation Program through the Project Quantum Internet Alliance (QIA) under
Grant 820445; and in part by Fundação para a Ciência e Tecnologia / Ministério
da Ciência, Tecnologia e Ensino Superior (FCT/MCTES), Portugal, through
national funds and when applicable co-funded EU funds under projects
UIDB/50008/2020 and 2022.05558.PTDC. Diogo Cruz was supported by FCT
scholarship UI/BD/152301/2021.Diogo Cruz is with Instituto de
Telecomunicações, and IST, Universidade de Lisboa, Lisbon, Portugal, e-mail:
<EMAIL_ADDRESS>A. Monteiro is with Instituto de
Telecomunicações, and ISCTE - Instituto Universitário de Lisboa, Lisbon,
Portugal, e-mail<EMAIL_ADDRESS>Roque is with Instituto de
Telecomunicações, Lisbon, Portugal, e-mail:
<EMAIL_ADDRESS>Coutinho is with Instituto de
Telecomunicações, Lisbon, Portugal, e-mail<EMAIL_ADDRESS>
###### Abstract

This work addresses the open question of implementing fault-tolerant QRLCs
with feasible computational overhead. We present a new decoder for quantum
random linear codes (QRLCs) capable of dealing with imperfect decoding
operations. A first approach, introduced by Cruz et al., only considered
channel errors, and perfect gates at the decoder. Here, we analyze the fault-
tolerant characteristics of QRLCs with a new noise-guessing decoding
technique, when considering preparation, measurement, and gate errors in the
syndrome extraction procedure, while also accounting for error degeneracy. Our
findings indicate a threshold error rate (${p_{\rm threshold}}$) of
approximately ${2\times 10^{-5}}$ in the asymptotic limit, while considering
realistic noise levels in the mentioned physical procedures.

###### Index Terms:

Quantum error correction, noise guessing decoding, QRLCs, fault-tolerance,
syndrome extraction.

##  I Introduction

It is known that classical random linear codes (RLCs) are capacity-achieving
[1], however, until the advent of guessing random additive noise decoding
(GRAND) their decoding was not practical, apart some decoders based on
trellises (as pointed out in [2]). GRAND has been proposed with the aim of
reducing end-to-end latency in coded wireless systems, which has been a
drawback for a long time. The rationale in the original proposal of GRAND was
that by using short codewords, the so-called interleavers, used to make the
errors independent and identically distributed (iid), would no longer be
required [3]. Using short blocks in wireless systems also helps to better
adapt to the channel variations when applying precoding techniques [4, 5, 6].
In the quantum realm, due to technical limitations in manipulating qubits,
short block codes appear as natural candidates for quantum error correction
codes (QECCs) [7, 8, 9, 10, 11]. These limitations also necessitate the
development of fault-tolerant techniques to handle noise and errors in quantum
operations [12].

Likewise classical RLCs, quantum random linear codes (QRLCs) attain the
capacity of the quantum channels, but no practical decoder existed for them
until the advent of quantum guessing random additive noise decoding (QGRAND),
which allowed to numerically assess their performance for the first time [2].
A recent work also used a GRAND-like approach to decode several families of
structured quantum codes which are based on stabilizer codes [13]. QGRAND has
also been applied to the purification of quantum links, taking advantage of
the connection between purification and error correction [14], which will have
great implications on the way routing is implemented in quantum networks [15,
16, 17, 18].

QRLCs are a much more flexible solution than other structured quantum codes
for QECCs, with advantages in respect to the state-of-the-art solutions
designed to detect and correct errors in quantum setups [19, 20]. In contrast
to structured codes, which may only exist for a very limited number of code
rates and codeword lengths [21, 22], QRLCs can exist for a wide range of
coding rates and codeword lengths that may better fit some particular
applications. A method to generate QRLCs efficiently was proposed in 2013
[23], however, almost no practical method existed until recently to decode
them until the proposal in [2]. The channel model used in that work was a
Shannon-like channel, where errors occur only in the channel and all the
decoding process is perfect. However, in all current technologies implementing
qubits, the errors that take place in the quantum gates of the decoding
circuit cannot be ignored. Hence, a practical challenge remained after [2]:
can a QRLC-QGRANDf system be made practical in the presence of the extra
errors coming from the quantum gates, enabling fault-tolerant QECCs based on
QRLCs?

This paper shows that, surprisingly, due to the particular way that the
syndrome extraction takes place in codes based on stabilizers, some heavy
reduction of the effects of those errors takes place, making the whole system
viable. Building on previous work [2, 14], we present a comprehensive analysis
of fault-tolerant QRLCs, incorporating the effects of preparation,
measurement, and gate errors. Our results show that QRLCs, decoded with the
proposed method, exhibit robust error correction capabilities with a threshold
error rate ${p_{\rm threshold}}$ of approximately ${2\times 10^{-5}}$. This
advancement paves the way for practical implementations of QRLCs in quantum
error correction, contributing to the development of scalable and resilient
quantum systems.

Although our results suggest that QGRAND could in theory enable a fault-
tolerant implementation of QRLCs, some challenges remain that limit its
usefulness in that regime. QGRAND is most suitable for situations where the
noise entropy is relatively low, in which case decoding becomes
computationally efficient. However, in the fault-tolerant regime where $n$ may
be considered to be considerably large or it is necessary to iteratively apply
error correction to suppress errors, the noise entropy can be considerably
high. In this regime, the optimal procedure described in this paper becomes
infeasible, and suboptimal heuristics would have to be introduced.
Nonetheless, this work paves the way for applications of QGRAND whenever the
considered noise types all have low entropy, which encompasses setups with
realistic noise conditions.

This paper is organized as follows. In Section II we introduce the setup
considered in the analysis, and in particular its noise model. In Section III,
we define some useful error notation terms and set the notation used
throughout the paper. Section IV presents the decoding method, extended form
[2] to account for degenerate errors. In Section V, we present an analysis of
the codes’ performance for various qubit counts, and in Section VI we present
some final thoughts on our results.

##  II Setup and noise model

TABLE I: Notation summary. Variable |  Description | Relationships
---|---|---
$U$ |  Unitary encoding circuit for a quantum error-correcting code |
$S_{i}$ |  The $i^{\text{th}}$ minimal stabilizer of the code ($1\leq i\leq n-k$ ) | $S_{i}=UZ_{i+k}U^{\dagger}$
$\bar{X}_{j}$ |  Logical $X$ operator on the $j^{\text{th}}$ encoded qubit ($1\leq j\leq k$) | $\bar{X}_{j}=UX_{j}U^{\dagger}$
$\bar{Z}_{j}$ |  Logical $Z$ operator on the $j^{\text{th}}$ encoded qubit ($1\leq j\leq k$) | $\bar{Z}_{j}=UZ_{j}U^{\dagger}$
$\mathcal{N}$ |  List of all possible errors $E_{i}$ in the noise model, with associated probabilities $p_{i}$ |
$E_{i}^{B}$ |  A base error (error affecting a single qubit or gate) |
$\omega$ |  The number of base errors that compose a compound error | $E_{j}=E_{i_{1}}^{B}\cdots E_{i_{\omega}}^{B}$
$e_{i}^{l}$ |  Local error pattern corresponding to a base error $E_{i}^{B}$ |
$C,B$ |  Unitary components of a syndrome extraction circuit, applied before/after an error $E_{i}^{B}$ occurs | $V=CB$
$V_{E}$ |  Syndrome extraction circuit affected by error $E_{i}^{B}$ | $V_{E}=Ce^{l}_{i}B$
$e_{i}$ |  Propagated error pattern on the main qubits after $E_{i}^{B}$ and subsequent circuit operations | $e_{i}=(Ce^{l}_{i}C^{\dagger})_{m}$
$e_{i}^{s}$ |  Propagated error pattern on the ancilla qubits after $E_{i}^{B}$ and subsequent circuit operations | $e_{i}^{s}=(Ce^{l}_{i}C^{\dagger})_{a}$
$\mathbf{A}$ |  Quantum check matrix of the code (binary representation in $[X|Z]$ format) |
$\mathbf{e}_{i}$ |  Binary representation of the main error pattern $e_{i}$ (in $[Z|X]$ format) |
$\mathcal{L}$ |  Logical error group generated by $\bar{X}_{j}$ and $\bar{Z}_{j}$ |
$\mathtt{L}_{i}$ |  One of the $2^{2k}$ logical error patterns in $\mathcal{L}$ | $e_{i}=\mathtt{E}_{i}\mathtt{S}_{i}\mathtt{L}_{i}$
$\mathcal{S}$ |  Stabilizer group generated by $S_{j}$ |
$\mathtt{S}_{i}$ |  One of the $2^{n-k}$ stabilizer patterns in $\mathcal{S}$ | $e_{i}=\mathtt{E}_{i}\mathtt{S}_{i}\mathtt{L}_{i}$
$\mathtt{E}_{i}$ |  Error pattern with the same syndrome as $e_{i}$ | $e_{i}=\mathtt{E}_{i}\mathtt{S}_{i}\mathtt{L}_{i}$
$\mathbf{0}$ |  Vector representing zero syndrome ($n-k$ zero bits) |
$\hat{\mathbf{s}}_{i}$ |  Syndrome associated with a (propagated) error pattern $e_{i}$ | $\hat{\mathbf{s}}_{i}=\mathbf{e}_{i}\mathbf{A}^{T}$
$\mathcal{D}$ |  A degenerate set: A set of error patterns with the same syndrome that can be corrected similarly |
$e_{i}^{d}$ |  Representative of the errors in a degenerate set $\mathcal{D}$ | $e^{d}_{i}=\mathtt{E}_{i}\mathtt{L}_{i}$
$g$ |  Index of the syndrome extraction where an error $E_{i}^{B}$ occurred |
${\tilde{\mathbf{s}}}_{i}$ |  Syndrome acquired in the same extraction as error $E_{i}^{B}$ | ${\tilde{\mathbf{s}}}_{i}=\text{comp}_{X}(\text{bin}(e_{i}^{s}))$
${\hat{\mathbf{s}}}_{i}$ |  Syndrome acquired in a subsequent extraction after $E_{i}^{B}$ occurred | ${\hat{\mathbf{s}}}_{i}=\text{comp}_{X}(\text{bin}((Ve_{i}V^{\dagger})_{a}))$
${{\mathbf{s}}}_{i}$ |  Measured syndrome in a particular syndrome extraction |
$s$ |  List of all acquired syndromes over multiple extractions: $\\{\mathbf{s}^{1},\ldots,\mathbf{s}^{q}\\}$ |
$\mathcal{Q}(E_{j})$ |  Syndrome sequence expected for a compound error $E_{j}$ | $\mathcal{Q}(E_{j})=s_{i_{1}}\oplus\cdots\oplus s_{i_{\omega}}$

We use the same setup as in [2], but consider the fault-tolerant regime, where
the constituent quantum gates in the circuit may be affected by error. We
consider an initial $k$-qubit $\ket{\psi}$ quantum state, to be encoded into
$n>k$ qubits. [23] presents a method of generating a random qubit encoding,
which we use in this work. One starts by randomly selecting Clifford unitaries
from the $\mathcal{C}_{2}$ group (i.e., Clifford unitaries for 2 qubits).
There are $|\mathcal{C}_{2}|=11\,520$ such unitaries, and all of them can be
built by simple combinations of the Hadamard ($H$), phase ($\sqrt{Z}$), and
CNOT gates, which have efficient physical implementations in virtually any
quantum setting [24]. In matrix form, these are defined as

$H=\frac{1}{\sqrt{2}}\matrixquantity(1&1\\\
1&-1),\;\sqrt{Z}=\matrixquantity(1&0\\\
0&i),\;\text{CNOT}=\matrixquantity(I&0\\\ 0&X),$ (1)

with $X,Y,$ and $Z$ the Pauli matrices, and $I$ the $2\times 2$ identity
matrix.

After selecting these random unitaries from $\mathcal{C}_{2}$, one
successively applies each of them to a random pair of qubits, taken from the
set of $n$ qubits.

Fig. 1: Noise model considered.

This process leads to an encoding unitary for our stabilizer code which, when
applied to the initial $k$ qubits and $(n-k)$ extra $\ket{0}$ qubits added,
returns a $n$-qubit encoded quantum state. As shown in [23], as long as
$\order{n\log^{2}n}$ gates are used, with a circuit depth of
$\order{\log^{3}n}$, the construction leads to a highly performant $(n,k)$
code, and from [25] it is already known that these complexity orders can be
further lowered.

We use these QRLCs to construct stabilizer codes. Compared to the approach in
[2], in this work, we consider a noise model that is more realistic by also
including preparation, measurement, and gate errors. Given that, in practical
applications, the error of 2-qubit entangling gates generally dominates over
single-qubit gate errors [10], we focus on the former type of error. We assume
that every gate in both the encoding and syndrome extraction steps is
decomposed into the Clifford gates $\quantity{\text{CNOT},H,\sqrt{Z}}$.

For the noise statistics, we consider the model similar to the one in [10],
but without single-qubit gate errors (see Fig. 1):

  * •

CNOT gate errors: After the ideal implementation of the CNOT$(a,b)$ gate, with
qubit $a$ controlling $b$, it is assumed that one of the 15 errors of the form

$O_{a}O_{b}$ (2)

with $O_{a},O_{b}\in\quantity{I,X,Y,Z}$ and excluding $O_{a}O_{b}\neq
I_{a}I_{b}$, occurs with probability $p/15$. Here, $I$ is the identity gate,
and $X,Y,Z$ are the Pauli matrices.

  * •

Preparation errors: While setting the $(n-k)$ ancilla qubits (for each
syndrome extraction) to $\ket{0}$, each qubit has (independently) a
probability $p$ of being prepared in the state $\ket{1}$ instead.

  * •

Measurement errors: While measuring each ancilla qubit to extract the
syndrome, each measurement bit has a probability $p$ of being misread, so that
a zero bit is read as a 1, and vice-versa.

Unlike the model in [2], to demonstrate the fault-tolerant properties of this
model, we exclude a source of error between the encoding and syndrome
extraction sections (i.e., the “transmission error” in Fig. 1), and instead
focus on the case where the CNOT gate error stemming from the syndrome
extraction dominates the noise statistics of the circuit. This simpler model
facilitates the study of the QGRAND decoding approach in the fault-tolerant
regime, which is the focus of this work. While possible (see Appendix A), we
make no further modifications to the circuit implementation.

##  III Error correction overview

In the fault-tolerant regime with a noisy gate model, degenerate errors play a
significant role in the error correction capabilities of the code [26]. As a
result, the approximation made in [2], where codes were approximated to be
non-degenerate, is no longer accurate, as it would significantly underestimate
the code’s capabilities.

Additionally, in the fault-tolerant regime, we must consider an iterated
application of the syndrome extraction procedure, instead of a single
application, in order to capably detect the errors being introduced by the
syndrome extraction procedure itself. This is a common approach [27, 19] to
quantum error correction when gate and measurement errors are non-negligible,
and the decoding procedure has into account not just the syndrome from one
extraction process, but the whole history of syndrome measurements.

Fig. 2: Simple example, with two syndrome extractions (SE). The error is not
detected by the first syndrome extraction process, but it is detected by the
second extraction.

As a result of this added complexity, in this section we clarify the notation
we use in this work. We use $\bar{X}_{j},\bar{Z}_{j}$ to represent the logical
operators corresponding to the unencoded operators $X_{j},Z_{j}$,
respectively. Given an encoding $U$ (see Fig. 1), the choice of minimal
stabilizers $S_{i}$ and logical operators is not unique. Without loss of
generality (W.l.o.g.), we consider the minimal stabilizer $S_{i}$ (for $1\leq
i\leq n-k$) and logical operators $\bar{X}_{j}$, $\bar{Z}_{j}$ (for $1\leq
j\leq k$) to be given by

$\displaystyle S_{i}$ $\displaystyle=UZ_{i+k}U^{\dagger}$ (3)
$\displaystyle\bar{X}_{j}$ $\displaystyle=UX_{j}U^{\dagger}$ (4)
$\displaystyle\bar{Z}_{j}$ $\displaystyle=UZ_{j}U^{\dagger}.$ (5)

Following Section II, the noise model enables us to create a list
$\mathcal{N}=\quantity{(p_{0},E_{0}),(p_{1},E_{1}),\ldots}$ of all the errors
$E_{i}$ that the encoded quantum state may be subjected to, along with its
respectively probability $p_{i}$ of occurring. An error $E_{i}$ refers to the
qualitative process that occurred physically, such as “a $X_{2}Z_{3}$ error
occurred in the CNOT$(2,3)$ gate, and no other errors”, for example.

An error $E_{i}$ that corresponds to either only one wrongly prepared qubit,
or one wrongly measured qubit, or one noisy CNOT gate, is called a _base
error_ , and may be explicitly labeled as $E_{i}^{B}$. Every other error in
the noise model of Section II can be described as a combination of base
errors.

We consider the errors $E_{i}$ to be disjunctive, so only one error in
$\mathcal{N}$ may occur, and their probability sums to 1. When using the base
error notation $E_{i}^{B}$, we implicitly refer only to the specific base
error that occurred, without making claims about the occurrence of other base
errors. For example, using the noise model in Section II, the base error
$E^{B}=$“$X_{2}Z_{3}$ error in the CNOT$(2,3)$ gate” would have a probability
of occurring of $p/15$, while the corresponding error $E=$“$X_{2}Z_{3}$ error
in the CNOT$(2,3)$ gate, and no other errors” would have a probability of
$(p/15)\times P(\text{no other base error occurs})$, which would possibly be
much lower. We may use the shorthand notation $\hat{E}^{B}:=E$ for errors
where only one base error occurs.

Compound errors may be represented by their own symbol or as the product of
errors that compose it. That is, for simplicity, given base errors $E_{i}^{B}$
and $E_{j}^{B}$, we also have the compound error notation

$E_{r}=E_{i}^{B}\cap E_{j}^{B}\cap\quantity(\bigcap_{m\neq
i,j}\overline{E_{m}^{B}})=:E_{i}^{B}E_{j}^{B}$ (6)

An error $E_{j}$ is said to be of order $\omega$ if $\omega$ base errors
suffice to describe it, so that $E_{j}=E_{i_{1}}^{B}\cdots
E_{i_{\omega}}^{B}$. Note that the constituting base errors may stem from
different syndrome extractions.

Given a base error, let $e^{l}$ be the _local error pattern_ corresponding to
the error that occurred locally. In the example above, we would have
$e^{l}_{i}=X_{2}Z_{3}$. In general, for gate errors affecting only one CNOT
gate, we would have an error pattern from 2. For preparation and measurement
errors, $e^{l}$ would be represented by $X$ operators in the appropriate
ancilla qubits.

Unless the error $E_{i}^{B}$ occurs at the end of a syndrome extraction
process, it will propagate through the rest of the quantum circuit, possibly
impacting other qubits. Let $V$ be the unitary corresponding to one noiseless
syndrome extraction process, minus the final measurement step of the ancilla
qubits. We may partition $V$ into the unitaries $B$ and $C$, corresponding to
the portion of the syndrome extraction circuit that occurs before and after
the error $E_{i}^{B}$, respectively. If the syndrome extraction affected by
$E_{i}^{B}$ is given by the unitary $V_{E}$, we have

$\displaystyle V$ $\displaystyle=CB$ (7) $\displaystyle V_{E}$
$\displaystyle=Ce^{l}_{i}B=(e_{i}^{s}\otimes e_{i})V.$ (8)

The resulting (propagated) error pattern may affect non-trivially both the
main $n$ qubits (main _error pattern_ $e_{i}$) and the $(n-k)$ ancilla qubits
(_ancilla error pattern_ $e_{i}^{s}$).

A Pauli string of $n$ qubits is an operator that is the product of the Pauli
operators $X,Y$, and $Z$ on those qubits. It has the form

$\displaystyle e^{i\frac{\pi}{2}\phi}O_{1}O_{2}\cdots O_{n},$ (9)
$\displaystyle\text{ with }O_{j}\in\quantity{X,Y,Z,I}\text{ and
}\phi\in\quantity{0,1,2,3}.$

As $e^{l}_{i}$ is a Pauli string, and $C$ is a Clifford unitary, then both
$e_{i}$ and $e_{i}^{s}$ are Pauli strings. Similarly, following 3, 4 and 5,
the minimal stabilizers and logical operators are also Pauli strings, since
$U$ is a Clifford unitary as well. A Pauli string is said to have weight $t$
if it acts on $t$ qubits, that is, if its Pauli string contains $t$ Pauli
operators (excluding the identity).

For the previous example with $E_{i}^{B}$, we would have $e^{s}_{i}\otimes
e_{i}=C(X_{2}Z_{3})C^{\dagger}$. While the effect of $e^{s}_{i}$ is removed by
the syndrome measurement, the same cannot be said of $e_{i}$. As $E_{i}^{B}$
propagates through the circuit, the pattern $e_{i}$ is picked up by subsequent
syndrome extractions, and is ultimately the error pattern that our correction
process needs to consider to undo the effect of $E_{i}^{B}$ on the main $n$
qubits. See Fig. 2 for an example.

In Fig. 2, we showcase a simple example, with two syndrome extractions (SE),
where there is only one minimal stabilizer $S_{1}=X_{1}X_{2}$. An error occurs
in the first CNOT gate, so $E=$ “$Z_{1}I_{2}$ error in first CNOT gate, and no
other errors”. The error is not detected by the first syndrome extraction
process, so ${{\mathbf{s}}}={\tilde{\mathbf{s}}}=0$. By the end of the first
syndrome extraction, the evolved uncorrected error is $e=Z_{1}I_{2}$. It is
now detected by the second extraction, so
${{\mathbf{s}}}={\hat{\mathbf{s}}}=1$. If it is not corrected, subsequent
extractions will behave similarly to the second one, returning the syndrome
$1$.

Since $Y=iXZ$, any Pauli string of $n$ qubits can also be written in the form

$e^{i\frac{\pi}{2}\varphi}\quantity(O_{1}^{X}\cdots
O_{n}^{X})\quantity(O_{1}^{Z}\cdots O_{n}^{Z}),$ (10)

with $O_{j}^{X}\in\quantity{X,I},\;O_{j}^{Z}\in\quantity{Z,I}$ and
$\varphi\in\quantity{0,1,2,3}$.

The Pauli string may then be encoded as a binary row vector. In $[X|Z]$
format, it takes the form

$\displaystyle\matrixquantity[b^{X}_{1}&b^{X}_{2}&\cdots&b^{X}_{n}&b^{Z}_{1}&b^{Z}_{2}&\cdots&b^{Z}_{n}],$
(11) $\displaystyle\text{with }b^{P}_{j}=\begin{cases}1,&\text{if }O_{j}=P\\\
0,&\text{if }O_{j}=I\end{cases}\text{ and }P\in\quantity{X,Z}.$ (12)

In $[Z|X]$ format, the $b^{X}_{j}$ entries are swapped with $b^{Z}_{j}$. By
default, binary vectors and matrices are represented in bold. We may use the
functions

(13)

with $P\in\quantity{X,Z}$ and $c=|\mathbf{e}|/2$, to indicate the conversion
to and from binary representation, and to refer to a particular component of
$\mathbf{e}$, respectively. Calculations using binary are performed in
$\mathbb{F}_{2}$, that is, using modular arithmetic mod 2. The functions bin
and op stand for the transformations of Pauli operators from and to,
respectively, binary arrays.

Let $\mathbf{A}$ be the quantum check matrix [28], a $(n-k)\times 2n$ binary
matrix (in $[X|Z]$ format) where each row $j$ encodes the minimal stabilizer
$S_{j}$ of the code. This is a compact way of representing the encoding used.
Let $\mathbf{e}_{i}$ be the binary representation of the error pattern $e_{i}$
as a $2n$-sized row vector, in $[Z|X]$ format. Any evolved error pattern
$e_{i}$ can be written as

$\displaystyle e_{i}=\mathtt{E}_{i}\mathtt{S}_{i}\mathtt{L}_{i},$ (14)

where $\mathtt{L}_{i}$ is one of the $2^{2k}$ logical error patterns in the
logical error group $\mathcal{L}$ generated by the logical operators
$\bar{X}_{j},\bar{Z}_{j},1\leq j\leq k$; $\mathtt{S}_{i}$ is one of the
$2^{n-k}$ stabilizers in the stabilizer group $\mathcal{S}$ generated by the
minimal stabilizers $S_{j},1\leq j\leq n-k$; and $\mathtt{E}_{i}$ is some
error pattern with the same syndrome
$\hat{\mathbf{s}}=\mathbf{e}_{i}\mathbf{A}^{T}$ as $e_{i}$ [28]. We use
$\mathbf{0}$ to represent the syndrome with all entries equal to zero.
W.l.o.g., for the decomposition, we assume the phase factor $\varphi$ (see 10)
to be zero, since neglecting it adds at most a global phase to the encoded
quantum state, which can be disregarded. As a result, we consider each error
pattern to equal its inverse.

The decomposition in 14 is not unique, and is dependant on the choice made for
the particular logical operators, minimal stabilizers, and $\mathtt{E}_{i}$
patterns to use. For the sake of simplicity in the notation, in this work, it
is assumed that such a decomposition is the unique one obtained
deterministically by following the procedure described in Section IV.
Consequently, we assume that, associated with each error pattern $e_{i}$,
there is a unique set of operators $\mathtt{E}_{i},\mathtt{S}_{i},$ and
$\mathtt{L}_{i}$. In particular, for patterns with
${\hat{\mathbf{s}}}=\mathbf{0}$, the operator $\mathtt{E}_{i}$ is the
identity. Since all error patterns with the same syndrome will have the same
error component $\mathtt{E}$, we use $\mathtt{E}_{{\hat{\mathbf{s}}}}$ to
indicate the error component of the error patterns with syndrome
${\hat{\mathbf{s}}}$.

Compound error patterns, such as $e_{r}=e_{i}e_{j}$, may be easily encoded in
binary form by using the modular sum (i.e. XOR), so that
$\mathbf{e}_{r}=\mathbf{e}_{i}\oplus\mathbf{e}_{j}$ and
${\hat{\mathbf{s}}}_{r}={\hat{\mathbf{s}}}_{i}\oplus{\hat{\mathbf{s}}}_{j}$.
Given two error patterns $e_{i},e_{j}$ with the same syndrome
$\hat{\mathbf{s}}$, their product $e_{r}$ has syndrome
${\hat{\mathbf{s}}}_{k}={\hat{\mathbf{s}}}\oplus{\hat{\mathbf{s}}}=\mathbf{0}$,
so $\mathtt{E}_{r}$ is the identity operator. Therefore, there is a unique
$\mathtt{S}\in\mathcal{S},\mathtt{L}\in\mathcal{L}$ such that
$e_{i}=e_{j}\mathtt{S}\mathtt{L}$, with
$\mathtt{S}=\mathtt{S}_{i}\mathtt{S}_{j}$ and
$\mathtt{L}=\mathtt{L}_{i}\mathtt{L}_{j}$.

A _degenerate set_ $\mathcal{D}$ is a set of evolved error patterns that can
be treated similarly, for correction purposes. This set depends on
$\hat{\mathbf{s}}$ and $\mathtt{L}$. Although all error patterns with the same
syndrome $\hat{\mathbf{s}}$ have the same representative error pattern
$\mathtt{E}_{\hat{\mathbf{s}}}$, not all can be corrected similarly. For that
to be the case, their logical error component $\mathtt{L}$ must be the same.
Since we know that two error patterns are degenerate if
$e_{i}e_{j}\in\mathcal{S}$, we may verify this by computing
$e_{r}=e_{i}e_{j}=(\mathtt{E}_{i}\mathtt{S}_{i}\mathtt{L}_{i})(\mathtt{E}_{j}\mathtt{S}_{j}\mathtt{L}_{j})=(\mathtt{E}_{i}\mathtt{E}_{j})(\mathtt{S}_{i}\mathtt{S}_{j})(\mathtt{L}_{i}\mathtt{L}_{j})=\mathtt{E}_{r}\mathtt{S}_{r}\mathtt{L}_{r}$.
For $e_{r}$ to be in $\mathcal{S}$, we must have
$\mathtt{E}_{r}=\mathtt{L}_{r}=I$, which is only the case if
$\mathtt{E}_{i}=\mathtt{E}_{j}$ and $\mathtt{L}_{i}=\mathtt{L}_{j}$. The
former is true if $e_{i}$ and $e_{j}$ have the same syndrome
$\hat{\mathbf{s}}$, while the latter is more complicated to verify, but we
know that there are only $2^{2k}$ possibilities in $\mathcal{L}$ to consider.
Ultimately, we may index the degenerate sets based on their syndrome and
logical error component, both represented by the tuple
$(\hat{\mathbf{s}},\mathtt{L})$. We use
$e^{d}_{i}=\mathtt{E}_{i}\mathtt{L}_{i}$ to refer to the actual representative
of $e_{i}$ (and its degenerate equivalents) during the correction process,
since we know that if we can correct $e^{d}_{i}$ by applying the unitary
$(e^{d}_{i})^{\dagger}$ to the circuit, so can we indirectly also correct
$e_{i}$, since $(e^{d}_{i})^{\dagger}e_{i}=\mathtt{S}_{i}$, and stabilizers
act as the identity on the encoded quantum state.

Fig. 3: Relations between the different quantities of interest. For
simplicity, every error represented is assumed to be a base error.

For an error $E_{i}$ arising from syndrome extraction $g$, there are two
associated syndromes of interest, instead of one. The syndrome

$\hat{\mathbf{s}}_{i}=\mathbf{e}_{i}\mathbf{A}^{T}$ (15)

corresponds to the syndrome obtained from a subsequent noiseless syndrome
extraction after extraction $g$, that is, after the error has occurred. In
this case, we can consider the error model to be similar to the one used in
[2], where the (propagated) error pattern $e_{i}$ is present before any
stabilizer is applied for the syndrome extraction process. Instead of using
15, we may alternatively compute ${\hat{\mathbf{s}}}_{i}$ by first computing
the ancilla error pattern. If we think of $e_{i}$ as a different local error
pattern $e^{l}_{j}$, then, following 8, we must have

$Ve_{i}V^{\dagger}=Ve_{j}^{l}V^{\dagger}=e^{s}_{j}\otimes e_{i},$ (16)

and ${\hat{\mathbf{s}}}_{i}$ is given by the $X$ component (i.e. second half
in $[Z|X]$ format, see 11) of $\mathbf{e}_{j}^{s}$. This type of syndrome is
always zero for preparation and measurement errors, since measurement errors
do not affect subsequent extractions. Under this latter formalism, we may
observe this by noting that if $e_{i}=I$, then necessarily $e^{s}_{j}=I$ and
${\hat{\mathbf{s}}}_{i}=\mathbf{0}$.

Beyond this typical syndrome, we also have the syndrome
${\tilde{\mathbf{s}}}_{i}$ obtained from the same extraction $g$ where the
error $E_{i}^{B}$ occurred. For instance, if the error occurs at the last
implemented CNOT gate, it is likely that ${\tilde{\mathbf{s}}}_{i}=0$. Unlike
${\hat{\mathbf{s}}}_{i}$, this syndrome is non-zero for simple measurement
errors. In general, this syndrome contains less information than
${\hat{\mathbf{s}}}_{i}$, since, for errors later in the extraction, many of
the syndrome bits will be zero, as the stabilizers were applied before the
error occurred. Following the second approach previously presented to compute
${\hat{\mathbf{s}}}_{i}$ (see 16), we have that ${\tilde{\mathbf{s}}}_{i}$ is
given by the $X$ component of the original ancilla qubit pattern
$\mathbf{e}_{i}^{s}$ (in binary form).

Both ${\tilde{\mathbf{s}}}$ and ${\hat{\mathbf{s}}}$ refer to a $(n-k)$ bit
string, corresponding to the syndrome that could be obtained from a single
syndrome extraction. As both these syndromes can be deterministically obtained
from the error $E$ of interest, we use the simple notation ${{\mathbf{s}}}$ to
specifically refer to the syndrome that is measured during the syndrome
extraction. As previously stated, for errors stemming from only one extraction
(labeled $g$), we have either ${{\mathbf{s}}}={\tilde{\mathbf{s}}}$ (if the
measured syndrome comes from the noisy extraction),
${{\mathbf{s}}}=\mathbf{0}$ (if it comes from a previous extraction) or
${{\mathbf{s}}}={\hat{\mathbf{s}}}$ (if from a subsequent extraction).

In general, compound errors may stem from multiple syndrome extractions. We
use superscript notation to indicate the extraction index, in order to
distinguish it from the error index (which is a subscript). When there are $q$
syndrome extractions, we refer to the total list of measured syndromes by
$s:=\quantity{\mathbf{s}^{1},\ldots,\mathbf{s}^{q}}$. If some base error
$E^{B,g}_{i}$ occurs at extraction $g$, we expect to measure the syndrome
sequence given by

$s_{i}=\\{\ldots,\mathbf{0}^{g-1},{\tilde{\mathbf{s}}}_{i}^{g},{\hat{\mathbf{s}}}_{i}^{g+1},\ldots,{\hat{\mathbf{s}}}_{i}^{q}\\}.$
(17)

Note that, for compound errors, the syndrome sequences of the constituting
errors may be combined. If $E_{r}=E_{i}E_{j}$, then $s_{r}=s_{i}\oplus s_{j}$,
where the modular sum operation is applied element-wise, to all $q$ syndromes.
Then, for $E_{j}=E_{i_{1}}^{B}\cdots E_{i_{\omega}}^{B}$, we have

$\mathcal{Q}(E_{j}):=s_{j}=s_{i_{1}}\oplus\cdots\oplus s_{i_{\omega}}.$ (18)

In particular, if errors $E_{i}$ and $E_{j}$ occur at extractions $g$ and $h$
($h>g$), respectively, and no other errors occur, then we would expect to
measure the syndrome sequence

$s=\\{\ldots,\mathbf{0}^{g-1},{\tilde{\mathbf{s}}}_{i}^{g},{\hat{\mathbf{s}}}_{i}^{g+1},\ldots,\\\
{\hat{\mathbf{s}}}_{i}^{h-1},{\hat{\mathbf{s}}}_{i}^{h}\oplus{\tilde{\mathbf{s}}}_{j}^{h},{\hat{\mathbf{s}}}_{i}^{h+1}\oplus{\hat{\mathbf{s}}}_{j}^{h+1},\ldots\\}.$
(21)

As a result, we observe that
${\tilde{\mathbf{s}}}_{i},{\tilde{\mathbf{s}}}_{j},{\hat{\mathbf{s}}}_{i},{\hat{\mathbf{s}}}_{j}$
do not directly provide the full information necessary to identify the
compound error $E_{i}^{g}E_{j}^{h}$ that occurred. In the general case where
there are $q$ syndrome extractions, we may require all $q$ measured syndromes
to optimally correct errors.

For compound errors $E_{r}$ stemming from multiple syndrome extractions, the
syndrome ${\tilde{\mathbf{s}}}_{r}$ is undefined, but ${\hat{\mathbf{s}}}_{r}$
may still be defined as

${\hat{\mathbf{s}}}_{r}=\bigoplus_{j=1}^{\omega}{\hat{\mathbf{s}}}_{i_{j}},$
(22)

where ${\hat{\mathbf{s}}}_{i_{j}}$ are the syndromes of the constituting base
errors. Similarly, $e_{r}=e_{i_{1}}\cdots e_{i_{\omega}}$. The decomposition
in 14 and subsequent analysis is also applicable.

The notation is summarized in Fig. 3, with an example given in Fig. 2.

In Fig. 3, the mappings $\mathcal{V}_{s}$, $\mathcal{V}$, $\hat{\mathcal{H}}$,
$\tilde{\mathcal{H}}$, $\mathcal{F}_{E}$ and $\mathcal{F}_{L}$ are mostly
independent, and generally non-injective. $\mathcal{V}$ and $\mathcal{V}_{s}$
stem from 8, and provide the main and ancilla error patterns $e_{i}$ and
$e_{i}^{s}$. Concretely, we have
$e_{i}=\mathcal{V}(e^{l}_{i})=(Ce^{l}_{i}C^{\dagger})_{m}$ and
$e_{i}^{s}=\mathcal{V}_{s}(e^{l}_{i})=(Ce^{l}_{i}C^{\dagger})_{a}$, where $m$
and $a$ stand for the main and ancilla subspaces, respectively. Using 16
yields $\tilde{\mathcal{H}}$ and $\hat{\mathcal{H}}$. The latter can also be
implemented by using 15. Concretely, we have
${\hat{\mathbf{s}}}_{i}=\hat{\mathcal{H}}(e_{i})=\text{bin}(e_{i})\mathbf{A}^{T}=\text{comp}_{X}(\text{bin}((Ve_{i}V^{\dagger})_{a}))$
and
${\tilde{\mathbf{s}}}_{i}=\tilde{\mathcal{H}}(e_{i}^{s})=\text{comp}_{X}(\text{bin}(e^{s}_{i}))$
(see 13 and III). The $\hat{\mathbf{s}}_{i}$ and $\mathbf{s}_{i}$ obtained by
the syndrome extraction process can then be used to try and determine
$e_{i}^{d}$, the representative pattern of the degenerate set to which $e_{i}$
belongs. By applying $e_{i}^{d}$ to the noisy quantum state, we correct the
effect of the error $E_{i}$. The mappings $\mathcal{F}_{E}$ and
$\mathcal{F}_{L}$ are quite involved, so their description is delegated to
Section IV.

##  IV Decoding

The error pattern statistics given by the noise model of Section II lead to a
very high number of degenerate error patterns (see Appendix B for examples).
As a result, the approximation made in [2], where codes were approximated to
be non-degenerate, is no longer accurate, as it would significantly
underestimate the code’s capabilities. In this section, we modify the decoding
procedure in [2] to account for error degeneracy. The modified procedure is
optimal in principle. It has previously been shown that such optimal
procedures must be #P-complete in general [29, 30, 31]. Since we are applying
the decoding procedure to random codes with no exploitable structure, our
decoding procedure has poor scaling capabilities for high entropy noise and
large code sizes. Nonetheless, following [2], we hope to show it to be of
interest in regimes of small code size or low entropy, so it is still worth
exploring the decoding properties of this optimal procedure. It is also
possible (though not covered in this work) for the decoding complexity to be
greatly improved with simpler approximations and heuristics to the optimal
approach. The optimal decoding procedure is summarily presented in Algorithm
2.

Algorithm 1 Error processing

0: $\mathcal{N}$

0: A data table $D$

1: Initialize empty data table $D$

2: for all $(p_{i},E_{i})\in\mathcal{N}$ do

3: Compute $e_{i}$, ${\hat{\mathbf{s}}}_{i}$, and $s_{i}$

4: Compute $\mathtt{L}_{i}$ associated with $e_{i}$

5: Compute $e^{d}_{i}$

6: if $e^{d}_{i}$ not in any entry in $D[s_{i}]$ then

7: Store $(e^{d}_{i},p_{i})$ in $D[s_{i}]$

8: else

9: Add $p_{i}$ to $p$ in entry $(e^{d}_{i},p)$

10: end if

11: end for

Algorithm 2 Optimal decoding

0: $\mathcal{N}$

0: A decoding table $T$

1: Initialize empty decoding table $T$

2: $D\leftarrow\textsc{Data}(\mathcal{N})$

3: for all entry $s$ in $D$ do

4: Set $T[s]$ as the pattern $e^{d}$ with highest $p$ in $D[s]$

5: end for

When considering this optimal decoding procedure, we note that, while we focus
on the noise model in Fig. 1, the decoding procedure is naturally applicable
to models where there are additional sources of error independent of the
syndrome extractions themselves. For that case, the noise statistics would
simply include those additional errors.

Moreover, the decoding procedure presented in this section does incorporate
any assumptions about the underlying nature of the noise, as it meant to be a
fully general procedure. In particular, we do not wish to assume that higher
order errors are less likely than lower order ones, as there may be practical
regimes where particular high order errors dominate the noise statistics (such
as burst errors). In subsection Appendix H, we adapt the general decoding
procedure to the particular noise model described in Section II.

For the decoding, we require a procedure that, given a syndrome sequence $s$,
outputs the error pattern $e^{d}$ that needs to be applied to the circuit to
correct the most likely source of error. Since we are interested in the
analysis of the decoding procedure in the optimal case, and less concerned
about practical limitations, we assume that such a procedure corresponds to a
decoding table $T$, storing the $s,e^{d}$ pairs.

The decoding table $T$ may be obtained as follows (see Algorithms 1 and 2 for
pseudo-code, and Fig. 8 for an example):

  1. 1.

For each error $E_{i}$ (with corresponding probability $p_{i}$), we compute
its syndrome sequence $s_{i}$, and also $e_{i}$ and ${\hat{\mathbf{s}}}_{i}$
(corresponding to the mapping $\mathcal{Q}$ in 18, and the mappings
$\mathcal{V}$ and $\hat{\mathcal{H}}\circ\mathcal{V}$, respectively, in Fig.
3, for base errors). Since the circuit is a stabilizer circuit, it can be
efficiently simulated [32], and these quantities efficiently computed.

  2. 2.

We compute $\mathtt{E}_{i}=\mathcal{F}_{E}({\hat{\mathbf{s}}}_{i})$ and
$\mathtt{L}_{i}=\mathcal{F}_{L}(e_{i})$. As we already know
${\hat{\mathbf{s}}}_{i}$, we end up with the degenerate set
$({\hat{\mathbf{s}}}_{i},\mathtt{L}_{i})$ (and its representative
$e_{i}^{d}=\mathtt{E}_{i}\mathtt{L}_{i}$), to which $e_{i}$ belongs.

  3. 3.

We repeat steps 1 and 2 for all errors in $\mathcal{N}$. Starting with an
empty data table $D$, for each error $E_{i}$, we add $(e_{i}^{d},p_{i})$ to
the entry $D(s_{i})$. If an entry with $e^{d}_{i}$ already exists, we add
$p_{i}$ to the entry’s probability. This procedure results in the data table
$D$.

  4. 4.

For each syndrome sequence
$s=\quantity{{{\mathbf{s}}}^{1},\ldots,{{\mathbf{s}}}^{q}}$ in $D$, we choose
the degenerate set with the highest associated probability as the actual coset
leader, that is, the one that is corrected if $s$ is measured.

  5. 5.

The resulting syndrome table $T$ then acts as our decoding method.

This decoding is optimal because, for any given syndrome, there is no other
way for the decoding to be more successful than as described here, since this
method already picks the most probable degenerate set
$({\hat{\mathbf{s}}},\mathtt{L})$, given the only information available _a
priori_ , which is $\mathcal{N}$ and the observed syndrome $\mathbf{s}$. It is
optimal under the reasoning that we consider any unsuccessful correction to be
a complete failure, with no possible partial success.

While the procedure as described is done in series, iteratively traversing the
$E_{i}$ errors, it can be trivially parallel, by splitting the error list
across multiple parallel workers. See Appendix E for a full description. The
pseudo-code for the parallel implementation can be seen in Algorithm 4.

To implement the decoding procedure (in particular step 2), _a priori_ , we
require the efficient implementation of two functions:

  * •

A function
$\mathcal{F}_{E}:\hat{\mathbf{s}}\mapsto\mathtt{E}_{\hat{\mathbf{s}}}$ that,
for a given code, and taking a syndrome ${\hat{\mathbf{s}}}$ as input, outputs
a deterministic error pattern $\mathtt{E}_{\hat{\mathbf{s}}}$ that can act as
a coset leader for the syndrome ${\hat{\mathbf{s}}}$. That is, any error
pattern $e_{i}$ with syndrome ${\hat{\mathbf{s}}}$ can be decomposed
(following 14) using the error component $\mathtt{E}_{\hat{\mathbf{s}}}$.
Having access to this function considerably reduces the required serialized
processing for the decoding, and the required memory, as we don’t need to keep
track of tentative coset leaders as we iterate through the errors $E_{i}$, and
we can be sure that different parallel workers have the coset leader in the
same degenerate set (in fact, we can be sure that they are equal).

  * •

A function $\mathcal{F}_{L}:e_{i}\mapsto\mathtt{L}_{i}$ that, for a given
code, and taking an error pattern $e_{i}$ as input, deterministically outputs
the logical component $\mathtt{L}_{i}$ of the degenerate set to which this
error pattern belongs to.

These functions are described in detail in Sections IV-A and IV-B.

###  IV-A Function $\mathcal{F}_{E}$

When analyzing the code, instead of working with the $(n-k)$ minimal
stabilizers $\quantity{S_{i}}$ we extracted from the encoding $U$ (see 3), we
work with a different set $\quantity{S_{i,\rm rre}}$. Each stabilizer in this
new set can be thought of as some combination of the stabilizers in
$\quantity{S_{i}}$. To be more specific, considering that $S_{i}$ corresponds
to row $i$ of the quantum check matrix $\mathbf{A}$ (with size $(n-k)\times
2n$), $\quantity{S_{i,\rm rre}}$ corresponds to row $i$ of $\mathbf{A}$ in
reduced row echelon form (also known as canonical form). We can convert
$\mathbf{A}$ to reduced row echelon form because products of stabilizers are
still stabilizers. Since we are in $\mathbb{F}_{2}$, adding or subtracting
rows of $\mathbf{A}$ is equivalent to multiplying stabilizers. As long as the
resulting matrix is full rank (which is always the case, since the procedure
for converting to reduced row echelon form preserves rank), the resulting new
matrix ${\mathbf{A}_{\rm rre}}$ encodes a new set of minimal stabilizers,
$\quantity{S_{i,\rm rre}}$, in its rows.

In practice, we can imagine that the measured syndrome $\mathbf{s}$ gets
converted to the “reduced row echelon” syndrome $\mathbf{s}_{\rm rre}$, which
can be done with a $(n-k)\times(n-k)$ matrix that encodes the steps needed to
convert $\mathbf{A}$ to reduced row echelon form. Let this matrix be
$\mathbf{J}$. We have ${\mathbf{A}_{\rm rre}}=\mathbf{J}\mathbf{A}$ and
$\mathbf{s}_{\rm rre}=\mathbf{J}\mathbf{s}$.

Working with ${\mathbf{A}_{\rm rre}}$, let $h_{i}$ be the index of the pivot
of row $i$ (it’s not guaranteed that $h_{i}=i$, since the pivots may not all
be along the main diagonal of ${\mathbf{A}_{\rm rre}}$). Since
$\quantity{S_{i,\rm rre}}$ comes from reduced row echelon form, the stabilizer
$S_{i,\rm rre}$ will be the only minimal stabilizer with a nonzero entry at
index $h_{i}$. Then, if $1\leq h_{i}\leq n$, the error $Z_{h_{i}}$ necessarily
yields the syndrome bit 1 for $S_{i,\rm rre}$ and zero for all other minimal
stabilizers in $\quantity{S_{i,\rm rre}}$. If $n+1\leq h_{i}\leq 2n$, the
error $X_{h_{i}-n}$ necessarily yields the syndrome bit 1 for $S_{i,\rm rre}$
and zero for all other minimal stabilizers. Consequently, we can use these
$(n-k)$ errors as a basis to construct a deterministic error pattern
$\mathtt{E}_{{\hat{\mathbf{s}}}}$ for every syndrome ${\hat{\mathbf{s}}}$. Let
$\mathtt{E}_{i}$ be the error associated with $S_{i,\rm rre}$
($\mathtt{E}_{i}$ equals $Z_{h_{i}}$ or $X_{h_{i}-n}$, as described). Since
the code is linear, for any syndrome $\mathbf{s}_{\rm rre}$, if
$i_{1},\ldots,i_{k}$ are the indices where the syndrome $\mathbf{s}_{\rm rre}$
is 1, then the compound error $e=\mathtt{E}_{i_{1}}\ldots\mathtt{E}_{i_{k}}$
must necessarily have syndrome $\mathbf{s}_{\rm rre}$. In other words,
$\mathbf{s}_{\rm rre}=\mathbf{e}{\mathbf{A}_{\rm rre}}^{T}$.

Since $e=\mathtt{E}_{\mathbf{s}_{\rm rre}}$ when using the minimal stabilizers
$\quantity{S_{i,\rm rre}}$, and $\mathbf{J}$ is a linear transformation, then
we must have $e=\mathtt{E}_{{\hat{\mathbf{s}}}}$ when using the minimal
stabilizers $\quantity{S_{i}}$. Therefore, if the code has stabilizers
$\quantity{S_{i}}$, then $\mathcal{F}_{E}$ implements the procedure

$\hat{\mathbf{s}}\implies\mathbf{s}_{\rm rre}\implies
e=\mathtt{E}_{\hat{\mathbf{s}}}.$ (23)

Because of the construction of $e$, for all error patterns with the same
syndrome, the same error component is computed. The error
$\mathtt{E}_{\hat{\mathbf{s}}}$ then acts as the error component for all error
patterns with syndrome ${\hat{\mathbf{s}}}$, for the decoding.

###  IV-B Function $\mathcal{F}_{L}$

Algorithm 3 Finding logical component

0: $\bm{e_{i}}^{\prime},\bm{A}_{\text{rre}},\bm{L}_{\text{rre}}$

0: Vectors $\bm{u_{A}},\bm{u_{L}},\bm{v^{\prime}}$

1: Initialize $\bm{u_{A}},\bm{u_{L}}$ to zero vectors

2: Let $\bm{v}\leftarrow\bm{e_{i}}^{\prime}$

3: Let $H_{A}$ (resp. $H_{L}$) be an ordered list of pivot positions of
$\bm{A}_{\text{rre}}$ (resp. $\bm{L}_{\text{rre}}$)

4: for all $h_{i}$ in $H_{A}$ do

5: if entry $h_{i}$ of $\bm{v}$ is 1 then

6: Subtract row $i$ of $\bm{A}_{\text{rre}}$ from $\bm{v}$ (mod 2)

7: $[\bm{u_{A}}]_{i}\leftarrow 1$

8: end if

9: end for

10: Let $\bm{v^{\prime}}\leftarrow\bm{v}$

11: for all $l_{i}$ in $H_{L}$ do

12: if entry $l_{i}$ of $\bm{v}$ is 1 then

13: Subtract row $i$ of $\bm{L}_{\text{rre}}$ from $\bm{v}$ (mod 2)

14: $[\bm{u_{L}}]_{i}\leftarrow 1$

15: end if

16: end for

17: return $\bm{u_{A}},\bm{u_{L}}$

18: (if the computation was correct, then $\bm{v}$ should equal $\bm{0}$)

For the function $\mathcal{F}_{L}$, we need to consider the different
degenerate sets. We know that each error $e_{i}$ can be decomposed in terms of
the coset leader $\mathtt{E}_{i}$, some stabilizer $\mathtt{S}_{i}$, and some
logical operator $\mathtt{L}_{i}$ (see 14). There are $4^{k}$ logical
operators (including the identity) and each identifies one of the $4^{k}$
degenerate sets associated with each syndrome ${\hat{\mathbf{s}}}$.

Consequently, we can create a one-to-one mapping between the logical operators
and the degenerate sets. Since we can determine the tentative coset leader
$\mathtt{E}_{i}$ with $\mathcal{F}_{E}$, we only need to determine the logical
component $\mathtt{L}_{i}$ that composes our input error pattern.

With this in mind, we continue the approach from Section IV-A. We use the row
echelon form of $\mathbf{A}$, that is, ${\mathbf{A}_{\rm rre}}$, so we work
with $\quantity{S_{i,\rm rre}}$ instead. We perform the same procedure to the
logical operators. Let $\mathbf{\bar{X}}_{i}$ and $\mathbf{\bar{Z}}_{i}$ be
the binary row vector representations of $\bar{X}_{i}$ and $\bar{Z}_{i}$,
respectively (see 4 and 5), in $[X|Z]$ format. Let $\mathbf{L}$ be the
$2k\times 2n$ binary matrix that encodes the original $2k$ minimal logical
operators (see 4 and 5), that act as generators to the $4^{k}$ total logical
operators. Row $i$ of $\mathbf{L}$ is given either by $\mathbf{\bar{X}}_{i}$,
if $1\leq i\leq k$, or by $\mathbf{\bar{Z}}_{i-k}$, if $k+1\leq i\leq 2k$.

Just as with the stabilizers, we know that products of logical operators are
also logical operators. Moreover, products of a logical operator with
stabilizers correspond to the same logical operator. Since we are working in
$\mathbb{F}_{2}$, adding or subtracting rows of ${\mathbf{A}_{\rm rre}}$ or
$\mathbf{L}$ is equivalent to multiplying stabilizers and operators in Pauli
string form. Considering the augmented $(n+k)\times 2n$ matrix
$\matrixquantity[{\mathbf{A}_{\rm rre}}\\\ \mathbf{L}]$, by using the rows of
${\mathbf{A}_{\rm rre}}$ and $\mathbf{L}$, we may put the $\mathbf{L}$
component in its row echelon form, $\mathbf{L}_{\rm re}$. We can then put
$\mathbf{L}_{\rm re}$ in reduced row echelon form using only the rows of
$\mathbf{L}_{\rm re}$, yielding $\mathbf{L}_{\rm rre}$. Note that we cannot
use the rows in $\mathbf{L}_{\rm re}$ to further simplify ${\mathbf{A}_{\rm
rre}}$, as the resulting rows would no longer correspond to stabilizers. The
procedure may be represented as

with $I_{p}$ a $p\times p$ identity matrix. The matrices $\mathbf{J}_{A}$ and
$\mathbf{J}_{L}$ are of size $2k\times(n-k)$ and $2k\times 2k$, respectively,
and just like $\mathbf{J}$ in Section IV-A, they represent the linear
transformation required to put the matrix in reduced row echelon form.

The resulting rows of $\mathbf{L}_{\rm rre}$ correspond to $2k$ (possibly
different) generators for the logical operators. These generators may no
longer satisfy the anti-commutation relations expected of $\bar{X}$ and
$\bar{Z}$, but they are not required to. The final $\mathbf{L}_{\rm rre}$
matrix is such that the columns with the same index as the pivots of
${\mathbf{A}_{\rm rre}}$ are zero, and the columns with the pivots of
$\mathbf{L}_{\rm rre}$ have only one non-zero element, its pivot.

For every error pattern $e_{i}$ with syndrome $\mathbf{s}_{i}$, we know that
its error component $\mathtt{E}_{i}$ (given by $\mathcal{F}_{E}$) is such that
$e_{i}\mathtt{E}_{i}=\mathtt{S}_{i}\mathtt{L}_{i}=:e_{i}^{\prime}$, for some
unknown $\mathtt{S}_{i}$ and $\mathtt{L}_{i}$. Consequently, to determine the
degenerate set to which $e_{i}$ belongs, we only need to decompose
$e_{i}^{\prime}$ into its $\mathtt{S}_{i}$ and $\mathtt{L}_{i}$ components.
Concretely, we are looking for the unique row vectors $\mathbf{u}_{A}$ (of
size $n-k$) and $\mathbf{u}_{L}$ (of size $2k$) such that

where $\mathbf{e}_{i}^{\prime}$ is exceptionally in $[X|Z]$ format. Since
${\mathbf{A}_{\rm rre}}$ and $\mathbf{L}_{\rm rre}$ are already in reduced row
echelon form, finding the two vectors is straightforward. The procedure is
described in Algorithm 3. Once the $\mathbf{u}_{A}$ and $\mathbf{u}_{L}$ row
vectors are determined, the $\mathtt{S}_{i}$ and $\mathtt{L}_{i}$ components
are simply given by (see 13)

$\displaystyle\mathtt{S}_{i}$
$\displaystyle=\text{op}(\mathbf{u}_{A}{\mathbf{A}_{\rm rre}})$ (24)
$\displaystyle\mathtt{L}_{i}$
$\displaystyle=\text{op}(\mathbf{u}_{L}\mathbf{L}_{\rm rre}).$ (25)

Alternatively, we may simply skip the computation of $\mathbf{u}_{L}$ in
Algorithm 3. Let $\mathbf{v}^{\prime}$ equal the computed row vector
$\mathbf{v}$ just after $\mathbf{u}_{A}$ is computed, but before the iteration
through the pivots of $\mathbf{L}_{\rm rre}$. Then, we equivalently have
$\mathtt{L}_{i}=\text{op}(\mathbf{v}^{\prime})$.

The full procedure

$e_{i}\implies e_{i}\mathtt{E}_{i}\implies\mathbf{u}_{L}\;(\text{or
}\mathbf{v}^{\prime})\implies\mathtt{L}_{i}$ (26)

corresponds to the function $\mathcal{F}_{L}$.

##  V Asymptotic regime

We can estimate the optimal performance we can obtain from the decoding
procedure by looking at how it performs as the number of extractions
considered is increased. We are interested in computing the limit where we
have infinite extractions, where the decoding would be optimal. Although this
regime is impossible to attain in practice, we expect that, as we increase the
number of extractions, the decoding dynamics should converge to the asymptotic
corresponding to that optimal case, allowing us to estimate the code’s
performance in that regime.

We consider the total probability of correction failure $P_{\rm total}$ to
correspond to the probability that an error is not completely corrected. That
is, the correction chosen does not correspond to the right degenerate set.
Note that this definition provides a lower bound on the fidelity $F$ of the
resulting quantum state, given by

$F\geq 1-P_{\rm total},$ (27)

since it effective treats any unsuccessful correction as producing a state
with zero fidelity, whereas in practice the uncorrected error may not produce
an orthogonal quantum state. Nonetheless, it is a useful lower bound often
used in the literature [10, 2], and that we choose to use here as well.

Let $P_{\infty}$ be the asymptotic limit of $P_{\rm total}$ when the number of
syndrome extractions $q$ goes to infinity (see Fig. 4). Since there are
$L=2^{2k}$ degenerate sets associated to each syndrome sequence $s$, then,
regardless of the encoding used, for a given $s$, the probability $p$ of an
error having occurred that is in the most likely degenerate set satisfies
$p\geq 1/L$. If $e^{c}_{i}$ is the error pattern representative of the most
likely degenerate set for $s_{i}$, then we must have

$\displaystyle P_{\infty}$
$\displaystyle=1-\sum_{i}p(e^{c}_{i}e_{i}\in\mathcal{S}|E_{i})p(E_{i})$ (28)
$\displaystyle\leq 1-\sum_{i}(1/L)p(E_{i})$ (29) $\displaystyle=1-1/L$ (30)
$\displaystyle=1-2^{-2k},$ (31)

with equality achieved for the case of maximum noise entropy.

When comparing two setups, $A$ and $B$, with $q_{A}$ and $q_{B}=q_{A}+h$
$(h>0)$ syndrome extractions, respectively, we necessarily have

$P_{\rm total}(A)\leq P_{\rm total}(B)$ (32)

since introducing $h$ additional noisy syndromes extractions introduces
additional errors in the model, which may or may not be correctable.

Fig. 4: Model considered to compute the asymptotic regime, where
$q\rightarrow\infty$.

We are interested in determining the failure probability $P_{\rm failure}$
induced by a single additional syndrome extraction, preceded and succeeded by
an arbitrarily high number of extractions. In the context of fault-tolerance,
we wish to determine if, for a given $p$, $P_{\rm failure}$ increases or
decreases with increasing qubit count $n$. We expect, for low (resp. high)
values of $p$, $P_{\rm failure}$ decreases (resp. increases) with $n$, with a
phase transition at some $p_{\rm threshold}$, to be determined.

Since we do not have direct access to $P_{\rm failure}$, it must be computed
from the measured value of $P_{\rm total}$. We develop an effective model to
quantitatively relate the two quantities.

Consider a variant of the $B$ setup above, labeled $B^{\prime}$, where the
first $q_{A}$ extractions are solely used to identify and correct errors
stemming from implementing those extractions, and similarly, the last $h$
extractions are solely used to deal with errors resulting from the $h$
extractions, for a total of $q_{B}=q_{A}+h$, as before. In other words, in the
$B^{\prime}$ setup, the procedure is partitioned into to separate and
independent decoding processes.

We expect

$P_{\rm total}(B)\leq P_{\rm total}(B^{\prime}).$ (33)

since, in the $B$ setup, the last $h$ extractions also provide information
about errors in the previous extractions, which can lead to a more successful
decoding. The $B^{\prime}$ setup does not use this information.

In fact, if an error occurs at extraction $q_{A}$, we expect that a lower
number $h$ of subsequent extractions will result in higher failure rates (per
extraction), since the decoding process has less information to correctly
identify the error. Since we are interested in the limiting case where the
number of subsequent extractions is infinite (for any given extraction where
an error can occur), we wish to discount the effect of limited syndrome
information from the calculated probability of failure $P_{\rm failure}$. We
label the errors that could have been successfully corrected with
$h\rightarrow\infty$ but were not with low $h$ _escaped errors_.

For low $q$, we expect (see [27]) that escaped errors (in particular errors
with ${\tilde{\mathbf{s}}}=0$ but $\hat{\mathbf{s}}\neq 0$) can be identified
with additional syndromes from more subsequent extractions, so that each new
extraction reduces the number of escaped errors by a factor $\delta$. Of
course, new extractions also introduce new escaped errors, and errors at the
end extractions are more likely to escape correction.

Consider a setup with $q$ extractions as a setup with $q-1$ extractions
preceded by one additional extraction. The errors of this additional
extraction will be detected by the $q-1$ subsequent extractions, so that only
a factor $\delta^{q-1}$ escape through the whole setup incorrectly identified.
Therefore, applying the reasoning recursively for $q$ extractions, we expect
the probability of an error passing through the extractions undetected to be
given by

$\displaystyle P_{u}(p,q)$ $\displaystyle\simeq
P_{u}(p,q-1)+\delta^{q-1}P_{u}(p,1)$ (34) $\displaystyle\simeq
P_{u}(p,1)\frac{1-\delta^{q}}{1-\delta}.$ (35)

For $q\gg 1$, we expect that the probability of successful correction with $q$
extractions $P_{\rm succ}(p,q)$ will be approximately the probability of
success with $q-1$ extractions times the per-extraction probability of success
(which accounts for the additional extraction). We have

$\displaystyle P_{\rm succ}(p,q)$ $\displaystyle\simeq P_{\rm
succ}(p,q-1)(1-P_{\rm failure}(p))$ (36) $\displaystyle=(1-P_{\rm
failure}(p))^{q}$ (37) with $\displaystyle P_{\rm succ}(p,0)=1.$ (38)

However, since $P_{\rm failure}$ does not incorporate escaped errors, the true
probability of success $P_{\rm succ}^{\prime}$ is given by

$P_{\rm succ}^{\prime}(p,q)=P_{\rm succ}(p,q)(1-P_{u}(p,q)),$ (39)

yielding

$P_{\rm total}(p,q)\simeq 1-(1-P_{\rm failure}(p))^{q}(1-P_{u}(p,q)).$ (40)

If $\delta\ll 1$, which is expected, then, when using $q\gg 1$ total
extractions, we may approximate $P_{u}(p,q)\simeq P_{u}(p,\infty)$, leading to

$\displaystyle P_{\rm total}(p,q)$ $\displaystyle\simeq 1-C(p)(1-P_{\rm
failure}(p))^{q},$ (41) $\displaystyle\text{with }C(p)$
$\displaystyle:=1-P_{u}(p,\infty),$ (42)

where $C$ incorporates the escaped errors. See Fig. 5 for a numerical
verification of this model. Once more, note that we discount these errors, and
their probability $P_{u}$, from the failure probability $P_{\rm failure}$,
since we are interested in the per-extraction failure probability, and $P_{u}$
constitutes a global effect. As previously indicated, if a syndrome extraction
is followed by $h\rightarrow\infty$ extractions, then the probability that an
error stemming from that extraction goes completely undetected is
$\delta^{h}P_{u}(p,1)\rightarrow 0$.

$P_{\rm failure}$ is the asymptotic contribution of each syndrome extraction
to the probability of failure. We have that, by fitting, for each $p$,

$\displaystyle Y=mX+b,$ (43) $\displaystyle\text{with }Y:=\log(1-P_{\rm
total}(p,q)),\quad X:=q,$ (44)

then, from 41,

$P_{\rm failure}(p)=1-e^{m},\quad C(p)=e^{b},$ (45)

for each $p$ considered.

Fig. 5: Experimental $P_{\rm total}$, and resulting fit by 41. We observe the
experimental data matching the qualitative description of the theoretical
analysis, with $R^{2}>0.999$ for all cases. Fig. 6: Performance of QRLCs with
$k=1$, using fault-tolerant QGRAND. We observe that the asymptotic version
presents a threshold around $p\simeq{2\times 10^{-5}}$. The shaded regions
denote a 50% confidence interval (from 50 samples), and the dots are the
median performance observed. The vertical line indicates the ${p_{\rm
threshold}}$ value.

See Fig. 6 for results. We observe ${p_{\rm threshold}}\simeq{2\times
10^{-5}}$, suggesting the QGRAND technique can be used in the fault-tolerant
regime. Nonetheless, we note that this optimal decoding procedure is not
scalable for high entropy noise models, such as those given by
$p\gtrsim{p_{\rm threshold}}$. Therefore, to use these techniques, we are
forced to either simplify our model, turning the decoding procedure
suboptimal, or to focus on a regime where it can be applied in practice.

For reference, we also estimate the performance of the uncoded case.
Considering the number of noisy CNOT gates present in a circuit with $q$
iterations to be ${N_{\rm CNOT}}(q)$, we get

$P_{\rm failure,uncoded}(p)\simeq 1-(1-p)^{{N_{\rm CNOT}}(1)}.$ (46)

${N_{\rm CNOT}}$ doesn’t include preparation and measurement errors, as these
don’t propagate throughout the circuit.

The simulation is performed for $\omega<\omega_{\rm max}$, and approximated
for the higher $\omega$ values. For high $\omega$, we use the reasonably
accurate assumption that error patterns are uniformly assigned to the syndrome
sequences. Therefore, before computing $P_{\rm failure}$, we modify $P_{\rm
total}$ with the correction

$P_{\rm total}^{\prime}=P_{\rm total}-\frac{P(\omega>\omega_{\rm
max})}{2^{n+k}},$ (47)

where $2^{n+k}$ is the number of degenerate sets associated with each syndrome
sequence. The correction is negligible for high $n$, but may play a noticeable
role for $p\simeq 1$.

##  VI Discussion and conclusions

In this work, we extend the decoding procedure for QRLCs introduced in [2] to
explicitly account for error degeneracy. Consequently, our technique
constitutes a maximum likelihood decoding procedure, which is guaranteed to be
optimal. We analyze the fault-tolerant characteristics of QRLCs with the
presented decoding technique, by accounting for preparation, measurement, and
gate errors in the syndrome extraction procedure itself, and observe a
${p_{\rm threshold}}\simeq{2\times 10^{-5}}$ in the asymptotic limit. As far
as the authors are aware, this is the first proposed decoding technique in the
literature for quantum random linear codes in the fault-tolerant regime, where
preparation, measurement, and gate errors are not considered negligible.

We note that this decoding procedure is not equivalent to finding the lowest
weight error pattern associated with each syndrome, as might be done by more
standard algorithms, since a faulty CNOT gate error effect can propagate
considerably through the circuit before being possible to detect it, so that,
by the time it is detected, its error pattern is no longer low weight.

In this work, we have removed the channel errors present in [2] and considered
only the main error sources associated with the syndrome extraction process.
In particular, we considered preparation and measurement errors in the ancilla
qubits, and two-qubit gate errors. Although this is a common approach to take
when studying the fault-tolerance capabilities of different codes [10], it
leads to unrealistic results for high code rates. In the limit when
$R\rightarrow 1$, the syndrome extraction process has a negligible number of
minimal stabilizers, and as a result negligible error sources, under this
noise model. Consequently, in this regime, higher code rates lead to lower
$P_{\rm failure}$, not because of better correction capabilities, but because
error sources decrease faster than the correction capabilities do, as the code
rate increases.

Moreover, we have analyzed the asymptotic regime of infinite syndrome
extractions. Although impractical, these asymptotic results enable us to study
the behavior of the optimal decoding procedure, as previously described.
Nonetheless, practical limitations might impose suboptimal steps in the
decoding process, and obviously a finite number of syndrome extractions.

To account for these limitations, we must consider that, in practice, there
are non-trivial computing steps performed between syndrome extractions (such
as logical gates for quantum computing, and Bell-pair creation for quantum
communication) that introduce their own errors independently from the syndrome
extraction steps. When accounting for this additional error source, we expect
the pathological behavior for high code rates to disappear. In future work, we
intend to study these more practical regimes. Furthermore, we assumed that
all-to-all connectivity (between any of the $n$ qubits) is possible in
practice. This assumption is required for the scaling results in [23], and is
used in this work. Nonetheless, it may be dropped for practical reasons, as
the more recent results in [25] suggest.

As previously mentioned, the noise guessing decoding procedure is expected to
be viable only in situations of low noise entropy and low $n$. Even
disregarding the limitations imposed by the asymptotically large number of
syndrome extraction, it is also the case that the noise entropy increases
rapidly as $n\rightarrow\infty$ and $k=1$, as considered for the fault-
tolerance analysis. This is a known limitation of the decoding procedure. For
this reason, and for the fact that better known codes, such as surface codes,
have higher ${p_{\rm threshold}}$ values, we do not expect the decoding
procedure described in this work to be competitive in those regimes. Although
it remains to be confirmed in future work, we conjecture that, given the
optimal decoding properties of the described procedure, it may be worthwhile
to employ in scenarios where code versatility is needed, the noise statistics
are not approximately fixed, and the code rate is desired to be very high. In
those cases, we expect the method to have similar use cases to those
previously described in [2], as the additional gates used by the syndrome
extraction process would not have a strong impact on decoding performance.

Beyond the straightforward approach described in Algorithm 2, we may also wish
to sacrifice the decoding optimality for the sake of decoding throughput, or
lower hardware requirements, rendering the decoding process more easily
scalable. This can be achieved with either known techniques, such as
compressive sensing or deep learning, or with more straightforward approaches,
such as greedy variants of the method. For instance, for the Bernoulli noise
model in this work, if we take the coset leader to be the first error pattern
associated with a syndrome, we will end up with a suboptimal version of
Algorithm 2, equivalent to [2], but one which reduces the memory requirements
by as much as a factor of $4^{k}$. There are also specific simplifications
that can be used to implement the decoding procedure faster when the noise
model has some exploitable structure, as is the case with the noise model
considered here. We plan to cover some of these approaches in future work.

##  Appendix A Reducing stabilizer weight

Although we are working with quantum random linear codes, which have little
exploitable structure _a priori_ , we note that the minimal stabilizers can be
efficiently chosen to have weight lower than the average of $3n/4$. To do so,
we may take the original minimal stabilizer arising from the technique
described in [2], represent them with the parity check matrix, and put the
matrix in canonical form, which is equivalent to reduced row echelon form. The
new simpler minimal stabilizers correspond to the rows of the resulting
matrix.

If the pivots of the matrix in reduced row echelon form are all in the first
$n$ columns, then this technique reduces the weight of the non-$Z$ components
of each minimal stabilizer to at most $1+k$, and $1+k/2$ on average. If $k$ is
low and $n$ is large, this technique can result in a considerable reduction in
the weight of the minimal stabilizers, as their average weight goes from
$3n/4$ to $3k/4+(n-k-1)/2+1=(2n+k+2)/4$. Instead of each term being equally
distributed between $I,X,Y,$ and $Z$ as before, here only the indices greater
than $n-k$ maintain that distribution, and we have, for $S_{i}$, index $i$
equally distributed between $X$ and $Y$, and index $j\leq n-k,j\neq i$ equally
distributed between $I$ and $Z$.

This structure simplifies the application of the syndrome extraction process,
as it reduces the number of CNOT gates from $\sim 3n(n-k)/4$ to
$(2n+k+2)(n-k)/4$, and similarly reduces the number of 1-qubit gates. Despite
these benefits, in our numerical analysis we have not assumed such an approach
was taken in the circuit implementation, in order not to introduce unwarranted
structure in the noise statistics, as we are interested in analyzing the more
general scenario.

Nonetheless, as explained in Sections IV-A and IV-B, we have used this
simplification in our decoding implementation, when given the noise statistics
associated with the unsimplified stabilizers. As they generate the same
stabilizer group, they are mathematically equivalent for the same given noise
statistics, and we expect either approach to lead to similar numerical
results.

##  Appendix B Degeneracy analysis

Regarding degeneracy, following the notation introduced in Section III, we
consider errors $E_{i}$ and $E_{j}$ to be degenerate if and only if
$e_{i}e_{j}\in\mathcal{S}$. Nonetheless, we may describe three types of
degenerate errors, all prevalent in the noise model considered in this work.

#### Identical errors.

These are errors such that $e_{i}=e_{j}$ and $e_{i}^{s}=e_{j}^{s}$. For
example, since we are considering the model implementation where the CNOT
gates of the conditional stabilizer are implemented in succession, with the
control always being the ancilla qubit (see Fig. 1), then any error of the
form $Z_{c}I_{t}$ (with $c$ and $t$ the control and target qubit indices,
respectively) will commute with subsequent CNOT gates controlled by the qubit
$c$. Therefore, this component does not add any error terms to the main $n$
qubits, and instead simply negates the measured ancilla qubit. As a result,
for any error term without this component, there is an error term with this
component where the error pattern in the main $n$ qubits is the same, and the
ancilla qubit is simplify negated. Given this degeneracy, the problem reduces
to two scenarios: one where there is an even number of such errors, where the
syndrome is unaffected, and one with an odd number of such errors, where the
ancilla bit is negated. Among these two classes, all errors are not only
degenerate, but identical.

#### Pseudo-identical errors.

Besides the identical errors, we also observe cases where $e_{i}=e_{j}$ but
$e_{i}^{s}\neq e_{j}^{s}$ (with
$\text{comp}_{X}(e_{i}^{s}e_{j}^{s})=\mathbf{0}$, otherwise the errors would
have different syndromes).

#### Non-identical errors.

We also have the more general case where $e_{i}\neq e_{j}$ (with either
$e_{i}^{s}=e_{j}^{s}$ or $e_{i}^{s}\neq e_{j}^{s}$), while still retaining
$e_{i}e_{j}\in\mathcal{S}$.

See Fig. 7 for an example. There, the code’s sole non-trivial stabilizer is
$X_{1}X_{2}$. We have $e_{i}^{s}=e_{a}^{s}=a_{c}^{s}=X$, $e_{b}^{s}=Y$
(ignoring the phase), $e_{i}=e_{a}=a_{b}=I_{1}I_{2}$, and $e_{c}=X_{1}X_{2}$.

Fig. 7: For the example code in Fig. 2, we may observe the three forms of
degenerate errors. Considering $E_{i}$ as the error showcased in the top left
circuit, the identical, pseudo-identical, and non-identical errors can be seen
in subfigures (a), (b), and (c), respectively.

##  Appendix C Analytical threshold without degeneracy

For this analysis, we disregard preparation and measurement errors, as the
derivation can be readily extended to the complete model.

Keeping $k$ constant, the value of $n$ will determine the number of CNOT gates
(${N_{\rm CNOT}}$) in the circuit, and the code’s correction capabilities. We
may estimate its performance by considering the approximation given by random
ideal codes, as in [2].

For $S=:2^{n-k}\gg 1$ and $N$ the number of distinct errors, the equation

$f=\frac{S}{N+1}\quantity[1-\quantity(1-\frac{1}{S})^{N+1}]$ (48)

may be approximated by

$\displaystyle f$
$\displaystyle\simeq\frac{1-e^{-r}}{r},\qquad\qquad\qquad\qquad
r:=\frac{N+1}{S}$ (49) $\displaystyle\implies f$
$\displaystyle\simeq\frac{1-(1-r+r^{2}/2)}{r}=1-\frac{r}{2}\text{ for }r\ll
1,$ (50)

since, from 48, we have

$\displaystyle f$
$\displaystyle=\frac{1}{r}\quantity[1-\quantity[\quantity(1-\frac{1}{S})^{S}]^{r}]$
(51) $\displaystyle\simeq\frac{1}{r}\quantity[1-(e^{-1})^{r}].$ (52)

Since $S=2^{n-k}$, this indicates that

$\displaystyle f$ $\displaystyle\geq 1-\epsilon$ (53) $\displaystyle\iff N$
$\displaystyle\lesssim 2^{n-k+1}\epsilon.$ (54)

W.l.o.g., consider that each CNOT gate can only suffer from a specific error,
instead of 15. For the Bernoulli noise model we are considering, the error
order $\omega$ is given by the binomial distribution

$\omega\sim\mathcal{B}({N_{\rm CNOT}},p)$ (55)

For $p$ fixed, and as ${N_{\rm CNOT}}\rightarrow\infty$, this distribution can
be approximated by

$\mathcal{N}({N_{\rm CNOT}}p,{N_{\rm CNOT}}p(1-p))$ (56)

using the De Moivre-Laplace theorem.

Suppose we start by correcting the lowest order errors (which are more likely
to occur), and we wish to correct the errors up to order $\omega_{\rm max}$
such that we have the probability $(1-\epsilon)$ of correcting an error we
observe. For a normal distribution, this is given by the quantile function

$Q(p)=\mu+\sigma\sqrt{2}\text{erf}^{-1}(2p-1).$ (57)

The error function erf cannot be easily approximately. Nonetheless, we may
observe that it can approximated by

$\text{erf}(x)\simeq 1-\alpha\exp(-(x-\beta)^{2}),\text{ for }x\gg 1,$ (58)

leading to

$\text{erf}^{-1}(x)\simeq\beta+\sqrt{\log\quantity(\frac{\alpha}{1-x})}\text{
for }1-x\ll 1.$ (59)

For simplicity, we consider $\alpha=1,\beta=0$, which does not meaningfully
affect our conclusions here. The quantile function then becomes

$\displaystyle Q(1-\epsilon)$
$\displaystyle\simeq\mu+\sigma\sqrt{2}\quantity(\beta+\sqrt{\log\quantity(\frac{\alpha}{2\epsilon})})$
(60)
$\displaystyle\simeq\mu+\sigma\sqrt{2\log\quantity(\frac{1}{2\epsilon})}.$
(61)

with

$\displaystyle\mu$ $\displaystyle={N_{\rm CNOT}}p$ (62) $\displaystyle\sigma$
$\displaystyle=\sqrt{{N_{\rm CNOT}}p(1-p)}$ (63)
$\displaystyle\simeq\sqrt{{N_{\rm CNOT}}p}.$ (64)

Now that we have $\omega_{\rm max}=Q(1-\epsilon)$, we need to estimate the
number of errors $\tilde{N}$ up to order $\omega_{\rm max}$, given by

$\tilde{N}=\sum_{j=0}^{\omega_{\rm max}}\matrixquantity({N_{\rm CNOT}}\\\ j).$
(65)

Unfortunately, there is no closed form expression for this value. However, for
$\omega_{\rm max}\ll{N_{\rm CNOT}}$, this is roughly equal to

$\displaystyle\tilde{N}$ $\displaystyle\simeq\matrixquantity({N_{\rm CNOT}}\\\
\omega_{\rm max})$ (66) $\displaystyle\simeq\frac{{N_{\rm CNOT}}^{N_{\rm
CNOT}}}{{\omega_{\rm max}}^{\omega_{\rm max}}({N_{\rm CNOT}}-\omega_{\rm
max})^{{N_{\rm CNOT}}-\omega_{\rm max}}}$
$\displaystyle\phantom{\qquad\qquad}\times\sqrt{\frac{{N_{\rm
CNOT}}}{2\pi\omega_{\rm max}({N_{\rm CNOT}}-\omega_{\rm max})}}.$ (67)

This may be simplified down to

$\tilde{N}=2^{{N_{\rm CNOT}}h_{2}(\omega_{\rm max}/{N_{\rm
CNOT}})}\sqrt{\frac{1}{2\pi\omega_{\rm max}}},$ (68)

where $h_{2}$ is the Shannon entropy.

From 54 and 68, we therefore conclude that

$\displaystyle\log N$ $\displaystyle\sim\tilde{O}(n)$ (69)
$\displaystyle\log\tilde{N}$ $\displaystyle\sim\tilde{O}({N_{\rm CNOT}}),$
(70)

where $\tilde{O}$ denotes Big-O notation up to log factors. Since $N$
indicates the code’s correction capabilities, while $\tilde{N}$ indicates the
necessary number of errors that the code needs to correct to preserve $P_{\rm
failure}$, then we must have $N\gtrsim\tilde{N}$ and consequently ${N_{\rm
CNOT}}\sim\order{n}$. This is verified for some common codes, such as surface
codes, but for our implementation we have

${N_{\rm CNOT}}=\frac{3}{4}n(n-k)\sim\order{n^{2}},$ (71)

so we conclude that, if all errors are non-degenerate, the code does not have
a visible $p_{\rm threshold}$, since an increase in $n$ increases $P_{\rm
failure}$, regardless of $p$.

However, we actually observe a threshold for QRLCs. This is thanks to the fact
that the noise statistics given by the noise model of Section II actually lead
to a very high number of degenerate errors. Therefore, in practice, the number
of distinct errors grows with $\order{n}$ and not $\order{n^{2}}$ as indicated
by the analysis above. We later confirm this scaling for escaped errors, in
Appendix K.

With this insight in mind, we modify the QGRAND algorithm in [2] to account
for the possibility of degenerate errors. The modified algorithm is presented
in Section IV.

##  Appendix D Applying error correction

Certain QECCs, such as surface codes, are designed so that a physical error
correction is actually unnecessary to implement, as all changes can be made in
software, classically [10]. If the whole quantum circuit is unitary, then this
procedure can actually be implemented in general: instead of correcting the
error, we leave the affected state as is and simply XOR any subsequent
syndrome $\mathbf{s}$ with the identified error syndrome $\mathbf{e}$, that
is, $\mathbf{s}\mapsto\mathbf{s}\oplus\mathbf{e}$. As a result of this, we
only need to keep track of these detected errors classically, in order to
correct the subsequent syndromes.

In any case, since the correction portion is always single-qubit gates, we
assume that their contribution to the total error is negligible, so we can
disregard this trick for now, for the sake of simplicity. As a result, the
procedure to apply the error correction is the same as in [2].

##  Appendix E Parallel decoding

The decoding procedure described in Section IV can be performed in parallel.
If there are $W$ parallel workers available, we start by splitting the entries
in $\mathcal{N}$ into $W$ parts of equal size, labeling each
$\mathcal{N}_{w},1\leq w\leq W$. Each set $\mathcal{N}_{w}$ is then processed
independently by an individual procedure according to the procedure described
in the Section IV, thereby yielding the data table $D_{w}$.

All the $W$ data tables $D_{w}$ may then be merged to generate the full data
table $D$, from which the decoding table $T$ can be straightforwardly
computed. See Algorithm 4 for a description of the parallel decoding
procedure.

Algorithm 4 Parallel decoding

0: $\mathcal{N},W$

0: A decoding table $T$

1: Initialize empty data table $D$ and decoding table $T$

2: Split $\mathcal{N}$ into $W$ sets (almost) equal in size, labeled
$\mathcal{N}_{w}$ ($1\leq w\leq W$)

3: for all $w$ parallel workers do

4: Initialize empty data table $D_{w}$

5: $D_{w}\leftarrow\textsc{Data}(\mathcal{N}_{w})$

6: end for

7: $D\leftarrow\bigcup_{w}D_{w}$

8: for all entry $s$ in $D$ do

9: Set $T[s]$ as the pattern $e^{d}$ with highest $p$ in $D[s]$

10: end for

11: return $T$

##  Appendix F Full decoding example

Fig. 8: Optimal decoding of the code in Fig. 2 (but with only one syndrome
extraction), as described in Algorithm 2.

For the example in Fig. 8, we consider the encoding gate to be
$U=\text{CNOT}(2,1)H_{2}$, with the starting qubit at index 1. $P$ and $M$
stand for preparation and measurement error in the only ancilla qubit $a$,
respectively. $AB_{j})$ is the error corresponding to “error $A_{a}B_{j}$
occurred at CNOT gate $j$”. Following Algorithm 2, we iterate through the
errors in $\mathcal{N}$ and, using the functions $\mathcal{F}_{E}$ and
$\mathcal{F}_{L}$, determine where to put them in the table $D$. Once we have
iterated through all errors, we compute the optimal
$({\hat{\mathbf{s}}},\mathtt{L})$ entry, or alternatively, $e^{d}$
representative, and delete the remaining entries, yielding the decoding table
$T$.

Given $U$, and following 3, 4 and 5, the minimal stabilizer is
$S_{1}=X_{1}X_{2}$, and the logical operators are $\bar{X}=I_{1}X_{2}$ and
$\bar{Z}=Z_{1}Z_{2}$. This choice of encoding leads to minimal stabilizers and
logical operators such that the augmented matrix is

$\matrixquantity[\mathbf{A}\\\ \mathbf{L}]=\matrixquantity[\mathbf{A}\\\
\mathbf{\bar{X}}\\\ \mathbf{\bar{Z}}]=\matrixquantity[1&1&0&0\\\ 0&1&0&0\\\
0&0&1&1]=\matrixquantity[{\mathbf{A}_{\rm rre}}\\\ \mathbf{L}_{\rm rre}],$
(72)

since, in this simple example, we already have $\mathbf{A}={\mathbf{A}_{\rm
rre}}$ and $\mathbf{L}=\mathbf{L}_{\rm rre}$, so $\mathbf{J}=I$. Here,
$\mathbf{A},\mathbf{\bar{X}},$ and $\mathbf{\bar{Z}}$ are the binary
representations of the minimal stabilizers and logical operators, in
$\matrixquantity[X|Z]$ format.

Following the procedure in Section IV-A, we have

$\mathtt{E}_{0}=I_{1}I_{2}\qquad\mathtt{E}_{1}=Z_{1}I_{2}.$ (73)

Let’s consider the full procedure in Section IV applied to the specific error
in Fig. 2, such as

$E=``\text{Error }I_{a}Z_{1}\text{ in CNOT gate }1\text{''.}$ (74)

Associated to this error, we have the quantities

(75) (76) (77) (78) (79) (80)

Applying the procedure in Section IV and Algorithm 2, we obtain the tentative
decoding table in Table II. In the table, for the sake of simplicity, we
represent preparation and measurement errors by $P$ and $M$, respectively.
$AB_{i}$ represents the CNOT gate error where error $A_{a}B_{i}$ occurs just
after the noiseless CNOT gate. For simplicity, compound error are not shown.

TABLE II: Decoding for the code in Fig. 2. $(\hat{\mathbf{s}}_{\rm rre},\mathtt{L})$ | $e^{d}$ | $\mathbf{s}=0$ | $\mathbf{s}=1$
---|---|---|---
$(0,I)$ | $I_{1}I_{2}$ | $\emptyset,XI_{2},XX_{1}$ | $P,\\!M,\\!ZI_{2},\\!ZI_{1},\\!YX_{1},\\!YI_{2}$
$(0,\bar{X})$ | $I_{1}X_{2}$ | $IX_{1},\\!XI_{1},\\!IX_{2},\\!XX_{2}$ | $ZX_{1},YI_{1},ZX_{2},YX_{2}$
$(0,\bar{Y})$ | $Z_{1}Y_{2}$ |  |
$(0,\bar{Z})$ | $Z_{1}Z_{2}$ |  |
$(1,I)$ | $Z_{1}I_{2}$ | $IZ_{1},XY_{1}$ | $ZZ_{1},YY_{1}$
$(1,\bar{X})$ | $Z_{1}X_{2}$ | $XZ_{1},IY_{1}$ | $YZ_{1},ZY_{1}$
$(1,\bar{Y})$ | $Z_{1}Y_{2}$ | $IY_{2},XY_{2}$ | $ZY_{2},YY_{2}$
$(1,\bar{Z})$ | $I_{1}Z_{2}$ | $IZ_{2},XZ_{2}$ | $ZZ_{2},YZ_{2}$

The preparation and measurement errors have probability $p$ of occurring, and
the gate errors have probability $p/15$. If we assume that it is very unlikely
that no error has occurred (i.e. $p$ is high), then the final decoding table
(when only considering errors of order 1) is given by Table III. In the table,
if ${{\mathbf{s}}}=0$ is measured, the most likely degenerate set to have
occurred is $(0,\bar{X})$, with probability $4p/15$ (see Table II). We assume
that $p$ is such that the no-error case is unlikely, otherwise $(0,\bar{I})$
would be the most likely degenerate set. If ${{\mathbf{s}}}=1$ is measured,
the most likely degenerate set to have occurred is $(0,\bar{I})$, with
probability $34p/15$. For each case, the error pattern that should be applied
to the quantum state to correct the error is given by
$e^{d}=\mathtt{E}_{{\hat{\mathbf{s}}}}\mathtt{L}$.

TABLE III: Final decoding table for Fig. 2. $\mathbf{s}=0$ | $\mathbf{s}=1$
---|---
$(0,\bar{X})$ | $(0,I)$
$\downarrow$ | $\downarrow$
$\mathtt{E}_{0}\bar{X}=I_{1}X_{2}$ | $\mathtt{E}_{0}I=I_{1}I_{2}$

##  Appendix G Simplified noise statistics

When considering a Bernoulli noise model, such as in Appendix H, including
preparation and measurement errors into the noise model breaks some of the
structure of the noise statistics, since not all base errors will be equally
likely. It also makes the decoding process harder to simulate. In the simpler
setup where only gate errors occur, if we have $g$ CNOT gates affected with an
error, with each error having probability $p_{\rm CNOT}/15$ of occurring, then
the number of errors and their individual probability would be given by

$\displaystyle N_{E}(g)$ $\displaystyle=15^{g}\matrixquantity(N_{\rm CNOT}\\\
g)$ (94) $\displaystyle P(g)$ $\displaystyle=\quantity(\frac{p_{\rm
CNOT}}{15})^{g}(1-p_{\rm CNOT})^{N_{\rm CNOT}-g}.$ (95)

These formulas stem from the fact that each CNOT gate has 15 associated
errors, and only one of these may occur at a time. For preparation and
measurement errors, there is only one error pattern per ancilla qubit: either
there is a bit flip, or there isn’t. If there are $A$ ancilla qubits
(generally, $A=n-k$), and a preparation or measurement error occurs with
probability $p_{M}$, these same quantities are given by

$\displaystyle N_{E}(\omega)$
$\displaystyle=\sum_{g=0}^{\omega}15^{g}\matrixquantity(N_{\rm CNOT}\\\
g)\matrixquantity(2A\\\ \omega-g)$ (96) $\displaystyle P(\omega,g)$
$\displaystyle=\quantity(\frac{p_{\rm CNOT}}{15})^{g}(1-p_{\rm CNOT})^{N_{\rm
CNOT}-g}$ (97) $\displaystyle\qquad\qquad\times
p_{M}^{\omega-g}(1-p_{M})^{2A-\omega+g},$ (98)

where $\omega$ indicates the total error order, and $g$ indicates the error
order when ignoring preparation and measurement errors. Note that these
expressions are somewhat more complicated. In particular, for errors of order
$\omega$, we now need to keep track of the distinct number of CNOT ($g$) and
preparation/measurement ($\omega-g$) base errors that occurred, instead of
just one parameter.

Fortunately, if we are using optimal decoding (that properly accounts for
degenerate errors), there is a quick-and-dirty way to mimic the simpler noise
statistics associated with only having gate errors. If we use $p_{M}=p_{\rm
CNOT}=:p$ (which is a relatively common choice in the literature, see [10],
and the one used in Section II), then we can consider that each preparation
and measurement error is a CNOT gate error. Instead of there being only one
error per qubit (corresponding to the possible bit flip), we consider that
there are 15, all equal in nature, and each occurring with probability
$p_{M}/15$. These cloned errors will be degenerate among themselves, so the
optimal decoding procedure will analyze this setup correctly. The total number
of error patterns $N_{E}(\omega)$ will be overcounted, but we never actually
use it directly for the decoding procedure, so the overcounting does not
constitute an issue. In this formulation, we may pretend that we have no
preparation and measurement errors, and that we have instead

$\tilde{N}_{\rm CNOT}:=N_{\rm CNOT}+2A$ (99)

CNOT gates in the syndrome extraction circuit. The probability associated with
each error will be correct, yielding

$P(\omega)=\quantity(\frac{p}{15})^{\omega}(1-p)^{\tilde{N}_{\rm
CNOT}-\omega}.$ (100)

##  Appendix H Bernoulli noise model improvements

Algorithm 5 Data table $\tilde{D}_{1}$ for Bernoulli noise

0: $\mathcal{B}$

0: A data table $\tilde{D}_{1}$

1: Initialize empty data table $\tilde{D}_{1}$

2: $\bm{n_{0}}\leftarrow(1,0)$

3: Store $\\{I:\bm{n_{0}}\\}$ in $\tilde{D}_{1}[\\{\bm{0},\ldots,\bm{0}\\}]$

4: for all $E_{i}^{B}$ in $\mathcal{B}$ do

5: Compute $e_{i}$, $\hat{s}_{i}$, and $s_{i}$

6: Compute $\mathcal{L}_{i}$ associated with $e_{i}$

7: Compute $e^{d}_{i}$

8: if $e^{d}_{i}$ not in $\tilde{D}_{1}[s_{i}]$ then

9: $\bm{n_{i}}\leftarrow(0,0)$

10: $\bm{n_{i}}(1)\leftarrow 1$

11: Store $\\{e^{d}_{i}:\bm{n_{i}}\\}$ in $\tilde{D}_{1}[s_{i}]$

12: else

13: $\bm{n_{i}}(1)\leftarrow\bm{n_{i}}(1)+1$

14: Update $\\{e^{d}_{i}:\bm{n_{i}}\\}$ in $\tilde{D}_{1}[s_{i}]$

15: end if

16: end for

17: return $\tilde{D}_{1}$

For the special case where each CNOT gate has the same probability $p$ of
suffering an error, as described in Section II, the decoding procedure can be
made much more efficient. This procedure may be adapted to other Bernoulli-
like noise statistics, but here we focus on this error model. We can optimize
this decoding process in order to avoid having to iterate through all compound
errors. Since the technique relies on the inherent structure of errors with
the same probability, here we employ the reformulation detailed in Appendix G
to treat preparation and measurement errors as additional gate errors.

The procedure for the list of base errors (with $\omega=1$) is similar to the
one described in the beginning of Section IV. Instead of using the full noise
statistics $\mathcal{N}$, instead we consider a list of base errors

$\mathcal{B}:=\quantity{E^{B}_{1},E^{B}_{2},\ldots}.$ (101)

Given the Bernoulli noise model, all base errors have the same associated
probability of occurring, given by $p/15$, so it doesn’t need to be stored in
$\mathcal{B}$ (we exclude the no error case). Once we have the data table
$D_{1}$ for $\omega=1$, we can start to optimize the analysis for compound
errors. Instead of iterating through compound errors individually, we iterate
through the degenerate sets obtained in the $\omega=1$ step. We also preserve
the probability associated with observing an error pattern from each
degenerate set in the table. For $\omega=1$, and given the reformulation of
Appendix G, all errors $\hat{E}_{i}^{B}$ may be considered to have a
probability $P(1)$ of occurring (see 100), so the probability associated with
each degenerate set in the data table is given by

$p_{i}:=N_{i}P(1),$ (102)

where $N_{i}$ is the number of errors $E_{i}$ that can be corrected by
applying the coset leader $e_{i}^{d}$ associated with the degenerate set of
$\hat{E}_{i}^{B}$. In summary, we may restructure the data table $D_{1}$
obtained with Algorithm 2 (before the final degenerate set selection)

$D_{1}=\\{s_{1}:\quantity{(e^{d}_{11},p_{11}),(e^{d}_{12},p_{12}),\ldots},\\\
s_{2}:\quantity{(e^{d}_{21},p_{21}),(e^{d}_{22},p_{22}),\ldots},\ldots\\}$
(105)

to encode the count $N_{i}$ instead of $p_{i}$, and to store a list of error
counts for different orders, yielding

$\tilde{D}_{1}=\\{s_{1}:\quantity{e^{d}_{11}:\mathbf{n}_{11},e^{d}_{12}:\mathbf{n}_{12},\ldots},\\\
s_{2}:\quantity{e^{d}_{21}:\mathbf{n}_{21},\ldots},\ldots\\}$ (108)

with

$\mathbf{n}_{i}:=(0,N_{i},0,\ldots)$ (109)

a list of size $(\omega+1)$, where only the second entry of the list
(corresponding to $\omega=1$) starts with non-zero entries. The first entry is
only non-zero for the $E_{0}=I$ case, when $\mathbf{s}={\hat{\mathbf{s}}}=0$
and $\mathtt{L}=I$, corresponding to the case where no error occurs. We
represent the entry of order $g$ by $\mathbf{n}_{i}(g)$.

Under the formulation of 108, instead of iterating through the combinations
$\quantity{E_{1}^{B}E_{2}^{B},E_{1}^{B}E_{3}^{B},\ldots,E_{2}^{B}E_{3}^{B},\ldots}$
as we could do with the naive implementation of Algorithm 2, we iterate
through the degenerate sets in $\tilde{D}_{1}$ as a whole.

Consider the data table $\tilde{D}_{\omega-1}$ that includes the errors up to
order $\omega-1$. To obtain the table for errors up to order $\omega$, we
iterate through the combination of the degenerate sets in
$\tilde{D}_{\omega-1}$ and $\tilde{D}_{1}$. If the noise statistics are highly
degenerate (which is generally the case following the noise model in Section
II), we can have considerable computational savings, since we only need to
perform $|\tilde{D}_{\omega-1}||\tilde{D}_{1}|$ computations instead of
$15^{\omega}\matrixquantity(N_{\rm CNOT}+2(n-k)\\\ \omega)$ (see Appendix G).
While we expect the latter to grow quickly with $\order{n^{2\omega}}$, the
former approach should grow, at worst, with $\order{n^{\omega}}$, and it may
grow more slowly in practice.

With this approach we generally overcount the number of errors $N_{i}$
associated with each degenerate set. There are three types of overcounting:

  * •

Counting permuted copies: Consider an order-$(\omega-1)$ error
$E_{i_{1}}^{B}E_{i_{2}}^{B}\ldots E_{i_{\omega-1}}^{B}$ (with
$i_{1}<i_{2}<i_{3}<\ldots$), coming from $\tilde{D}_{\omega-1}$, and the error
$\hat{E}_{j}^{B}$, coming from $\tilde{D}_{1}$. W.l.o.g., suppose $j<i_{1}$.
Then, for $\tilde{D}_{\omega}$, we will not only count the error
$E_{j}^{B}E_{i_{1}}^{B}E_{i_{2}}^{B}\ldots E_{i_{\omega-1}}^{B}$, but also
that same error coming from the combination of the errors
$E_{j}^{B}E_{i_{1}}^{B}E_{i_{2}}^{B}\ldots E_{i_{\omega-1}}^{B}\backslash
E_{i_{k}}^{B}$ and $E_{i_{k}}^{B}$. In total, we overcount each order-$\omega$
error $\omega$ times.

  * •

Recounting lower order errors: for the error $E_{i_{1}}^{B}E_{i_{2}}^{B}\ldots
E_{i_{\omega-1}}^{B}$, composing with any $E_{i_{k}}^{B}$ ($1\leq
k\leq\omega-1$) reduces the error to one of order $\omega-2$, which was
previously counted. Each order-$(\omega-2)$ error we counted before will be
recounted $\zeta_{\omega-1,1}$ times, where $\zeta$ is given in 113.

  * •

Counting two errors occurring in the same CNOT gate: an error of order
$\omega$ stems from base errors that occurred on $\omega$ CNOT gates. When
composing this error with another, the resulting compound error may have more
than one base error occurring at one or more CNOT gates. As this compound
error is impossible, it should be discounted.

Algorithm 6 Data table $\tilde{D}_{a+b}$

0: $\tilde{D}_{a},\tilde{D}_{b}$

0: A data table $\tilde{D}_{a+b}$

1: Initialize empty data table $\tilde{D}_{a+b}$

2: for all $(s_{i},e^{d}_{i},\bm{n_{i}})$ in $\tilde{D}_{a}$ do

3: for all $(s_{j},e^{d}_{j},\bm{n_{j}})$ in $\tilde{D}_{b}$ do

4: $\tilde{\bm{n}_{ij}}\leftarrow\bm{n_{i}}*\bm{n_{j}}$ (convolution)

5: $\bm{n_{ij}}\leftarrow\tilde{\bm{n}_{ij}}$ with overcounting correction

6: if $e^{d}_{i}e^{d}_{j}$ not in $\tilde{D}_{a+b}[s_{i}\oplus s_{j}]$ then

7: Store $\\{e^{d}_{i}e^{d}_{j}:\tilde{\bm{n}_{ij}}\\}$ in
$\tilde{D}_{a+b}[s_{i}\oplus s_{j}]$

8: else

9: Add $\tilde{\bm{n}_{ij}}$ to vector in $e^{d}_{i}e^{d}_{j}$ entry in
$\tilde{D}_{a+b}[s_{i}\oplus s_{j}]$

10: end if

11: end for

12: end for

13: for all $(s_{r},e^{d}_{r},\bm{n_{r}})$ in $\tilde{D}_{a+b}$ do

14: $\bm{n_{r}}\leftarrow\tilde{\bm{n_{r}}}$ with overcounting correction

15: Store $\\{e^{d}_{r}:\bm{n_{r}}\\}$ in $\tilde{D}_{a+b}[s_{r}]$

16: end for

17: return $\tilde{D}_{a+b}$

We can extend this approach further. Instead of constructing the data table in
one order increments, if we already have $\tilde{D}_{\omega}$, we may combine
it with itself to obtain $\tilde{D}_{2\omega}$, thereby requiring
exponentially fewer iterations, as $\omega$ increases, as long as $\omega$ is
such that the codes capabilities are not yet saturated, i.e., not all
syndromes are assigned to a degenerate set.

In general, if we compute the noise statistics of errors of order $a$ and $b$
to compute those of order $\omega=a+b$, we have

$\displaystyle\mathbf{n}_{i}(\omega)=\frac{1}{R_{a,b}}\Big{[}\tilde{\mathbf{n}}_{i}(\omega)-\sum_{\begin{subarray}{c}0<k+r\leq
b\\\ k,r\geq 0\end{subarray}}\zeta_{a,b}(k,r)\mathbf{n}_{i}(c)\Big{]},$ (110)
$\displaystyle\text{with }c:=a+b-2k-r,$ (111)

where $\tilde{\mathbf{n}}_{i}(\omega)$ is the count obtained for order
$\omega$ before the overcounting correction. The auxiliary functions are given
by

$\displaystyle R_{a,b}$ $\displaystyle:=\matrixquantity(a+b\\\ a)$ (112)
$\displaystyle\zeta_{a,b}(k,r)$ $\displaystyle:=K^{k}(K-1)^{r}\xi_{a,b}(k,r)$
(113) $\displaystyle\xi_{a,b}(k,r)$
$\displaystyle:=\matrixquantity({\tilde{N}_{\rm CNOT}}-c\\\
k)\matrixquantity(c\\\ r,a-k-r,b-k-r),$ (114)

where $K$ is the number of distinct errors per CNOT gate (in our case, always
15). Note the use of binomial and multinomial coefficients. To incorporate the
effect of preparation and measurement errors, we use $\tilde{N}_{\rm
CNOT}={N_{\rm CNOT}}+2(n-k)$ and not ${N_{\rm CNOT}}$, as explained in
Appendix G. See Appendix I for a derivation of these expressions.

The probability associated with the degenerate set with list $\mathbf{n}_{i}$
is given by

$p_{i}=\sum_{j=0}^{\omega}\mathbf{n}_{i}(j)P(j).$ (115)

Given this procedure to obtain $\tilde{D}_{\omega}$, we may obtain the
decoding table $T_{\omega}$ by following Algorithms 5, 6 and 7.

Algorithm 7 Decoding table $T_{a+b}$

0: $\tilde{D}_{\omega}$

0: A decoding table $T_{\omega}$

1: Initialize empty decoding table $T_{\omega}$

2: for all $s$ in $\tilde{D}_{\omega}$ do

3: $(j,p)\leftarrow(-1,0)$

4: for all $(e^{d}_{i},\bm{n_{i}})$ in $\tilde{D}_{\omega}[s]$ do

5: Using $\bm{n_{i}}$, compute $p_{i}$ (115)

6: $(j,p)\leftarrow(i,p_{i})$ if $p_{i}>p$

7: end for

8: Set $T[s]$ as the pattern $e^{d}_{j}$, which has the highest $p$ in $D[s]$

9: end for

10: return $T_{\omega}$

##  Appendix I Derivation of decoding formulas for Bernoulli noise

As stated in Appendix H, a straightforward implementation of the procedure
described will overcount the number of errors associated to any given syndrome
sequence. There are three types of overcounting, which we may analyze
separately.

###  I-A Recounting lower order errors

Suppose we have already computed the correct error count $\mathbf{n}_{i}(j)$
for $0\leq j\leq\omega-1$ (for all degenerate sets), and we are currently
trying the determine $\mathbf{n}_{i}(\omega)$.

For the error $E_{i_{1}}^{B}E_{i_{2}}^{B}\ldots E_{i_{\omega-1}}^{B}$,
composing with any $E_{i_{k}}^{B}$ ($1\leq k\leq\omega-1$) reduces the error
to one of order $\omega-2$, which was previously counted. To determine how
many errors stem from this dynamic, we may note that any fake compound error
of order $\omega$ has a corresponding error of order $\omega-2$, which has
already been counted in $\mathbf{n}_{i}(\omega-2)$. Similarly, any error
$E_{i}$ counted in $\mathbf{n}_{i}(\omega-2)$ has a corresponding set of fake
compound errors that appear in $n_{i}(\omega)$. As $E_{i}$ stems from
$\omega-2$ base errors, each affecting a different CNOT gate, these fake
compound errors must correspond to an error of the form
$E_{i}E_{j}^{B}E_{j}^{B}$, where $E_{j}^{B}$ is a base error from a CNOT gate
not present in $E_{i}$. For each CNOT gate there are $K=15$ associated base
errors, so there are a total of

$\zeta_{\omega-1,1}(1,0)=K({\tilde{N}_{\rm CNOT}}-(\omega-2))$ (116)

fake error compounds that associated with the error $E_{i}$. Alternatively,
defining $\omega=a+k$, with $k=1$, we may also write the total as

$\zeta_{a,1}(1,0)=K({\tilde{N}_{\rm CNOT}}-(a-k)).$ (117)

The same principle applies to higher order combinations. If a order-$a$ error
$E_{i}$ is composed with a order-$k$ error $E_{j}$ ($a\geq k$), and the base
errors composing $E_{j}$ all stem from CNOT gates whose same base errors
already compose $E_{i}$, then the resulting compound error will have order
$a-k$, instead of $a+k$. The total number of errors is now given by

$\displaystyle\zeta_{a,k}(k,0)$
$\displaystyle=\frac{1}{k!}\prod_{j=0}^{k-1}K({\tilde{N}_{\rm CNOT}}-(a-k)-j)$
(118) $\displaystyle=K^{k}\matrixquantity({\tilde{N}_{\rm CNOT}}-(a-k)\\\ k).$
(119)

Note, however, that, when composing a order-$a$ error $E_{i}$ with a order-$b$
error $E_{j}$ ($a\geq b\geq k$), it may be the case that only some, and not
all, of the base errors composing $E_{j}$ appear in $E_{i}$. In general, there
will only be $k$ base errors in common, for all $1\leq k\leq b$.

In this case, to cover all possible fake errors, we must choose not $k$ CNOT
gates out of the ${\tilde{N}_{\rm CNOT}}-(a-k)$ gates not related to the
order-$(a-k)$ error (as in 119), but instead choose $k$ CNOT gates out of the
gates not related to both the order-$(a-k)$ error, but also the $(b-k)$ base
errors in $E_{j}$ that are valid. Therefore, there are a total of
${\tilde{N}_{\rm CNOT}}-(a-k)-(b-k)$ CNOT gates from which we must consider
$k$ invalid base errors.

Moreover, associated with the order-$(a-k)$ error from $E_{i}$, there are
several possible valid $(b-k)$ base errors stemming from $E_{j}$. The total
number of fake errors is then given by

$\displaystyle\zeta_{a,b}(k,0)$
$\displaystyle=K^{k}\matrixquantity({\tilde{N}_{\rm CNOT}}-(a-k)-(b-k)\\\ k)$
(120)
$\displaystyle\qquad\qquad\qquad\quad\times\matrixquantity((a-k)+(b-k)\\\
b-k)$ (121) $\displaystyle=K^{k}\matrixquantity({\tilde{N}_{\rm CNOT}}-c\\\
k)\matrixquantity(c\\\ b-k),$ (122) $\displaystyle\text{with }c:=a+b-2k.$
(123)

Note that, for $b=k$, we have $c=a-k$, so that 122 trivially reduces to 119.
The resulting lower order error will have order $c$. We would need to discount
its affect on $\mathbf{n}_{i}(\omega)$ to obtain the correct count.
Unfortunately, it would be difficult to determine the original syndromes of
the errors that combined to result in the impossible error, as they may have
different origins. As an approximation, we use $\mathbf{n}_{i}(c)$ to estimate
the error count. The resulting correction is achieved by subtracting
$\mathbf{n}_{i}(c)$ times $\zeta$ from $\mathbf{n}_{i}(\omega)$.

###  I-B Counting impossible errors

If a order-$a$ error $E_{i}$ is composed with a order-$r$ error $E_{j}$
($a\geq r$), and the base errors composing $E_{j}$ all stem from CNOT gates
already associated with the base errors that compose $E_{i}$, then the
resulting compound error will be impossible, since it will contain at least
two different base errors associated with the same CNOT gate (one from $E_{i}$
and one from $E_{j}$).

For $r=1$, each error in $\mathbf{n}_{i}(a)$ will have

$\zeta_{a,1}(0,1)=(K-1)a$ (124)

associated impossible order-$(a+1)$ errors, since $E_{i}$ is composed of $a$
base errors, and for each base error, there are $(K-1)$ different base errors
associated to the same CNOT gate.

For a general $r$, we have, for each order-$a$ error

$\zeta_{a,r}(0,r)=(K-1)^{r}\matrixquantity(a\\\ r)$ (125)

associated impossible errors.

When composing a order-$a$ error $E_{i}$ with a order-$b$ error $E_{j}$
($a\geq b$), it may be the case that only $r<b$ base errors composing $E_{j}$
are impossible, with the remaining $(b-r)$ base errors stemming from CNOT
gates not related to $E_{i}$.

To estimate the number of impossible errors, we may look at
$\mathbf{n}_{i}(a+b-r)$. As before, we must choose $r$ CNOT gates out of the
$a$ gates related to $E_{i}$ to count the number of impossible errors. But, as
seen in the previous subsection, to must also count the possible $(b-r)$ base
errors in $E_{j}$ that are valid. These factors result in

$\displaystyle\zeta_{a,b}(0,r)$ $\displaystyle=(K-1)^{r}\matrixquantity(a\\\
r)\matrixquantity(a+b-r\\\ b-r)$ (126)
$\displaystyle=(K-1)^{r}\matrixquantity(c\\\ r,a-r,b-r),$ (127)
$\displaystyle\text{with }c:=a+b-r$ (128) $\displaystyle\text{and
}\matrixquantity(x+y+z\\\ x,y,z):=\frac{(x+y+z)!}{x!y!z!}$ (129)

the multinomial coefficient. Again, note that 127 trivially reduces to 125
when $b=r$. The resulting lower order error will have order $c$, so, for this
case, we would also need to discount its affect on $\mathbf{n}_{i}(\omega)$ by
subtracting $\mathbf{n}_{i}(c)$ times $\zeta$.

###  I-C Counting permuted copies

Consider an order-$(\omega-1)$ error $E_{i_{1}}^{B}E_{i_{2}}^{B}\ldots
E_{i_{\omega-1}}^{B}$ (with $i_{1}<i_{2}<i_{3}<\ldots$), coming from
$\tilde{D}_{\omega-1}$, and the error $\hat{E}_{j}^{B}$, coming from
$\tilde{D}_{1}$. W.l.o.g., suppose $j<i_{1}$. Then, for $\tilde{D}_{\omega}$,
we will not only count the error $E_{j}^{B}E_{i_{1}}^{B}E_{i_{2}}^{B}\ldots
E_{i_{\omega-1}}^{B}$, but also that same error coming from the combination of
the errors $E_{j}^{B}E_{i_{1}}^{B}E_{i_{2}}^{B}\ldots
E_{i_{\omega-1}}^{B}\backslash E_{i_{k}}^{B}$ and $E_{i_{k}}^{B}$. In total,
we overcount each order-$\omega$ error $\omega$ times.

In general, for every order-$\omega$ error, any possible combination of
order-$a$ errors and order-$b$ errors that can generate it (with $\omega=a+b$)
will appear in the counting. Since there are

$R_{a,b}:=\matrixquantity(\omega\\\ a)=\matrixquantity(\omega\\\ b)$ (130)

ways for order-$a$ and order-$b$ errors to generate an order-$\omega$ error,
the final counting (after discounting the previous overcounting cases) should
be reduced by a factor of $R_{a,b}$.

###  I-D Full expression

In general, the erroneous errors that the decoding procedure may containing
not only repeated base errors ($k>0$), but also base errors stemming from the
same CNOT gate ($r>0$). Therefore, these two factors need to be considered
together.

Combining the analyses of the previous subsections, we conclude that, when
composing a order-$a$ error $E_{i}$ with a order-$b$ error $E_{j}$ ($a\geq
b$), we can have $k$ base errors $E_{j}$ already appearing in $E_{i}$, and $r$
base errors in $E_{j}$ sharing the same origin CNOT gate as a base error in
$E_{i}$, with $k+r\leq b$.

To count all these errors, we may look that the errors with order
$c=(a+b-2k-r)$, from which we can generate all the invalid order-$\omega$
errors. As before, the $k$ repeated base errors are chosen from those
associated with CNOT gates that are not related to a valid base error in the
compound error. There are ${\tilde{N}_{\rm CNOT}}-c$ such gates, and each one
has $K$ associated base errors.

Moreover, the from the $c$ base errors, we may consider that $a-k-r$ (resp.
$b-k-r$) correspond to the base errors in $E_{i}$ (resp. $E_{j}$) that raise
no issue, with the remaining $r$ errors corresponding to base errors stemming
from CNOT gates that also originated invalid base errors in $E_{j}$.

Grouping all three overcounting issues, we end up with

$\displaystyle\zeta_{a,b}(k,r)=K^{k}(K-1)^{r}\xi_{a,b}(k,r)$ (131)

with

$\displaystyle\xi_{a,b}(k,r)$ $\displaystyle:=\matrixquantity({\tilde{N}_{\rm
CNOT}}-c\\\ k)\matrixquantity(c\\\ r,a-k-r,b-k-r),$ (132)
$\displaystyle\text{and }c$ $\displaystyle:=a+b-2k-r,$ (133)

which generalizes 122 and 127.

The corrected count is consequently given by

$\displaystyle\mathbf{n}_{i}(\omega)=\frac{1}{R_{a,b}}\Big{[}\tilde{\mathbf{n}}_{i}(\omega)-\sum_{\begin{subarray}{c}0<k+r\leq
b\\\ k,r\geq 0\end{subarray}}\zeta_{a,b}(k,r)\mathbf{n}_{i}(c)\Big{]},$ (134)
$\displaystyle\text{with }c:=a+b-2k-r,$ (135)

as indicated in 110, with $\tilde{\mathbf{n}}_{i}(\omega)$ being the original
count from the optimized decoding process. As previously indicated, since the
estimate of the impossible errors is not exact, this formula is approximate.

##  Appendix J Alternative definitions of $\mathcal{F}_{E}$ and
$\mathcal{F}_{L}$

Instead of using the formulation described in Sections IV-A and IV-B, we may
consider an alternative formulation that, while less computationally
efficient, is conceptually more straightforward. Under this formalism, the
components $\mathtt{E}_{i}$ and $\mathtt{L}_{i}$ can be computed at once from
$e_{i}$, so there is less of an need to separate the two processes.

For a given error $E_{i}$, we compute $e_{i}$. Taking the encoding $U$, we
compute

$e_{i}^{u}:=U^{\dagger}e_{i}U.$ (136)

The _unencoded error pattern_ $e_{i}^{u}$ corresponds to the effect of $e_{i}$
on the quantum state if it were decoded. We may decompose it into

$e_{i}^{u}:=\mathtt{E}_{i}^{u}\mathtt{S}_{i}^{u}\mathtt{L}_{i}^{u},$ (137)

with

$\displaystyle\mathtt{E}_{i}^{u}$ $\displaystyle=U^{\dagger}\mathtt{E}_{i}U,$
(138) $\displaystyle\mathtt{S}_{i}^{u}$
$\displaystyle=U^{\dagger}\mathtt{S}_{i}U,$ (139)
$\displaystyle\mathtt{L}_{i}^{u}$ $\displaystyle=U^{\dagger}\mathtt{L}_{i}U.$
(140)

We may also decompose it into the Pauli string for the first $k$ data qubits
($e_{i}^{D}$) and the additional $(n-k)$ redundancy qubits ($e_{i}^{R}$),

$e_{i}^{u}=:e_{i}^{D}\otimes e_{i}^{R}.$ (141)

From 3, 4 and 5, we have that

$\displaystyle Z_{i+k}$ $\displaystyle=U^{\dagger}S_{i}U$ (142) $\displaystyle
X_{j}$ $\displaystyle=U^{\dagger}\bar{X}_{j}U$ (143) $\displaystyle Z_{j}$
$\displaystyle=U^{\dagger}\bar{Z}_{j}U.$ (144)

Therefore, decoding $e_{i}$ into $e_{i}^{u}$ cleanly separates the different
components. $\mathtt{L}_{i}^{u}$ corresponds to the components of $e_{i}^{u}$
in the first $k$ qubits. We have

$\displaystyle\mathtt{L}_{i}^{u}$ $\displaystyle:=e_{i}^{D}\otimes I_{n-k}$
(145)
$\displaystyle=\quantity(\prod_{j=1}^{k}X_{j}^{b_{j}^{X}})\quantity(\prod_{j=1}^{k}Z_{j}^{b_{j}^{Z}})$
(146) $\displaystyle\implies\mathtt{L}_{i}$ $\displaystyle=U(e_{i}^{D}\otimes
I_{n-k})U^{\dagger}$ (147)
$\displaystyle=\quantity(\prod_{j=1}^{k}{\bar{X}}_{j}^{b_{j}^{X}})\quantity(\prod_{j=1}^{k}{\bar{Z}}_{j}^{b_{j}^{Z}}),$
(148)

where $b_{j}^{X}$ and $b_{j}^{Z}$ are the $X$ and $Z$ components of
$\mathbf{e}_{i}^{D}$, respectively.

Let $e_{i}^{R,X}$ and $e_{i}^{R,Z}$ be the $X$ and $Z$ components of
$e_{i}^{R}$, respectively (where the $Y$ components have been decomposed into
$X$ and $Z$, as in 10), so that $e_{i}^{R}=e_{i}^{R,X}e_{i}^{R,Z}$
(disregarding the phase factor). We have

$\displaystyle\mathtt{E}_{i}^{u}$ $\displaystyle:=I_{k}\otimes e_{i}^{R,X}$
(149) $\displaystyle=\prod_{i=k+1}^{n}X_{i}^{b_{i-k}^{X}}$ (150)
$\displaystyle\implies\mathtt{E}_{i}$ $\displaystyle=U(I_{k}\otimes
e_{i}^{R,X})U^{\dagger}$ (151)
$\displaystyle=\prod_{i=k+1}^{n}(UX_{i}U^{\dagger})^{b_{i-k}^{X}},$ (152)

and

$\displaystyle\mathtt{S}_{i}^{u}$ $\displaystyle:=I_{k}\otimes e_{i}^{R,Z}$
(153) $\displaystyle=\prod_{i=k+1}^{n}Z_{i}^{b_{i-k}^{Z}}$ (154)
$\displaystyle\implies\mathtt{S}_{i}$ $\displaystyle=U(I_{k}\otimes
e_{i}^{R,Z})U^{\dagger}$ (155)
$\displaystyle=\prod_{i=k+1}^{n}(UZ_{i}U^{\dagger})^{b_{i-k}^{Z}}.$ (156)

where $b_{i-k}^{X}$ and $b_{i-k}^{Z}$ are the $X$ and $Z$ components of
$\mathbf{e}_{i}^{R,X}$ and $\mathbf{e}_{i}^{R,Z}$, respectively. As this
procedure is deterministic, we obtain unique components
$\mathtt{E}_{i},\mathtt{S}_{i}$, and $\mathtt{L}_{i}$ associated with the
error pattern $e_{i}$.

Regarding runtime complexity, the method presented in Section IV-A requires
just $\order{n-k}$ steps per error $E_{i}$, in order to assemble
$\mathtt{E}_{i}$ from the precomputed $Z_{h_{i}}$ and $X_{h_{i}-n}$ terms. The
method presented in Section IV-B is more involved. Computing $e_{i}^{\prime}$
requires $2n$ steps. Determining its stabilizer component $\mathtt{S}_{i}$
requires identifying the pivots in $\mathbf{e}_{i}^{\prime}$ ($\order{n}$
steps) and then multiplying the constituting stabilizers by
$\mathbf{e}_{i}^{\prime}$. As it is constituted by $\order{n-k}$ stabilizers,
and accounting for each takes at most $(2n-(n-k-1))=n+k+1$ steps, the whole
stabilizer part takes $\order{(n-k)(n+k+1)}$ steps. For the logical component,
there are $\order{2k}$ components in $\mathbf{e}_{i}^{\prime}$, and the whole
each operator takes $(2n-(n-k)-2k+1)=n-k+1$ steps, for a total of
$\order{(2k)(n+k-1)}$ steps. The full procedure requires

$\displaystyle\order{n+(n-k)(n+k+1)+(n-k+1)(2k)}$ (157)
$\displaystyle\sim\order{n^{2},k^{2}}\sim\order{n^{2}}$ (158)

steps per error $E_{i}$ to compute $\mathtt{L}_{i}$. The computation for
$N_{E}$ errors requires

$\order{N_{E}n^{2}}$ (159)

steps.

For this simpler technique, the greatest computational expense comes from
computing $e_{i}^{u}$ for each error $E_{i}$, as the remaining steps can be
precomputed and subsequently applied to all errors.

To facilitate the calculation, we may precompute the $e^{u}$ patterns
associated with all base errors, and use those to compute the pattern
$e_{i}^{u}$ for each error $E_{i}$.

From [32], simulating a stabilizer circuit (i.e. $U$) with $N$ gates takes
$\order{n^{2}N}$ steps. Since $U$ is built from $\order{n\log^{2}n}$ Clifford
gates, we have that the full precomputation associated with the base errors
scales as

$\order{{N_{\rm CNOT}}n^{3}\log^{2}n}.$ (160)

The cost of computing $e_{i}^{u}$ for each $E_{i}$ then scales as

$\order{n\omega}$ (161)

where $\omega$ is the order of the error. The full computation for $N_{E}$
errors requires

$\order{N_{E}n\omega+{N_{\rm CNOT}}n^{3}\log^{2}n}$ (162)

steps. For cases where $N_{E}\gg{N_{\rm CNOT}}$, the simpler approach may lead
to a faster implementation, while, for smaller cases, the main approach is
faster, as it doesn’t require precomputation.

##  Appendix K Analysis of numerical results

To get a good understanding of the performance of the decoding method, we
consider an equidistant range for $h$, and we sample $p$ using the expression

$p=10^{h}.$ (163)

For that reason, most of the fits in this section are performed after applying
a logarithmic transformation to both the dependent and independent variables.
That is, we prefer to work with $\log(p)$ than $p$ directly, as it is more
numerically stable.

In this section, we verify that $C(p)$ and $P_{\rm failure}$ scale as

$\displaystyle C(p)$ $\displaystyle\simeq e^{-\gamma{N_{\rm CNOT}}p}$ (164)
$\displaystyle\simeq 1-\gamma{N_{\rm CNOT}}p$ (165) $\displaystyle P_{\rm
failure}(p)$ $\displaystyle\simeq 1-e^{-\mu p^{\eta}},\text{ for
}\eta\in\mathbb{N}$ (166) $\displaystyle\simeq\mu p^{\eta},$ (167)

for $p\ll 1$. $\mu$ and $\gamma$ are positive real parameters, and $\eta$ is
the lowest order that the code cannot fully correct. We analyze these
expressions separately in the next subsections.

###  K-A Escaped errors

We start by considering $P_{u}(p,1)$. For the noise model in Section II, we
expect that the probability of finding escaped errors will be given by

$\displaystyle P_{u}(p,1)$ $\displaystyle\simeq\sum_{i=1}^{N_{\rm
CNOT}}\matrixquantity({N_{\rm CNOT}}\\\ i)(\gamma p)^{i}(1-\gamma p)^{{N_{\rm
CNOT}}-i}$ (168) $\displaystyle=\sum_{i=1}^{N_{\rm
CNOT}}(-1)^{i+1}\matrixquantity({N_{\rm CNOT}}\\\ i)(\gamma p)^{i}$ (169)
$\displaystyle=1-\sum_{i=0}^{N_{\rm CNOT}}\matrixquantity({N_{\rm CNOT}}\\\
i)(-\gamma p)^{i},$ (170)

where $\gamma$ reflects the fraction of errors that can escape. For $p\ll 1$,
the lower order terms dominate, so we may use the approximation

$\matrixquantity({N_{\rm CNOT}}\\\ i)\simeq\frac{{N_{\rm
CNOT}}^{i}}{i!},\text{ for }{N_{\rm CNOT}}\gg i,$ (171)

and we have

$\displaystyle P_{u}(p,1)$ $\displaystyle\simeq 1-\sum_{i=0}^{N_{\rm
CNOT}}\frac{(-{N_{\rm CNOT}}\gamma p)^{i}}{i!}$ (172) $\displaystyle\simeq
1-\sum_{i=0}^{\infty}\frac{(-{N_{\rm CNOT}}\gamma p)^{i}}{i!}$ (173)
$\displaystyle=1-e^{-\gamma{N_{\rm CNOT}}p}.$ (174)

Given 35 and 42, we end up with 164,

$C(p)\simeq e^{-\gamma{N_{\rm CNOT}}p},$ (175)

where $\gamma$ is an unknown parameter. Since we are considering $p\ll 1$,
this expression may be further simplified into

$C(p)\simeq 1-\gamma{N_{\rm CNOT}}p.$ (176)

In order to perform a fit, we consider a more general version of this
expression, given by

$C(p)\simeq\exp(-\gamma{N_{\rm CNOT}}p^{\eta_{C}}),$ (177)

and we fit the function

$\displaystyle\log_{10}(-\log(C(p)))$
$\displaystyle=\eta_{C}\log_{10}(p)+\log_{10}(\gamma{N_{\rm CNOT}})$ (178)
$\displaystyle\implies\log_{10}(-b)$
$\displaystyle=\eta_{C}\log_{10}(p)+\beta,$ (179)

where $\beta=\log_{10}(\gamma{N_{\rm CNOT}})$ and $b$ stems from 45. We use
$\log_{10}$ to keep the figures more legible.

Fig. 9: Fit of the various parameters, averaged over 50 random codes for each
$n$.

We may now study the behavior of $\eta_{C}$ and $\beta$ for different $n$. See
Fig. 9 for the results. As expected, we observe that $\eta_{C}\simeq 1$,
regardless of $n$.

From Appendix C, we have that ${N_{\rm CNOT}}\sim\order{n^{2}}$. If we assume
that $\gamma\sim\order{\text{poly}(n)}$, then $\beta$ should scale as

$\displaystyle\beta$ $\displaystyle=b_{1}\log(n-n_{\beta})+b_{2}.$ (180)

with $\eta_{0}=1$. We assume this expression for its fit. The fitted
parameters are given in Table IV.

TABLE IV: Fitted parameters for $\beta$. Variable | Value
---|---
$b_{1}$ | $0.4494$
$n_{\beta}$ | $3.6453$
$b_{2}$ | $0.7505$

We may alternatively write $\beta$ as

$\beta\simeq\log_{10}(5.630\cdot(n-3.6453)^{1.035})$ (185)

Given the dependence between $\beta$ and ${N_{\rm CNOT}}$, we may conclude
that

$\gamma{N_{\rm CNOT}}\sim\order{n^{1.035}}\simeq\order{n},$ (186)

despite the actual ${N_{\rm CNOT}}$ count scaling with $\order{n^{2}}$. These
results are in line with the expectations from the theoretical analysis of
Appendix C, indicating that we may observe a visible ${p_{\rm threshold}}$.

###  K-B Direct $P_{\rm failure}$ extrapolation

We may apply a similar procedure to $P_{\rm failure}$. We empirically observe
that 166 holds. However, unlike the previous section, it is no longer the case
that $\eta_{C}\simeq 1$.

If a code is able to correct all errors of order $\omega<\eta$, then we expect
$P_{\rm failure}$ to be given by

$\displaystyle P_{\rm failure}$ $\displaystyle=\sum_{i=1}^{N_{\rm
CNOT}}f_{i}(p,{N_{\rm CNOT}})\matrixquantity({N_{\rm CNOT}}\\\
i)p^{i}(1-p)^{{N_{\rm CNOT}}-i}$ (187)
$\displaystyle\simeq\sum_{i=\eta}^{N_{\rm
CNOT}}\tilde{f}_{i}\matrixquantity({N_{\rm CNOT}}\\\ i)p^{i}(1-p)^{{N_{\rm
CNOT}}-i},\text{ for }p\ll 1$ (188)
$\displaystyle\simeq\tilde{f}_{\eta}\matrixquantity({N_{\rm CNOT}}\\\
\eta)p^{\eta}(1-p)^{{N_{\rm CNOT}}-\eta},\text{ for }p\ll 1,$ (189)
$\displaystyle=\mu p^{\eta},\text{ for }p\ll 1.$ (190)

for some unknown $\mu$, where $\tilde{f}_{i}$ is an approximation of
$f_{i}(p,{N_{\rm CNOT}})$, which is unknown function. In the approximation in
188, we consider $\tilde{f}_{i}$ as a scalar.

In order to perform a fit, we consider an equivalent version of this
expression for $p\ll 1$, given by

$P_{\rm failure}(p)\simeq 1-\exp(-\mu p^{\eta}),$ (191)

and we fit the function

$\displaystyle\log_{10}(-\log(1-P_{\rm failure}))$
$\displaystyle=\eta\log_{10}(p)+\log_{10}(\mu)$ (192)
$\displaystyle=\eta\log_{10}(p)+\alpha,$ (193)

where $\alpha=\log_{10}(\mu)$. As before, we use $\log_{10}$ to keep the
figures more legible. See Fig. 10 for an example.

Fig. 10: Fit of 179, for a random example with $n=20$. We fit only using
values below $10^{-6}$, where it is safe to assume $p\ll 1$. As expected, the
fit worsens for higher $p$.

Fig. 11: Plot of $\eta$ and $\alpha$. We fit a linear function to $\alpha$ for
the higher $n$ values.

We may now study the behavior of $\eta$ and $\alpha$ for different $n$. See
Fig. 11 for the results. In this case, we have different $\eta$ values, and
the values cluster around integers. Since the $n$ values we tested are
relatively low, we only observe $\eta$ equal to either 1 or 2. As these cases
display notably different behavior, we separate their data before fitting.

As before, we fit $\eta$ to an expression of the form

$\displaystyle\eta$
$\displaystyle=\eta_{0}+d_{1}\log(1+\exp(d_{2}\cdot(n-n_{P}))).$ (194)

We empirically observe that the $\alpha$ variable is better fitted by a simple
linear expression

$\alpha=a_{1}n+a_{2}.$ (195)

The fitted parameters are given in Table V.

TABLE V: Fitted parameters for $\alpha$. Variable | $\eta_{0}=1$ | $\eta_{0}=2$
---|---|---
$a_{1}$ | $-0.0074$ | $0.0838$
$a_{2}$ | $-0.8170$ | $2.8530$

We may also have a look at the probability of having different $\eta$ values.
The empirical results can be seen in Figs. 12 and VI. We observe that, for low
$n$ values, the fraction of random codes with $\eta=1$ and $\eta=2$ is roughly
constant, since the code’s capabilities are not large enough to generally
correct all $\omega=1$ errors. As $n$ increases, the probability that the code
corrects all order-1 errors also increases, and we so the fraction of $\eta=2$
cases increases. Its behavior follows a sigmoid-like function, of the form

$s_{1}\quantity(\frac{1}{1+e^{-s_{2}(n-n_{f})}}-\frac{1}{2})+s_{3}.$ (199)

The errorbars indicate the standard deviation, which stems from the finite
number (48) of samples taken for each $n$ value. Also, note the symmetry in
the parameters in Table VI, reflecting the fact that the fractions must add up
to one.

Fig. 12: Fraction of the simulations with different $\eta_{0}$ values. TABLE VI: Fitted parameters. Variable | $\eta_{0}=1$ | $\eta_{0}=2$
---|---|---
$s_{1}$ | $-0.7206$ | $0.7206$
$s_{2}$ | $0.8665$ | $0.8665$
$n_{f}$ | $16.5506$ | $16.5506$
$s_{3}$ | $0.4673$ | $0.5327$

For very low $n\leq 12$, we observe that about $20\%$ of the codes have
$\eta=2$. On further inspection, their seemingly high performance does not
stem from strong correction capabilities, but from the fact that, due to
random chance, the stabilizers of these codes have relatively low weight,
leading to a very low number of CNOT gates in the syndrome extraction circuit,
and consequently fewer errors needed to consider. In a more complex setting
where there are additional sources of error, we would expect these codes in
particular to perform poorly.

###  K-C Extrapolating behavior for larger $n$

We may take the results above and use them to extrapolate the performance for
larger $n$ values. We also incorporate the uncertainty observed in the
numerical data by using the standard deviation observed for the sampled $n$ to
estimate the deviation for larger $n$.

## Acknowledgments

All authors are thankful to Dr. Bill Munro (NTT Basic Research Labs, Japan)
and Prof. Kae Nemoto (National Institute of Informatics, Japan) for insightful
discussions about QGRAND. Francisco Monteiro is grateful to Prof. Frank
Kschischang (University of Toronto) for discussions on noise-guessing
decoding, and to Dr. Ioannis Chatzigeorgiou (Lancaster University) for
discussions on random linear codes and noise-guessing decoding.

## References

  * [1] K. R. Duffy, J. Li, and M. Médard, “Capacity-achieving guessing random additive noise decoding,” _IEEE Transactions on Information Theory_ , vol. 65, no. 7, pp. 4023–4040, Jul. 2019.
  * [2] D. Cruz, F. A. Monteiro, and B. C. Coutinho, “Quantum error correction via noise guessing decoding,” _IEEE Access_ , vol. 11, pp. 19 446 – 119 461, oct 2023.
  * [3] W. An, M. Médard, and K. R. Duffy, “Keep the bursts and ditch the interleavers,” _IEEE Transactions on Communications_ , vol. 70, no. 6, pp. 3655–3667, Jun. 2022.
  * [4] M. Shirvanimoghaddam, M. S. Mohammadi, R. Abbas, A. Minja, C. Yue, B. Matuz, G. Han, Z. Lin, W. Liu, Y. Li, S. Johnson, and B. Vucetic, “Short block-length codes for ultra-reliable low latency communications,” _IEEE Communications Magazine_ , vol. 57, no. 2, pp. 130–137, Feb. 2019.
  * [5] R. Alberto and F. A. Monteiro, “Downlink MIMO-NOMA With and Without CSI: A short survey and comparison,” in _12th International Symposium on Communication Systems, Networks and Digital Signal Processing (CSNDSP)_ , Porto, Portugal, Jun. 2020, pp. 1–6.
  * [6] F. A. Monteiro and I. J. Wassell, “Recovery of a lattice generator matrix from its Gram matrix for feedback and precoding in MIMO,” in _4th International Symposium on Communications, Control and Signal Processing (ISCCSP)_ , Limassol, Cyprus, 2010, pp. 1–6.
  * [7] M. Chiani and L. Valentini, “Short codes for quantum channels with one prevalent pauli error type,” _IEEE Journal on Selected Areas in Information Theory_ , vol. 1, no. 2, pp. 480–486, Aug. 2020.
  * [8] P. W. Shor, “Scheme for reducing decoherence in quantum computer memory,” _Physical Review A_ , vol. 52, pp. R2493–R2496, 1995.
  * [9] A. M. Steane, “Error correcting codes in quantum theory,” _Physical Review Letters_ , vol. 77, pp. 793–797, 1996.
  * [10] A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, “Surface codes: Towards practical large-scale quantum computation,” _Physical Review A_ , vol. 86, no. 3, p. 032324, Sep. 2012, arXiv:1208.0928 [quant-ph]. [Online]. Available: http://arxiv.org/abs/1208.0928
  * [11] A. R. Calderbank and P. W. Shor, “Good quantum error-correcting codes exist,” _Physical Review A_ , vol. 54, no. 2, pp. 1098–1105, Aug. 1996.
  * [12] D. Gottesman, “Stabilizer codes and quantum error correction,” Ph.D. dissertation, California Institute of Technology, May 1997.
  * [13] D. Chandra, Z. B. Kaykac Egilmez, Y. Xiong, S. X. Ng, R. G. Maunder, and L. Hanzo, “Universal decoding of quantum stabilizer codes via classical guesswork,” _IEEE Access_ , vol. 11, pp. 19 059–19 072, 2023.
  * [14] A. Roque, D. Cruz, F. A. Monteiro, and B. C. Coutinho, “Efficient entanglement purification based on noise guessing decoding,” _arXiv:2310.19914 [quant-ph] [cs.IT]_ , pp. 1–16, 2023. [Online]. Available: https://arxiv.org/abs/2310.19914
  * [15] S. Santos, F. A. Monteiro, B. C. Coutinho, and Y. Omar, “Shortest path finding in quantum networks with quasi-linear complexity,” _IEEE Access_ , vol. 11, pp. 7180–7194, jan 2023.
  * [16] L. Bugalho, B. C. Coutinho, F. A. Monteiro, and Y. Omar, “Distributing multipartite entanglement over noisy quantum networks,” _Quantum_ , vol. 7, p. 920, 2 2023.
  * [17] B. C. Coutinho, W. J. Munro, K. Nemoto, and Y. Omar, “Robustness of noisy quantum networks,” _Communications Physics_ , vol. 5, no. 1, pp. 1–9, Apr. 2022.
  * [18] A.-K. Wu, L. Tian, B. C. Coutinho, Y. Omar, and Y.-Y. Liu, “Structural vulnerability of quantum networks,” _Phys. Rev. A_ , vol. 101, p. 052315, May 2020. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.101.052315
  * [19] G. Q. AI, “Suppressing quantum errors by scaling a surface code logical qubit,” _Nature_ , vol. 614, no. 7949, pp. 676–681, Feb. 2023.
  * [20] D. F. Locher, L. Cardarelli, and M. Müller, “Quantum Error Correction with Quantum Autoencoders,” _Quantum_ , vol. 7, p. 942, Mar. 2023.
  * [21] J. Roffe, “Quantum error correction: an introductory guide,” _Contemporary Physics_ , vol. 60, no. 3, pp. 226–245, Jul. 2019.
  * [22] Z. Babar, D. Chandra, H. V. Nguyen, P. Botsinis, D. Alanis, S. X. Ng, and L. Hanzo, “Duality of quantum and classical error correction codes: Design principles and examples,” _IEEE Communications Surveys & Tutorials_, vol. 21, no. 1, pp. 970–1010, Firstquarter 2019.
  * [23] W. Brown and O. Fawzi, “Short random circuits define good quantum error correcting codes,” in _Proc. of IEEE Inter. Symp. on Information Theory (ISIT)_ , Istanbul, Turkey, Jul. 2013, pp. 346–350.
  * [24] A. K. Fedorov, N. Gisin, S. M. Beloussov, and A. I. Lvovsky, “Quantum computing at the quantum advantage threshold: A down-to-business review,” Mar. 2022.
  * [25] M. J. Gullans, S. Krastanov, D. A. Huse, L. Jiang, and S. T. Flammia, “Quantum coding with low-depth random circuits,” _Physical Review X_ , vol. 11, no. 3, p. 031066, Sep. 2021.
  * [26] G. Smith and J. A. Smolin, “Degenerate quantum codes for pauli channels,” _Phys. Rev. Lett._ , vol. 98, p. 030501, Jan 2007. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.98.030501
  * [27] E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, “Topological quantum memory,” _Journal of Mathematical Physics_ , vol. 43, no. 9, pp. 4452–4505, Sep. 2002, arXiv:quant-ph/0110143. [Online]. Available: http://arxiv.org/abs/quant-ph/0110143
  * [28] I. B. Djordjevic, _Quantum Information Processing, Quantum Computing, and Quantum Error Correction: An Engineering Approach_ , 2nd ed. Oxford, UK: Academic Press, Mar. 2021.
  * [29] P. Iyer and D. Poulin, “Hardness of Decoding Quantum Stabilizer Codes,” _IEEE Transactions on Information Theory_ , vol. 61, no. 9, pp. 5209–5223, Sep. 2015.
  * [30] M.-H. Hsieh and F. Le Gall, “NP-hardness of decoding quantum error-correction codes,” _Phys. Rev. A_ , vol. 83, p. 052331, May 2011. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.83.052331
  * [31] K.-Y. Kuo and C.-C. Lu, “On the hardness of decoding quantum stabilizer codes under the depolarizing channel,” in _2012 International Symposium on Information Theory and its Applications_ , 2012, pp. 208–211.
  * [32] S. Aaronson and D. Gottesman, “Improved simulation of stabilizer circuits,” _Physical Review A_ , vol. 70, no. 5, p. 052328, Nov. 2004.

|  Diogo Cruz obtained his BSc and MSc degrees in Physics Engineering from
Instituto Superior Técnico (IST), University of Lisbon, Portugal. He is
currently a PhD student in Physics, also at IST, and is a researcher at
Instituto de Telecomunicações, Lisbon, Portugal. He was a Calouste Gulbenkian
Scholar in 2018/2019.
---|---
|  Francisco A. Monteiro (M’07) is Associate Professor in the Dep. of
Information Science and Technology at Iscte - University Institute of Lisbon,
and a researcher at Instituto de Telecomunicações, Lisbon, Portugal. He holds
a PhD from the University of Cambridge, UK, and the Licenciatura and MSc
degrees in Electrical and Computer Engineering from IST, University of Lisbon,
where he also became a Teaching Assistant. He held visiting research positions
at the Universities of Toronto (Canada), Lancaster (UK), Oulu (Finland), and
Pompeu Fabra (Barcelona, Spain). He has won two best paper prizes awards at
IEEE conferences (2004 and 2007), a Young Engineer Prize (3rd place) from the
Portuguese Engineers Institution (Ordem dos Engenheiros) in 2002, and for two
years in a row was a recipient of Exemplary Reviewer Awards from the IEEE
Wireless Communications Letters (in 2014 and in 2015). He co-edited the book
“MIMO Processing for 4G and Beyond: Fundamentals and Evolution”, published by
CRC Press in 2014. In 2016 he was the Lead Guest Editor of a special issue on
Network Coding of the EURASIP Journal on Advances in Signal Processing. He was
a general chair of ISWCS 2018 - The 15th International Symposium on Wireless
Communication Systems, an IEEE major conference in wireless communications.
---|---
|  André Roque obtained both his BSc. and MSc. degrees in Applied Mathematics
and Computation, from Instituto Superior Técnico (IST, University of Lisbon),
Portugal in 2023. Since 2023 he is with the Physics of Information and Quantum
Technologies Group, at Instituto de Telecomunicações as a Research Assistant.
---|---
|  Bruno C. Coutinho obtained his PhD in Physics from Northeastern University,
USA, in 2016, and both his BSc. and MSc. in Physics, from the University of
Aveiro, Portugal, in 2009 and 2011, respectively. Since 2017 he is with the
Physics of Information and Quantum Technologies Group, at Instituto de
Telecomunicações, initially as a postdoc and later as a Research Fellow.
---|---