traditional SPA decoder would yield the lowest weight operator from the coset
$\mathbf{T}_{4}\star\mathcal{\mkern
1.5mu\overline{\mkern-1.5muZ\mkern-1.5mu}\mkern 1.5mu(\mkern
1.5mu\overline{\mkern-1.5muS\mkern-1.5mu}\mkern 1.5mu)}$ which is either the
error operator $ZII$ belonging to coset
$\mathbf{T}_{4}\star\mathbf{L}_{1}\star\mathcal{\mkern
1.5mu\overline{\mkern-1.5muS\mkern-1.5mu}\mkern 1.5mu}$ or the error operator
$IZI$ belonging to coset
$\mathbf{T}_{4}\star\mathbf{L}_{4}\star\mathcal{\mkern
1.5mu\overline{\mkern-1.5muS\mkern-1.5mu}\mkern 1.5mu}$. Notice, as shown in
Figure 4.8b, that the probability of the coset
$\mathbf{T}_{4}\star\mathbf{L}_{1}\star\mathcal{\mkern
1.5mu\overline{\mkern-1.5muS\mkern-1.5mu}\mkern 1.5mu}$ is identical to that
of the coset $\mathbf{T}_{4}\star\mathbf{L}_{4}\star\mathcal{\mkern
1.5mu\overline{\mkern-1.5muS\mkern-1.5mu}\mkern 1.5mu}$. As in the previous
case, a degenerate decoder capable of considering the partition of the
effective centralizer cosets into stabilizer cosets would not outperform the
traditional SPA decoder in this scenario. Note that, for both of the previous
examples, this happens because the error sequence with highest probability is
in the stabilizer coset with highest probability. As shown in (4.27),
regardless of whether the estimated error sequence and the channel error
match, the traditional SPA decoder will correctly solve the decoding problem
if the estimated error sequence is in the same stabilizer coset as the channel
error.

To provide an example in which the degenerate decoder clearly outperforms the
traditional SPA decoder, let us now consider transmission of encoded quantum
states over a Pauli channel with $p_{x}=0.26$, $p_{y}=0.28$, and $p_{z}=0.15$.
Figures 4.9a and 4.9b portray the individual probabilities of each of the
operators shown in Figure 4.7 and the probabilities of each stabilizer coset,
respectively, after transmitting over the Pauli channel with $p_{x}=0.26$,
$p_{y}=0.28$, and $p_{z}=0.15$. In this case, there are multiple scenarios in
which the optimal (degenerate) QLDPC decoder would outperform the traditional
SPA decoder. Let us discuss some of them.

(a)

(b)

Figure 4.9: (a) (a) Probability of the Pauli operators that are shown in
Figure 4.7 when a Pauli channel with parameters $p_{x}=0.26$, $p_{y}=0.28$,
and $p_{z}=0.15$ is considered. The darker shaded rectangles denote the error
operators from each centralizer coset that could be obtained by the classical
SPA decoder of (4.24). (b) Probability of each stabilizer coset considered in
the partition $\mathcal{\mkern 1.5mu\overline{\mkern-1.5muG\mkern-1.5mu}\mkern
1.5mu}_{3}$ shown in Figure 4.7 when a Pauli channel with parameters
$p_{x}=0.26$, $p_{y}=0.28$, and $p_{z}=0.15$ is considered. The darker shaded
rectangles denote the stabilizer cosets with the highest probability within
each effective centralizer coset. Notice that for syndrome $\mathbf{w}_{1}$,
the result produced by the classical SPA decoder does not belong to the
stabilizer coset that has the highest probability, and thus classical decoding
underperforms when compared to optimal quantum (degenerate) decoding.

Assume, as previously, that we have transmitted a quantum codeword over this
channel and that an error $\mathbf{E}_{2}\in\mathbf{T}_{1}\star\mathcal{\mkern
1.5mu\overline{\mkern-1.5muZ\mkern-1.5mu}\mkern 1.5mu(\mkern
1.5mu\overline{\mkern-1.5muS\mkern-1.5mu}\mkern 1.5mu)}$ has been introduced
by the Pauli channel, which results in the syndrome measurement yielding
$\mathbf{w}_{1}=[0\ 0]$. A traditional SPA decoder would be capable of
determining that $\mathbf{T}(\mathbf{E}_{2})=\mathbf{T}_{1}=III$, and would
choose the error operator contained in the effective centralizer coset
$\mathbf{T}_{1}\star\mathcal{\mkern
1.5mu\overline{\mkern-1.5muZ\mkern-1.5mu}\mkern 1.5mu(\mkern
1.5mu\overline{\mkern-1.5muS\mkern-1.5mu}\mkern 1.5mu)}$ that has the highest
probability of occurring, i.e., $\hat{\mathbf{E}}_{2}^{\text{SPA}}=III$ (see
Figure 4.9a). However, Figure 4.9b shows that the probability of the
stabilizer coset $(\mathbf{T}_{1}\star\mathbf{L}_{1})\star\mathcal{\mkern
1.5mu\overline{\mkern-1.5muS\mkern-1.5mu}\mkern 1.5mu}$, which contains the
most likely operator, $\hat{\mathbf{E}}_{2}^{\text{SPA}}=III$, is lower than
the probability of the stabilizer coset
$(\mathbf{T}_{1}\star\mathbf{L}_{3})\star\mathcal{\mkern
1.5mu\overline{\mkern-1.5muS\mkern-1.5mu}\mkern 1.5mu}$. This means that
producing an estimate
$\hat{\mathbf{E}}_{2}\in(\mathbf{T}_{1}\star\mathbf{L}_{3})\star\mathcal{\mkern
1.5mu\overline{\mkern-1.5muS\mkern-1.5mu}\mkern 1.5mu}$ will result in better
performance than choosing the most likely error operator in
$\mathbf{T}_{1}\star\mathcal{\mkern
1.5mu\overline{\mkern-1.5muZ\mkern-1.5mu}\mkern 1.5mu(\mkern
1.5mu\overline{\mkern-1.5muS\mkern-1.5mu}\mkern 1.5mu)}$. Such an estimate can
only be produced by the decoder given in (4.26), which is capable of
considering the partition of the effective centralizer into cosets of the
stabilizer. Therefore, in this instance, the degenerate decoder would
outperform the traditional SPA decoder. This would also occur if an error
$\mathbf{E}_{3}\in\mathbf{T}_{2}\star\mathcal{\mkern
1.5mu\overline{\mkern-1.5muZ\mkern-1.5mu}\mkern 1.5mu(\mkern
1.5mu\overline{\mkern-1.5muS\mkern-1.5mu}\mkern 1.5mu)}$ were to take place.
By comparing Figures 4.9a and 4.9b, we can see how, in this scenario, the most
likely error operator does not belong to the most likely stabilizer coset.

In the case that $\mathbf{E}\in\mathbf{T}_{3}\star\mathcal{\mkern
1.5mu\overline{\mkern-1.5muZ\mkern-1.5mu}\mkern 1.5mu(\mkern
1.5mu\overline{\mkern-1.5muS\mkern-1.5mu}\mkern 1.5mu)}$ or
$\mathbf{E}\in\mathbf{T}_{4}\star\mathcal{\mkern
1.5mu\overline{\mkern-1.5muZ\mkern-1.5mu}\mkern 1.5mu(\mkern
1.5mu\overline{\mkern-1.5muS\mkern-1.5mu}\mkern 1.5mu)}$, there are multiple
error operators that have the highest probability to occur, but only one of
them belongs to the most likely stabilizer coset. This implies that, although
performance of the traditional SPA decoder would be better than in the two
previous cases, it would sometimes produce suboptimal estimates that would not
belong to the most likely stabilizer coset. Therefore, in instances such as
this one, the optimal degenerate decoder would also outperform traditional SPA
decoding methods.

Lastly, it is important to mention that when a traditional SPA-based decoder
is used to estimate operators from $\mathcal{\mkern
1.5mu\overline{\mkern-1.5muG\mkern-1.5mu}\mkern 1.5mu}_{N}$ and it fails to
find the correct logical component of the error, this goes unnoticed. Recall
that although the effect of logical operators on the codeword is non-trivial,
their actions preserve the codespace. Based on this fact, it is easy to see
how these undetected decoding errors can quickly become a significant nuisance
when using stabilizer codes with a large number of stabilizer elements. As
mentioned earlier, this is a common occurrence when operating with QLDPC codes
that utilize a large number of qubits, as they may sometimes have many low
weight operators spread out across their stabilizer cosets. In such scenarios,
hefty performance prices may potentially be paid in consequence of employing a
suboptimal decoder based on traditional SPA decoding.

###  4.4 Chapter Summary

The quantum phenomenon known as degeneracy should theoretically improve the
performance of quantum codes. Unfortunately, degeneracy can end up sabotaging
the performance of sparse quantum codes because its existence is neglected in
the decoding process. In this chapter we have provided a broad overview of the
role this phenomenon plays in the realm of quantum error correction and, more
specifically, in the field of QLDPC codes. We began by introducing a group
theoretical explanation of the most relevant concepts in the field of quantum
error correction. Following this, we examined the differences between the
classical decoding problem and its quantum counterpart. Despite the intricate
similarities between classical and quantum decoders, the coset partition of
the $N$-fold Pauli space in the context of stabilizer codes reveals the higher
complexity of the quantum decoding task. Based on this discussion, we were
later able to show why applying the classical decoding algorithm for sparse
codes to the quantum problem is suboptimal. Then, we provided a detailed
explanation regarding the origin of degeneracy and how it may have detrimental
effects on traditional SPA-based decoders. We finished with an example that
serves to facilitate the comprehension of the topics discussed throughout the
chapter.

##  CHAPTER 5 Detecting Degeneracy and Improved Decoding Strategies

> “Our need will be the real creator”
>
> Plato.

In the previous chapter we analyzed the phenomenon of degeneracy through the
lens of group theory. We introduced the coset structure of stabilizer codes
and showed how degeneracy is responsible for the existence of error
equivalence classes (stabilizer cosets) whose individual elements act
identically on the transmitted information (encoded quantum states). Following
this, we presented how, when using decoding based on the QMLD rule, different
decoding scenarios can be encountered. We referred to these scenarios as end-
to-end errors, and showed how they represent particular instances that must be
distinguished in order to both assess and improve the performance of
stabilizer codes. For example, it is necessary to differentiate between end-
to-end degenerate errors and end-to-end identical syndrome errors, since the
former type of end-to-end error has no impact on encoded quantum states but
the latter one does (it acts non-trivially on the codespace). This is
especially relevant when studying sparse quantum codes, whose degenerate
nature will more than likely increase the frequency with which degenerate
errors occur [16, 55, 56, 67, 68, 69, 70, 71, 98].

In this chapter, we employ the group theoretic framework presented in Chapter
4 to derive a strategy capable of accurately assessing the impact of
degeneracy on the performance of sparse quantum codes. We also explain another
method that has been used in [151, 152, 153, 154] to do so. Then, we use our
methodology to show how sparse quantum codes should always be assessed using a
metric known as the logical error rate. We back our claims up by using our
strategy to analyze the frequency with which different types of errors occur
when using sparse quantum codes. Finally, we provide insight on how the design
and decoding of these codes can be improved, and we discuss the most relevant
advancements that have appeared in the literature [18, 20, 55, 135, 149, 151,
152, 153, 155].

###  5.1 Performance metrics

Despite its theoretical performance benefits, limited research exists on how
to quantify the true impact that degeneracy has on QLDPC codes. This has
resulted in the performance of sparse quantum codes being assessed differently
throughout the literature; while some research considers the effects of
degeneracy by computing a metric known as the logical error rate [55, 135,
151, 152, 153, 154, 156], other works employ the classical strategy of
computing the physical error rate [20, 21, 22, 23, 149, 157], a metric which
provides an upper bound on the performance of these codes. Let us analyze the
differences between the two.

####  5.1.1 Physical and Logical Error rate

The manifestation of the degeneracy phenomenon in the realm of quantum error
correction makes it impossible to accurately predict the performance of QEC
codes with methods that disregard its presence. The more degenerate the code
family that is being studied, the larger the discrepancy between results
computed based on degeneracy-ignoring metrics and the true performance of
these codes will be. Thus, in the paradigm of sparse quantum codes appropriate
performance assessment is of paramount importance. As was mentioned in the
previous chapter, this requires a method that can distinguish between the
different types of end-to-end errors. For reference, the characteristics of
these end-to-end errors are summarized in table LABEL:errors (see section
4.3.2 for a more complete discussion on end-to-end errors). Fortunately, a
metric capable of telling different end-to-end errors apart already exists. It
is known as the logical error rate and it has been widely employed to assess
the performance of various other families of QEC codes such as QTCs and
quantum topological codes [68, 29, 72, 73, 74]. Generally, the decoders used
in QTC or topological schemes are capable of producing estimates of the
stabilizer coset representatives (the logical operators) of the channel
errors, hence these decoders “inherently” compute the logical error rate. In
contrast, the classical decoding algorithms [48, 47] used to decode QLDPC
codes by solving the QMLD rule (4.24) are unable to produce estimates of
stabilizer coset representatives, and so their logical error rate must be
computed differently.

Table 5.1: Characteristics of the different types of end-to-end errors that can arise when using stabilizer codes. The hat notation is used to represent estimations made by the decoder, i.e., $\hat{\mathbf{w}}$, $\hat{\mathbf{E}}$, $\mathbf{\hat{T}}_{i}$, and $\mathbf{\hat{L}}_{j}$ represent the estimated syndrome, estimated error sequence, centralizer coset representative of the estimated error sequence and stabilizer coset representative of the estimated error sequence, respectively.  Type of | Defining | Outcome | Outcome
---|---|---|---
error | Characteristics | (Physical) | (Logical)
End-to-end | $\hat{\mathbf{w}}\neq\mathbf{w}$ |  |
error with | $\mathbf{\hat{T}}_{i}\neq\mathbf{T}_{i}$ | Failure | Failure
different syndrome | $\hat{\mathbf{E}}\neq\mathbf{E}$ |  |
End-to-end | $\hat{\mathbf{w}}=\mathbf{w}$ |  |
identical |  $\mathbf{\hat{T}}_{i}=\mathbf{T}_{i}$ and $\mathbf{\hat{L}}_{j}\neq\mathbf{L}_{j}$ | Failure | Failure
syndrome error | $\hat{\mathbf{E}}\neq\mathbf{E}$ |  |
End-to-end | $\hat{\mathbf{w}}=\mathbf{w}$ |  |
degenerate |  $\mathbf{\hat{T}}_{i}=\mathbf{T}_{i}$ and $\mathbf{\hat{L}}_{j}=\mathbf{L}_{j}$ | Failure | Success
error | $\hat{\mathbf{E}}\neq\mathbf{E}$ |  |

With our knowledge regarding the coset structure of sparse quantum codes,
intuition would point towards calculating the logical error rate by finding
and comparing the stabilizer cosets of the estimated error sequences and the
stabilizer cosets of the channel errors. Unfortunately, the task of computing
stabilizer cosets has been shown to be computationally hard [56, 70, 149],
which is the reason why the performance of some sparse quantum codes [21, 22,
20, 23, 157] and some improved decoding strategies [149] has been assessed
based on the physical error rate. This metric is computed by comparing the
error sequence estimated by the decoder, $\hat{\mathbf{E}}\in\mathcal{\mkern
1.5mu\overline{\mkern-1.5muG\mkern-1.5mu}\mkern 1.5mu}_{N}$, to the channel
error, $\mathbf{E}\in\mathcal{\mkern
1.5mu\overline{\mkern-1.5muG\mkern-1.5mu}\mkern 1.5mu}_{N}$. Essentially, if
the estimation matches the channel error, the decoder has been successful, and
if not, a decoding failure has occurred. Note, however, that because this
metric ignores the degenerate nature of stabilizer codes, the physical error
rate overestimates the number of decoding failures and actually represents an
upper bound on the performance of stabilizer codes.

Despite the use of the physical error rate in some works, other literature has
successfully computed the logical error rate of specific sparse quantum codes
[55, 135, 151, 152, 153, 154, 156]. These works succeed in computing the
logical error rate because they do not approach the issue from the perspective
of stabilizer cosets. Instead, in most of these works [55, 151, 152, 153,
154], they use Gaussian elimination to obtain the parity check matrix of the
code in what is known as standard form [16, 158, 159], and then use it to
extract a basis for the encoded Pauli operators of the corresponding codes.
Then, they employ this basis to differentiate between different types of end-
to-end errors. Additionally, other research [135] employs a different, albeit
much more computationally demanding, method to compute the logical error rate.
These strategies and concepts are explained in what follows.

##### Undetected classical errors

Before studying how the logical error rate can be computed, it should be
mentioned that the concept of undetected errors is not exclusive to the
quantum paradigm. In fact, even though degeneracy does not exist in the
classical coding realm, undetected or logical errors in classical LDPC codes
and classical turbo codes have previously been studied. This idea was
introduced by the early work of MacKay et al. [112], where a classical
undetected error is defined as a decoding estimate that is not equal to the
original error sequence and that is produced when the decoder exits before the
maximum number of decoding iterations (it produces a valid syndrome). More
explicitly, a classical undetected error occurs when the estimate of the
channel error is not equal to the real error but the estimated syndrome and
the measured syndrome match. In their analysis of classical LDPC codes, MacKay
et al. showed that all of the decoding mistakes they encountered were detected
errors (classical undetected errors were only observed in turbo codes). This
was also shown in [153] for a slightly different decoding algorithm. Similar
outcomes were observed in the quantum paradigm for the failed recoveries of
the modified decoding strategies of [55, 149]. The techniques of [55, 149]
serve to improve standard SPA decoding of quantum codes by post-processing the
initial error estimates and producing new estimates of the channel error. If
these new estimates do not revert the channel error, then they are referred to
as failed recoveries or failed error corrections. In [55], all of the failed
error corrections were shown to be end-to-end errors with different syndromes,
whereas in [149] a small percentage of failed estimates were shown to be end-
to-end identical syndrome errors and end-to-end degenerate errors111The
authors of this work do not distinguish between end-to-end identical syndrome
errors and end-to-end degenerate errors..

Aside from these failed recovery analyses, the literature is limited when it
comes to assessing the percentage of decoding failures that is caused by each
type of end-to-end error. It is reasonable to believe that QLDPC codes, given
their large number of degenerate operators [55, 56, 70, 98, 131, 134], will
experience a large number of end-to-end degenerate errors. We confirm this
intuition in the final section of this chapter, where we show how up to $30\%$
of the end-to-end errors that take place when using the QLDPC codes of [21,
22, 23] are degenerate.

####  5.1.2 Discriminating between different types of end-to-end errors

It is clear from the defining characteristics of each specific type of end-to-
end error (see table LABEL:errors) that end-to-end errors with different
syndromes are the easiest type of error to identify. In fact, doing so is
trivial, as all that is required is a comparison of the syndrome estimate,
$\mathbf{\hat{w}}\in\mathbb{F}_{2}^{N-k}$, and the measured syndrome,
$\mathbf{w}\in\mathbb{F}_{2}^{N-k}$, where $k$ and $N$ represent the number of
logical qubits and physical qubits (block length) of the quantum code,
respectively. Similarly, knowing that either an end-to-end identical syndrome
error or an end-to-end degenerate error has occurred is simple. This can be
done by comparing the estimate of the error sequence $\mathbf{\hat{E}}$ to the
channel error $\mathbf{E}$ whenever $\mathbf{\hat{w}}=\mathbf{w}$, i.e., if
$\mathbf{\hat{E}}\neq\mathbf{E}$ either an end-to-end degenerate error or an
identical syndrome error has occurred, and if $\mathbf{\hat{E}}=\mathbf{E}$,
no error has taken place. The issue arises when trying to distinguish between
these two families of end-to-end errors. Notice that the comparison
$\mathbf{\hat{E}}\neq\mathbf{E}$ does not reveal if the error estimate belongs
to the same stabilizer coset as the channel error. Hence, we have no way of
discriminating between end-to-end degenerate errors and end-to-end identical
syndrome errors.

The first strategy that comes to mind to resolve this problem is to compute
the stabilizer of the code in question, calculate the $\star$ product of the
stabilizer with the channel error $\mathbf{E}$ to extract the specific
stabilizer coset of the channel error, and then check if $\mathbf{\hat{E}}$
belongs to this coset. This works because the coset representative choice for
the coset $(\mathbf{T}_{i}\star\mathbf{L}_{j})\star\mathcal{\overline{S}}$ is
irrelevant (any operator belonging to the coset serves as a valid
representative). Thus, computing $\mathbf{E}\star\mathcal{\overline{S}}$ will
yield the stabilizer coset of the channel error, i.e.,
$\mathbf{E}\star\mathcal{\overline{S}}=(\mathbf{T}_{i}\star\mathbf{L}_{j})\star\mathcal{\overline{S}}$.
Therefore, whenever $\mathbf{\hat{w}}=\mathbf{w}$ and
$\mathbf{\hat{E}}\neq\mathbf{E}$, we will know that an end-to-end degenerate
error has occurred if the estimated error sequence $\mathbf{\hat{E}}$ is in
the coset $\mathbf{E}\star\mathcal{\overline{S}}$. If this does not occur,
then an end-to-end identical syndrome error will have taken place.

Unfortunately, since extracting the stabilizer of a quantum code becomes
increasingly complex as its block length increases, this strategy will only be
applicable to short quantum codes. We know from Chapter 4 that the number of
elements in the stabilizer of a quantum code with block length $N$ and rate
$R_{Q}$ is given by $2^{N-k}=2^{N(1-R_{Q})}$, which grows exponentially with
$N$ and can rapidly become intractable on a classical machine as this
parameter increases. In light of this, it is apparent that more practical
methods to differentiate between end-to-end degenerate errors and end-to-end
identical syndrome errors are necessary. Both the strategy we propose herein
and that employed in [55, 153, 151, 152, 154], which are explained in the next
two sections, resolve this issue.

###  5.2 An algebraic perspective on end-to-end degenerate errors

The problem of differentiating between end-to-end identical syndrome errors
and end-to-end degenerate errors can also be formulated as a set of linear
equations. We know from section 4.2.3.3 that the QPCM of a stabilizer code
that encodes $k$ logical qubits into $N$ physical qubits (a rate
$R_{Q}=\frac{k}{N}$ code with block length $N$) can be written as

$\mathbf{H}_{\mathcal{\overline{S}}}=\begin{pmatrix}\mathbf{h}_{1}\\\
\mathbf{h}_{2}\\\ \vdots\\\ \mathbf{h}_{N-k}\end{pmatrix},$ (5.1)

where $\mathbf{h}_{v}=\mathbf{s}_{v}$ denotes the symplectic representation of
the generators $\\{\mathbf{S}_{v}\\}_{v=1}^{N-k}\in\mathcal{\overline{G}}_{N}$
that define the stabilizer group. Each of the elements of
$\mathcal{\overline{S}}$ is a linear combination of the $N-k$ generators,
hence, if $\mathbf{S}$ is an element of the stabilizer and $\mathbf{s}$ is the
symplectic representation of this stabilizer element, then

$\mathbf{s}=\left(\sum_{v=1}^{N-k}\mathrm{a}_{v}\mathbf{h}_{v}\right)\mod{2},$
(5.2)

where $\mathbf{a}=(\mathrm{a}_{1},\ldots,\mathrm{a}_{N-k})$ is a unique binary
vector.

Whenever a channel error $\mathbf{E}$ takes place, the decoder will compute an
estimate of this error and produce an estimate of the syndrome associated to
it. As discussed previously, this syndrome only determines which specific
effective centralizer coset the channel error belongs to. In other words, the
syndrome diagnoses the effective centralizer coset representative
$\mathbf{T}_{i}$ of the channel error. Assuming that an end-to-end error with
different syndrome does not occur, the estimated syndrome will match the
measured syndrome, hence the centralizer coset representative of the estimated
error sequence and the centralizer coset representative of the channel error
will also be the same, i.e., $\mathbf{\hat{T}}_{i}=\mathbf{T}_{i}$. Thus, if
we compute the $\star$ operation of the channel error $\mathbf{E}$ and the
estimated error $\mathbf{\hat{E}}$, which can also be understood as the mod2
sum of their symplectic representations over $\mathbb{F}_{2}^{2N}$:
$\beta(\mathbf{E})\oplus\beta(\mathbf{\hat{E}})=\mathbf{e}\oplus\mathbf{\hat{e}}$,
where $\beta$ denotes the symplectic map, the sequence $\mathbf{E}$ will be
shifted to the effective centralizer
$\mathcal{\overline{Z}}(\mathcal{\overline{S}})$. Note that we can also write
this using the symplectic map as
$\mathbf{E}\star\mathbf{\hat{E}}\in\mathcal{\overline{Z}}(\mathcal{\overline{S}})\rightarrow\beta(\mathbf{E})\oplus\beta(\mathbf{\hat{E}})\in\beta(\mathcal{\overline{Z}}(\mathcal{\overline{S}}))=\mathbf{e}\oplus\mathbf{\hat{e}}\in\Gamma_{R}$.
Based on this, the issue of determining whether an end-to-end error is
degenerate can be resolved by answering the following question:

$\exists\
\mathbf{a}:\mathbf{e}\oplus\mathbf{\hat{e}}=\left(\sum_{i=1}^{N-k}\mathrm{a}_{i}\mathbf{h}_{i}\right)\mod{2}\
\text{ ?}$ (5.3)

Essentially, if a set of coefficients $\mathbf{a}$ exists such that the above
equation holds, i.e., if
$\mathbf{e}\oplus\mathbf{\hat{e}}\in\mathbb{F}_{2}^{2N}$ is a linear
combination of the symplectic representation of the stabilizer generators,
then $\mathbf{E}\star\mathbf{\hat{E}}$ belongs to the stabilizer and an end-
to-end degenerate error will have occurred. If such a set of coefficients does
not exist, then and end-to-end identical syndrome error has taken place.

The expression shown in (5.3) defines a linear system of Diophantine equations
over the binary field. An answer to this question can be found by writing the
augmented matrix
$[\mathbf{H}_{\mathcal{\overline{S}}}^{\top}|(\mathbf{e}\oplus\mathbf{\hat{e}})^{\top}]$
in its row-echelon form. This means that, based on this procedure, it is
possible to determine the type of end-to-end errors that occur and
subsequently compute the logical error rate. This is done in [135]. However,
although the procedure is conceptually simple, rewriting the augmented matrix
in such a manner becomes increasingly computationally complex as matrices grow
in size. Unfortunately, for sparse quantum codes to be good, the block length
must be large, which implies that the PCMs of these codes will also be
large222The PCMs of QEC codes are of size $N-k\times 2N$. A common size in the
literature of QLDPC codes is $10000$ qubits, thus the PCM associated to such a
code would be of size $(10000-k)\times 20000$.. Furthermore, the row-echelon
form of the matrix
$[\mathbf{H}_{\mathcal{\overline{S}}}^{\top}|(\mathbf{e}\oplus\mathbf{\hat{e}})^{\top}]$
must be computed during every simulation iteration (whenever the estimated
syndrome and the measured syndrome match) to determine what type of end-to-end
error has taken place, which may significantly increase simulation time. For
these reasons, calculating the logical error rate based on this procedure can
become a cumbersome and lengthy endeavour. Hence, the task at hand is to find
a more practical and less computationally demanding way to determine if the
congruence equation system given in (5.3) has a solution, as this suffices to
determine if the end-to-end error is degenerate (we do not actually need to
solve the system itself).

####  5.2.1 Classical coding inspired strategy

It is possible to find an answer to (5.3) by casting the problem in the
framework of classical linear block codes. In classical coding theory, the
encoding matrix or generator matrix $\mathbf{G}_{c}$ of a binary linear block
code and its corresponding parity check matrix $\mathbf{H}_{c}$ fulfil
$(\mathbf{G}_{c}\mathbf{H}_{c}^{\top})\mod
2=(\mathbf{H}_{c}\mathbf{G}_{c}^{\top})\mod 2=0$. This means that the parity
check matrix defines a basis for the null space of the generator matrix and
viceversa. In the classical paradigm, having a basis for the null space of a
code enables us to determine whether the decoding outcome $\mathbf{x}$ belongs
to the code by simply computing its product with the parity check matrix of
the code, i.e., if $(\mathbf{H}_{c}\mathbf{x}^{\top})\mod 2=0$ then
$\mathbf{x}$ is a codeword. Essentially, whenever
$(\mathbf{H}_{c}\mathbf{x}^{\top})\mod 2=0$, the decoding outcome is a linear
combination of the rows of the generator matrix $\mathbf{G}_{c}$ and it
belongs to the code, and whenever $(\mathbf{H}_{c}\mathbf{x}^{\top})\mod 2\neq
0$, $\mathbf{x}$ does not belong to the code.

Notice that, based on this formulation, the quandary posed in (5.3) is
reminiscent of the classical decoding scenario. The main difference is that
instead of determining if the decoding outcome belongs to the code, we must
discover if the sum of the symplectic representations of the channel error and
the estimated error belong to the stabilizer. This parallelism between the
classical and quantum problems allows us to apply the classical resolution
strategy to the quantum paradigm with only a slight caveat: answering (5.3)
requires an inverse approach to the classical method. Since the generators of
the stabilizer code are given by the rows of the parity check matrix
$\mathbf{H}_{\mathcal{\overline{S}}}$, the corresponding kernel generator
matrix333We refer to the matrix $\mathbf{G}_{\mathcal{\overline{S}}}$ as the
kernel generator matrix to avoid the term stabilizer generator matrix, as this
latter term implies that the the matrix can be used for encoding purposes
(which may not be true in the present case).
$\mathbf{G}_{\mathcal{\overline{S}}}$ (instead of the parity check matrix like
in the classical paradigm) must be used to discover if
$\mathbf{e}\oplus\mathbf{\hat{e}}$ can be written as a linear combination of
the stabilizer generators. The matrix $\mathbf{G}_{\mathcal{\overline{S}}}$
defines a basis for the nullspace of the stabilizer code, hence it will
suffice to compute
$[\mathbf{G}^{\top}_{\mathcal{\overline{S}}}(\mathbf{e}\oplus\mathbf{\hat{e}})^{\top}]\mod
2$ to find the answer to (5.3). If
$[\mathbf{G}^{\top}_{\mathcal{\overline{S}}}(\mathbf{e}\oplus\mathbf{\hat{e}})^{\top}]\mod
2=0\rightarrow\mathbf{E}\star\mathbf{\hat{E}}\in\mathcal{\overline{S}}$ which
means that an end-to-end degenerate error has occurred, and if
$[\mathbf{G}^{\top}_{\mathcal{\overline{S}}}(\mathbf{e}\oplus\mathbf{\hat{e}})^{\top}]\mod
2\neq
0\rightarrow\mathbf{E}\star\mathbf{\hat{E}}\not\in\mathcal{\overline{S}}$,
meaning that an end-to-end identical syndrome error will have taken place.

This strategy provides us with a simple and computationally efficient method
to determine the type of end-to-end error that has taken place. The only
requirement is obtaining the matrix $\mathbf{G}_{\mathcal{\overline{S}}}$,
which can be computed once (by finding a basis for the nullspace of its parity
check matrix $\mathbf{H}_{\mathcal{\overline{S}}}$) and can then be stored
offline for any stabilizer code. In this manner, we have designed a simple
method to solve (5.3) that does not require the computation of the stabilizer
and so avoids the complexity issues that this entails.

####  5.2.2  Detecting end-to-end degenerate errors using encoded Pauli
operators

There is another manner of distinguishing between end-to-end identical
syndrome errors and end-to-end degenerate errors. It involves obtaining the
encoded Pauli operators (see section 4.2.3.1) of a code following a method
derived by Gottesman in his seminal work [16], and then using these operators
to determine whether the error estimate produced by the decoder is in the
stabilizer coset of the channel error. This strategy was first applied to
QLDPC codes in [55], and has since been used in [151, 152, 153, 154].

Based on the definition of the encoded Pauli operators given in the previous
chapter, we know that an encoded Pauli operator $\overline{\mathbf{Z}}_{q}$
commutes with all the elements of $\mathcal{\overline{S}}$ as well as with all
other encoded Pauli operators except for the operator
$\overline{\mathbf{X}}_{l}$ when $q=l$. This means that, if the encoded Pauli
operators of a stabilizer code are known, we can determine if an operator
$\mathbf{A}\in\mathcal{\overline{Z}(\overline{S})}\subset\mathcal{\overline{G}}_{N}$
belongs to $\mathcal{\overline{S}}$ by checking the commutation relations of
$\mathbf{A}$ with the encoded Pauli operators. If $\mathbf{A}$ commutes with
all the encoded Pauli operators it is within the stabilizer and if it does not
(it anti commutes with one encoded Pauli operator) it is not in the
stabilizer. Against this backdrop, it is easy to see how this strategy can be
applied to solve the issue of discriminating between end-to-end identical
syndrome errors and end-to-end degenerate errors. After successful decoding
(the decoder produces a matching estimate of the syndrome), we know that
$\mathbf{E}\star\mathbf{\hat{E}}\in\mathcal{\overline{Z}(\overline{S})}$. Now,
we determine if $\mathbf{E}\star\mathbf{\hat{E}}$ is in
$\mathcal{\overline{S}}$ by checking its commutation status with
$\\{\overline{\mathbf{Z}}_{q}\\}_{q=1}^{k}$ and
$\\{\overline{\mathbf{X}}_{l}\\}_{l=1}^{k}$. If
$\mathbf{E}\star\mathbf{\hat{E}}$ commutes with all the encoded Pauli
operators, $\mathbf{E}\star\mathbf{\hat{E}}\in\mathcal{\overline{S}}$ and an
end-to-end degenerate error has occurred. If not, an end-to-end identical
syndrome error has occurred. It is based on these comparisons that the logical
error rate was successfully computed in [151, 152, 153, 154].

Naturally, to be able to apply this method, one must first have knowledge of
the encoded Pauli operators of the code. This is similar to the classical
coding-based strategy we proposed earlier, which requires the computation of
the kernel generator matrix $\mathbf{G}_{\mathcal{\overline{S}}}$. The encoded
Pauli operators of a stabilizer code can be found based on the concept of the
standard form (see Chapter 4 of [16]). In this work, Gottesman showed how, by
applying row operations (i.e. Gaussian elimination) together with the
necessary qubit permutations (i.e. column permutations) on the parity check
matrix of a stabilizer code, one can obtain a special row reduced echelon form
of the parity check matrix: the standard form. Once the standard form is
known, the encoded Pauli operators $\\{\overline{\mathbf{Z}}_{q}\\}_{q=1}^{k}$
and $\\{\overline{\mathbf{X}}_{l}\\}_{l=1}^{k}$ can be directly obtained from
it using matrix algebra [16, 158]. As with the kernel generator matrix
$\mathbf{G}_{\mathcal{\overline{S}}}$, the encoded Pauli operators of a
specific code need only be computed once and can then be stored offline.

###  5.3 Frequency of each type of end-to-end error

We now employ our method to study the frequency with which the different types
of end-to-end error occur when using QLDPC codes. For this purpose, we
simulate the CSS QLDGM codes of [21, 22, 23] with different rates and block
lengths over the depolarizing channel. These codes are presented in detail in
the next chapter. If desired, the reader can skip ahead for a rigorous
discussion on their design. However, this is not necessary to understand the
remainder of this chapter. For reference, the particular characteristics of
the simulated codes are detailed in table 5.2.

The results of our simulations are shown in Figure 5.1, where each subfigure
groups the results by block length, i.e, each of the subfigures portrays the
results for all the codes with the same value of $N$. The graphs plot the
ratio of a specific type of end-to-end error against the depolarizing
probability. The aforementioned ratio is computed as
$\frac{\mathrm{E}_{i}}{\mathrm{E}_{T}}$, where $\mathrm{E}_{i}$ denotes the
total number of end-to-end errors of a specific type ($i=1,2,3$.):

  * •

$\mathrm{E}_{1}\rightarrow$ end-to-end errors with different syndromes,

  * •

$\mathrm{E}_{2}\rightarrow$ end-to-end errors with identical syndromes,

  * •

$\mathrm{E}_{3}\rightarrow$ end-to-end degenerate errors,

and $\mathrm{E}_{T}$ represents the total number of end-to-end errors. To
ensure that the simulation results are precise, the ratios have been computed
after a total of $1000$ decoding mistakes have been made (following the Monte
Carlo simulation rule of thumb provided in [162]), i.e.,
$\mathrm{E}_{T}=1000$. For a complete discussion on how these simulations are
conducted the reader is referred to Appendix C.

Table 5.2: Parameter values and configurations of simulated codes.  $N$ | $R_{Q}$ | Classical LDGM | $[m,p,x,y]$
---|---|---|---
$100$ | $0.1$ | P($3,3$) | [$45,24,6,3$]
$100$ | $0.2$ | P($3,3$) | [$40,18,6,3$]
$100$ | $0.25$ | P($3,3$) | [$38,15,6,3$]
$100$ | $0.5$ | P($3,3$) | [$25,6,7.57,3$]
$500$ | $0.1$ | P($5,5$) | [$225,170,11,3$]
$500$ | $0.2$ | P($5,5$) | [$200,144,11,3$]
$500$ | $0.25$ | P($5,5$) | [$188,130,11,3$]
$500$ | $0.33$ | P($5,5$) | [$163,102,11,3$]
$500$ | $0.5$ | P($5,5$) | [$125,60,11,3$]
$2000$ | $0.1$ | P($9,9$) | [$900,691,11,3$]
$2000$ | $0.2$ | P($9,9$) | [$800,581,11,3$]
$2000$ | $0.25$ | P($9,9$) | [$750,526,11,3$]
$2000$ | $0.33$ | P($9,9$) | [$670,438,11,3$]
$2000$ | $0.5$ | P($9,9$) | [$500,251,11,3$]

The outcomes portrayed in Figure 5.1 confirm our initial intuition that sparse
quantum codes are degenerate. It is easy to see that for all of the simulated
block lengths and rates (except for $R_{Q}=0.5$), the percentage of end-to-end
errors that are not of the $\mathrm{E}_{1}$ type is not negligible, i.e.,
$\frac{\mathrm{E}_{2}}{\mathrm{E}_{T}}+\frac{\mathrm{E}_{3}}{\mathrm{E}_{T}}\neq
0$. Furthermore, these results speak towards the higher precision of the
logical error rate compared to the physical error rate when assessing the
performance of these codes. For instance, at a noise level of $p=0.005$,
$\frac{\mathrm{E}_{3}}{\mathrm{E}_{T}}=0.198$ for the $N=500$ $R_{Q}=0.1$
code. This means that $19.8\%$ of the end-to-end errors are degenerate and
should not be counted as decoding failures. Thus, in this scenario, the
physical error rate overestimates the number of decoding failures and does not
provide an accurate representation of the performance of the code. In fact,
regardless of the noise level of the channel, the rate of the code (except for
$R_{Q}=0.5$), and the block length of the code, end-to-end degenerate errors
take place, and so the physical error rate will always provide an inaccurate
representation of the performance of these sparse quantum codes. Therefore, as
is stated in [154], it is clear that performance results assessed based on the
physical error rate ($\mathbf{\hat{E}}=\mathbf{E}$ as the decoding success
criterion) [20, 21, 22, 23, 149, 157] are inaccurate (they report an upper
bound).

(a)

(b)

(c)

Figure 5.1: Ratios of end-to-end different syndrome errors, identical syndrome
errors, and degenerate errors for codes of various rates and block lengths:
(a) $N=100$ (b) $N=500$ (c) $N=2000$. .

Furthermore, the results shown in Figure 5.1 also reveal how the frequency
with which each type of end-to-end error takes place varies as a function of
different parameters:

  * •

End-to-end errors with different syndromes represent a large percentage of the
total number of end-to-end errors when the rate of the code is high. This
percentage decreases as the rate of the codes goes from $R_{Q}=0.5$ to
$R_{Q}=0.1$ (see ratio $\frac{\mathrm{E}_{1}}{\mathrm{E}_{T}}$ in Figure 5.1).
This trend becomes further exacerbated as the block length of the simulated
codes increases, i.e., for low rate large block length codes the ratio
$\frac{\mathrm{E}_{1}}{\mathrm{E}_{T}}$ will be significantly smaller than for
low rate short codes.

  * •

End-to-end identical syndrome errors represent the smallest percentage of the
total number of end-to-end errors in most of the simulated cases. This is
reflected by the fact that
$\frac{\mathrm{E}_{2}}{\mathrm{E}_{T}}<\frac{\mathrm{E}_{1}}{\mathrm{E}_{T}},\frac{\mathrm{E}_{3}}{\mathrm{E}_{T}}$
in all of our simulation outcomes.

  * •

As the noise level of the channel grows, the ratio
$\frac{\mathrm{E}_{1}}{\mathrm{E}_{T}}$ becomes larger and the ratio
$\frac{\mathrm{E}_{2}}{\mathrm{E}_{T}}$ diminishes. The ratio of end-to-end
degenerate errors $\frac{\mathrm{E}_{3}}{\mathrm{E}_{T}}$ stays relatively
constant.

The relationships between these parameters and different types of end-to-end
errors serve to draw important conclusions. For instance, the large values of
$\frac{\mathrm{E}_{1}}{\mathrm{E}_{T}}$ in many of the simulated instances can
be understood as a sign that performance gains may be attained by improving
the decoding algorithm. This means that applying modified decoding strategies,
such as those of [135, 149, 151, 152, 153], will aid in reducing the presence
of end-to-end errors with different syndromes and improve performance. A
matter that should also be considered is how often these strategies produce
failed error corrections in the form of end-to-end identical syndrome errors.
For the methodology of [149], such events were shown to be rare, hence we
expect these strategies to be a good approach to improve the performance of
QLDPC codes. We discuss modified decoding strategies for QLDPC codes in the
next section of this chapter.

In terms of other end-to-end error ratios, the large values of
$\frac{\mathrm{E}_{3}}{\mathrm{E}_{T}}$ when compared to
$\frac{\mathrm{E}_{2}}{\mathrm{E}_{T}}$, especially at higher block lengths,
show that end-to-end identical syndrome errors are the least frequent of all
the end-to-end error types. Despite the relatively small percentage that end-
to-end identical syndrome errors represent, it is possible that their
relevance will grow when the amount of end-to-end errors with different
syndromes is reduced (using modified decoding strategies) or when the
degenerate content of the code is increased (through design). At this point,
it may be that further improvements in performance will only be possible by
designing an optimal degenerate decoder with the capability to correct end-to-
end identical syndrome errors. Finally, given that the method proposed in
5.2.1 is valid to detect end-to-end degenerate errors, it could be interesting
in future work to employ this methodology to specifically design codes to be
degenerate. This might lead to code constructions whose probability of
suffering end-to-end degenerate errors is maximized, which would allow the
positive effects of degeneracy (improved error correction capabilities without
a decoding complexity increase) to be completely exploited for quantum error
correction purposes.

###  5.4 Improved decoding strategies for QLDPC codes

We close this chapter by providing a succinct summary of the most relevant
improved decoding strategies that have been proposed in the literature. A more
thorough look into each of these methods is provided in Appendix B.

In the previous section we discussed how
$\frac{\mathrm{E}_{1}}{\mathrm{E}_{T}}$, the ratio of end-to-end errors with
different syndromes, accounts for a large portion of the decoding mistakes of
the simulated QLDGM codes. Fortunately, although they cause decoding mistakes,
these errors are always detected (the estimated syndrome is not equal to the
measured syndrome). This means that the decoder will know when these errors
occur, an outcome that can be used to apply certain modifications to the
original QMLD strategy to try to revert the errors. Eliminating the presence
of these end-to-end errors may lead to drastic performance improvements, and
although it does not address the issue of constructing a degenerate decoder
(end-to-end identical syndrome errors will still occur), it represents an
important frontier for QLDPC code design.

The earliest mention of improved decoding strategies for QLDPC codes dates
back to the work of Mackay et al. [18], who proposed a strategy to adapt the
conventional SPA decoder to the depolarizing channel. Later on, this technique
was applied by Lou et al in [22], where a modified decoder was built for the
depolarizing channel and shown to surpass traditional BP decoders. Following
this, a set of heuristic methods that successfully improved the ability of the
classical qubit-wise BP decoder to handle detected harmful errors was built in
[55]. In this work, the authors also discussed the concept of symmetric
degeneracy errors and proposed a host of techniques (freezing, collision, and
random perturbation) capable of improving the performance of QLDPC codes under
BP decoding. Simultaneously, an enhanced-feedback decoder specifically
designed for the depolarizing channel was derived in [149]. Later on, in [20],
a modified decoder for dual-containing CSS QLDPC codes which also led to
performance improvements was introduced. Recently, in [135, 151, 152, 153,
154], a number of new and improved decoding strategies have been proposed. A
timeline of the most significant contributions to the field of modifed QLDPC
decoding is provided in table 1.

Except for the decoders proposed in [22, 20, 153], all of these heuristic
methods operate according to the same working principle: prior to applying any
changes to the decoder, the original qubit-wise BP decoder must fail.
Generally, these modified decoding processes begin by running a standard
unaltered version of the qubit-wise BP decoder. If the standard decoder finds
an error estimate whose corresponding syndrome is equal to the real one, i.e.,
$\hat{\mathbf{w}}=\mathbf{w}$, then the procedure halts and assumes that the
error estimate is correct. However, if the standard decoder fails to find a
matching estimate of the syndrome after the allotted number of iterations,
changes are made to the decoder (according to specific techniques) and
decoding is reattempted in order to fix this decoding impasse.

These decoding alterations combine a range of strategies to revert the impact
of end-to-end errors with different syndromes. Some techniques, like those of
[18, 22, 55, 135, 149], utilize the incorrect error sequence and the syndrome
estimates of the original decoder to compute new a priori probabilities that,
when used by the decoder, may result in a matching syndrome estimate. Others,
like the augmented decoder of [135] and the supernode decoder of [20], rely on
changing the structure of the original factor graph. Also in [135], the
authors apply the two proposed approaches in unison, so that when one fails
the other is applied and viceversa, a technique called the combined decoder.
Finally, the most recent strategies of [151, 152, 153, 154] focus more on
post-processing and direct modifications to the decoding algorithm.

Table 5.3: Most significant modified decoding strategies for QLDPC codes.

2004 $\cdots\cdots$ $\bullet$ Initial Proposal for a Modified SPA-based
decoding Strategy [18].

2005 $\cdots\cdots$ $\bullet$ Correlation Exploiting Decoder [22].

2008 $\cdots\cdots$ $\bullet$ Freezing, Collision & Random Perturbation
Decoders [55].

2012 $\cdots\cdots$ $\bullet$ Enhanced Feedback Decoder [149].

2015 $\cdots\cdots$ $\bullet$ Supernode Decoder [20].

2019 $\cdots\cdots$ $\bullet$ Adjusted & Augmented Decoders [135].

2019/2020 $\cdots\cdots$ $\bullet$ Ordered Statistics Decoder [151, 152].

2020 $\cdots\cdots$ $\bullet$ Refined Belief Propagation Decoding [153].

2021 $\cdots\cdots$ $\bullet$ Degeneracy Exploiting Decoder [154].

Regardless of the specific modified decoding method that is employed, the
impact of its modifications spreads quickly during the new decoding phase,
mostly due to the presence of short cycles in QLDPC codes. This means that,
while short cycles hinder the traditional BP decoder, they benefit these
modified decoding strategies [55, 135, 149]. The downside of these heuristic
schemes comes in the form of an increased decoding complexity. Because most of
these techniques rely on the failure of a standard decoder and a re-execution
of the modified process anew, the chosen method sometimes requires numerous
decoding attempts before it finds the correct syndrome estimate. With regard
to performance, the degree to which it can be improved varies depending on the
chosen strategy; the techniques of [55, 135] can yield performance
improvements of about 30% in terms of the word error rate over traditional
decoding, while the enhanced feedback decoding technique of [149] has been
shown to be approximately 10 times better than the traditional SPA decoder,
even though it only requires a 25-35% increase in the number of decoding
iterations. In [151, 152] the Ordered Statistics Decoder (OSD) is shown to
outperform all of the aforementioned modified decoding techniques.

In any case, aside from a potential increase in complexity, these heuristic
methods are relatively simple tools that can be easily included within
conventional qubit-wise BP decoders to improve the performance of QLDPC codes
under BP/SPA decoding.

###  5.5 Chapter summary

In this chapter we have presented a method to detect degenerate errors in
sparse quantum codes in a computationally efficient manner. Based on this
method, we have shown how the physical error rate provides an inaccurate
representation of the performance of sparse quantum codes and we have shown
that logical error rate should be used instead. The discrepancy between the
logical error rate and the physical error rate is especially relevant to the
field of sparse quantum codes because of their degenerate nature. This is
reflected by the results we have obtained for a specific family of QLDPC
codes, whose performance can be up to $20\%$ better than would be expected
based on previous results in the literature. In addition, these simulation
outcomes serve to show how performance may be improved by constructing
degenerate quantum codes, and they also speak toward the positive impact that
modified decoding strategies can have on the performance of sparse quantum
codes. The last portion of this chapter surveys the literature on these
modified decoding strategies, most of which are thoroughly discussed in the
Appendix.

##  CHAPTER 6 Non-CSS QLDPC codes

> “The most important step a man can take. It’s not the first one, is it? It’s
> the next one. Always the next step…”
>
> Brandon Sanderson.

Up to this point in the dissertation our focus has been (for the most part)
theoretical. Aside from studying the phenomenon of degeneracy, what we have
seen thus far has served to lay out the necessary groundwork to understand how
QEC works and why it is important. This context should be useful to understand
the remaining chapters of the dissertation, where our attention will shift to
the design and performance of a specific family of QLDPC codes. Before getting
started with Chapter $6$, in the following discussion we provide some insight
into why we chose to work with sparse quantum codes.

#### Why build QEC codes using LDPC codes?

In the realm of classical communications, turbo codes [46, 166] and LDPC codes
[110, 111, 112, 167, 168, 169] are known to exhibit capacity approaching
performance at a reasonable decoding computational complexity. In particular,
turbo codes offer great flexibility when it comes to choosing their block
length and rate, whereas the sparsity of LDPC codes makes them easy to decode.
Given their appealing characteristics, the scientific community has searched
diligently for the quantum equivalents of classical turbo and LDPC codes.
Quantum codes based on turbo codes first appeared in [28, 29], and have since
been modified and improved [30, 31, 170, 171, 172]. In turn, QLDPC codes were
first analyzed in [18], were their sparse nature was shown to be especially
advantageous in the quantum paradigm because it ensures that a smaller number
of quantum interactions per qubit is necessary during the error correction
procedure. Because quantum gates are faulty, having less quantum interactions
per qubit avoids additional quantum operations, which minimizes errors and
facilitates fault-tolerant computing [88, 173, 174]. Thus, QLDPC codes can be
said to be particularly well suited for quantum error correction.

Out of the existing types of LDPC codes, LDGM codes [175] provide a seamless
manner for code design in the quantum domain. LDGM codes are a specific subset
of LDPC codes whose generator matrices are also sparse, and thus their
encoding complexity is similar to that of turbo codes, and much lesser than
for standard LDPC codes. Given that LDGM codes form a special subclass of the
LDPC code family, they can be decoded in the same manner and with the same
complexity as any other LDPC code. LDGM codes have been extensively studied
[155, 175, 176] and used in classical communications [177, 178]. In [112],
regular LDGM codes were studied and shown to be asymptotically bad, displaying
error floors that do not decrease with the block length. In [155] and [176], a
concatenated LDGM scheme was shown to achieve irregular LDPC code-like
performance at a very low encoding/decoding complexity.

Based on what was shown in Chapter 4, we know that quantum codes can be built
from classical codes by casting them in the framework of stabilizer codes
[16]. In [20], the authors document the design of QLDPC codes from their
classical counterparts based on the stabilizer formalism by detailing numerous
construction and decoding techniques along with their flaws and merits. Among
the discussed methods, the construction of QLDPC codes based on LDGM codes is
shown to yield performance and code construction improvements, albeit at an
increase in decoding complexity. This method was originally proposed in [21]
and [22], where CSS quantum codes based on regular LDGM classical codes were
shown to surpass the best quantum coding schemes of the time. Later,
performance was significantly improved in [155] and [176] by utilizing a
parallel concatenation of two regular LDGM codes.

As with most QLDPC designs, QLDGM-based quantum code implementations are based
on CSS constructions. CSS codes, simultaneously proposed by Calderbank, Shor,
and Steane in [57], [58], are a particular subset of the stabilizer code
family. They provide a straightforward method to design quantum codes via
existing classical codes. However, due to the specific nature of CSS
constructions, their performance is limited by an unsurpassable bound,
referred to as the CSS lower bound [62]. This inspires the search for non-CSS
constructions, as they should theoretically be able to outperform CSS codes if
designed optimally. Non-CSS LDPC-based codes were proposed in [63] and [64].
However, despite showing promise, they fail to outperform existing CSS QLDPC
codes for comparable block lengths.

In this chapter, we introduce a non-CSS scheme based on LDGM codes and compare
its performance to existing CSS QLDGM codes. We begin by explaining how CSS
codes are constructed and how they can be modified to create non-CSS quantum
codes. Following this, we provide insight regarding how our construction is
optimized, and we show how the performance of our non-CSS codes is similar to
that of the CSS schemes they are derived from, despite the fact that their
quantum rate is higher. When their rate is the same, the non-CSS scheme
outperforms the original CSS design over the depolarizing channel. Finally, we
compare the non-CSS structures proposed here with other existing QLDPC codes
in the literature, illustrating that our method surpasses such error
correction schemes.

The chapter is structured as follows. We commence with a brief presentation of
important preliminary topics, such as CSS codes or LDGM codes, that did not
appear in Chapter 3. We proceed by presenting CSS LDGM based codes in section
6.2 and our non-CSS LDGM-based strategy in section 6.3. In section 6.4, we
compare the performance of the proposed scheme to existing CSS quantum codes.

###  6.1 Preliminaries

In this section we provide an overview of some preliminary topics in the field
of QEC that were not presented in Chapter 3.

####  6.1.1 Pauli channels

We saw in Chapter 3 that the most popular quantum channel model is the generic
Pauli channel $\xi_{p}$. To recap, the effect of the Pauli channel $\xi_{p}$
upon an arbitrary quantum state described by its density matrix $\rho$ can be
written as

$\xi_{p}(\rho)=(1-p_{x}-p_{y}-p_{z})\rho+p_{x}X\rho X+p_{y}Y\rho Y+p_{z}Z\rho
Z.$

This expression can be interpreted as the quantum state experiencing a bit-
flip ($X$ Pauli operator) with probability $p_{x}$, a phase-flip ($Z$ Pauli
operator) with probability $p_{z}$, or a combination of both ($Y$ Pauli
operator) with probability $p_{y}$.

#####  6.1.1.1 Depolarizing channel

We also mentioned previously that most of the QEC literature considers the
independent depolarizing channel model. This model is a specific instance of
the Pauli channel in which the depolarizing probabilities are all equal, i.e,
$p_{x}=p_{z}=p_{y}=p$, and the channel is characterized by the depolarizing
probability $p$. When quantum states of $N$ qubits are considered, the errors
that take place belong to the $N$-fold Pauli111Recall that the global phase
has no observable consequence, so we can consider the channel errors to be
elements of the effective $N$-fold Pauli group. group $\mathcal{G}_{N}$. These
$N$-qubit error operators are made up of single qubit Pauli operators that act
independently on each qubit causing an $X$, $Z$, or $Y$ error with probability
$p/3$ and leaving it unchanged with probability $(1-p)$.

#####  6.1.1.2 i.i.d. $X/Z$ Channel

A simpler quantum channel model, known as the standard flipping channel or
i.i.d. X/Z channel, was introduced in [18], where $Z$ and $X$ errors are
modelled as independent events identically distributed (i.i.d.) according to
the flip probability $f_{m}$. This quantum channel model is analogous to two
independent Binary Symmetric Channels (BSCs) with marginal bit flip
probability $f_{m}=2p/3$, where the separate BSCs can be seen as $Z$ and $X$
error channels, respectively. Given that $Y$ errors occur when both a phase
and a bit-flip happen to the same qubit, the simplified notion of the i.i.d.
X/Z channel ignores any correlation that exists between $X$ and $Z$ errors in
the depolarizing channel.

####  6.1.2 The Hashing bound

In the introduction to section 3.2 we mentioned how the classical channel
capacity establishes the maximum information transfer rate at which reliable
communications can take place over a classical channel. Unsurprisingly, we can
also derive the quantum counterpart of this concept and use it to study the
theoretical limits of quantum channels.

The capacity of a quantum channel is defined as the highest possible
achievable rate at which quantum information can be asymptotically transmitted
in an error-less manner. Unfortunately, a closed formula for the capacity of
the Pauli channel is not known [97, 179, 180], which means that a closed
formula for the capacity of the depolarizing channel (the most prominent
channel model for decoherence in the literature) is also unknown. Instead, we
work with a quantity known as the Hashing bound, which defines a lower bound
on the capacity of the depolarizing channel and is computed as
$C_{\text{Hash}}(p)=1-H_{2}(p)-p\text{log}_{2}3$, where $H_{2}(p)$ is the
binary entropy function and $p$ represents the depolarizing probability [101].
This means that for a given value of $p$, $C_{\text{Hash}}(p)$ represents a
lower bound on the highest possible coding rate at which asymptotically error-
free quantum communication is possible. In theory, it is possible for quantum
codes to surpass the Hashing bound due to the phenomenon of degeneracy (which
is also the reason why a closed formula for Pauli channels is difficult to
obtain) [54]. Alternatively, for a specific quantum rate $R_{Q}$, where we
have $R_{Q}=C_{\text{Hash}}(p^{*})$, $p^{*}$ represents a bound on the
channel’s depolarizing probability [165]. As in the classical domain, we can
refer to $p^{*}$ as the noise limit.

#####  6.1.2.1 Distance to the Hashing bound

Ideally, quantum codes that are properly designed should ensure error-free
communications close to the noise limit $p^{*}$. Thus, we can efficiently
characterize the quality of quantum codes of a specific quantum rate $R_{Q}$
built for the depolarizing channel by assessing how far away they are from the
Hashing bound. The distance from the Hashing bound can be computed based on
the expression

$\delta=10\text{log}_{10}\bigg{(}\frac{p^{*}}{p}\bigg{)}\,,$ (6.1)

where we use $\delta$ to represent the distance to the Hashing bound in
decibels (dB), $p^{*}$ is the noise limit of the depolarizing channel for a
specific quantum coding rate $R_{Q}$, and $p$ is the highest depolarizing
probability at which the code in question can operate in an error-free manner.

####  6.1.3 CSS codes

Based on our previous discussion on stabilizer codes (see section 4.2.3.3), we
know that two binary classical LDPC codes can only be used to construct a
quantum stabilizer code if they satisfy the symplectic criterion (4.23). With
this knowledge, the first design strategy one could devise to construct
quantum stabilizer codes would be to randomly select pairs of classical LDPC
codes and combine them into a QPCM. However, finding two LDPC codes of
reasonable block size that satisfy (4.23) is highly unlikely. Calderbank-Shor-
Steane (CSS) codes [57], [58], provide a more efficient design strategy than
random selection of classical codes. The quantum parity check matrix of these
codes is written as

$\mathbf{H}_{Q}=(\mathrm{H}_{x}|\mathrm{H}_{z})=\begin{pmatrix}\mathrm{H}_{x}^{{}^{\prime}}&0\\\
0&\mathrm{H}_{z}^{{}^{\prime}}\end{pmatrix},$ (6.2)

where $\mathrm{H}_{x}=\begin{pmatrix}\mathrm{H}_{x}^{{}^{\prime}}\\\
0\end{pmatrix}$ and $\mathrm{H}_{z}=\begin{pmatrix}0\\\
\mathrm{H}_{z}^{{}^{\prime}}\end{pmatrix}$.

In this construction, $\mathrm{H}_{x}^{\prime}$ and $\mathrm{H}_{z}^{\prime}$
are the parity check matrices of two binary classical LDPC codes $C_{1}$ and
$C_{2}$, respectively, where each matrix is used to correct either bit-flips
or phase-flips. The classical codes are chosen so that $C_{2}^{\perp}\subseteq
C_{1}$, where $C_{2}^{\perp}$ is the dual of the classical LDPC code $C_{2}$.
This design constraint, generally referred to as the CSS condition, reduces
(4.23) to $(\mathrm{H}_{x}^{{}^{\prime}}\mathrm{H}_{z}^{{}^{\prime}\top})=0$.

####  6.1.4 Systematic classical LDGM codes

Systematic LDGM codes are useful, both in classical and quantum environments,
because of the particular structure of their generator and parity check
matrices. Let $C$ be a binary systematic LDGM code. Then, its generator matrix
$\tilde{\mathrm{G}}$ and its parity check matrix $\tilde{\mathrm{H}}$ can be
written as

$\displaystyle\begin{gathered}\tilde{\mathrm{G}}=(\mathrm{I}\ \mathrm{P})\\\
\tilde{\mathrm{H}}=(\mathrm{P}^{\top}\ \mathrm{I}),\end{gathered}$ (6.5)

where $\mathrm{I}$ denotes the identity matrix, and $\mathrm{P}$ is a sparse
matrix.

Because LDGM codes belong to the family of linear block codes, these matrices
will satisfy
$\tilde{\mathrm{G}}\tilde{\mathrm{H}}^{\top}=\tilde{\mathrm{H}}\tilde{\mathrm{G}}^{\top}=0$.
Those systematic LDGM codes whose variable and parity check nodes have
degrees222The degree of the variable nodes is the number of nonzero entries
per column of the PCM. The degree of the parity check nodes is given by the
number of nonzero entries per row of the PCM. An LDGM code is said to be
regular when all the rows of its PCM have the same number of nonzero entries,
$x$, and so do its columns, $y$. $x$ and $y$, respectively, will be denoted as
$(x,y)$ regular LDGM codes. Regular LDGM codes are known to be asymptotically
bad [112], displaying error floors that do not decrease with the block length.
However, in [181], codes built via the parallel concatenation of two regular
LDGM codes333The parallel concatenation of regular LDGM codes is equivalent to
an LDGM code with an irregular degree distribution. were shown to yield
significant reduction in these error floors. The parallel concatenation of two
regular LDGM codes $C_{1}$ and $C_{2}$ with generator matrices
$\mathrm{G}_{1}=[\mathrm{I}\ \mathrm{P}_{1}]$ and $\mathrm{G}_{2}=[\mathrm{I}\
\mathrm{P}_{2}]$, where $\mathrm{P}_{1}$ and $\mathrm{P}_{2}$ have degree
distributions $(y_{1},y_{1})$ and $(y_{2},z_{2})$, is the irregular LDGM code
with generator matrix $\mathrm{G}=[\mathrm{I}\ \mathrm{P}_{1}\mathrm{P}_{2}]$.
Generally, this concatenation is accomplished by using a high rate code
$C_{2}$ that is able to reduce the error floor of $C_{1}$, while also causing
negligible degradation of the original convergence threshold.

With regard to decoding, because LDGM codes are a specific subset of LDPC
codes, they are decoded in exactly the same manner as generic LDPC codes. In
Chapter 3 we showed that classical LDPC syndrome-based decoding is performed
by solving the equation $\mathbf{z}=\mathbf{H}\mathbf{e}$, where $\mathbf{z}$
represents the received classical syndrome, $\mathbf{H}$ is the PCM of the
code, and $\mathbf{e}$ is the error pattern that has corrupted our information
(a rigorous description on the details of this procedure is provided in
Appendix A). It should be mentioned that it is also possible to decode
systematic LDGM codes by solving equation $\mathbf{c}=\mathrm{P}\mathbf{u}$,
where $\mathbf{c}$ is the vector of parity bits generated at the encoder,
$\mathrm{P}$ is the constituent sparse matrix of the LDGM generator matrix
(see equation (6.5)), and $\mathbf{u}$ is the information message we want to
obtain. This means that the decoding algorithm for LDGM codes can also be
implemented by applying the SPA [48, 47] over the graph associated to the
equation $\mathbf{c}=\mathrm{P}\mathbf{u}$.

###  6.2 CSS LDGM-based codes

Based on what we have seen thus far, our first intuition to derive the QPCM of
a QLDGM CSS code would be to select any classical LDGM code with parity check
and generator matrices $\tilde{\mathrm{H}}$ and $\tilde{\mathrm{G}}$, and set
$\mathrm{H}^{\prime}_{z}=\tilde{\mathrm{H}}$ and
$\mathrm{H}^{\prime}_{x}=\tilde{\mathrm{G}}$ in (6.2), since the property
$\tilde{\mathrm{G}}\tilde{\mathrm{H}}^{\top}=\tilde{\mathrm{H}}\tilde{\mathrm{G}}^{\top}=0$
would ensure the fulfilment of the symplectic criterion. However, this results
in a QPCM $\mathbf{H}_{Q}$ of size $N\times 2N$, which cannot be used for
encoding purposes. This is easy to see based on the following discussion.

Consider a stabilizer code that has $(N-k)$ stabilizer generators and whose
QPCM is of of size $(N-k)\times 2N$. Such a quantum code encodes $k$ logical
qubits into $N$ physical qubits, which implies that the code has a quantum
rate $R_{Q}=\frac{k}{N}$. This means that the quantum rate of a code with QPCM
$\mathbf{H}_{Q}$ of size $N\times 2N$ is $R_{Q}=0$. Therefore, to build a
valid quantum code from classical LDGM codes, we must reduce the number of
rows in $\mathbf{H}_{Q}$ while ensuring that the CSS condition is fulfilled.
In [21], the authors successfully achieve this via linear row operations. They
do so by applying the following theorem.

######  Theorem 3.

Given the generator and parity check matrices of a systematic LDGM code (6.5),
define $\mathrm{H}_{m_{1}\times N}=[\mathrm{M}_{1}]_{m_{1}\times
n_{1}}[\tilde{\mathrm{H}}]_{n_{1}\times N}$ and $\mathrm{G}_{m_{2}\times
N}=[\mathrm{M}_{2}]_{m_{2}\times n_{2}}[\tilde{\mathrm{G}}]_{n_{2}\times N}$,
where $n_{1}+n_{2}=N$ and $\mathrm{M}_{1}$ and $\mathrm{M}_{2}$ are low-
density full-rank binary matrices whose number of rows satisfy $m_{1}<n_{1}$
and $m_{2}<n_{2}$, respectively. Then, the quantum PCM shown in (6.6),
obtained by setting $\mathrm{H}^{\prime}_{x}=\mathrm{H}$ and
$\mathrm{H}^{\prime}_{z}=\mathrm{G}$ in (6.2), is the quantum PCM of an LDGM-
based CSS code with rate $R_{Q}=\frac{N-m_{1}-m_{2}}{N}$.

$\mathbf{H}_{Q}=(\mathrm{H}_{x}|\mathrm{H}_{z})=\begin{pmatrix}\mathrm{H}&0\\\
0&\mathrm{G}\end{pmatrix}=\begin{pmatrix}\mathrm{M}_{1}\tilde{\mathrm{H}}&0\\\
0&\mathrm{M}_{2}\tilde{\mathrm{G}}\end{pmatrix}.$ (6.6)

We showed in Chapter 4 that sparse quantum codes are decoded by running the
SPA algorithm over the factor graph associated to the expression

$\mathbf{w}=\mathrm{\mathbf{H}}_{\mathcal{\mkern
1.5mu\overline{\mkern-1.5muS\mkern-1.5mu}\mkern
1.5mu}}\odot\mathbf{e}=\mathbf{e}_{x}\mathrm{H}^{\top}_{z}\oplus\mathbf{e}_{z}\mathrm{H}^{\top}_{x},$

where $\mathbf{H}_{\mathcal{\mkern
1.5mu\overline{\mkern-1.5muS\mkern-1.5mu}\mkern 1.5mu}}$ denotes the QPCM of
the stabilizer code in question.

Thus, CSS LDGM codes will be decoded by applying the SPA over the factor graph
defined by $\mathbf{w}=\mathrm{\mathbf{H}}_{Q}\odot\mathbf{e}$, where
$\mathbf{H}_{Q}$ is given in (6.6). We can easily derive this factor graph
based on the unique structure of a CSS QPCM and the properties of the
symplectic representation, which allows us to split
$\mathbf{e}=(\mathbf{e}_{x}|\mathbf{e}_{z})$. Notice how, given the diagonal
structure of $\mathbf{H}_{Q}$, the terms $\mathbf{e}_{x}\mathrm{H}^{\top}_{z}$
and $\mathbf{e}_{z}\mathrm{H}^{\top}_{x}$ have no non-zero overlaps. This
means that the syndrome is made up of two separate parts,
$\mathbf{w}=[\mathbf{w}_{x},\mathbf{w}_{z}]$, where
$\mathbf{w}_{x}=\mathbf{e}_{x}\mathrm{H}^{\top}_{z}$ and
$\mathbf{w}_{z}=\mathbf{e}_{z}\mathrm{H}^{\top}_{x}$ . Thus, we can actually
decode CSS codes separately, i.e, by generating two separate subgraphs
associated to $\mathbf{w}_{x}$ and $\mathbf{w}_{z}$. In the following, we
illustrate this derivation for
$\mathbf{w}_{x}=\mathbf{e}_{x}\mathrm{H}^{\top}_{z}$. The procedure for
$\mathbf{w}_{z}=\mathbf{e}_{z}\mathrm{H}^{\top}_{x}$ is identical but using
$\mathrm{G}$ instead of $\mathrm{H}$ in (6.7). We can write the first half of
the syndrome of a CSS code, $\mathbf{w}_{x}^{\top}$ (in column form), as

$\mathbf{w}_{x}^{\top}=(\mathbf{e}_{x}\mathrm{H}_{z}^{\top})^{\top}=\mathrm{H}_{z}\mathbf{e}_{x}^{\top}=\mathrm{M}_{1}\tilde{\mathrm{H}}\mathbf{e}_{x}^{\top}=\mathrm{M}_{1}[\mathrm{P}^{\top}\
\mathrm{I}]\mathbf{e}_{x}^{\top}.$ (6.7)

If we now split $\mathbf{e}_{x}^{\top}=[\mathbf{e}_{x_{1}}\
\mathbf{e}_{x_{2}}]^{\top}$, we can write

$\displaystyle\mathrm{d}_{x}$ $\displaystyle=[\mathrm{P}^{\top}\
\mathrm{I}]\mathbf{e}_{x}^{\top}=[\mathrm{P}^{\top}\ \mathrm{I}]_{n_{1}\times
N}\begin{pmatrix}\mathbf{e}_{x_{1}}\\\
\mathbf{e}_{x_{2}}\end{pmatrix}_{N\times 1}$
$\displaystyle=\mathrm{P}^{\top}_{n_{1}\times
n_{2}}[\mathbf{e}_{x_{1}}^{\top}]_{n_{2}\times
1}+[\mathbf{e}_{x_{2}}^{\top}]_{n_{1}\times 1}.$ (6.8)

We then relate $\mathrm{d}_{x}$ to $\mathbf{w}_{x}^{\top}$ as

$[\mathbf{w}_{x}^{\top}]_{m_{1}\times 1}=\mathrm{M}_{1_{m_{1}\times
n_{1}}}\mathrm{d}_{x_{n_{1}\times 1}}.$ (6.9)

The factor graph shown in Figure 6.1 is obtained based on expressions (6.2)
and (6.9), as well as their equivalents when using $\mathrm{e}_{z}$ and
$\mathrm{G}$ in (6.7).

As mentioned previously, and upon closer examination of the QPCM shown in in
(6.6), it is easy to see that decoding for the $\mathrm{H}$ and $\mathrm{G}$
matrices can be done separately. Notice how this is visible in Figure 6.1,
where the leftmost subgraph is associated to the matrix $\mathrm{H}$, which is
used to decode $\mathbf{e}_{x}$, and the rightmost subgraph is associated to
the matrix $\mathrm{G}$, which is used to decode $\mathbf{e}_{z}$. Separate
decoding of these matrices is made possible by the nature of CSS
constructions, which results in syndrome nodes containing information only of
either $X$ or $Z$ operators, hence why we can write
$\mathbf{w}=[\mathbf{w}_{x},\mathbf{w}_{z}]$. This is reflected on the factor
graph by the fact that a specific $\mathrm{s}$ node connects to either a
$\mathrm{d}_{x}$ or a $\mathrm{d}_{z}$ node. Note that, for notation purposes,
we refer to the syndrome nodes of the factor graph (top level diamonds in
Figure 6.1) as $\mathrm{s}$ nodes.

Figure 6.1: Decoding graph for a QLDGM CSS scheme. The dotted line is included
to emphasize the separation of the two constituent subgraphs. The top layer
nodes (diamonds) represent the syndrome nodes, which we will denote as
$\mathrm{s}$ nodes. The leftmost subgraph decodes the $X$ operators while the
one on the right decodes the $Z$ operators. We have assumed that
$m_{1}=m_{2}$, $n_{1}=n_{2}=\frac{N}{2}$, and $m=m_{1}+m_{2}$.

The matrix multiplications used to perform the linear row operations on
$\tilde{\mathrm{H}}$ and $\tilde{\mathrm{G}}$ generate a middle layer,
represented by the $\mathrm{c}$ and $\mathrm{d}$ nodes, in both decoding
subgraphs of Figure 6.1. This new layer hampers the decoding algorithm,
especially during the initial decoding iterations, since a priori information
regarding the aforementioned middle layer nodes is not be available. This can
be seen in Figure 6.2, where a generic quantum communication system is shown.
The LDGM decoder block of this figure, which runs the SPA over the graph shown
in Figure 6.1, has the syndrome $\mathbf{w}$ and the a priori probability of
the error pattern $P_{ch}$ as its inputs. However, it receives no information
pertaining to the $\mathrm{c}$ and $\mathrm{d}$ nodes.

Figure 6.2: Schematic of a quantum communication system using QLDGM codes. At
the transmitter, a QLDGM code with QPCM $\mathbf{H}_{Q}$ maps the quantum
state (logical qubits) $\ket{\psi}\in\mathcal{H}_{2}^{\otimes k}$ onto the
codeword (physical qubits) $\ket{\mkern
1.5mu\overline{\mkern-1.5mu\psi\mkern-1.5mu}\mkern
1.5mu}\in\mathcal{H}_{2}^{\otimes N}$ by using ($N-k$) ancilla qubits (denoted
in the figure by $\ket{0})$. At the receiver, the noisy codeword $\ket{\mkern
1.5mu\overline{\mkern-1.5mu\psi\mkern-1.5mu}\mkern 1.5mu}_{\xi}=E\ket{\mkern
1.5mu\overline{\mkern-1.5mu\psi\mkern-1.5mu}\mkern 1.5mu}$ is received, where
$E\in\mathcal{G}_{N}$ is the error inflicted by the quantum channel. The
quantum state $\ket{\mkern 1.5mu\overline{\mkern-1.5mu\psi\mkern-1.5mu}\mkern
1.5mu}_{\xi}$ is processed by the syndrome computation block at the decoder to
compute its error syndrome $\mathbf{w}$. The ancilla qubits at the input of
the syndrome computation block are necessary to physically implement the
syndrome calculation. Together with the a priori channel information $P_{ch}$,
$\mathbf{w}$ is provided to the syndrome based LDGM decoder, which yields an
estimate of the original error pattern $\hat{E}$. The recovery operator
$\mathcal{R}$ uses $\hat{E}$ to correct the noisy codeword. Finally, the
inverse encoder yields an estimate of the logical qubits $\hat{\ket{\psi}}$
from the corrected codeword $\hat{\ket{\mkern
1.5mu\overline{\mkern-1.5mu\psi\mkern-1.5mu}\mkern 1.5mu}}$.

In [21], the authors circumvent this lack of information by using the so-
called doping technique of [182]. This method introduces degree-1 syndrome
nodes into the decoding graph. These degree-1 nodes, which we will refer to as
$\mathrm{s}_{A}$ nodes, transmit correct information to the $\mathrm{d}$ nodes
they are connected to, ultimately pushing the decoding process in the right
direction. They are embodied within the $\mathrm{M}_{1}$ and $\mathrm{M}_{2}$
matrices as rows with a single non-zero entry, which corresponds to the edge
that connects a given $\mathrm{s}_{A}$ node to a $\mathrm{d}$ node. The other
rows of matrices $\mathrm{M}_{1}$ and $\mathrm{M}_{2}$, which correspond to
the rest of the $\mathrm{s}$ nodes, have as many non-zero entries as required
to guarantee the regularity444Regularity in this context implies that all the
$d$ nodes have the same degree, i.e, that they are all connected to the same
number of $\mathrm{s}$ nodes. of the $\mathrm{d}$ nodes and the necessary
number of $\mathrm{s}_{A}$ nodes. This results in matrices $\mathrm{M}_{1}$
and $\mathrm{M}_{2}$ having a special degree distribution which is described
by means of the notation $(y;1,x)$ and the parameter $t$, where $y$ represents
the degree of the $\mathrm{d}$ nodes, $t$ is the number of syndrome nodes that
are forced to have degree 1 (they become $\mathrm{s}_{A}$ nodes), and $x$
represents the degree of the remaining syndrome nodes, referred to as
$\mathrm{s}_{B}$ nodes.

Given the particular structure of the $\mathrm{M}_{1}$ and $\mathrm{M}_{2}$
matrices and the number of different types of nodes that are present in the
factor graph shown in Figure 6.1, the sum-product decoding of these quantum
LDGM CSS codes becomes relatively nuanced. The reason for deriving a complex
graph like the one shown in Figure 6.1 is that decoding over it is different
to decoding over the graph associated to the matrix $\mathbf{H}_{Q}$ that
results from the product shown in (6.6). This occurs because the matrix
products $\mathrm{M}_{1}\mathrm{\tilde{H}}$ and
$\mathrm{M}_{2}\mathrm{\tilde{G}}$ eliminate some edges and introduces more
cycles, which negatively impacts the performance of the SPA [183]. This is is
similar to what happens for serial concatenated LDGM schemes in classical
error correction [184]. Therefore, although decoding over the graph associated
to the set of matrix products shown in Figure 6.1 is more complex than doing
so over the factor graph associated to the final matrix $\mathbf{H}_{Q}$, it
is worth doing so for the sake of performance. In [176], a technique known as
Discretized Density Evolution (DDE) [114] is applied to optimize the design of
quantum LDGM CSS codes and a complete description of how the decoding process
unfolds over the graph shown in Figure 6.1 is provided.

###  6.3 Design of non-CSS LDGM-based codes

We know from the previous section that LDGM-based CSS codes can be decoded
over two separate (sub)graphs like the ones shown in Figure 6.1. This is made
possible by the specific nature of the quantum PCMs of CSS codes (6.2), and is
visible on a CSS decoding graph by the fact that any given $\mathrm{s}$ node
can only be connected to either $\mathrm{d}_{x}$ or $\mathrm{d}_{z}$ nodes: a
subset of $\mathrm{s}$ nodes is used to decode the $X$ operators (the $X$
component of the symplectic representation of the error sequence
$\mathbf{e}_{x}$) and another subset is used to decode the $Z$ operators (the
$Z$ component of the symplectic representation of the error sequence
$\mathbf{e}_{z}$).

The main appeal of non-CSS codes is their ability to exploit redundancy more
efficiently than CSS schemes. In our proposed non-CSS construction, we achieve
this by allowing edges from a given $\mathrm{s}$ node to go to both
$\mathrm{d}_{x}$ and $\mathrm{d}_{z}$ nodes. The first method that comes to
mind to implement this idea is to randomly distribute the edges of the upper
layer of the graph in a manner that ensures that $\mathrm{s}$ nodes are
connected to both $\mathrm{d}_{x}$ and $\mathrm{d}_{z}$ nodes. However,
attempting to decode the $X$ and $Z$ parts over a decoding graph with
$\mathrm{s}$ nodes whose edges have been haphazardly assigned to both
$\mathrm{d}_{x}$ and $\mathrm{d}_{z}$ nodes will cause numerous decoding
problems. For instance, not defining a specific distribution for these edges
inadvertently causes a reduction in the number of $\mathrm{s}_{A}$ nodes, and
not limiting their total number causes a reduction in the values of the log-
likelihood messages exchanged in the decoding process, which severely degrades
the decoding performance. Therefore, it is important to optimally design the
upper layer of the decoding graph when constructing a non-CSS QLDGM based
code. Devising a proper way of distributing the connections among
$\mathrm{s}$, $\mathrm{d}_{x}$, and $\mathrm{d}_{z}$ nodes in the decoding
graph is paramount to construct good non-CSS LDGM-based quantum codes.

####  6.3.1 Proposed procedure for the construction of non-CSS QLDGM codes

We begin the non-CSS design process by using a CSS quantum code based on
classical LDGM codes [21, 22, 155, 176] as the starting point. For the sake of
simplicity and comparison continuity, we maintain the requirements enforced in
[155, 176]: the matrices used to perform linear row operations are equal to
each other $\mathrm{M}_{1}=\mathrm{M}_{2}=\mathrm{M}$, and the degree
distribution of $\mathrm{P}^{\top}$ and $\mathrm{P}$ is the same.

The CSS QLDGM code used as a starting point will be associated to two separate
decoding subgraphs, one for $\mathrm{H}$ and the other for $\mathrm{G}$. The
upper layers of these subgraphs (the number and degree distribution of the
$\mathrm{d}$, $\mathrm{s}_{A}$, and $\mathrm{s}_{B}$ nodes) will be defined by
two identical matrices $\mathrm{M}$ of size $m\times\frac{N}{2}$ described by
$(y;1,x)$ which have $t$ rows with a single non-zero entry.

We can build our non-CSS scheme using two different strategies. Given that
both of them involve very similar procedures, we begin by explaining the
simplest construction method. Then, we will present the second proposed design
technique.

#####  6.3.1.1 Method 1: Syndrome node combination

Non-CSS codes based on the first strategy are constructed as follows:

  1. 1.

First, generate a new matrix, $\mathrm{M}_{d}$, as

$\mathrm{M}_{d}=\begin{pmatrix}\mathrm{M}_{m\times\frac{N}{2}}&0_{m\times\frac{N}{2}}\\\
0_{m\times\frac{N}{2}}&\mathrm{M}_{m\times\frac{N}{2}}\end{pmatrix}_{2m\times
N}.$ (6.10)

  2. 2.

Select $q$ nodes out of the $2t$ $\mathrm{s}_{A}$ nodes of matrix
$\mathrm{M}_{d}$555Note that $\mathrm{M}_{d}$, as defined in (6.10), is the
matrix representation of the upper layer of the graph in Figure 6.1., which we
will refer to as $\mathrm{s}_{C}$ nodes, and add an edge from these nodes to
the $\mathrm{d}$ nodes on the side of the decoding graph they are not
connected to. We apply a criterion to ensure these new connections are not
made randomly: the edges added to the $q$ selected $s_{A}$ nodes can only be
made to a $\mathrm{d}$ node ($\mathrm{d}_{x}$ or $\mathrm{d}_{z}$) that is a
$\mathrm{d}_{A}$ node. We define $\mathrm{d}_{A}$ nodes as any $\mathrm{d}$
nodes that are connected to an $\mathrm{s}_{A}$ node. Of the $q$
$\mathrm{s}_{C}$ nodes, half of them proceed from $\mathrm{s}_{A}$ nodes in
the CSS subgraph used to decode the $X$ operators, while the other half come
from $\mathrm{s}_{A}$ nodes in the CSS subgraph used to decode the $Z$
operators. Figure 6.3 illustrates how an $\mathrm{s}_{C}$ node is generated.

Figure 6.3: Generation of an $\mathrm{s}_{C}$ node. The upper nodes represent
the syndrome nodes while the bottom nodes represent the $\mathrm{d}$ nodes
($\mathrm{d}_{x}$ and $\mathrm{d}_{z}$ denote the $\mathrm{d}$ nodes
associated to each of the separate CSS decoding subgraphs). The
$\mathrm{s}_{A}$ nodes are represented in yellow, the $\mathrm{d}_{A}$ nodes
are shown in red, and the $\mathrm{s}_{C}$ node is pictured in green.

The reasoning behind adding edges that traverse the $X$ and $Z$ sides of the
graph only to $\mathrm{s}_{A}$ nodes is based on the following considerations:
First, transforming an $\mathrm{s}_{A}$ node into an $\mathrm{s}_{C}$ node
implies that the new node no longer provides perfect syndrome information,
given that it is now connected to two $\mathrm{d}$ nodes. However, the fact
that an $\mathrm{s}_{C}$ node only has two edges implies that its syndrome
information, although not transferred exactly, still has high impact when
computing messages for associated nodes. At the same time, the edge that
traverses from the $\mathrm{s}_{C}$ node to the other side of the factor graph
(either $\mathrm{d}_{x}$ or $\mathrm{d}_{z}$) reaches a $\mathrm{d}_{A}$ node.
Considering that messages from $\mathrm{d}_{A}$ nodes are more likely to be
correct (they are connected to an $\mathrm{s}_{A}$ node), coupled with the
fact that $\mathrm{s}_{C}$ node syndrome information still plays an important
role in the messages that the node computes, it is reasonable to assume that
$\mathrm{s}_{C}$ nodes relay accurate information and that they behave in a
similar manner to $\mathrm{s}_{A}$ nodes. Therefore, $\mathrm{s}_{C}$ nodes
provide a way in which reliable messages can be exchanged between both sides
of the factor graph, which should have a positive impact on decoding and
improve performance.

It is important to note that if we were to add a cross-graph edge to an
$\mathrm{s}_{B}$ node, because of its high degree, the messages received over
this new edge would play a limited role in the computations made by the node.
By association, the cross-graph messages transmitted over the new edge would
also have a very limited effect on the computation of messages exchanged on
the other side of the graph and little performance improvement, if any, would
be obtained.

Notice that at this stage we have transformed $\mathrm{M}_{d}$ into a new
matrix $\mathrm{M}^{\prime}_{d}$, modifying the upper layer of the original
CSS decoding graph of Figure 6.1 in the following manner:

     * •

There are $q$ $\mathrm{s}_{C}$ nodes that are connected to both sides of the
graph.

     * •

Some $\mathrm{d}$ nodes are connected to both $\mathrm{s}_{A}$ and
$\mathrm{s}_{C}$ nodes.

These modifications force the $\mathrm{s}$ and $\mathrm{d}$ nodes of the non-
CSS decoding graph to have a somewhat irregular edge distribution. Indeed, the
“regularity” of the $\mathrm{d}$ nodes has been violated in order to connect
the separate CSS decoding subgraphs, resulting in $\frac{q}{2}$
$\mathrm{d}_{x}$ nodes and $\frac{q}{2}$ $\mathrm{d}_{z}$ nodes having an
additional edge. Furthermore, $q$ $\mathrm{s}$ nodes now have two edges, one
of them directed towards a $\mathrm{d}_{x}$ node and the other towards a
$\mathrm{d}_{z}$ node.

It is intuitive to think that the performance of this novel non-CSS structure
should at least be as good, if not better, than that of the CSS scheme
utilized as a starting point, provided that the parameter $q$ is chosen
properly. If we select $q<<m$, the decrease in the number of $\mathrm{s}$
nodes providing perfect information will be small and should have negligible
impact in the decoding process666A total of $q$ $\mathrm{s}_{A}$ nodes get
converted into $\mathrm{s}_{C}$ nodes, which do not provide perfect
information.. On the contrary, the degree-2 $\mathrm{s}_{C}$ nodes allow the
exchange of information between both sides of the graph as the iterative
decoding process progresses, potentially improving the decoding performance.
Therefore, we expect this scheme to present its best performance for a
specific range of small values of $q$, with deterioration occurring when $q$
is increased beyond this range.

#####  6.3.1.2 Method 2: Syndrome node combination + removal of
$\mathrm{s}_{A}$ nodes

The second design technique removes $q$ syndrome nodes from the decoding graph
generated by the first method, specifically the $q$ $\mathrm{s}_{A}$ nodes
connected to a $\mathrm{d}_{A}$ node that is linked to an $\mathrm{s}_{C}$
node. The process is shown in Figure 6.4. Notice that with this construction
the regularity of the $d$ nodes is maintained and the data rate of the code is
increased777By eliminating syndrome nodes we are decoding the same number of
qubits using less syndrome information.. Moreover, as long as the number of
removed $\mathrm{s}_{A}$ nodes is not too large, the impact on decoding should
be minimal: although $\mathrm{s}_{C}$ nodes do not provide “perfect”
information, much of the reliability of the messages they transmit to the
corresponding $\mathrm{d}$ (previously $\mathrm{d}_{A}$) nodes will be kept,
as they only have two edges. This should mitigate any impact on performance.
Because method 2 requires the removal of some $\mathrm{s}_{A}$ nodes, compared
with the CSS code used as a starting point, a larger amount of
$\mathrm{s}_{A}$ nodes may be necessary in the non-CSS structure to ensure
acceptable performance as the value of $q$ grows. This hints towards an
increased importance of applying doping (increasing the value of $t$) to the
constituent matrices $\mathrm{M}$.

Figure 6.4: Removal of an $\mathrm{s}_{A}$ (yellow) node that was previously
used to generate an $\mathrm{s}_{C}$ (green) node.

Once the specific $s_{A}$ nodes are removed, we obtain a new matrix
$\mathrm{M}^{\prime}_{d}$ of size $(2m-q)\times N$, which has the following
characteristics:

  * •

It has $2(t-q)$ rows with a single nonzero entry. In terms of the decoding
graph, this means that there are $2(t-q)$ $\mathrm{s}_{A}$ nodes.

  * •

There are $q$ rows with two nonzero entries. The first entry must be placed in
any of the first $\frac{N}{2}$ columns of the matrix while the second one must
be placed in any of the last $\frac{N}{2}$ columns. This ensures that
$\mathrm{s}_{C}$ nodes connect both sides of the decoding graph.

  * •

The other $2(m-t)$ rows have $x$ nonzero entries. In the decoding graph, these
rows correspond to the $\mathrm{s}_{B}$ nodes, which remain the same as in the
CSS structure used as a starting point.

#####  6.3.1.3 Non-CSS QPCM

The quantum PCM of the proposed non-CSS code obtained using either of the
aforementioned methods is calculated as

$\displaystyle\mathbf{H}_{Q_{\text{nonCSS}}}=\mathrm{M}^{\prime}_{d}\mathbf{H}_{\text{CSS}}=\mathrm{M}^{\prime}_{d}(\mathrm{H}_{x}|\mathrm{H}_{z})$
$\displaystyle=\mathrm{M}^{\prime}_{d}\begin{pmatrix}\tilde{\mathrm{H}}&0\\\
0&\tilde{\mathrm{G}}\end{pmatrix}=(\mathrm{H}_{x}^{\prime\prime}|\mathrm{H}_{z}^{\prime\prime}),$
(6.11)

where $\mathbf{H}_{\text{CSS}}$ is defined as in (6.2), $\tilde{\mathrm{H}}$
and $\tilde{\mathrm{G}}$ are the parity check and generator matrices of a
classical LDGM code, and $\mathrm{M}^{\prime}_{d}$ is obtained using any of
the construction methods.

As shown below, the construction in (6.3.1.3) satisfies the symplectic
criterion given in (4.23). Assume that $\mathrm{M}^{\prime}_{d}$ is obtained
based on the second construction method presented above. With the goal of
simplifying the proof, we write $[\mathrm{M}^{\prime}_{d}]_{m_{r}\times N}$ as
the concatenation of two sub-matrices, i.e.,
$[\mathrm{M}^{\prime}_{d}]_{m_{r}\times
N}=[\mathrm{M}^{\prime}_{\alpha_{m_{r}\times\frac{N}{2}}}\mathrm{M}^{\prime}_{\gamma_{m_{r}\times\frac{N}{2}}}]$.
Substituting this expression into (6.3.1.3), we obtain

$\displaystyle\mathbf{H}_{Q_{\text{nonCSS}}}$
$\displaystyle=(\mathrm{H}_{x}^{\prime\prime}|\mathrm{H}_{z}^{\prime\prime})$
$\displaystyle=[\mathrm{M}^{\prime}_{d}]_{m_{r}\times
N}\mathbf{H}_{\text{CSS}_{N\times 2N}}$
$\displaystyle=[\mathrm{M}^{\prime}_{\alpha_{m_{r}\times\frac{N}{2}}}\mathrm{M}^{\prime}_{\gamma_{m_{r}\times\frac{N}{2}}}]\begin{pmatrix}\tilde{\mathrm{H}}_{\frac{N}{2}\times
N}&0_{\frac{N}{2}\times N}\\\ 0_{\frac{N}{2}\times
N}&\tilde{\mathrm{G}}_{\frac{N}{2}\times N}\end{pmatrix}$
$\displaystyle=\bigg{(}[\mathrm{M}^{\prime}_{\alpha_{m_{r}\times\frac{N}{2}}}\tilde{\mathrm{H}}_{\frac{N}{2}\times
N}]_{m_{r}\times N}\ \big{|}\
[\mathrm{M}^{\prime}_{\gamma_{m_{r}\times\frac{N}{2}}}\tilde{\mathrm{G}}_{\frac{N}{2}\times
N}]_{m_{r}\times N}\bigg{)},$

where $m_{r}=2m-q$ is the total number of rows of $\mathrm{M}^{\prime}_{d}$.

Since for an LDGM code
$\tilde{\mathrm{G}}\tilde{\mathrm{H}}^{T}=\tilde{\mathrm{H}}\tilde{\mathrm{G}}^{T}=0$,
when checking the symplectic criterion, we obtain

$\displaystyle\mathrm{H}_{x}^{\prime\prime}\mathrm{H}_{z}^{\prime\prime\top}\oplus\mathrm{H}_{z}^{\prime\prime}\mathrm{H}_{x}^{\prime\prime\top}=$
$\displaystyle\bigg{(}[\mathrm{M}^{\prime}_{\alpha_{m_{r}\times\frac{N}{2}}}\tilde{\mathrm{H}}_{\frac{N}{2}\times
N}][\mathrm{\mathrm{M}}^{\prime}_{\gamma_{m_{r}\times\frac{N}{2}}}\tilde{\mathrm{\mathrm{G}}}_{\frac{N}{2}\times
N}]^{\top}$
$\displaystyle\oplus[\mathrm{M}^{\prime}_{\gamma_{m_{r}\times\frac{N}{2}}}\tilde{\mathrm{G}}_{\frac{N}{2}\times
N}][\mathrm{M}^{\prime}_{\alpha_{m_{r}\times\frac{N}{2}}}\tilde{\mathrm{H}}_{\frac{N}{2}\times
N}]^{\top}\bigg{)}$
$\displaystyle=\bigg{(}\mathrm{M}^{\prime}_{\alpha_{m_{r}\times\frac{N}{2}}}\underbrace{\tilde{\mathrm{H}}_{\frac{N}{2}\times
N}\tilde{\mathrm{G}}^{\top}_{N\times\frac{N}{2}}}_{0_{\frac{N}{2}\times\frac{N}{2}}}\mathrm{M}^{\prime\top}_{\gamma_{\frac{N}{2}\times
m_{r}}}$
$\displaystyle\oplus\mathrm{M}^{\prime}_{\gamma_{m_{r}\times\frac{N}{2}}}\underbrace{\tilde{\mathrm{G}}_{\frac{N}{2}\times
N}\tilde{\mathrm{H}}^{T}_{N\times\frac{N}{2}}}_{0_{\frac{N}{2}\times\frac{N}{2}}}\mathrm{M}^{\prime\top}_{\alpha_{\frac{N}{2}\times
m_{r}}}\bigg{)}$ $\displaystyle=0_{m_{r}\times m_{r}}$

proving that $\mathbf{H}_{Q_{\text{nonCSS}}}$ satisfies the symplectic
criterion.

#####  6.3.1.4 Mixture of both methods

Another possibility to design non-CSS codes is to remove only a fraction of
the $\mathrm{s}_{A}$ nodes that are used to generate $\mathrm{s}_{C}$ nodes in
the first construction method. This procedure is identical to the second
technique, with the sole exception that instead of removing the entire subset
of $q$ $\mathrm{s}_{A}$ syndrome nodes involved in the generation of the
$\mathrm{s}_{C}$ nodes, only $l<q$ $\mathrm{s}_{A}$ nodes are removed. In the
following section, we focus on codes obtained using the first two methods.
Optimizing the performance of codes derived using this third approach may be
of interest in future work.

####  6.3.2 Decoding non-CSS QLDGM codes

Independently of the design method, decoding of the novel non-CSS quantum
codes is performed utilizing the sum-product algorithm over the factor graph
defined by the product $\mathrm{M}^{\prime}_{d}\times\mathbf{H}_{\text{CSS}}$.
Message passing will differ from that performed at a CSS QLDGM decoder, in the
sense that both sides of the graph interact during the decoding process
(messages are exchanged between nodes on the left and right subsections of the
graph). This occurs because of the modified upper layer in the decoding graph
of the non-CSS code, as shown in Figure 6.5 for a non-CSS code derived using
the first design method.

Figure 6.5: Upper layer of the decoding graph associated to a non-CSS code
obtained using method 1. The upper nodes represent the syndrome nodes, while
the bottom nodes represent the $\mathrm{d}$ nodes ($\mathrm{d}_{x}$ and
$\mathrm{d}_{z}$ denote the $\mathrm{d}$ nodes associated to each of the
original separated CSS decoding subgraphs). The $\mathrm{s}_{A}$ nodes are
represented in yellow and the $\mathrm{s}_{C}$ nodes are pictured in green.

####  6.3.3 Rate considerations

Both design methods allow a high degree of flexibility in terms of selecting
the rate of the non-CSS quantum code. In fact, different non-CSS codes of the
same rate can be obtained depending on the selected design method. Consider an
arbitrary non-CSS code of quantum rate $R_{Q}$ obtained based on the first
design method taking as a starting point a CSS code of the same rate. A
different non-CSS code of rate $R_{Q}$ can be obtained by using the second
design method, taking as a starting point a CSS code of lower rate. In fact,
the second construction technique allows us to build multiple matrices
$\mathrm{M}^{\prime}_{d}$ of equal size (which will lead to codes of equal
quantum rate) by starting from different matrices $\mathrm{M}$ (and thus from
CSS codes of different rates) and varying the parameter $q$, which represents
number of $\mathrm{s}_{A}$ nodes that are removed. For instance, we could
design a matrix $\mathrm{M}^{\prime}_{d_{1}}$ of size $(2m_{1}-q_{1})\times N$
using two matrices $\mathrm{M}_{1}$ of size $m_{1}\times\frac{N}{2}$, and
construct a second matrix $\mathrm{M}^{\prime}_{d_{2}}$ of size
$(2m_{2}-q_{2})\times N$ using two matrices $\mathrm{M}_{2}$ of size
$m_{2}\times\frac{N}{2}$. If $2m_{1}-q_{1}=2m_{2}-q_{2}$, then both codes will
have the same rate. Therefore, when the second method is utilized, code
optimization depends on the choice of matrix $\mathrm{M}_{d}$, as well as
parameters $m$ and $q$.

Notice that for a fixed $m\times N$ matrix $\mathrm{M}$, by using the second
design method and varying the value of $q$, we obtain different matrices
$\mathrm{M}^{\prime}_{d}$ of size $(2m-q)\times 2N$. This will result in non-
CSS codes that encode $N-(2m-q)$ logical qubits into $N$ physical qubits, and
thus their rate will be

$R_{Q,\text{non-CSS}}=\frac{N-(2m-q)}{N}.$ (6.12)

Since $q>0$, $R_{Q,\text{non-CSS}}$ is always higher than the rate of the CSS
QLDGM code used as a starting point, which is given by

$R_{Q,\text{CSS}}=\frac{N-2m}{N}.$ (6.13)

Notice that if the non-CSS code obtained from method 2 maintains the same
performance as the original CSS code, this will be achieved with a higher
rate. We introduce the parameter $R_{I}$, defined as

$R_{I}=R_{Q,\text{non-CSS}}-R_{Q,\text{CSS}}=\frac{q}{N-2m},$ (6.14)

to quantify the rate increase provided by the non-CSS scheme derived using the
second construction method when compared to the original CSS scheme. This rate
increase is determined by the value of $q$, which for the second design method
represents the number of $\mathrm{s}_{C}$ nodes in the non-CSS decoding graph,
as well as the number of $\mathrm{s}_{A}$ nodes removed from the decoding
graph of the CSS code used as a starting point. The value of $q$ will
influence the performance of the resulting non-CSS code: intuitively, large
increases in its value should lead to worsened performance, as the doping
effect is reduced, but $q>0$ allows for information exchange between the left
and the right sides of the decoding graph, which should have a positive effect
on performance. The impact of $q$ on the proposed schemes is studied in the
following section.

###  6.4 Simulation Results

In this section we compare the performance of the proposed non-CSS codes to
that of the CSS codes of [155] and [176] when they are used over the i.i.d.
$X/Z$ channel and the depolarizing channel. The CSS codes in [155] and [176]
have rate $R_{Q}\approx\frac{1}{4}$ and block length $N=19014$, encoding
$k=4752$ qubits into $N$ qubits. Matrix $\mathrm{P}$, of size $9507\times
9507$, has the same degree distribution as its transpose $\mathrm{P}^{\top}$,
and corresponds to a rate $\frac{1}{2}$ classical LDGM code. Hence, both
$\tilde{\mathrm{G}}$ and $\tilde{\mathrm{H}}$ have size $9507\times 19014$.
Matrix $\mathrm{M}$, which is used to transform $\tilde{\mathrm{G}}$ and
$\tilde{\mathrm{H}}$ into $\mathrm{G}$ and $\mathrm{H}$, is full-rank, low-
density, and has size $7131\times 9507$. Results are depicted in terms of
either the Qubit Error Rate (QBER) or the Word Error Rate (WER). QBER
represents the fraction of qubits that experience an error, while WER is the
fraction of transmitted blocks that have at least one qubit error. We use the
QBER metric for some of our simulations because it can be estimated with high
confidence faster than the WER, which is helpful in shortening the required
simulation time of some of our codes. Readers should refer to Appendix C for a
more complete explanation on how these simulations have been conducted.

First, the codes are simulated over the i.i.d. $X/Z$ channel model of [18],
where $Z$ and $X$ errors are modeled as independent events identically
distributed according to the flip probability $f_{m}$. We begin by using as a
starting point the family of CSS codes of the first proposed structure in
[155] and [176], which are individual regular LDGM codes. The simplicity of
the channel model and of the code structure allow us to assess, in a rapid and
efficient manner, the values of $q$ that optimize the performance of the non-
CSS construction. Using these values of $q$, we will repeat the simulations
when the CSS codes used as the starting point consist of the parallel
concatenation of regular LDGM codes, as described in [155, 176]. Both design
methods are utilized to obtain the resulting non-CSS codes. Finally, we repeat
the same process for the depolarizing channel.

####  6.4.1 i.i.d. X/Z channel - Non-CSS codes based on individual regular
LDGM codes

For these simulations, the CSS code utilized as a starting point is an
individual regular LDGM code. Matrix $\mathrm{P}$ is generated pseudorandomly
and corresponds to a regular $(X,X)$ LDGM code. $\mathrm{M}$ is characterized
by the parameter values888The fractional number $8.72$ represents the fact
that $72\%$ of the $\mathrm{s}_{B}$ nodes will have degree 9 while $28\%$ of
them will have degree 8. $\mathrm{M}(3;1,8.72)$ and $t=4361$. The
degrees999Given that the degree distribution of $\mathrm{P}^{\top}$ and
$\mathrm{P}$ is the same, we refer to them indistinctly throughout this paper.
of $\mathrm{P}$ (and $\mathrm{P}^{\top}$) are varied between $(9,9)$ and
$(13,13)$. In the figures that follow, $f_{m}$ is the probability of error in
each separate $X$ and $Z$ error channels and the analytical error floors of
the LDGM codes have been obtained as shown in [183].

#####  6.4.1.1 Non-CSS codes derived using method 1

As explained before, non-CSS codes based on this method are obtained by
transforming $q$ $\mathrm{s}_{A}$ nodes of the CSS decoding graph into
degree-2 $\mathrm{s}_{C}$ nodes. All the non-CSS codes obtained in this manner
have the same quantum rate ($R_{Q}=\frac{1}{4}$). Matrix $\mathrm{M}_{d}$ is
built from $\mathrm{M}$ as shown in (6.10). The rest of the underlying
components of the non-CSS configuration are identical to those of the CSS
designs101010The only difference between the CSS and non-CSS codes lies in
matrix $\mathrm{M}^{\prime}_{d}$. The rate $\frac{1}{2}$ classical LDGM code
and, therefore, matrices $\mathrm{P}$, $\tilde{\mathrm{G}}$, and
$\tilde{\mathrm{H}}$, are identical.. We test three different configurations,
$q=[100,750,1500]$, for different degrees of the $\mathrm{P}$ matrices. The
simulation results, which are shown in Figure 6.6 reflect how for $q=100$ and
$q=750$, regardless of the degree of the pseudorandom matrix $\mathrm{P}$, the
performance of the proposed non-CSS codes is slightly better than that of the
CSS schemes used as a starting point. This performance improvement is most
notable for the case of $\mathrm{P}(13,13)$, where, as $f_{m}$ increases, the
non-CSS schemes operate closer than the original CSS code to the analytical
error-floor. However, for $q=1500$, the performance of the non-CSS code is
worse than that of the CSS scheme. The best results are observed when the non-
CSS code is designed using $q=750$.

Figure 6.6: Simulated WER for non-CSS QLDGM codes based on individual regular
LDGM codes obtained using the first design method when they are applied over
the flipping channel. $f_{m}$ is the probability of error in each separate $X$
and $Z$ error channel.

#####  6.4.1.2 Non-CSS codes derived using method 2

Earlier we saw how non-CSS codes derived using method $2$ are obtained by
removing $q$ syndrome nodes from the decoding graph generated by the first
method, specifically the $q$ $\mathrm{s}_{A}$ nodes connected to a
$\mathrm{d}_{A}$ node that is linked to an $\mathrm{s}_{C}$ node. Note that
removing syndrome nodes will result in codes with different quantum rates. As
previously, we test the values $q=[100,750,1500]$ for different degrees of the
$\mathrm{P}$ matrices. The results are shown in Figure 6.7.

The results displayed in Figure 6.7 are once again consistent regardless of
the degree of $\mathrm{P}$. They show how for the two smaller $q$ values,
$100$ and $750$, the non-CSS codes yield the same performance as the CSS
schemes of [155]. For $q=1500$, the performance of the non-CSS codes is
significantly worse. For instance, at a value of $f_{m}=0.04$, the word error
rate for the $q=1500$ schemes is around an order of magnitude higher than for
the $q\leq 750$ non-CSS schemes. This corroborates our intuition that there is
an optimum range of values for $q$, and that utilizing values outside of that
range degrades the code performance. Based on the results in Figure 6.7, the
optimal value of $q$ should be a small percentage of the total number of
syndrome nodes $m$, $q<0.1\times m$ ($\frac{1500}{14262}\approx 0.1$).

Figure 6.7: Simulated WER for non-CSS QLDGM codes based on individual regular
LDGM codes obtained using the second design method when they are applied over
the flipping channel. $f_{m}$ is the probability of error in each separate $X$
and $Z$ error channel.

Table LABEL:table presents the WER performance for the codes considered in
Figure 6.7 when matrix $\mathrm{P}$ has degrees $(13,13)$ and $f_{m}=0.03$.
The CSS scheme has rate $R_{Q-\text{CSS}}=\frac{19014-2\times
7131}{19014}=0.2499$. Results for the $q=1500$ non-CSS scheme have not been
included, since the performance of the original CSS scheme is better. As with
the first method, the best result here is obtained for the $q=750$ non-CSS
scheme, which achieves similar performance to that of the CSS code with an
approximately $15\%$ higher rate ($R_{I}\approx 0.158$).

Overall, the results obtained for both design methods illustrate that our
proposed non-CSS codes, regardless of the design method, outperform QLDGM CSS
codes when individual regular LDGM codes are utilized. The first design method
provides a way to obtain non-CSS codes that outperform CSS codes of the same
rate. The second method enables us to construct non-CSS codes with error
correcting capabilities comparable to those of lower rate CSS schemes.
Therefore, to design non-CSS codes of a fixed rate, we could apply the first
design method to a CSS code of the same rate, or we could start with a CSS
code of lower rate and apply the second method. In this case, we should
carefully chose the rate of the original CSS code to obtain the desired rate
in the designed non-CSS code.

Table 6.1: Comparison between the codes shown in Figure 6.7. The WER data included in the table corresponds to the codes whose $\mathrm{P}$ matrix has degrees $(13,13)$. Code Type | $R_{Q}$ | $q$ | WER @ $f_{m}=0.03$
---|---|---|---
CSS | 0.2499 | - | $7.12\times 10^{-}3$
non-CSS | 0.2551 | 100 | $7.26\times 10^{-}3$
non-CSS | 0.2893 | 750 | $7.13\times 10^{-}3$

####  6.4.2 i.i.d. X/Z Channel - Non-CSS codes based on the parallel
concatenation of LDGM codes

As mentioned in section 6.1.4, regular LDGM codes used in classical channels
present error floors. Fortunately, these error floors can be substantially
lowered if we use the parallel concatenation of two regular LDGM codes. In
[21], [22] CSS quantum codes based on the use of single regular LDGM codes
were shown to also exhibit error floors. Inspired by the good performance
displayed by parallel LDGM codes in the classical domain, a scheme based on
the parallel concatenation of LDGM codes was designed and applied to the
i.i.d. $X/Z$ channel in [155] and [176]. Similar to the classical scenario,
CSS codes built based on the parallel structure display lower error floors and
better performance overall.

We now repeat the study carried out in the previous subsection, but using the
parallel concatenation of regular LDGM codes as the starting point to derive
our proposed non-CSS codes. In [176], varios parallel111111The notation
$\mathrm{P}[(y_{1},y_{1});(y_{2},z_{2})]$ indicates the degree distributions
of the constituent regular LDGM codes utilized in the parallel concatenation.
In [176], the parameters of the second code were typically chosen as
$z_{2}=20y_{2}$. LDGM structures $\mathrm{P}[(y_{1},y_{1});(y_{2},z_{2})]$
were employed. For our analysis we use the structure with the lowest degrees
that appears in [176]: $\mathrm{P}[(8,8);(3,60)]$. Although performance is
better when the degrees of the second code $(y_{2},z_{2})$ are larger, codes
with smaller values for these degrees require less processing and simulation
time. To ease simulation requirements even further, results in this subsection
are presented in terms of the QBER. The best configuration for
$\mathrm{P}[(y_{1},y_{1});(y_{2},z_{2})]$ in [176] will be used later for the
simulations over the depolarizing channel.

As we did for individual regular LDGM codes in the previous subsection, we
analyze the performance of the non-CSS codes obtained using the two design
methods proposed in section 6.3. The CSS code used as a starting point is the
same for both methods, and utilizes the same matrix $\mathrm{M}$ as in the
scenario for individual regular LDGM codes: $\mathrm{M}_{7131\times
9507}(3;1,8.72)$ and $t=4361$. We consider the values of
$q=\\{100,500,1000,1500\\}$. As before, $f_{m}$ is the probability of error in
each separate $X$ and $Z$ error channel and the analytical error floors of the
LDGM codes have been obtained as shown in [183].

Figure 6.8 presents the performance of the $R=\frac{1}{4}$ original CSS code
and of the $R=\frac{1}{4}$ non-CSS codes obtained by applying the first design
method. As shown in the figure, the non-CSS codes derived by selecting $q=100$
and $q=500$ outperform the original CSS structure. For $q>500$, performance of
the non-CSS codes gradually deteriorates, with the result for $q=1500$ being
substantially worse than that of the original CSS code.

Figure 6.9 shows the results for the non-CSS codes derived using the second
proposed design method. The curves shown in this figure portray how the
performance of the non-CSS codes is drastically degraded as we increase the
value of $q$. This effect is much more noticeable than for codes based on a
single regular LDGM code. In fact, the only value for which the non-CSS
configuration based on parallel concatenation matches the performance of the
original CSS scheme is $q=100$, whereas in Figure 6.7 we could see that
schemes based on individual regular LDGM codes matched the performance of the
original CSS code at least up to $q=750$. In essence, although the
$\mathrm{s}_{A}$ node elimination step explained in section 6.3.1 still yields
a small benefit, this is much lower than for the case of single regular LDGM
codes.

Figure 6.8: Simulated QBER for a $R_{Q}=\frac{1}{4}$ CSS code and non-CSS
codes of $R_{Q}=\frac{1}{4}$ code derived using the first design methodology.
The underlying classical LDGM code is the same for all the codes and has
degree distribution $\mathrm{P}[(8,8);(3,60)]$. $f_{m}$ is the probability of
error in each separate $X$ and $Z$ error channel.

Throughout this chapter we have mentioned that the second non-CSS code design
methodology can be used not only to obtain higher rate non-CSS codes with
performance similar to that of lower rate CSS codes, but also to generate
different non-CSS codes of a fixed rate by varying the CSS codes used as
starting points and selecting the appropriate value of $q$. Analyzing the
performance of $R_{Q}=\frac{1}{4}$ non-CSS codes obtained in this manner and
comparing the results to those obtained using the first design method will
allow us to determine which design technique yields codes with better
performance.

Figure 6.9: Simulated QBER for a $R_{Q}=\frac{1}{4}$ CSS code and non-CSS
codes of different rate derived using the second design methodology. The
underlying classical LDGM code is the same for all the codes and has degree
distribution $\mathrm{P}[(8,8);(3,60)]$. $f_{m}$ is the probability of error
(iid) in each separate $X$ and $Z$ error channel.

This comparison is shown in Figure 6.10, where various $R_{Q}=\frac{1}{4}$
non-CSS codes obtained using the second design method are compared to the best
$R_{Q}=\frac{1}{4}$ code generated by the first design method ($q=500$ in
Figure 6.8) and to the original $R_{Q}=\frac{1}{4}$ CSS structure. The non-CSS
codes generated by method 2 are derived by building matrices
$\mathrm{M}^{\prime}_{d}$ using matrices $\mathrm{M}$ of different size, which
are designed according to the analysis conducted in [176]. We introduce
parameter $q^{\prime}$ to refer to the values of $q$ used to derive these
codes and to distinguish them from the code built using the first method.

The $q^{\prime}=100$ code uses $\mathrm{M}_{7181\times 9507}(3;1,8.56)$ with
$t=4361$ (using this $\mathrm{M}$ for a CSS QLDGM scheme would yield a code of
rate $R_{Q}=0.244$). The $q^{\prime}=500$ code uses $\mathrm{M}_{7381\times
9507}(3;1,8.36)$ with $t=4561$ (using this $\mathrm{M}$ for a CSS QLDGM scheme
would yield a code of rate $R_{Q}=0.2236$). The $q^{\prime}=1000$ code uses
$\mathrm{M}_{7631\times 9507}(3;1,8.27)$ with $t=4761$ (using this
$\mathrm{M}$ for a CSS QLDGM scheme would yield a code of rate
$R_{Q}=0.1973$).

Figure 6.10 shows that the non-CSS codes designed using the second method
outperform the CSS scheme for all values of $q^{\prime}$. However, the $q=500$
non-CSS code designed using the first method is still better than any of the
aforementioned codes, although the performance of the $q^{\prime}=100$ non-CSS
code is only slightly worse.

In this subsection we have discussed results for the i.i.d $X/Z$ Channel,
where the $X$ and $Z$ operators are modelled independently according to the
same distribution. Our analysis has allowed us to determine the design
methodologies and the values of $q$ that lead to the best performance. Making
use of this knowledge, we will now consider performance over the depolarizing
channel.

Figure 6.10: Simulated QBER for a $R_{Q}=\frac{1}{4}$ CSS code and
$R_{Q}=\frac{1}{4}$ non-CSS codes constructed using the two proposed design
methods. $q$ denotes how many $\mathrm{s}_{A}$ nodes have become
$\mathrm{s}_{C}$ nodes in the upper layer of the decoding graph when method 1
is applied. $q^{\prime}$ denotes how many $\mathrm{s}_{A}$ nodes have become
$\mathrm{s}_{C}$ nodes and how many $\mathrm{s}_{A}$ nodes have been removed
from the upper layer of the decoding graph when method 2 is used. The
underlying classical LDGM code is the same for all the codes and has degree
distribution $\mathrm{P}[(8,8);(3,60)]$. $f_{m}$ is the probability of error
(iid) in each separate $X$ and $Z$ error channel.

####  6.4.3 Depolarizing channel

We now focus on the depolarizing channel introduced in section 6.1.1. We
consider the best non-CSS codes obtained before for the i.i.d. $X/Z$ channel:
The $q=500$ $R_{Q}=\frac{1}{4}$ non-CSS code obtained using the first design
method and the $q=100$ $R_{Q}=0.255$ non-CSS code obtained using the second
method. Figure 6.11 shows the QBER of the aforementioned codes for two
different degree distributions of the parallel concatenated LDGM scheme. The
curves associated to the original CSS codes are also included.

Similar to the results for the i.i.d. $X/Z$ channel, Figure 6.11 portrays how
the $R_{Q}=0.255$ non-CSS codes display performance very close to that of the
$R_{Q}=\frac{1}{4}$ CSS schemes. This phenomenon can be explained for both the
depolarizing and the i.i.d. $X/Z$ channels by the nature of the non-CSS
construction, which adds a very small number of edges and removes very few
syndrome nodes from the original CSS factor graph. As in the case of the $X/Z$
channel model, the $q=500$, $R_{Q}=\frac{1}{4}$ non-CSS codes designed
utilizing method 1 also outperform the CSS code.

An important observation, which is reflected in Figure 6.11, is that the
results are consistent regardless of the degrees $(y_{2},z_{2})$ that are
chosen. This is significant, since increasing $y_{2}$ and $z_{2}$ enables us
to lower the error-floor of the QLDGM code. As shown in [155] and [176] for
CSS codes, we can see from Figure 6.11 that selecting $\mathrm{P}_{2}$ with
larger degrees lowers the error floor but worsens the decoding threshold.

Figure 6.11: Simulated QBER for three quantum codes: An $R_{Q}=\frac{1}{4}$
CSS QLDGM code, an $R_{Q}=\frac{1}{4}$ non-CSS QLDGM code obtained using the
first proposed method and $q=500$, and an $R_{Q}=0.255$ non-CSS QLDGM code
derived via the second design technique with $q=100$. All three codes have
been simulated for two different degree distributions of the underlying
parallel concatenated LDGM scheme: $\mathrm{P}[(8,8);(3,60)]$ and
$\mathrm{P}[(8,8);(5,100)]$. $p$ is the depolarizing probability. Figure 6.12:
Simulated QBER for the best $R=\frac{1}{4}$ CSS QLDGM code in [176] and the
best non-CSS QLDGM code designed in this paper. The Hashing bound is also
shown. The codes are based on the parallel concatenation of regular LDGM codes
with degree distribution $\mathrm{P}[(8,8);(8,160)]$. $p$ is the depolarizing
probability.

#####  6.4.3.1 Distance to the theoretical limit

The most effective way to characterize the performance improvement of our
proposed non-CSS codes is to measure their gap with respect to the Hashing
bound. For this comparison, we will employ the design parameters that yield
the best possible code. Such a scheme is obtained by using the first
construction method with $t=5000$, $q=500$, $\mathrm{M}(3;1,11.04)$, and a
parallel concatenated LDGM code of degree distribution
$\mathrm{P}[(8,8);(8,160)]$.

Figure 6.12 depicts the performance of this non-CSS scheme as well as that of
the CSS code used as a starting point for the design, which is the best CSS
code proposed in [176]. The Hashing bound for $R_{Q}=\frac{1}{4}$ is also
shown.

We compute the distance to the Hashing bound $\delta$ as defined in (6.1),
knowing that the the noise limit for $R_{Q}=\frac{1}{4}$ is $p^{*}\approx
0.127$, and taking $p_{\text{CSS}}=0.0825$ and $p_{\text{non-CSS}}=0.0865$ as
the depolarizing probabilities at which the CSS and non-CSS codes enter the
waterfall region, respectively. This yields $\delta_{\text{CSS}}=1.873$ dB and
$\delta_{\text{non-CSS}}=1.668$ dB. In other words, the non-CSS scheme is
about $0.2$ dB closer to the Hashing bound. Thus, in terms of overall
performance over the depolarizing channel, the non-CSS codes proposed in this
article outperform existing CSS techniques.

#####  6.4.3.2 Comparison with existing QLDPC schemes

We close out this section by studying how our proposed non-CSS codes measure
up against other QLDPC schemes in the literature. For this purpose, we conduct
two different comparisons. We begin by comparing the codes in Figure 6.12 to
other quantum codes of rate $\frac{1}{4}$ and then use a second comparison to
study how decoders capable of exploiting the correlation between $X$ and $Z$
operators match up to our non-CSS construction. The first comparison is shown
in Figure 6.13, which includes the performance for the following codes:

  * •

The CSS QLDGM code based on a single regular LDGM code from [22]. The degree
distribution of the underlying classical LDGM code is $\mathrm{P}(13,13)$. The
block length of the code is $19014$.

  * •

The $K=32$ bicycle code of block length $19014$ introduced by MacKay et al. in
[18].

  * •

The quantum serial turbo Code of [28], with block length $4000$.

  * •

The non-CSS concatenated code (Code $C$) from [63], with block length
$138240$.

Figure 6.13 shows that our proposed non-CSS QLDGM codes outperform existing
quantum turbo codes and previously proposed quantum LDPC codes.

##### Comparison to improved CSS decoding strategies

In Chapter $5$ we mentioned that CSS decoders capable of improving performance
by exploiting the correlation that exists between $X$ and $Z$ operators over
the depolarizing channel have been studied in the literature. Some of the
earliest work on this topic was conducted in [55], where a set of modified BP
decoders for CSS codes that reintroduce $X/Z$ correlations were proposed. The
most notable of these decoding schemes is known as the random perturbation
decoder. In [135], further work on the topic of modified BP decoders for CSS
codes was conducted and two novel CSS decoders were presented: the adjusted
decoder and the augmented decoder.

Figure 6.13: Word error rate for various quantum codes when they are applied
over the depolarizing channel. The Hashing bound is also included. $p$ is the
depolarizing probability.

The adjusted decoder attempts to reintroduce the correlations between $X$ and
$Z$ operators, neglected by a standard binary BP decoder, by adjusting prior
probabilities. The augmented decoder operates by appending a specific subset
of rows $\mathrm{H}_{\delta}$ from the original PCM $\mathbf{H}$ into an exact
copy of that matrix, resulting in an augmented PCM
$\mathbf{H}_{A}=\begin{pmatrix}\mathbf{H}\\\ \mathrm{H}_{\delta}\end{pmatrix}$
which is associated to a larger factor graph over which the decoding algorithm
is run. Also in [135], the adjusted and augmentation techniques are combined
to form a new CSS decoder known as the combined decoder. An in-depth look at
some of these modified decoding strategies is provided in Appendix B.

In Figure 6.14, we compare the performance of the random perturbation decoder,
as well as that of the adjusted, augmented, and combined decoders, to that of
our proposed non-CSS codes when they are applied over the depolarizing
channel. The underlying LDGM code and CSS configuration is the same as in most
of our previous simulations: the classical code is defined by the parallel
concatenation $\mathrm{P}[(8,8);(3,60)]$ and the CSS construction is achieved
using $\mathrm{M}(3;1,8.72)$ and $t=4361$. Performance of a typical CSS
decoder (separate decoding of $X$ and $Z$ operators) is also included in
Figure 6.14. The non-CSS scheme is obtained from the CSS code by using the
first design method and setting $q=500$, which is the parameter configuration
that produced the best results in our earlier simulations. Both the CSS code
and the non-CSS configuration have rate $R_{Q}=\frac{1}{4}$.

Figure 6.14: Simulated QBER for different types of modified CSS BP decoders
over the depolarizing channel. Results for the separate decoding of $X$ and
$Z$ errors (standard CSS decoding) and for our proposed non-CSS scheme are
also included. $p$ is the depolarizing probability of the depolarizing
channel.

As shown in Figure 6.14, all of the modified CSS BP decoders yield performance
improvements when compared to the generic CSS decoding scheme. Nonetheless,
they are all outperformed by our proposed non-CSS construction, despite the
close proximity between the QBER curves of the combined decoder and the non-
CSS scheme. Importantly, we must note that although these modified decoders
achieve performance close to that of our proposed scheme, they require
specific modifications to the decoding algorithm that result in higher
decoding complexity. This increase in decoding complexity arises from the fact
that the modified CSS schemes require the execution of a standard decoder
prior to their application. As mentioned in section 5.4, most modified
decoding strategies rely on the failure of a standard decoder to then apply
modifications to the factor graph according to the channel error estimate
produced by the failed standard decoder. Once these modifications have been
made (either to the a priori probabilities or to the factor graph itself)
decoding is re-attempted. In some instances, decoding must be re-attempted
multiple times before a correct syndrome estimation is produced. Moreover, the
augmented decoder and the combined decoder operate over larger factor graphs,
which further increases decoding complexity.

Since our proposed construction is decoded by running the SPA over the
corresponding factor graph, decoding never has to be re-attempted, and so the
complexity of our decoder is essentially the same as that of a standard CSS
decoder. Therefore, it is clear that the scheme proposed in this chapter
outperforms the aforementioned CSS decoders while displaying a lower decoding
complexity.

###  6.5 Chapter summary

This chapter has introduced a technique to design non-CSS quantum codes based
on the use of the generator and parity check matrices of LDGM codes. The
proposed methods are based on modifying the upper layer of the decoding graph
in CSS QLDGM constructions. The simplicity of the proposed scheme ensures that
the high degree of flexibility in the choice of the quantum rate and the block
length for the CSS code utilized as a starting point is translated to the non-
CSS design. Compared to quantum CSS codes based on the use of LDGM codes, the
proposed non-CSS scheme is $0.2$ dB closer to the Hashing bound in the
depolarizing channel and outperforms all other existing quantum codes of
comparable complexity.

##  CHAPTER 7 Performance of QLDPC codes over Pauli channels

> “The future can ever promise but one thing and one thing only: surprises”
>
> Steven Erikson.

In Chapter 6 we studied and analyzed the performance of quantum codes over the
depolarizing channel. However, despite serving as a practical abstraction that
is useful to design and evaluate the performance of quantum codes, the
depolarizing channel model we have worked with up to this point does not
always provide an accurate representation of practical communication schemes
or the real behaviour of quantum devices. A good example of this is the
scenario known as channel mismatch, which describes the event in which the
value of the depolarizing probability is not known prior to decoding. Notice
how, up to this point, a perfect channel knowledge assumption was implicit in
our simulations, i.e, we considered that the decoder knew the precise value of
the depolarizing probability prior to decoding. Clearly, the depolarizing
channel model that we have considered previously does not suffice to represent
the channel mismatch scenario. Another instance in which a different channel
model becomes necessary is when seeking to represent the behaviour of
realistic quantum devices. Many of these devices behave asymmetrically: the
probability of a phase-flip taking place is actually orders of magnitude
higher than the probability of a bit-flip; a type of behaviour that cannot be
appropriately described using the depolarizing channel. For these reasons, in
this chapter we introduce different Pauli channel models that are appropriate
to represent realistic scenarios that the depolarizing channel cannot re-
enact. We focus on the phenomenon of channel mismatch in section 7.1 and then
analyze the performance of CSS codes over asymmetric Pauli channels in 7.2.

###  7.1 Performance of non-CSS QLDPC codes over the misidentified
depolarizing channel

In the previous chapter we introduced a non-CSS inspired LDGM-based strategy
that outperforms all other CSS and non-CSS codes of similar complexity over
the depolarizing channel. We did so, as is common throughout the literature of
QEC, under the tacit premise that perfect knowledge of the quantum channel in
question was available. In reality, such a scenario is highly unlikely, and
the depolarizing probability must somehow be estimated prior to decoding. This
makes it relevant to study how the behaviour of QEC codes can change in terms
of the existing information about the quantum channel.

The phenomenon of channel mismatch in the context of QEC was first considered
in [185], where the authors studied the impact of decoding QLDPC codes with
imperfect channel knowledge over the depolarizing channel. In [186], the same
authors designed an improved decoding strategy for QLDPC codes when only an
estimate of the channel depolarizing probability was available. This last
method made use of quantum channel identification, a technique that requires
the introduction of a probe (a known quantum state) into the quantum channel
and the subsequent measurement of the channel output state to produce an
accurate estimate of the depolarizing probability. Quantum channel
identification procedures typically require additional qubits and result in a
latency increase, making the error correction procedure increasingly
cumbersome. For this reason, researchers have since focused on the design of
methodologies that can minimize this overhead (by avoiding the use of channel
identification) while yielding performance similar to the perfect channel
knowledge scenario. Such techniques have already been explored and
successfully demonstrated for QTCs. In [31] the authors derive a so-called on-
line depolarizing probability estimation technique that yields similar
performance to that obtained when using the same QTCs with perfect channel
information but without the need for additional resources. In light of this