# Degenerate Quantum LDPC Codes With Good Finite Length Performance

Pavel Panteleev and Gleb Kalachev Pavel Panteleev and Gleb Kalachev are with
the Lomonosov Moscow State University, Moscow, Russia. They are also with the
Huawei Russian Research Center.

###### Abstract

We study the performance of small and medium length quantum LDPC (QLDPC) codes
in the depolarizing channel. Only degenerate codes with the maximal stabilizer
weight much smaller than their minimum distance are considered. It is shown
that with the help of an OSD-like post-processing the performance of the
standard belief propagation (BP) decoder on many QLDPC codes can be improved
by several orders of magnitude. Using this new BP-OSD decoder we study the
performance of several known classes of degenerate QLDPC codes including the
hypergraph product codes, the hyperbicycle codes, the homological product
codes, and the Haah’s cubic codes. We also construct several interesting
examples of short generalized bicycle codes. Some of them have an additional
property that their syndromes are protected by small BCH codes, which may be
useful for the fault-tolerant syndrome measurement. We also propose a new
large family of QLDPC codes that contains the class of hypergraph product
codes, where one of the used parity-check matrices is square. It is shown that
in some cases such codes have better performance than the hypergraph product
codes. Finally, we demonstrate that the performance of the proposed BP-OSD
decoder for some of the constructed codes is better than for a relatively
large surface code decoded by a near-optimal decoder.

###### Index Terms:

Stabilizer codes, topological quantum codes, quantum LDPC, OSD decoder,
hypergraph product codes.

##  I Introduction

Quantum error correcting codes are considered as an essential component in the
current architectures of quantum computers due to the inherently faulty nature
of the quantum hardware. Topological quantum codes[1, 2, 3] are among the
quantum codes with the highest known noise thresholds. These codes have very
sparse parity-check matrices, and thus belong to a class of quantum LDPC
(QLDPC) codes. Moreover they are highly degenerate, which means that their
minimum distance is much higher than the weight of their stabilizers. It is
important that these codes also have very good decoding algorithms with near
to optimal performance[1, 4, 5]. Though the practical performance of
topological codes is really good, they usually have very small dimension
compared to general QLDPC codes of the same length (it is constant for the
surface and colour codes). There are also interesting classes of topological
quantum codes with very large dimension (e.g., the hyperbolic surface codes[6]
have constant rate). However such codes usually have much smaller minimum
distances compared to the surface and colour codes.

Recently there have been proposed a number of interesting families of
degenerate QLDPC codes (e.g., the hypergraph product codes[7] and the
homological product codes[8]) with very good asymptotic parameters. However
their practical performance for relatively small code lengths (say $n<1000$)
is largely unexplored, and it is not clear whether their performance is
competitive to the best known topological codes. From our point of view, the
difficulty of constructing degenerate QLDPC codes with good practical
performance is mostly related with the following two issues.

  1. 1.

Asymptotically good constructions may not necessarily produce the best QLDPC
codes for relatively small code lengths. Indeed, in [9, 10] the construction
of the hypergraph product codes was further improved and generalized. Although
the asymptotic characteristics of the improved codes are the same as before,
their parameters such as the rate and the minimum distance are much better for
smaller lengths.

  2. 2.

The performance of the proposed codes is far from the optimal under the state-
of-the-art decoders for QLDPC codes (including the binary and non-binary BP,
and their modifications). The performance degradation is usually
attributed[11] to unavoidable $4$-cycles in the corresponding Tanner graphs
and to a large number of degenerate errors. While the number of $4$-cycles can
be significantly reduced by using CSS codes[12] without $4$-cycles in the
parity-check matrices $H_{X}$ and $H_{Z}$, the number of degenerate errors can
not be easily reduced for highly-degenerate codes.

In this paper we try to address the both mentioned issues. In the first part
of the paper we introduce a new enhancement of the standard BP decoder111For a
good review of the standard BP decoder for QLDPC codes and its modifications
see [11]. for QLDPC codes (both binary and non-binary versions are allowed)
using a variant of the well-known decoding algorithm for short classical codes
called the _ordered statistics decoding (OSD)_[13, 14]. This new post-
processing algorithm works only if the BP decoder fails to find the correction
Pauli operator that commutes with all the stabilizers. We suppose here that
the QLDPC parity-check matrix $H$ is represented in the binary form222For a
QLDPC code on $n$ qubits with $m$ stabilizers the maytix $H$ is an $m\times
2n$ binary matrix.. The algorithm starts from finding a reliable information
set[15] for $H$ based on the soft-decisions obtained by the BP decoder. Then
it makes hard-decisions for the bits from this information set and flips the
$w$ most unreliable of them in order to find the $2^{w}$ corresponding
correction Pauli operators that return the corrupted quantum state to the
coding space. Finally, it selects a correction operator with the minimum
weight and applies it to the corrupted quantum state. Thus this new combined
BP-OSD decoder, in contrast to the standard BP, _always_ returns the
correction operator that moves the corrupted codeword back to the code space.
We show that with the help of this OSD-like post-processing the performance of
the standard BP decoder on many degenerate QLDPC codes can be improved by
several orders of magnitude. As it can be seen from its brief description
above, it is not restricted to CSS codes, and can also be used in conjunction
with any decoder, different from BP, that provides soft-decisions.

In the second part of the paper we construct a number of new relatively small
codes using two families of degenerate codes: the generalized bicycle codes
introduced in [10] and a new large family of QLDPC codes. This new family
contains the generalized bicycle codes and the class of hypergraph product
codes, where one of the two parity-check matrices used in the product is
square. We also derive a new simple formula for the dimension of generalized
bicycle codes and show how to design codes with a high dimension. Some of the
constructed generalized bicycle codes have an additional property that their
syndromes are protected by small BCH codes, which may be useful for the fault-
tolerant syndrome measurement. For the new class of generalized hypergraph
product codes we show how to find their dimension in some important special
cases.

We also study the performance of the proposed BP-OSD decoder on many known
classes of degenerate QLDPC codes including the already mentioned hypergraph
product codes, the hyperbicycle codes[10], the homological product codes[8],
and the Haah’s cubic codes[16]. We compare their performance with the
performance of the new constructed codes. We show that in many cases the new
codes with similar performance have better parameters such as the code length
and the rate. Besides that, we compare the new BP-OSD decoder with other known
modifications of BP such as the random perturbation[17], the enhanced
feedback[18], and the matrix augmentation[19] algorithms. We compare all the
above mentioned algorithms on the new $[[1270,28]]$ code from the class of
generalized hypergraph product codes mentioned earlier. We show that the
performance of the new decoding algorithm on this code is significantly
better. Moreover, we also show that the performance of this code under the BP-
OSD is even better than the performance of the $[[1201,1,25]]$ surface code
under the near optimal MPS-based decoder proposed in [5].

The remainder of the paper is organized as follows. Section II contains
background material, where we review some standard definitions and fix
notations. In Section III we describe the BP-OSD algorithm and compare its
performance with other known modifications of BP. In Section IV we study the
generalized bicycle codes and construct some new codes with good performance.
In Section V we introduce and study a new large family of QLDPC codes that
generalizes the class of hypergraph product codes in the case when one of the
parity-check matrices is square. In the last section we give some final
remarks. The paper also have two appendixes. Appendix A contains some
supplementary material on the ring of circulants. Finally, Appendix B contains
a description of all the codes used in the simulations.

##  II Basic facts and definitions

In this section we fix notations and briefly recall some standard definitions
related to quantum LDPC codes. More information can be found in the survey
[11].

###  II-A Classical codes

Let $n$ be a natural number. We denote by $[n]$ the set $\\{1,\dots,n\\}$.
Consider a finite set $A$ with $q$ elements. The _Hamming distance
$d(v,v^{\prime})$_ between two vectors $v,v^{\prime}\in A^{n}$ is the number
of positions in which they differ. Any $M$-element subset $\mathcal{C}$ of the
set $A^{n}$ is called an _$(n,M,d)_{q}$ code over333We usually omit “over $A$”
if the set $A$ is clear from the context and write $(n,M,d)$ instead of
$(n,M,d)_{2}$ if $q=2$. $A$_, where the parameter $n$ is called _the length_
and the parameter $d=\min\\{d(c,c^{\prime})\mid c\neq
c^{\prime};c,c^{\prime}\in C\\}$ is called the _minimal distance_ of $C$ and
is denoted by $d(\mathcal{C})$. By definition, we set $d(C)=\infty$ when
$M=1$. The elements of $\mathcal{C}$ are called _codewords_.

Let $A=\mathbb{F}_{q}$, where $\mathbb{F}_{q}$ is the finite field of
characteristic444In this paper we consider only finite fields of
characteristic $2$. $2$ with $q=2^{s}$ elements. If an $(n,M,d)_{q}$ code
$\mathcal{C}$ is a $k$-dimensional vector subspace of $\mathbb{F}_{q}^{n}$
then we have $M=q^{k}$ and say that $\mathcal{C}$ is a  _linear $[n,k,d]_{q}$
code over $\mathbb{F}_{q}$_, where $k$ is called the _dimension_ of
$\mathcal{C}$. For linear codes the minimal distance555If the minimal distance
is not known we say that $\mathcal{C}$ is an $[n,k]_{q}$ code. $d$ is equal to
the minimal weight $\mathrm{wt}({c})$ of non-zero codewords, where the _weight
$\mathrm{wt}({c})$_ is the number of non-zero components in $c$. A linear
$[n,k,d]_{q}$ code is usually defined either as the row space of a matrix $G$
called the _generator matrix_ , or as the dual space of a matrix $H$ called
the _parity-check matrix_. It is easy to see that
$GH^{\mathrm{T}}=\mathbf{0}$, $\operatorname{rank}G=k$, and
$\operatorname{rank}H=n-k$.

###  II-B Quantum stabilizer codes

The quantum analogs of classical linear codes are quantum stabilizer codes
introduced in [20]. To define them, we need a number of supporting
definitions. Consider an _$n$ -qubit Hilbert space_
$\mathbb{C}^{2^{n}}=(\mathbb{C}^{2})^{\otimes n}$. A  _Pauli operator on $n$
qubits_ is an operator $P=\alpha P_{1}\otimes\dots\otimes P_{n}$ on the space
$\mathbb{C}^{2^{n}}$, where $\alpha\in\\{\pm 1,\pm i\\}$,
$P_{i}\in\\{I,X,Y,Z\\}$. Here $I$ is the identity and $X,Y,Z$ are the Pauli
$2\times 2$ matrices. The _weight_ $\mathrm{wt}({P})$ of a Pauli operator $P$
is the number of non-identity components in its tensor product. The set
$\mathcal{P}_{n}$ of all Pauli operators $P$ on $n$ qubits is a non-
commutative group under the operator multiplication called the _$n$ -qubit
Pauli group_. While the group $\mathcal{P}_{n}$ is non-commutative, if we
forget about the global phase factors $\alpha$ of Pauli operators we obtain
the factor group $\mathcal{P}_{n}/\\{\pm I_{n},\pm iI_{n}\\}$, where $I_{n}$
is the identity operator on $\mathbb{C}^{2^{n}}$. This factor group is
isomorphic to the commutative group $\mathbb{Z}_{2}^{2n}$ and the isomorphism
is given by the following map:

$\alpha X^{a_{1}}Z^{b_{1}}\otimes\dots\otimes
X^{a_{n}}Z^{b_{n}}\mapsto(a_{1},\dots,a_{n}\mid b_{1},\dots,b_{n}).$ (1)

Denote by $\mathcal{P}_{n}^{*}$ the subset of Pauli operators
$P\in\mathcal{P}_{n}$ with the global phase factor $\alpha=1$. A _stabilizer
group_ $G$ is a commutative subgroup of the Pauli group $\mathcal{P}_{n}$
generated by $m$ Pauli operators $S_{1},\dots,S_{m}\in\mathcal{P}_{n}^{*}$
called _stabilizers generators_ , i.e., $G=\left<S_{1},\dots,S_{m}\right>$. It
is easy to verify that all the stabilizers $S_{1},\dots,S_{m}$ commute and
$-I_{n}\not\in G$. We say that $S_{1},\dots,S_{m}$ are _independent_ if none
of them can be obtained from the others by group multiplication.

A _quantum stabilizer $[[n,k,d]]$ code_666We usually omit the word “quantum”
in what follows. is a $2^{k}$-dimensional subspace of the $n$-qubit space
$\mathbb{C}^{2^{n}}$ defined as the common $+1$-eigenspace for a set of
$m=n-k$ independent stabilizers $S_{1},\dots,S_{m}\in\mathcal{P}_{n}^{*}$:

$\mathcal{C}=\\{\lvert{\psi}\rangle\in\mathbb{C}^{2^{n}}\mid
S_{i}\lvert{\psi}\rangle=\lvert{\psi}\rangle,i=1,\dots,m\\},$

where the group $\mathbb{S}(\mathcal{C})=\left<S_{1},\dots,S_{m}\right>$ is
called the _stabilizer group of $\mathcal{C}$_. Here the parameter
$d=d(\mathcal{C})$ is called the _minimal distance_ 777As in the case of
classical codes we write $[[n,k]]$ if the minimal distance is not known. of
$\mathcal{C}$ and is equal to the minimal possible weight of a Pauli operator
$P\in\mathcal{P}_{n}^{*}$ that commutes with all the stabilizers
$S_{1},\dots,S_{m}$ but $P\not\in\mathbb{S}(\mathcal{C})$.

A Pauli operator $P\in\mathcal{P}_{n}^{*}$ is usually interpreted as an error
operator (called a _Pauli error_) that can corrupt a quantum system and cause
it to go from a state $\lvert{\psi}\rangle$ to $P\lvert{\psi}\rangle$. However
if $\lvert{\psi}\rangle\in\mathcal{C}$, where $\mathcal{C}$ is some quantum
stabilizer code, it is easy to show that
$P\lvert{\psi}\rangle=\lvert{\psi}\rangle$ iff $P\in\mathbb{S}(\mathcal{C})$.
Hence we see that in this case not all Pauli errors $P\in\mathcal{P}_{n}^{*}$
can harm the state $\lvert{\psi}\rangle$. We call a Pauli error
$P\in\mathcal{P}_{n}^{*}$ _degenerate_ for a quantum stabilizer code
$\mathcal{C}$ if $P\lvert{\psi}\rangle=\lvert{\psi}\rangle$ and _non-
degenerate_ otherwise. We see that the elements from
$P\in\mathbb{S}(\mathcal{C})$ are precisely the degenerate Pauli errors and
the minimum distance $d(\mathcal{C})$ is the minimal possible weight of a non-
degenerate Pauli error. A stabilizer code $\mathcal{C}$ is called _degenerate_
if it has degenerate Pauli errors $P$ with weight
$\mathrm{wt}({P})<d(\mathcal{C})$.

If we apply the binary mapping (1) to the stabilizer generators
$S_{1},\dots,S_{m}$ of the $[[n,k,d]]$ code $\mathcal{C}$ we obtain the
$m\times 2n$ binary matrix $H=(H_{X}\mid H_{Z})$ called the _parity-check
matrix_ of $\mathcal{C}$, where each row corresponds to a stabilizer
generator. We do not require for the matrix $H$ to be full rank (i.e,
$\operatorname{rank}H=n-k\leq m$). The null space of $H$ corresponds precisely
to the binary mappings of Pauli errors $P\in\mathcal{P}_{n}^{*}$ that commute
with all the stabilizer generators $S_{1},\dots,S_{m}$.

We see that the matrix $H=(H_{X}\mid H_{Z})$ is not an arbitrary binary
$m\times 2n$ matrix since the stabilizer generators $S_{1},\dots,S_{m}$
corresponding to its rows should commute with each other. It is easy to verify
that this restriction can be formulated as the following _commutativity
condition_ :

$H_{X}H_{Z}^{\mathrm{T}}+H_{Z}H_{X}^{\mathrm{T}}=\mathbf{0}.$ (2)

A very important subclass of quantum stabilizer codes are the quantum
_Calderbank-Shor-Steane (CSS) codes_ introduced in [21]. A quantum CSS code is
a stabilizer code, where non-identity components in the tensor product of each
stabilizer generator are either all equal to $X$ or all equal to $Z$. Hence
the parity-check matrix $H$ of a CSS code of length $n$ can be represented in
the following form:

$H=\begin{pmatrix}[c|c]H_{X}&\mathbf{0}\\\ \mathbf{0}&H_{Z}\\\ \end{pmatrix},$

where $H_{X}$, $H_{Z}$ are some binary matrices with $n$ columns.

In this special case the commutativity condition can be written as:

$H_{X}H_{Z}^{\mathrm{T}}=\mathbf{0}.$ (3)

The dimension $k$ of the CSS code of length $n$ is given by the formula:

$k=n-\operatorname{rank}H_{X}-\operatorname{rank}H_{Z}.$ (4)

###  II-C Classical and quantum LDPC codes

A classical _low density parity check (LDPC) code_[22] is a linear code
defined by a sparse binary parity-check matrix $H=\left(h_{ij}\right)_{m\times
n}$. The sparseness usually means that the weights of all rows and columns in
$H$ are upper bounded by some constant $w$ as the code length $n$ grows to
infinity. It is helpful to define a bipartite graph
$\mathcal{T}=\mathcal{T}(H)$ called the _Tanner graph_[23]. In this graph the
fist part of nodes $v_{1},\dots,v_{n}$ (called the _v-nodes_) corresponds to
the columns of $H$ (the variables), the second part of nodes
$c_{1},\dots,c_{m}$ (called the _c-nodes_) corresponds to the rows of $H$ (the
checks), and we connect a v-node $v_{i}$ with with a c-note $c_{j}$ whenever
$h_{ij}=1$, $i\in[m]$, $j\in[n]$. If the parity-check matrix $H$ is
_$(w_{c},w_{r})$ -regular_ (i.e., each column has weight $w_{c}$ and each row
has weight $w_{r}$) then the corresponding Tanner graph is also
_$(w_{c},w_{r})$ -regular_ (i.e., each v-node has degree $w_{c}$ and each
c-node has degree $w_{r}$). We say that an LDPC code is _$w$ -limited_ if the
degree of each node in its Tanner graph is upper bounded by $w$. It is obvious
that any LDPC code with $(w_{c},w_{r})$-regular parity-check matrix is
$\max(w_{c},w_{r})$-bounded.

There are a number of decoding algorithms for classical LDPC codes but the
most frequently used one is the _belief propagation (BP) decoder_[22] also
known as the _message passing decoder_ and the _sum-product decoder_. It
assigns the a priory probability distributions of individual bits in the
codeword (obtained from the channel) to the v-nodes of the the Tanner graph
and iteratively calculates the posterior probability distributions for each
bit (the  _soft decisions_). After some maximal _iteration number limit_ is
reached the decoder uses the calculated posterior probability distributions to
produce the optimal binary decisions (called the _hard decisions_) for each
individual bit.

Another important property of LDPC codes is the _girth_ of the corresponding
Tanner graph $\mathcal{T}$, which is equal to the length of the shortest cycle
in $\mathcal{T}$. It is well known that short cycles in the Tanner graph
degrade the performance of the BP decoder. It was observed that LDPC codes
without $4$-cycles (i.e., the girth is at least $6$) perform very well in
practice. However this practical observation is not fully investigated from
theoretical point of view.

A _quantum LDPC (QLDPC)_ is a stabilizer $[[n,k,d]]$ code with a sparse
parity-check matrix $H$. We can also introduce the Tanner graph
$\mathcal{T}=\mathcal{T}(\mathcal{S})$ for any stabilizer $[[n,k,d]]$ code
$\mathcal{C}$ defined by a set of stabilizer generators
$\mathcal{S}=\\{S_{1},\dots,S_{m}\\}$. In the case of stabilizer codes the
v-nodes correspond to $n$ qubits and the c-nodes to the stabilizer generators
$S_{1},\dots,S_{m}$, and we connect a c-node with a v-node if the
corresponding stabilizer acts nontrivially on the corresponding qubit. Similar
to the classic case we say that a QLDPC code is _$w$ -limited_ if the degree
of each node in its Tanner graph is upper bounded by $w$. This property is
much more important in the quantum case due to the faulty nature of the
current quantum hardware.

It is clear that any CSS code with $(w_{c},w_{r})$-regular matrices $H_{X}$
and $H_{Z}$ is $\max(w_{c},w_{r})$-limited.

##  III OSD-like post-processing for BP

In this section we describe a new OSD-like post-processing algorithm that can
be used after the BP decoder for QLDPC codes. Before we give its detailed
description we consider two simple modifications of the OSD decoder for
_classical_ linear codes. These modifications will be used as the main
components in the OSD-like post-processing algorithm for quantum codes. We
should warn the reader that these modifications of the standard OSD decoder
are not intended to improve its performance for classic LDPC codes. We
introduce them because these algorithms eventually will be used in the OSD
post-processing algorithm (called qOSD) for _quantum_ codes described in
Section III-B. For example, one of the main differences between classical and
quantum codes is that we have to use the syndrome decoder in the quantum case.
Hence we consider only syndrome OSD decoders here since we are going use them
as components of the decoder for quantum codes.

###  III-A Syndrome OSD post-processing algorithm

The input for our syndrome based OSD post-processing algorithm is a binary
$m\times n$ parity-check matrix $H$, a syndrome binary vector
$s\in\mathbb{F}_{2}^{m}$, and an initial binary vector
$v\in\mathbb{F}_{2}^{n}$. We suppose that the columns of $H$ are already
rearranged such that the reliability888The reliability of each bit is
calculated by the BP decoder as shown in Section III-C. of the corresponding
bits increases from left to right.

We use the following notations in the algorithm description:

  * •

If $u=(u_{1},...,u_{n}),v=(v_{1},...,v_{m})$ are vectors, then

$[u,v]=(u_{1},...,u_{n},v_{1},...,v_{m})$

is their _concatenation_.

  * •

If $S=\\{i_{1},...,i_{k}\\}$, $i_{1}\leq i_{2}\leq...\leq i_{k}$ is a set of
indexes, $v=(v_{1},...,v_{n})$, then

$v|_{S}=(v_{i_{1}},v_{i_{2}},...,v_{i_{k}}).$

  * •

If $H$ is a matrix, then $H_{i}$ denotes the $i$-th column of the matrix $H$.

  * •

If $S=\\{i_{1},...,i_{k}\\}$, $i_{1}\leq i_{2}\leq...\leq i_{k}$ is a set of
indexes, $H$ is a matrix, then

$H_{S}=(H_{i_{1}},...,H_{i_{k}})$

denotes the matrix composed from the columns of $H$ with the indexes
$i_{1},...,i_{k}$.

In the beginning of our OSD decoder, similar to the standard OSD decoder, we
select the first $r=\operatorname{rank}H$ linearly independent columns of $H$.
Let $S$ be the indexes of the selected columns and
$\mathcal{E}\colon\mathbb{F}_{2}^{n-r}\to\mathbb{F}_{2}^{n}$ be the
corresponding encoding operator for the syndrome $s$ and the remaining bits
such that

$u=\mathcal{E}(x)\Longleftrightarrow u|_{T}=x,Hu=s,$

where $T=[n]\setminus S$. The encoding operator $\mathcal{E}$ always exists
and is unique since the set of indexes $T$ is an information set999The set of
indexes $T$ is called an _information set_ for the parity-check matrix $H$ if
any two codewords that are equal on the index set $T$ coincide. for the matrix
$H$. Here we assume that $s\in\operatorname{Im}H$, i.e., $s$ is a valid
syndrome, otherwise $\mathcal{E}$ does not exist and the OSD decoder cannot be
applied.

Then we flip the $w$ weakest bits (i.e., the bits with the smallest
reliabilities) from the information set $T$ and apply the encoding operator
$\mathcal{E}$ to all of them. We select a word $c$ with the minimal cost
$N(c)$ among all the $2^{w}$ obtained codewords, where the cost function
$N(\cdot)$ depends on the specific decoder we use. In the case of quantum
codes described in Section III-B this cost function is the weight of the
corresponding Pauli error.

Input: a target cost function $N(\cdot)$,

a binary parity-check matrix $H$,

a syndrome vector $s\in\mathbb{F}_{2}^{m}$,

an initial correction vector $v\in\mathbb{F}_{2}^{n}$

Output: the correction vector $c\in\mathbb{F}_{2}^{n}$ such that $Hc=s$.

1 $S\leftarrow\varnothing$;

2 for  _$i\leftarrow 1$ to $n$_ do

3 $S^{\prime}\leftarrow S\cup\\{i\\}$;

4 if  _$\operatorname{rank}H_{S^{\prime}} >\operatorname{rank}H_{S}$_ then

5 $S\leftarrow S^{\prime}$;

6

7 end if

8

9 end for

10$T\leftarrow[n]\setminus S$;

11 $\mathcal{E}\leftarrow$ the encoding operator for the information set $T$
such that $u=\mathcal{E}(x)\Longleftrightarrow u|_{T}=x,Hu=s$;

12 $W\leftarrow$ the smallest $w$ elements of $T$;

13 $F\leftarrow T\setminus W$;

14
$\hat{r}\leftarrow\operatorname*{arg\,min}\limits_{r\in\mathbb{F}_{2}^{w}}N(v_{r})$
where $v_{r}=\mathcal{E}([r,v|_{F}])$;

15 return $v_{\hat{r}}$;

Algorithm 1 Syndrome OSD-$w$ post-processing

The OSD-$w$ post-processing algorithm is mainly used to reduce the error floor
of the BP decoder. So, when it is applied, there is noise only around trapping
sets, which is a small part of the codeword. Hence in many cases OSD-$0$ is
enough and the procedure can be simplified. In this case there is no need to
do full Gaussian elimination for $H$. Instead, at each step we look at the
current syndrome $s^{\prime}$. If
$\operatorname{rank}{[H_{S},s^{\prime}]}=\operatorname{rank}H$ then the system
$H_{S}\,x=s^{\prime}$ has a solution, so we can stop the elimination and find
the values of $S$ bits (see Algorithm 2).

Input: a binary parity-check matrix $H$,

a syndrome vector $s\in\mathbb{F}_{2}^{m}$,

an initial correction vector $v\in\mathbb{F}_{2}^{n}$

Output: the correction vector $c\in\mathbb{F}_{2}^{n}$ such that $Hc=s$.

1 $S\leftarrow\varnothing$;

2 $s^{\prime}\leftarrow s+Hv$;

3 for  _$i\leftarrow 1$ to $n$_ do

4 if  _$\operatorname{rank}{[H_{S},s^{\prime}]}=\operatorname{rank}H_{S}$_
then

5 break ;

6

7 end if

8 $S^{\prime}\leftarrow S\cup\\{i\\}$;

9 if  _$\operatorname{rank}H_{S^{\prime}} >\operatorname{rank}H_{S}$_ then

10 $S\leftarrow S^{\prime}$;

11 $s^{\prime}\leftarrow s^{\prime}+v_{i}H_{i}$;

12

13 end if

14

15 end for

16$x\leftarrow$ the solution of $H_{S}\,x=s^{\prime}$;

17 return $v$ with $S$ positions replaced by $x$;

Algorithm 2 Simplified OSD-$0$

There are some differences between the standard OSD decoder and the proposed
post-processing algorithm. The main differences are the following:

  1. 1.

Here we use the order of bits induced by the posterior probabilities obtained
by the BP decoding algorithm but the target cost function $N(\cdot)$ should
not depend on these probabilities.

  2. 2.

Usually the reliability of a bit is calculated as the ratio of the most
reliable value to the sum of the other values. In our algorithm the
reliability is calculated as the posterior probability that this bit is not
flipped by the BP decoder.

  3. 3.

During the codeword search we try all the $2^{w}$ values of the $w$ weakest
bits, while in the standard OSD we try all the $\sum_{i\leq w}\binom{n-k}{i}$
bit flips of no more than $w$ bits.

###  III-B Modified OSD post-processing algorithm for stabilizer codes

There are a number of quantum noise models. In this paper we consider the
depolarizing channel only. However many of our ideas may be used for other
memoryless quantum noise models. In the _depolarizing channel_ model with
_error probability $p$_ a quantum state
${\lvert{\psi}\rangle\in\mathbb{C}^{2^{n}}}$ is subject to a random Pauli
error

$E=E_{1}\otimes\dots\otimes E_{n}\in\mathcal{P}_{n}^{*},$

where all $E_{i}$ are i.i.d, and $\Pr(E_{i}=X)=\Pr(E_{i}=Y)=\Pr(E_{i}=Z)=p/3$,
$i\in[n]$.

In this section it is convenient to consider (with some small abuse of
notation) the set of matrices $\mathcal{P}_{1}^{*}=\\{I,X,Y,Z\\}$ as elements
of the finite field $\mathbb{F}_{4}$, where $I$ corresponds to zero, and the
Pauli matrices $X,Y,Z$ correspond to the three non-zero elements of
$\mathbb{F}_{4}$. Hence we will consider a Pauli error
$E\in\mathcal{P}_{n}^{*}$ as a vector from $\mathbb{F}_{4}^{n}$. Using this
identification, we also represent the binary $m\times{2n}$ parity-check matrix
of a stabilizer code $\mathcal{C}$ as the corresponding $m\times n$ non-binary
matrix over $\mathbb{F}_{4}$ and call it the _stabilizer matrix_ of
$\mathcal{C}$.

We use the following notations in the algorithm description:

  * •

If $v\in\mathbb{F}_{4}^{n}$ is a Pauli vector and
$v_{i}=v^{X}_{i}X+v^{Z}_{i}Z$, where $v^{X}_{i},v^{Z}_{i}\in\mathbb{F}_{2}$,
$i\in[n]$, then we define the binary vectors:

$\displaystyle b(v)$
$\displaystyle=(v^{X}_{1},v^{Z}_{1},v^{X}_{2},v^{Z}_{2},...,v^{X}_{n},v^{Z}_{n})\in\mathbb{F}_{2}^{2n},$
$\displaystyle b^{*}(v)$
$\displaystyle=(v^{Z}_{1},v^{X}_{1},v^{Z}_{2},v^{X}_{2},...,v^{Z}_{n},v^{X}_{n})\in\mathbb{F}_{2}^{2n}.$

$b^{-1}$ denotes the inverse mapping for $b$.

  * •

If $H$ is an $m\times n$ stabilizer matrix, then $b(H)$ denote the $m\times
2n$ binary matrix obtained by mapping each row $h$ of $H$ to the row
$b^{*}(h)$. If $v\in\mathbb{F}_{4}^{n}$ is a Pauli error then it is easy to
check that $s=b(H)b(v)$ is the corresponding _syndrome_ vector, i.e.,
$s_{i}=0$ whenever the $i$-th stabilizer in the stabilizer matrix $H$ commutes
with the Pauli vector $v$, $i\in[m]$.

In the modified OSD algorithm stabilizer matrix $H$ is converted to binary
matrix $H^{\prime}$, Pauli vector $v$ is converted to binary vector
$v^{\prime}$ where each element of $v$ is converted into 2 bits of
$v^{\prime}$ by operator $b$.

Then the OSD post-processing algorithm is applied to the matrix $H^{\prime}$
and the vector $v^{\prime}$ with the target cost function101010It is easy to
see that this cost function is equal to the weight $\mathrm{wt}({E})$ of the
Pauli error $E\in\mathcal{P}_{n}^{*}$ represented in the binary form by the
vector $x\in\mathbb{F}_{2}^{2n}$.

$|x|_{P}=\sum_{i=1}^{n}(x_{2i-1}\vee x_{2i}).$

The qOSD algorithm can be simply defined via the OSD algorithm (described in
the previous section) and the Pauli binary mapping $b$ as follows

$\mathrm{qOSD}_{w}(H,s,v)=b^{-1}\bigl{(}\mathrm{OSD}_{w}(|\cdot|_{P},b(H),s,b(v))\bigr{)}.$

######  Remark.

The non-binary weight is used for the depolarizing channel. In a channel where
X and Z errors are independent the binary weight should be used instead.

###  III-C Decoding algorithm (BP-OSD)

Decoding algorithm consists of two steps: the BP decoding and the SD post-
processing. At the first step any BP modification may be also used if it can
provide soft-decisions. The goal of this step is either to decode the code or
to obtain the probabilities for each type of the Pauli error on each qubit.

If the BP decoding is successful then there is no need in the post-processing
and the algorithm returns the BP result. Otherwise, for the $i$-th qubit we
have $4$ numbers $l_{i}=(p_{i,I},p_{i,X},p_{i,Y},p_{i,Z})$, where $p_{i,E}$
can be interpreted as the probability $\Pr(E_{i}=E),E\in\\{I,X,Y,Z\\}$, where
$E_{i}$ is the error in the $i$-th qubit. These probabilities are used to sort
qubits in the order of decreasing total error probability. Then the
modification of the OSD algorithm for quantum stabilizer codes is used to
determine error in the weakest qubits using the hard decisions for the
strongest qubits. The hard decision for the $i$-th qubit can be calculated by
the formula:

$\hat{l}_{i}=\operatorname*{arg\,min}_{E\in\\{I,X,Y,Z\\}}p_{i,E}.$

Input: a stabilizer matrix H, a syndrome vector $s\in\mathbb{F}_{2}^{m}$

Output: the correction vector $c\in\mathbb{F}_{4}^{n}$

1 $l\leftarrow BP(s)$;

2 Make hard decisions: $v\leftarrow(\hat{l}_{i})_{i=1}^{n}$;

3 if  _$v$ satisfies the syndrome $s$ (i.e., $b(H)b(v)=s$)_ then

4 return $c=v$;

5else

6 Calculate the total error probability: $p_{i}\leftarrow
p_{i,X}+p_{i,Y}+p_{i,Z}$ ;

7 Sort qubits in the order of decreasing error probability. Let $\sigma\in
S_{n}$ be such an order that $p_{\sigma(1)}\geq p_{\sigma(2)}\geq...\geq
p_{\sigma(n)}$;

8 return
$c=\sigma^{-1}\bigl{(}\mathrm{qOSD}_{w}(\sigma(H),s,\sigma(v))\bigr{)}$;

9

10 end if

Algorithm 3 QLDPC decoding with OSD-$w$ post-processing

Here we use modification of the OSD decoder for stabilizer codes. For CSS code
$(H_{X},H_{Z})$ we also can use the standard OSD algorithm for the X and Z
components separately. In this case steps 3–3 are replaced by the following
steps:

  1. 1.

Calculate $X$ and $Z$ error probabilities:

$\displaystyle p_{i}^{X}$ $\displaystyle=p_{i,X}+p_{i,Y},$ $\displaystyle
p_{i}^{Z}$ $\displaystyle=p_{i,Y}+p_{i,Z};$

  2. 2.

Sort qubits in order of decreasing $X$-error and $Z$-error probability. Let
$\sigma_{X},\sigma_{Z}\in S_{n}$ be such orderings that

$\displaystyle p_{\sigma_{X}(1)}^{X}\geq p_{\sigma_{X}(2)}^{X}\geq...\geq
p_{\sigma_{X}(n)}^{X},$ $\displaystyle p_{\sigma_{Z}(1)}^{Z}\geq
p_{\sigma_{Z}(2)}^{Z}\geq...\geq p_{\sigma_{Z}(n)}^{Z}.$

  3. 3.

Let $v=v_{X}X+v_{Z}Z,[s_{X},s_{Z}]=s$. Run the OSD decoders for $X$ and $Z$
components:

$\displaystyle c_{X}$
$\displaystyle=\sigma_{X}^{-1}\bigl{(}\mathrm{OSD}_{w}(|\cdot|,\sigma_{X}(H_{Z}),s_{Z},\sigma_{X}(v_{X}))\bigr{)},$
$\displaystyle c_{Z}$
$\displaystyle=\sigma_{X}^{-1}\bigl{(}\mathrm{OSD}_{w}(|\cdot|,\sigma_{Z}(H_{X}),s_{X},\sigma_{Z}(v_{Z}))\bigr{)}.$

  4. 4.

Return $c=c_{X}X+c_{Z}Z$.

$10^{-2}$$10^{-1}$$10^{-8}$$10^{-7}$$10^{-6}$$10^{-5}$$10^{-4}$$10^{-3}$$10^{-2}$$10^{-1}$$10^{0}$Physical
error rateWERThe effect of OSD for different QLDPC codesA1, BPA1, BP-OSDB1,
BPB1, BP-OSDC1, BPC1, BP-OSDD, BPD, BP-OSD Figure 1: A1 — the $10$-limited
generalized bicycle [[254,28]] code; B1 — the $6$-limited generalized
hypergraph product [[882,24]] code; C1 — the $10$-limited hypergraph product
[[7938,578,16]] code; D — the $8$-limited Haah’s [[1024,30]] code on the grid
$8\times 8\times 8$. See Appendix B for details.
$10^{-1}$$10^{-6}$$10^{-5}$$10^{-4}$$10^{-3}$$10^{-2}$$10^{-1}$$10^{0}$$5\cdot
10^{-2}$Physical error rateWERBP-OSD with different orderno
OSDOSD-0OSD-4OSD-10OSD-15 Figure 2: The impact of OSD order on the
[[882,48,16]] code (for details see Appendix B, code B2). The OSD order has
effect mainly on codes with error floor induces by low weight non-degenerate
codewords.

On Fig. 2 we show the impact of the OSD order on the [[882,48,16]] code (for
details see Appendix B, code B2). We can see that the OSD order has effect
mainly on codes with error floor induced by low weight non-degenerate
codewords.

###  III-D Comparison of different post-processing algorithms

In this section the OSD post-processing algorithm is compared with other known
post-processing methods that also significantly improve the performance of
QLDPC codes. Below you can find a brief descriptions of these methods. All the
procedures are repeated until all the parity-checks are satisfied or the
maximal number of attempts $n_{a}$ is reached.

  * •

Random perturbation [17]. If the syndrome is non-zero after the BP decoding
then we randomly choose an unsatisfied c-node and randomly change the initial
LLRs for all the v-nodes adjacent to this c-node. The main parameter of this
method is the variance of the perturbation magnitude. After that the BP
decoder runs with the perturbed input LLRs.

  * •

Enhanced feedback [18]. It is similar to the previous approach but the
perturbation is not random and calculated using the previous BP output. If
after the BP decoding the parity-checks are not satisfied, we randomly choose
an unsatisfied c-node and for all the v-nodes adjacent to this c-node we set
the initial LLRs using the BP decoder output for these nodes. After that the
BP decoder runs with the perturbed input LLRs.

  * •

Matrix augmentation [19]. In this method instead of modification of the input
LLRs, the parity-check matrix itself is modified by random duplication of some
rows. The fraction $\delta$ of the duplicated rows is called the
_augmentation density_. Then a new decoding attempt with the augmented matrix
is performed.

$10^{-1}$$10^{-8}$$10^{-6}$$10^{-4}$$10^{-2}$$10^{0}$$5\cdot 10^{-2}$$2\cdot
10^{-1}$Physical error rateWERQLDPC post-processing comparisonPure
BPPert.EFBAug.OSD-0Surf. MWMSurf. MPS Figure 3: Comparison between different
post-processing algorithms on the [[1270,28]] QLDPC code (Appendix B, code B3)
and the [[1201,1,25]] surface code on the minimum weight matching (MWM)
decoder, and the MPS-based decoder from [5].

For all these methods we used $n_{a}=100$. On Fig. 3 we can see that the OSD
post-processing outperforms all the above mentioned post-processing methods
and also outperforms the $[[1201,1,25]]$ surface code on the MPS decoder from
[5], which is almost optimal for this surface code. Note that other post-
processing methods also have gain more than $10^{3}$ for the class of
$(3,6)$-regular CSS QLDPC codes with a sufficiently large minimum distance.
This is mainly because classical $(3,6)$-regular LDPC codes itself have many
harmful trapping sets and QLDPC codes additionally have a lot of degenerate
codewords of very low weight starting from $6$.

For all our simulations we used the normalized min-sum (NMS) decoder with the
normalization factor $0.625$, which approximates the BP decoder and is more
numerically stable in some cases. The maximal number of iterations was set to
$32$. We used the layered scheduling in order to increase the convergence
speed of the decoder by approximately two times. For a good review of
practical aspects of the BP decoder implementation see [24, Chapter 4].

##  IV New generalized bicycle codes

###  IV-A Ansatz with commuting matrices

The commutativity conditions such as (2) and (3) are a serious obstacle to
design good QLDPC using random-like constructions similar to the constructions
used for classical LDPC codes. Thus it makes sense to consider large families
of matrices of some particular form called _ansatz_ , where the commutativity
conditions are always satisfied. One such quite general ansatz for CSS codes
was proposed in [10] as a generalization of the Mackay bicycle QLDPC
codes[25]. Let us briefly remind this ansatz. Consider two commuting binary
$n\times n$ matrices $A$ and $B$, i.e., $AB=BA$. Let

$H_{X}=[A,B]\text{ and }H_{Z}=[B^{\mathrm{T}},A^{\mathrm{T}}].$ (5)

Then we see that $H_{X}H_{Z}^{\mathrm{T}}=AB+BA=\mathbf{0}$ and the
commutativity condition (3) is always satisfied. It was proposed in [10] to
use binary circulant matrices $A$ and $B$ since they always commute. The
corresponding class of codes is called the _generalized bicycle (GB) codes_ ,
where the Mackay bicycle codes[25] are obtained as a special case when
$B=A^{\mathrm{T}}$.

###  IV-B Ring of circulants

Let us recall that an $\ell\times\ell$ circulant matrix $A$ over
$\mathbb{F}_{q}$ takes the form

$A=\begin{pmatrix}a_{0}&a_{l-1}&\ldots&a_{1}\\\ a_{1}&a_{0}&\ldots&a_{2}\\\
{4}\\\ a_{\ell-1}&a_{\ell-2}&\ldots&a_{0}\\\ \end{pmatrix},$

where $a_{0},\ldots,a_{\ell-1}\in\mathbb{F}_{q}$. It is readily seen that the
matrix $A$ can be represented in the form

$A=a_{0}I+a_{1}P+\dots a_{\ell-1}P^{\ell-1},$

where $I$ is the $\ell\times\ell$ identity matrix and

$P=\begin{pmatrix}0&0&\ldots&1\\\ 1&0&\ldots&0\\\ 0&1&\ldots&0\\\ {4}\\\
0&0&\ldots&0\\\ \end{pmatrix}$

is the $\ell\times\ell$ permutation matrix representing the _right_ cyclic
shift by _one_ position. Since $P^{\ell}=I$, we see that the ring of all
$\ell\times\ell$ circulant matrices over $\mathbb{F}_{q}$ is isomorphic to the
ring $\mathbb{F}_{q}^{\left<\ell\right>}=\mathbb{F}_{q}[x]/(x^{\ell}-1)$ of
polynomials over $\mathbb{F}_{q}$ modulo the polynomial $x^{\ell}-1$.

Hence the circulant matrix $A$ can be uniquely represented by the polynomial
$a(x)=a_{0}+a_{1}x+\dots+a_{\ell}x^{\ell}$ and the product $C=AB$ of two
circulant matrices represented by polynomials $a(x),b(x)\in R_{\ell}$
corresponds to the polynomial

$c(x)=a(x)b(x)\mathop{\mathrm{mod}}x^{\ell}-1$ (6)

which is called the _cyclic convolution_ of $a(x)$ and $b(x)$. Likewise, if we
want to find a matrix-vector product $c=Ab$, where
$b=(b_{0},\dots,b_{\ell-1})^{\mathrm{T}}$ and
$c=(c_{0},\dots,c_{\ell-1})^{\mathrm{T}}$ are column vectors corresponding to
the polynomials $b(x)$ and $c(x)$ we can also use the cyclic convolution (6).

###  IV-C Dimension of generalized bicycle codes

Hence to define two binary circulant $\ell\times\ell$ matrices $A$ and $B$ we
need to provide two binary polynomials
$a(x),b(x)\in\mathbb{F}_{2}^{\left<\ell\right>}$. The dimension111111Let us
point out that the this dimension formula was given in the paper [10, Theorem
2] in a slightly more complex form. A similar formula was proved only in the
special case of single generator codes. $k$ of the corresponding CSS
$[[2\ell,k]]$ code is given by the following proposition.

######  Proposition 1.

The dimension $k$ of the the generalized bicycle $[[2\ell,k]]$ code defined by
polynomials $a(x),b(x)\in\mathbb{F}_{2}^{\left<\ell\right>}$ is given by the
formula:

$k=2\deg g(x),$ (7)

where $g(x)=\gcd(a(x),b(x),x^{\ell}-1)$.

To prove this formula we show that
$\operatorname{rank}H_{X}=\operatorname{rank}H_{Z}=n-\deg g(x)$ and use
formula (4) for the dimension of CSS codes.

Let us first find the rank of the matrix $H_{X}=[A,B]$, which is equal to the
dimension of its column space. It is easy to see that the column space of
$H_{X}$ (called its _syndrome space_) is equal to the following set:

$\\{Au^{\mathrm{T}}+Bv^{\mathrm{T}}\mid u,v\in\mathbb{F}_{2}^{\ell}\\}.$

Using the described above polynomial representation of column vectors and
circulant matrices we can consider this set as the following set of
polynomials from the ring $\mathbb{F}_{2}^{\left<\ell\right>}$:

$\\{a(x)u(x)+b(x)v(x)\mid u(x),v(x)\in\mathbb{F}_{2}^{\left<\ell\right>}\\}.$

It is easy to verify that this set is the principal121212An ideal $I$ in a
ring $R$ is _principal_ if $I=\\{au\mid u\in R\\}$ for some $a\in R$. ideal of
the ring $\mathbb{F}_{2}^{\left<\ell\right>}$ generated by $g(x)$. Hence it is
the cyclic code $\mathcal{C}_{g}$ with generator polynomial $g(x)$, and we
proved that $\operatorname{rank}H_{X}=\dim\mathcal{C}_{g}=n-\deg g(x)$. We
call this cyclic code $\mathcal{C}_{g}$ the _syndrome code_ of $H_{X}$ since
its codewords are precisely the polynomial representations of the syndrome
space of $H_{X}$.

To complete the proof we also need to show that
$\operatorname{rank}H_{Z}=n-\deg g(x)$. Using similar arguments as above we
can consider the syndrome code for $H_{Z}$ and show that it is generated by
the “transposed” polynomial $g^{*}(x)=g(x^{-1})$. Though the codes generated
by the polynomials $g(x)$ and $g^{*}(x)$ may differ they always have the same
dimension since the corresponding circulant matrices $G$ and $G^{\mathrm{T}}$
have the same rank. Hence we also proved that $\operatorname{rank}H_{Z}=n-\deg
g(x)$ and the proof of formula (7) is complete.

###  IV-D Construction methods

The proof of Proposition 1 gives us also some valuable information how to find
generalized bicycle codes with high dimension. If we fix the circulant size
$\ell$ then all possible dimensions $k$ of the generalized bicycle codes with
this circulant size are characterized by the degrees of all possible factors
of the polynomial $x^{\ell}-1$. Indeed, for each factor $g(x)$ of the
polynomial $x^{\ell}-1$ we can always choose polynomials
$a(x),b(x)\in\mathbb{F}_{2}^{\left<\ell\right>}$ such that:

$a(x)\mathop{\mathrm{mod}}g(x)=b(x)\mathop{\mathrm{mod}}g(x)=0$ (8)

since these polynomials are just two codewords from the cyclic code
$\mathcal{C}_{g}$ generated by $g(x)$, which we called the syndrome code of
$H_{X}$. In order to produce a $w$-limited QLDPC we need to find low weight
polynomials codewords. In practice this can be accomplished by several
methods. If the circulant size $\ell$ is relatively small we can find
$a(x),b(x)$ by an exhaustive search over all polynomials of the given weight.

Another alternative is to generate random polynomials of the given weight from
$\mathbb{F}_{2}^{\left<\ell\right>}$ until we find a pair of polynomials that
satisfies condition (8). Since the probability that a random polynomial of the
given weight belong to $\mathcal{C}_{g}$ is equal approximately to $2^{-\deg
g(x)}$; than if we test more then $2^{\deg g(x)}$ random polynomials we will
find a polynomial from $\mathcal{C}_{g}$ with high probability.

When we find a pair of polynomials $a(x),b(x)$ we also need to check that the
corresponding code has good error correcting performance. This can be done by
a simulation of the corresponding generalized bicycle code.

All the polynomials $a(x),b(x)$ for the generalized bicycle codes described in
Appendix B were found by the described above methods.

###  IV-E Bicycle codes with syndrome protection

Another important observation made in the proof of Proposition 1 is that the
syndrome codes of the parity-check matrices $H_{X}$ and $H_{Z}$ are the cyclic
codes with generator polynomials $g(x)$ and $g^{*}(x)$ respectively. Let us
mention that the syndrome code of a parity-check matrix is precisely the set
of all possible syndromes for it. Hence if we use generator polynomials $g(x)$
and $g^{*}(x)$ that define cyclic codes with minimum distance $d$ we see that
the syndromes for matrices $H_{X}$ and $H_{Z}$ are protected by these cyclic
codes. Since the syndrome measurements for quantum codes are performed by a
faulty hardware some additional protection of syndromes may be used to improve
the the reliability of syndrome measurements[26, 27]. Let us also mention that
the polynomials $g(x)$ and $g^{*}(x)$ always produce cyclic codes
$\mathcal{C}_{g}$ and $\mathcal{C}_{g^{*}}$ with the same minimum distance
since the “transposition” map

$c(x)=\sum_{i=0}^{\ell-1}c_{i}x^{i}\mapsto
c^{*}(x)=\sum_{i=0}^{\ell-1}c_{i}x^{\ell-i}\mathop{\mathrm{mod}}x^{\ell}-1$

is an automorphism of the ring $\mathbb{F}_{2}^{\left<\ell\right>}$ that
respects the weight of the polynomials, and we have that
$\mathcal{C}_{g^{*}}=\\{c^{*}(x)\mid c(x)\in\mathcal{C}_{g}\\}$.

Hence we can use any cyclic code with generator polynomial $g(x)$ and minimum
distance $d$ to construct a code, where the syndromes for $H_{X}$ and $H_{Z}$
are protected by cyclic codes with minimum distance $d$. It is important to
note the weights of the polynomials $a(x),b(x)$ is always not smaller than
this minimum distance $d$ since $a(x),b(x)\in\mathcal{C}_{g}$.

###  IV-F Comparison with other codes

$10^{-2}$$10^{-1}$$10^{-5}$$10^{-4}$$10^{-3}$$10^{-2}$$10^{-1}$$10^{0}$Physical
error rateWERHMP vs GBHMP [[49,1,9]]GB [[48,6,8]]GB [[46,2,9]] Figure 4:
Comparison between the generalized bicycle (GB) codes (A3 and A4 in Appendix
B) and the $[[49,1,9]]$ homological product (HMP) code from [8].
$10^{-4}$$10^{-3}$$10^{-2}$$10^{-1}$$10^{-6}$$10^{-5}$$10^{-4}$$10^{-3}$$10^{-2}$$10^{-1}$$10^{0}$Physical
error rateLogical error rate[[200,32]] BP (binary)[[200,32]] NBP[[126,28]] BP
(binary)[[126,28]] BP Figure 5: The performance of the $[[200,32]]$ code with
the neural BP (NBP) decoder from [28] and the performance of the
$[[126,28,8]]$ generalized bicycle code A2 with the BP decoder (binary and
non-binary). $10^{-1}$$10^{-7}$$10^{-5}$$10^{-3}$$10^{-1}$$5\cdot
10^{-2}$physical error rateWERHB vs GB under BP-OSD deocderHB [[900,50]]GB
[[180,10]]GB [[900,50]] Figure 6: Comparison between hyperbicycle (HB) code
and generalized bicycle codes (GB) under BP-OSD decoder.

Let us consider several examples.

######  Example 1.

Let us consider the primitive narrow-sense BCH $[127,14,5]$ code
$\mathcal{C}_{g}$ with generator polynomial:

$g(x)=(x^{7}+x+1)\cdot(x^{7}+x^{5}+x^{3}+x+1).$

If we set $a(x)=1+x^{15}+x^{20}+x^{28}+x^{66}$ and
$b(x)=1+x^{58}+x^{59}+x^{100}+x^{121}$ we obtain the generalized bicycle
$[[254,28]]$ code. Its minimum distance is not available but the performance
of this code (see Fig. 1, code A1) is almost the same as the performance of
hypergraph product $[[7938,578,16]]$ code obtained from the two identical
circulant parity-check matrices $H$ of the cyclic code $[63,17,16]$ code
defined by the polynomial $h(x)=1+x^{3}+x^{34}+x^{41}+x^{57}$. This particular
code was chosen in order to match the high rate of the $[[254,28]]$ code. It
is important to note that both codes do not have $4$-cycles in matrices
$H_{X}$ and $H_{Z}$, and they have the same weight of stabilizers. It is also
interesting that the performance of the $[[254,28]]$ code is almost the same
even under the classical BP decoder without OSD post-processing. The reason of
such good performance with the BP decoder is not fully understood. One of the
possible explanations is related with the trapping set structure of the
$[[254,28]]$ code. Since its syndrome code has minimum distance $5$ it can not
have $(a,b)$ trapping sets131313An _$(a,b)$ trapping set_ or a  _near-
codeword_ for a parity-check matrix $H$ is a vector $v$ of weight $a$ such
that the corresponding syndrome $s^{\mathrm{T}}=Hv^{\mathrm{T}}$ has weight
$b$. with $b<5$. It is very well known[29] that $(a,b)$ trapping sets with
small $a$ and $b$ may greatly decrease the performance of the BP decoder. And
the $[[254,28]]$ can not have the most harmful trapping sets.

######  Example 2.

Let us consider the cyclic $[63,14,5]$ code with the generator polynomial

$g(x)=(x^{2}+x+1)\cdot(x^{6}+x^{5}+1)\cdot(x^{6}+x^{5}+x^{4}+x+1)$

If we set $a(x)=1+x+x^{14}+x^{16}+x^{22}$, $b(x)=1+x^{3}+x^{13}+x^{20}+x^{42}$
we obtain the generalized bicycle $[[126,28]]$ code. Its performance with the
standard BP decoder (binary and non-binary) is shown on Fig. 5, code A2. We
compared its performance with the performance of the neural BP decoder for the
Mackay bicycle $[[200,32]]$ code constructed in [28]. Such big difference in
the performance is mostly because the QLDPC $[[200,32]]$ code used in [28] has
small minimum distance compared to the $[[126,28]]$ code with minimum distance
is $8$. This minimum distance was found by an exhaustive search (see Appendix
B). Another possible reason is because the neural BP decoder proposed in [28]
was based on the binary BP, which usually has worse performance than its non-
binary version.

######  Example 3.

In this example we constructed two very small $8$-limited generalized bicycle
codes (the $[[48,6,8]]$ code A3 and the $[[46,2,9]]$ code A4, see Appendix B).
We compared their performance (see Fig. 4) with the performance of a
$8$-limited $[[49,1,9]]$ homological product (HMP) code from [8] using the BP
with OSD-like post-processing. As we can see the performance of the new
constructed codes is similar to the $[[49,1,9]]$ code. At the same time, their
rates are much higher.

######  Example 4.

On Fig. 6 we compared the performance of the hyperbicycle [[900, 50, 14]] code
from [10] with a new generalized bicycle $[[180,10]]$ code (code A5 in
Appendix B). We can see that the performance of the generalized bicycle
$[[180,10]]$ code is similar to the hyperbicycle [[900, 50, 14]] code. At the
same time, it has the same weight of stabilizers and has $5$ times smaller
code length.

##  V Generalization of hypergraph product codes

###  V-A Hypergraph product codes

In this section we propose a new generalization of the hypergraph product
codes[7] in the case when one of the parity-check matrices in the product is
square. Let us first remind the definition of these codes in a matrix form[9].
Suppose we have an $[n_{a},k_{a},d_{a}]$ linear code $\mathcal{C}_{a}$ and an
$[n_{b},k_{b},d_{b}]$ linear code $\mathcal{C}_{b}$ defined by parity-check
matrices141414The parity-check matrices are not necessary full rank.
$a\in\mathcal{M}_{m_{a}\times n_{a}}(\mathbb{F}_{2})$ and
$b\in\mathcal{M}_{m_{b}\times n_{b}}(\mathbb{F}_{2})$ respectively. Then the
hypergraph product code is the CSS $[[N,K,d]]$ code with $H_{X}=(a\otimes
I_{m_{b}},I_{m_{a}}\otimes b)$ and $H_{Z}=(I_{n_{a}}\otimes
b^{\mathrm{T}},a^{\mathrm{T}}\otimes I_{n_{b}})$, where
$N=n_{a}m_{b}+n_{b}m_{a}$,
$K=2k_{a}k_{b}-k_{a}(n_{b}-m_{b})-k_{b}(n_{a}-m_{a})$. As it was shown in [7],
the minimum distance $d$ of the hypergraph product code $\mathcal{C}$
satisfies the following lower bound:

$d\geq\min(d_{a},d_{b},d_{a}^{\mathrm{T}},d_{b}^{\mathrm{T}}),$

where $d_{a}^{\mathrm{T}}$ and $d_{b}^{\mathrm{T}}$ are the minimal distances
of the “transposed” codes $C_{a}^{\mathrm{T}}$ and $C_{b}^{\mathrm{T}}$
defined by the parity-check matrices $a^{\mathrm{T}}$ and $b^{\mathrm{T}}$
respectively. It is important to note that if the matrices $a$ and $b$ are
$(w_{c},w_{r})$-limited then the corresponding CSS code $\mathcal{C}$ is
$w$-limited, where $w=w_{c}+w_{r}$. Hence, using known asymptotically good
families of classical LDPC codes with $(w_{c},w_{r})$-limited parity check-
matrices, it is possible[7] to construct $w$-limited CSS codes with
asymptotically non-zero rate and $d=\Theta(\sqrt{n})$ as $n\to\infty$. In [9]
the hypergraph product construction was further improved and it was shown that
it is also possible to construct good hypergraph product codes using square
parity-check matrices $a$ and $b$. In fact many of the best known small length
hypergraph product codes are constructed using square parity check matrices of
cyclic codes (see [9, 10]). In [10] the hyperbicycle CSS codes, which
generalize both the generalized bicycle and hypergraph product codes, were
proposed. Here we consider another generalization of the hypergraph product
codes where the matrix $b$ is square.

###  V-B Generalized hypergraph product codes

In this section by a _ring_ we always mean a commutative ring with identity.
Let $R$ be a ring. We denote the ring of all $m\times n$ matrices over $R$ by
$\mathcal{M}_{m\times n}(R)$ or by $\mathcal{M}_{n}(R)$ when $m=n$. If $R$ is
the ring of $\ell\times\ell$ matrices over some field $\mathbb{F}$ we identify
the elements of $\mathcal{M}_{m\times n}(R)$ with the corresponding block
matrices from $\mathcal{M}_{m\ell\times n\ell}(\mathbb{F})$.

Consider a binary matrix $b\in\mathcal{M}_{\ell}(\mathbb{F}_{2})$. We say that
the matrix $b$ and a ring $R\subseteq\mathcal{M}_{\ell}(\mathbb{F}_{2})$
_commute_ if all matrices from $R$ commute with $b$.

######  Example 5.

Consider $b\in\mathcal{M}_{\ell}(\mathbb{F}_{2})$ and $R=\\{\mathbf{0},I\\}$,
where $\mathbf{0}$ and $I$ are the zero and the identity matrices from
$\mathcal{M}_{\ell}(\mathbb{F}_{2})$ respectively; then $b$ and $R$ always
commute.

######  Example 6.

Let $b$ be a binary circulant matrix and $R$ be the ring of all binary
circulant matrices of the same size; then $b$ and $R$ always commute.

Suppose that a matrix $b\in\mathcal{M}_{\ell}(\mathbb{F}_{2})$ and a ring
$R\subseteq\mathcal{M}_{\ell}(\mathbb{F}_{2})$ commute. Consider a matrix
$A=(a_{ij})_{m\times n}\in\mathcal{M}_{m\times n}(R)$. We denote by
$\mathcal{C}(A,b)$ the CSS code with the following parity-check
matrices151515Let us warn the reader that we understand $H_{X}$ and $H_{Z}$ as
the corresponding binary block matrices (not as matrices over
$\mathcal{M}_{\ell}(\mathbb{F}_{2})$).:

$H_{X}=[A,bI_{m}],H_{Z}=[b^{\mathrm{T}}I_{n},A^{*}],$ (9)

where $A^{*}=(a_{ji}^{T})_{n\times m}$, and $I_{m},I_{n}$ are the identity
matrices over $R$ of size $m$ and $n$ respectively. The correctness of this
definition follows from the following:

$H_{X}H_{Z}^{\mathrm{T}}=[A,bI_{m}]\begin{bmatrix}I_{n}b\\\ A\\\
\end{bmatrix}=Ab+bA=\mathbf{0}.$

The code length $N$ of the CSS code $\mathcal{C}(A,b)$ is given by
$N=(m+n)\ell$. We will show later how to find the dimension $K$ of the code
$\mathcal{C}(A,b)$ in a special case.

One can easily verify that if we take a matrix
$b\in\mathcal{M}_{\ell}(\mathbb{F}_{2})$ and the ring $R=\\{\mathbf{0},I\\}$
(as in Example 5) then the CSS code $\mathcal{C}(A,b)$ is the hypergraph
product code defined by the binary $m\times n$ matrix
$\tilde{a}=(\tilde{a}_{ij})_{m\times n}$ and the binary $\ell\times\ell$
matrix $b$, where for all $i\in[m]$, $j\in[n]$ we have:

$\tilde{a}_{ij}=\begin{cases}0,&\text{if $a_{ij}=\mathbf{0}$;}\\\ 1,&\text{if
$a_{ij}=I$.}\end{cases}$

We can also see that the ansatz with two commuting matrices $A$ and $B$ given
in (5) is also a special case of the new ansatz described in (9), where the
the matrix $A$ is a $1\times 1$ block matrix.

###  V-C Quasi-cyclic generalized hypergraph product codes

Now, let us take $b$ and $R$ as in Example 6. Hence $b$ is a binary circulant
matrix and $R$ is the ring of all binary circulant matrices of the same size.
In this case the matrices $H_{X}$ and $H_{Z}$ defined by (9) are block
matrices, where each block is a binary circulant matrices of size $\ell$. Such
matrices are called _quasi-cyclic_. Quasi-cyclic (QC) matrices are well known
in classical coding theory. In fact, most of the best known practical
classical LDPC codes have QC parity-check matrices. We will show in this
section how to find the dimension of the generalized hypergraph product codes
defined by (9). For simplicity we consider here only the case when the
circulant size $\ell$ is odd. Before we can provide the formula for the
dimension we need some supplementary definitions from algebra.

Here we adopt the polynomial representation of QC matrices used in [30, 31].
For any polynomial $p(x)\in\mathbb{F}_{q}[x]$ of degree $d$ we consider the
ring $\mathbb{F}_{q}[x]/(p(x))$ of polynomials
${f_{0}+f_{1}x+\dots+f_{d-1}x^{d-1}\in\mathbb{F}_{q}[x]}$ with addition and
multiplication modulo $p(x)$. By $\mathbb{F}_{q}^{d}$ denote the
$d$-dimensional space of the $d\times 1$ column vectors over $\mathbb{F}_{q}$.
We identify an element $f(x)\in\mathbb{F}_{q}[x]/(p(x))$ with the
corresponding column vector
$f=(f_{0},\ldots,f_{d-1})^{\mathrm{T}}\in\mathbb{F}_{q}^{d}$.

Let us recall that by $\mathbb{F}_{2}^{\left<\ell\right>}$ we denote the ring
of circulants $\mathbb{F}_{2}[x]/(x^{\ell}-1)$. We use the standard
identification of the circulant $\ell\times\ell$ matrices over
$\mathbb{F}_{2}$ with the elements of the ring
$\mathbb{F}_{2}^{\left<\ell\right>}$, where a column vector
$a\in\mathbb{F}_{2}^{\left<\ell\right>}$ corresponds to the circulant matrix
with the first column equal to $a$. Using this identification we can consider
an $m\ell\times n\ell$ QC matrix over $\mathbb{F}_{2}$ of circulant size
$\ell$ as an $m\times n$ matrix over the ring
$\mathbb{F}_{2}^{\left<\ell\right>}$. We also consider $n\times 1$ column
vectors over $\mathbb{F}_{2}^{\left<\ell\right>}$ as $n\ell\times 1$ column
vectors over $\mathbb{F}_{2}$. Given the above identification we consider
multiplication of an $m\ell\times n\ell$ QC matrix by an $n\ell\times 1$
column vector over $\mathbb{F}_{2}$ as multiplication of an $m\times n$ matrix
by an $n\times 1$ column vector over $\mathbb{F}_{2}^{\left<\ell\right>}$.

The algebraic structure of the ring $\mathbb{F}_{2}^{\left<\ell\right>}$ is
very well studied in the literature (see Appendix A for further details).
Since we consider the case when $\ell$ is odd, the polynomial $x^{\ell}-1$
factors into a product of irreducible polynomials over $\mathbb{F}_{2}$

$x^{\ell}-1=f_{1}(x)\cdots f_{s}(x).$ (10)

Hence the ring $\mathbb{F}_{2}^{\left<\ell\right>}$ is isomorphic to the
direct product of finite fields:

$\mathbb{F}_{2}^{\left<\ell\right>}\cong F_{1}\times\dots\times F_{s},$ (11)

where the field $F_{i}=\mathbb{F}_{2}[x]/\bigl{(}f_{i}(x)\bigr{)}$ has the
size $2^{d_{i}}$; $d_{i}=\deg f_{i}(x)$, $i\in[s]$. Let us consider the maps
${\varphi_{i}\colon\mathbb{F}_{2}^{\left<\ell\right>}\to F_{i}}$ given by the
formula:

$\varphi_{i}\colon u(x)\mapsto u(x)\mathop{\mathrm{mod}}f_{i}(x),i\in[s].$

We also naturally extend this map to any vectors and matrices over
$\mathbb{F}_{2}^{\left<\ell\right>}$. The following lemma is the key to the
dimension formula for the QC generalized hypergraph product codes.

######  Lemma 1.

Let $A\in\mathcal{M}_{m\times n}(\mathbb{F}_{2}^{\left<\ell\right>})$ be a
binary QC matrix. Then its rank (over $\mathbb{F}_{2}$) is given by:

$\operatorname{rank}_{\mathbb{F}_{2}}A=\sum_{i=1}^{s}d_{i}\operatorname{rank}_{F_{i}}\varphi_{i}(A)$

###### Proof:

The lemma easily follows from the isomorphism shown in (11) between
$\mathbb{F}_{2}^{\left<\ell\right>}$ and the direct product of the fields
$F_{1},\dots,F_{s}$. Indeed, let
$r_{i}=\operatorname{rank}_{F_{i}}\varphi_{i}(A)$, $i\in[s]$. Let
$A_{1},\dots,A_{n}$ be the columns of $A$. It is easy to see that each vector
$v$ that belongs to the column space of the matrix $A$ can be represented as
follows:

$v=A_{1}u_{1}+\dots+A_{n}u_{n},$

where $u_{1},\dots,u_{n}\in\mathbb{F}_{2}^{\left<\ell\right>}$. Then we see
that the cardinality of the column space of the non-binary matrix
$\varphi_{i}(A)$ over the field $F_{i}$ is equal to
$(2^{d_{i}})^{r_{i}}=2^{d_{i}r_{i}}$. Hence using the isomorphism (11) we
conclude that the number of different vectors in the column space of the
matrix $A$ is equal to

$\prod_{i=1}^{s}2^{d_{i}r_{i}}=2^{\sum_{i=1}^{s}d_{i}r_{i}},$

and we proved that
$\operatorname{rank}_{\mathbb{F}_{2}}A=\sum_{i=1}^{s}d_{i}r_{i}$. ∎

The following proposition provides the formula for the dimension of the QC CSS
code $\mathcal{C}(A,b)$.

######  Proposition 2.

Consider $b(x)\in\mathbb{F}_{2}^{\left<\ell\right>}$,
$A\in\mathcal{M}_{m\times n}(\mathbb{F}_{2}^{\left<\ell\right>})$, where
$\ell$ is odd. Let $g(x)=\gcd(b(x),x^{\ell}-1)=\prod_{i\in S}f_{i}(x)$,
$S\subseteq[s]$, where $f_{i}(x)$ are some irreducible polynomials from (10),
and $F_{i}=\mathbb{F}_{2}[x]/(f_{i}(x))$, $i\in S$, are the corresponding
finite fields. Then $\mathcal{C}(A,b)$ is the CSS $[[N,K]]$ code, where
$N=(m+n)\ell$ and

$K=\sum_{i\in S}\deg
f_{i}(x)(m+n-2\operatorname{rank}_{F_{i}}\varphi_{i}(A)).$

###### Proof:

The proof idea is the following. Let us mention that
$\varphi_{i}(H_{X})=[\varphi_{i}(A),\mathbf{0}]$ for all $i\in S$. Hence we
have
$\operatorname{rank}_{F_{i}}\varphi_{i}(H_{X})=\operatorname{rank}_{F_{i}}\varphi_{i}(A)$,
for all $i\in S$. At the same time for ${i\in[s]\setminus S}$, we obtain

$\operatorname{rank}_{F_{i}}\varphi_{i}(H_{X})=\operatorname{rank}_{F_{i}}[\varphi_{i}(A),\varphi_{i}(b)I_{m}]=m,$

since for all ${i\in[s]\setminus S}$ we have that $\varphi_{i}(b)\neq 0$ and
therefore the non-binary matrix $\varphi_{i}(H_{X})$ is full rank. Hence by
applying Lemma 1 to the matrix $H_{X}$ we have:

$\displaystyle m\ell-\operatorname{rank}H_{X}$
$\displaystyle=\sum_{i=1}^{s}\deg
f_{i}(x)(m-\operatorname{rank}_{F_{i}}\varphi_{i}(H_{X}))$
$\displaystyle=\sum_{i\in S}\deg
f_{i}(x)(m-\operatorname{rank}_{F_{i}}\varphi_{i}(A)).$

In order to complete the proof we need also to find the rank of the matrix
$H_{Z}$. It easier to find the rank of the matrix $H^{\prime}_{Z}$ obtained
from $H_{Z}$ by the application of the “transposition” map $u\mapsto u^{*}$ to
each element. Since the transposition map is an automorphism on the ring
$\mathbb{F}_{2}^{\left<\ell\right>}$ we see that the number of vectors in the
row space of $H_{Z}$ and the row space of $H^{\prime}_{Z}$ is the same. Hence
$\operatorname{rank}H_{Z}=\operatorname{rank}H^{\prime}_{Z}$. The rank of the
matrix $H^{\prime}_{Z}=[bI_{n},A^{T}]$, can be found in the same way as for
the matrix $H_{X}$:

$\displaystyle n\ell-\operatorname{rank}H^{\prime}_{Z}$
$\displaystyle=\sum_{i=1}^{s}\deg
f_{i}(x)(n-\operatorname{rank}_{F_{i}}\varphi_{i}(H^{\prime}_{Z}))$
$\displaystyle=\sum_{i\in S}\deg
f_{i}(x)(n-\operatorname{rank}_{F_{i}}\varphi_{i}(A^{\mathrm{T}}))$
$\displaystyle=\sum_{i\in S}\deg
f_{i}(x)(n-\operatorname{rank}_{F_{i}}\varphi_{i}(A)).$

Now, we apply formula (4) for the CSS dimension and obtain:

$\displaystyle K$
$\displaystyle=N-\operatorname{rank}H_{X}-\operatorname{rank}H_{Z}$
$\displaystyle=(m\ell-\operatorname{rank}H_{X})+(n\ell-\operatorname{rank}H^{\prime}_{Z})$
$\displaystyle=\sum_{i\in S}\deg
f_{i}(x)(m+n-2\operatorname{rank}_{F_{i}}\varphi_{i}(A)).$

This concludes the proof. ∎

######  Example 7.

On Fig. 7 you can see the performance (under the BP-OSD decoder) of two codes:
the [[1922,50,16]] hypergraph product (HP) code (code C2 in Appendix B) and
the [[882,24]] generalized hypergraph product (GHP) code (B1 in Appendix B).
You can see that Code C2 has an error floor due to large amount of low weight
codewords.

$10^{-2}$$10^{-1}$$10^{-8}$$10^{-6}$$10^{-4}$$10^{-2}$$10^{0}$Physical error
rateWERGHP vs HPHP [[1922,50,16]]HP, OSD [[1922,50,16]]GHP [[882,24]]GHP, OSD
[[882,24]] Figure 7: Comparison between the [[1922,50,16]] hypergraph product
(HP) code (C2) and the [[882,24]] generalized hypergraph product (GHP) code
(B1). Code C2 has an error floor due to large amount of low weight codewords.

##  VI Conclusion

We proposed a new modification of the BP decoder based on an OSD-like post-
processing that shows on some codes much better performance than all the
modifications known to the authors. We also constructed several new
generalized bicycle codes that show very good performance compared to the
other known codes with similar parameters. We proposed a new ansatz for
quantum CSS codes and showed how to estimate the dimension of such codes in
some special cases. Unfortunately, we did not find any nontrivial general
lower bound on the minimum distance of such codes. We think that to find such
a bound is an interesting open problem since this class contains some already
known good QLDPC codes and the practical performance of some previously
unknown codes from it is also quite good. Finally, we compared the performance
of one of the code from the new family and showed that it has better
performance than a relatively large surface code with similar code length
decoded by a near optimal decoder.

## Acknowledgment

The authors would like to thank Dr. Xuecang Zhang from Huawei Technologies
Co., Ltd. for the support of this work and for useful discussion.

## References

  * [1] E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, “Topological quantum memory,” _Journal of Mathematical Physics_ , vol. 43, no. 9, pp. 4452–4505, 2002. [Online]. Available: https://doi.org/10.1063/1.1499754
  * [2] M. H. Freedman and D. A. Meyer, “Projective plane and planar quantum codes,” _Foundations of Computational Mathematics_ , vol. 1, no. 3, pp. 325–332, Jul 2001. [Online]. Available: https://doi.org/10.1007/s102080010013
  * [3] H. Bombin and M. A. Martin-Delgado, “Topological quantum distillation,” _Phys. Rev. Lett._ , vol. 97, p. 180501, Oct 2006. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.97.180501
  * [4] D. S. Wang, A. G. Fowler, and L. C. L. Hollenberg, “Surface code quantum computing with error rates over 1%,” _Phys. Rev. A_ , vol. 83, p. 020302, Feb 2011. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.83.020302
  * [5] S. Bravyi, M. Suchara, and A. Vargo, “Efficient algorithms for maximum likelihood decoding in the surface code,” _Phys. Rev. A_ , vol. 90, p. 032326, Sep 2014. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.90.032326
  * [6] N. P. Breuckmann and B. M. Terhal, “Constructions and noise threshold of hyperbolic surface codes,” _IEEE Transactions on Information Theory_ , vol. 62, no. 6, pp. 3731–3744, June 2016.
  * [7] J. Tillich and G. Zémor, “Quantum ldpc codes with positive rate and minimum distance proportional to $n^{1/2}$,” in _2009 IEEE International Symposium on Information Theory_ , June 2009, pp. 799–803.
  * [8] S. Bravyi and M. B. Hastings, “Homological product codes,” in _Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing_ , ser. STOC ’14. New York, NY, USA: ACM, 2014, pp. 273–282. [Online]. Available: http://doi.acm.org/10.1145/2591796.2591870
  * [9] A. A. Kovalev and L. P. Pryadko, “Improved quantum hypergraph-product ldpc codes,” in _2012 IEEE International Symposium on Information Theory Proceedings_ , July 2012, pp. 348–352.
  * [10] A. A. Kovalev and L. P. Pryadko, “Quantum kronecker sum-product low-density parity-check codes with finite rate,” _Phys. Rev. A_ , vol. 88, p. 012311, Jul 2013. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.88.012311
  * [11] Z. Babar, P. Botsinis, D. Alanis, S. X. Ng, and L. Hanzo, “Fifteen years of quantum ldpc coding and improved decoding strategies,” _IEEE Access_ , vol. 3, pp. 2492–2519, 2015.
  * [12] M. Hagiwara and H. Imai, “Quantum quasi-cyclic ldpc codes,” in _2007 IEEE International Symposium on Information Theory_ , June 2007, pp. 806–810.
  * [13] M. P. C. Fossorier and S. Lin, “Soft-decision decoding of linear block codes based on ordered statistics,” _IEEE Transactions on Information Theory_ , vol. 41, no. 5, pp. 1379–1396, Sep. 1995.
  * [14] M. P. C. Fossorier, “Iterative reliability-based decoding of low-density parity check codes,” _IEEE Journal on Selected Areas in Communications_ , vol. 19, no. 5, pp. 908–917, May 2001.
  * [15] B. Dorsch, “A decoding algorithm for binary block codes and $j$-ary output channels (corresp.),” _IEEE Transactions on Information Theory_ , vol. 20, no. 3, pp. 391–394, May 1974.
  * [16] J. Haah, “Local stabilizer codes in three dimensions without string logical operators,” _Phys. Rev. A_ , vol. 83, p. 042330, Apr 2011. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.83.042330
  * [17] D. Poulin and Y. C., “On the iterative decoding of sparse quantum codes,” _Quantum Info. Comput._ , vol. 8, no. 10, pp. 987–1000, Nov. 2008. [Online]. Available: http://dl.acm.org/citation.cfm?id=2016985.2016993
  * [18] Y. Wang, B. C. Sanders, B. Bai, and X. Wang, “Enhanced feedback iterative decoding of sparse quantum codes,” _IEEE Transactions on Information Theory_ , vol. 58, no. 2, pp. 1231–1241, Feb 2012.
  * [19] A. Rigby, J. Olivier, and P. Jarvis, “Modified belief propagation decoders for quantum ldpc codes,” _arXiv_ , March 2019. [Online]. Available: http://arxiv.org/abs/1903.07404v1
  * [20] D. Gottesman, “Stabilizer codes and quantum error correction,” Ph.D. dissertation, California Institute of Technology, 1993, quant-ph/9705052.
  * [21] A. R. Calderbank and P. W. Shor, “Good quantum error-correcting codes exist,” _Phys. Rev. A_ , vol. 54, pp. 1098–1105, Aug 1996. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.54.1098
  * [22] R. G. Gallager, _Low-Density Parity-Check Codes_. M.I.T. Press, Cambridge, MA, 1963.
  * [23] R. M. Tanner, “A recursive approach to low complexity codes,” _Information Theory, IEEE Transactions on_ , vol. 27, no. 5, pp. 533–547, 1981.
  * [24] M. Fossorier, D. Declercq, and E. Biglieri, _Channel Coding: Theory, Algorithms, and Applications_. Academic Press, July 2014.
  * [25] D. J. C. Mackay, _Information Theory, Inference and Learning Algorithms_. Cambridge, UK: Cambridge University Press, Oct. 2003.
  * [26] H. Bombin, R. W. Chhajlany, M. Horodecki, and M. A. Martin-Delgado, “Self-correcting quantum computers,” _New Journal of Physics_ , vol. 15, no. 5, p. 055023, may 2013. [Online]. Available: https://doi.org/10.1088%2F1367-2630%2F15%2F5%2F055023
  * [27] Y. Fujiwara, “Ability of stabilizer quantum error correction to protect itself from its own imperfection,” _Phys. Rev. A_ , vol. 90, p. 062304, Dec 2014\. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.90.062304
  * [28] Y.-H. Liu and D. Poulin, “Neural belief-propagation decoders for quantum error-correcting codes,” _arXiv_ , 2018.
  * [29] T. Richardson, “Error-floors of ldpc codes,” in _Proceedings of the 41st Annual Conference on Communication, Control and Computing_ , 2003, pp. 1426–1435.
  * [30] K. Lally and P. Fitzpatrick, “Algebraic structure of quasicyclic codes,” _Discrete Applied Mathematics_ , vol. 111, no. 1–2, pp. 157–175, 2001.
  * [31] R. Smarandache and P. Vontobel, “Quasi-cyclic LDPC codes: Influence of proto- and tanner-graph structure on minimum Hamming distance upper bounds,” _IEEE Transactions on Information Theory_ , vol. 58, no. 2, pp. 585–607, 2012.
  * [32] S. Ling, H. Niederreiter, and P. Solé, “On the algebraic structure of quasi-cyclic codes IV: Repeated roots,” _Designs, Codes and Cryptography_ , vol. 38, pp. 337–361, 2006.

##  Appendix A Algebraic structure of the ring
$\mathbb{F}_{q}^{\left<\ell\right>}$

Let $\mathbb{F}_{q}$ be a finite field of characteristics 2. The algebraic
structure of the ring $\mathbb{F}_{q}^{\left<\ell\right>}$ is well studied in
the coding literature (see, e.g., [32]). Below we briefly review it.

First, let us consider the special case when $\ell$ is odd. In this case the
polynomial $x^{\ell}-1$ factors into a product of irreducible polynomials over
$\mathbb{F}_{q}$

$x^{\ell}-1=f_{1}(x)\cdots f_{s}(x).$ (12)

This is true, since

$\gcd\left((x^{\ell}-1)^{\prime},x^{\ell}-1\right)=\gcd\left(\ell
x^{\ell-1},x^{\ell}-1\right)=1,$

and the polynomial $x^{\ell}-1$ is square-free.

In the general case we have $\ell=2^{e}\ell^{\prime}$, where $\ell^{\prime}$
is odd. Hence it follows that

$x^{\ell}-1=x^{2^{e}\ell^{\prime}}-1=(x^{\ell^{\prime}}-1)^{2^{e}}.$

Moreover, since $\ell^{\prime}$ is odd, we can apply the factorization (12) to
the polynomial $x^{\ell^{\prime}}-1$ and obtain that

$x^{\ell}-1=\bigl{(}f_{1}(x)\bigr{)}^{2^{e}}\cdots\bigl{(}f_{s}(x)\bigr{)}^{2^{e}}.$
(13)

Since the polynomials
$(f_{1}(x)\bigr{)}^{2^{e}},\dots,(f_{s}(x)\bigr{)}^{2^{e}}$ are pairwise
coprime, from the Chinese remainder theorem it follows that the ring
$\mathbb{F}_{q}^{\left<\ell\right>}$ is isomorphic to the direct product

$R_{1}\times\dots\times R_{s}$ (14)

of the rings $R_{i}=\mathbb{F}_{q}[x]/\bigl{(}f_{i}(x)\bigr{)}^{2^{e}}$,
$i\in[s]$.

When $\ell$ is odd we have $e=0$ and the rings $R_{1},\dots,R_{s}$ are in fact
fields, since the polynomials $f_{1}(x),\dots,f_{s}(x)$ are irreducible over
$\mathbb{F}_{q}$.

##  Appendix B Matrices used for simulations

All matrices for the generalized hypergraph product codes and the generalized
bicycle codes have the form $H_{X}=[A,B]$, $H_{Z}=[B^{T},A^{T}]$ where $A$ and
$B$ are quasicyclic matrices. To define the code we will specify only matrices
$A$ and $B$ in the polynomial form as matrices over
$\mathbb{F}_{2}^{\left<\ell\right>}$.

For some codes presented here we also give the exact minimum distance obtained
by a straightforward reduction of this problem to a mixed integer linear
program and using the GNU Linear Programming Kit, Version 4.63,
http://www.gnu.org/software/glpk/glpk.html.

  1. A.

Generalized bicycle (GB) codes. The matrices $A$ and $B$ have form $A=(a(x))$,
$B=(b(x))$, so here we specify the polynomials $a(x)$, $b(x)$, and the
circulant size $\ell$.

    1. A1)

$[[254,28]]$ code ($\ell=127$).

$\displaystyle a(x)$ $\displaystyle=1+x^{15}+x^{20}+x^{28}+x^{66},$
$\displaystyle b(x)$ $\displaystyle=1+x^{58}+x^{59}+x^{100}+x^{121}.$

    2. A2)

$[[126,28]]$ code ($\ell=63$).

$\displaystyle a(x)$ $\displaystyle=1+x+x^{14}+x^{16}+x^{22},$ $\displaystyle
b(x)$ $\displaystyle=1+x^{3}+x^{13}+x^{20}+x^{42}.$

    3. A3)

$[[48,6,8]]$ code ($\ell=24$).

$\displaystyle a(x)$ $\displaystyle=1+x^{2}+x^{8}+x^{15},$ $\displaystyle
b(x)$ $\displaystyle=1+x^{2}+x^{12}+x^{17}.$

    4. A4)

$[[46,2,9]]$ code ($\ell=23$).

$\displaystyle a(x)$ $\displaystyle=1+x^{5}+x^{8}+x^{12},$ $\displaystyle
b(x)$ $\displaystyle=1+x+x^{5}+x^{7}.$

    5. A5)

$[[180,10]]$ code ($\ell=90$).

$\displaystyle a(x)$ $\displaystyle=1+x^{28}+x^{80}+x^{89},$ $\displaystyle
b(x)$ $\displaystyle=1+x^{2}+x^{21}+x^{25}.$

    6. A6)

$[[900,50]]$ code ($\ell=450$).

$\displaystyle a(x)$ $\displaystyle=1+x^{97}+x^{372}+x^{425},$ $\displaystyle
b(x)$ $\displaystyle=1+x^{50}+x^{265}+x^{390}.$

  2. B.

Generalized hypergraph product (GHP) codes. Here the matrix $B$ is diagonal;
$B=b(x)I_{n}$, where $I_{n}$ is the $n\times n$ identity matrix over the ring
$\mathbb{F}_{2}^{\left<\ell\right>}$.

    1. B1)

$[[882,24]]$ code. Matrix is (3,6)-regular ($\ell=63$).

$\displaystyle A$
$\displaystyle=\left(\begin{array}[]{ccccccc}x^{27}&0&0&0&0&1&x^{54}\\\
x^{54}&x^{27}&0&0&0&0&1\\\ 1&x^{54}&x^{27}&0&0&0&0\\\
0&1&x^{54}&x^{27}&0&0&0\\\ 0&0&1&x^{54}&x^{27}&0&0\\\
0&0&0&1&x^{54}&x^{27}&0\\\ 0&0&0&0&1&x^{54}&x^{27}\end{array}\right),$
$\displaystyle B$ $\displaystyle=(1+x+x^{6})I_{7}.$

    2. B2)

$[[882,48]]$ code. The half of the columns for both $H_{X}$ and $H_{Z}$
matrices have weight $3$, another half has weight $5$. All the rows have
weight 8 ($\ell=63$).

$\displaystyle A$
$\displaystyle=\left(\begin{array}[]{ccccccc}x^{27}&0&0&1&x^{18}&x^{27}&1\\\
1&x^{27}&0&0&1&x^{18}&x^{27}\\\ x^{27}&1&x^{27}&0&0&1&x^{18}\\\
x^{18}&x^{27}&1&x^{27}&0&0&1\\\ 1&x^{18}&x^{27}&1&x^{27}&0&0\\\
0&1&x^{18}&x^{27}&1&x^{27}&0\\\
0&0&1&x^{18}&x^{27}&1&x^{27}\end{array}\right),$ $\displaystyle B$
$\displaystyle=(1+x+x^{6})I_{7}.$

    3. B3)

$[[1270,28]]$ code. Matrix is (3,6)-regular ($\ell=127$).

$\displaystyle A$
$\displaystyle=\left(\begin{array}[]{ccccc}1&0&x^{51}&x^{52}&0\\\
0&1&0&x^{111}&x^{20}\\\ 1&0&x^{98}&0&x^{122}\\\ 1&x^{80}&0&x^{119}&0\\\
0&1&x^{5}&0&x^{106}\end{array}\right),$ $\displaystyle B$
$\displaystyle=(1+x+x^{7})I_{5}.$

  3. C.

Hypergraph product (HP) codes. Each hypergraph product code in our simulations
is constructed from a single cyclic code defined by its parity polynomial
$h(x)$ and the length $\ell$.

    1. C1)

$[[7938,578,16]]$ code. Matrix is (5,10)-regular.

$\ell=63,\quad h(x)=1+x^{3}+x^{34}+x^{41}+x^{57}.$

    2. C2)

$[[1922,50,16]]$ code. Matrix is (3,6)-regular.

$\ell=31,\quad p(x)=1+x^{2}+x^{5}$

  4. D.

Haah’s cubic codes. We used the $[[1024,30]]$ Haah’s cubic code on the
$8\times 8\times 8$ lattice from [16, Code 1].

  5. E.

Hyperbicycle (HB) codes. We used the $[[900,50,14]]$ hyperbicycle code from
[10, Example 6].

  6. F.

Homological product (HMP) codes. We used one of randomly constructed
$[[49,1,9]]$ homological product codes from [8].

TABLE I: Codes parameters Code | $N$ | $K$ | $d$ | rate | $w_{r}$ | $w_{c}$ | girth
---|---|---|---|---|---|---|---
A1 | 254 | 28 |  | 0.110 | 10 | 5 | 6
A2 | 126 | 28 | 8 | 0.222 | 10 | 5 | 4
A3 | 48 | 6 | 8 | 0.125 | 8 | 4 | 4
A4 | 46 | 2 | 9 | 0.043 | 8 | 4 | 4
A5 | 180 | 10 |  | 0.056 | 8 | 4 | 6
A6 | 900 | 50 |  | 0.056 | 8 | 4 | 6
B1 | 882 | 24 |  | 0.027 | 6 | 3 | 6
B2 | 882 | 48 |  | 0.054 | 8 | 3,5 | 6
B3 | 1270 | 28 |  | 0.022 | 6 | 3 | 6
C1 | 7938 | 578 | 16 | 0.073 | 10 | 5 | 6
C2 | 1922 | 50 | 16 | 0.026 | 6 | 3 | 6
D | 1024 | 30 |  | 0.029 | 8 | 4 | 4
E | 900 | 50 | 14 | 0.056 | 8 | 4 | 4
F | 49 | 1 | 9 | 0.020 | 6,8 | 6,8 | 4


* Lavvas . (2013) lavvas2013titanionosphereLavvas, PP., Yelle, RV., Koskinen, T., Bazin, A., Vuitton, V., Vigren, E.Snowden, D.  201302\.  Aerosol growth in Titan’s ionosphere Aerosol growth in Titan’s ionosphere.  Proceedings of the National Academy of Science11082729-2734.  10.1073/pnas.1217059110
  * Lellouch . (2010) lellouch2010Lellouch, E., de Bergh, C., Sicardy, B., Ferron, S. Käufl, HU.  201003\.  Detection of CO in Triton’s atmosphere and the nature of surface-atmosphere interactions Detection of CO in Triton’s atmosphere and the nature of surface-atmosphere interactions.  Astronomy and Astrophysics512L8.  10.1051/0004-6361/201014339
  * Lewis . (2020) lewis2019plutoseasonsLewis, B., Stansberry, J., Holler, B., Grundy, W., Schmitt, B., Protopapa, S.the New Horizons Science Team  202001\.  Distribution and Energy Balance of Pluto’s Nitrogen Ice, as seen by New Horizons in 2015 Distribution and Energy Balance of Pluto’s Nitrogen Ice, as seen by New Horizons in 2015.  Icarusin press.  10.1016/j.icarus.2020.113633
  * Liang . (2007) Liang2007Liang, MC., Yung, YL. Shemansky, DE.  200706\.  Photolytically Generated Aerosols in the Mesosphere and Thermosphere of Titan Photolytically Generated Aerosols in the Mesosphere and Thermosphere of Titan.  ApJ6612L199-L202.  10.1086/518785
  * Luspay-Kuti . (2017) luspaykuti2017Luspay-Kuti, A., Mandt, K., Jessup, KL., Kammer, J., Hue, V., Hamel, M. Filwett, R.  201711\.  Photochemistry on Pluto - I. Hydrocarbons and aerosols Photochemistry on Pluto - I. Hydrocarbons and aerosols.  MNRAS4721104-117.  10.1093/mnras/stx1362
  * Lyons . (1992) lyons1992Lyons, JR., Yung, YL. Allen, M.  199204\.  Solar Control of the Upper Atmosphere of Triton Solar Control of the Upper Atmosphere of Triton.  Science2565054204-206.  10.1126/science.11540928
  * Maillard . (2018) maillard2018solubilityMaillard, J., Carrasco, N., Schmitz-Afonso, I., Gautier, T. Afonso, C.  201808\.  Comparison of soluble and insoluble organic matter in analogues of Titan’s aerosols Comparison of soluble and insoluble organic matter in analogues of Titan’s aerosols.  Earth and Planetary Science Letters495185-191.  10.1016/j.epsl.2018.05.014
  * Masters . (2014) masters2014tritonaspartofsolarsystemMasters, A., Achilleos, N., Agnor, CB., Campagnola, S., Charnoz, S., Christophe, B.Volwerk, M.  2014Dec.  Neptune and Triton: Essential pieces of the Solar System puzzle Neptune and Triton: Essential pieces of the Solar System puzzle.  Planetary and Space Science104108-121.  10.1016/j.pss.2014.05.008
  * Materese . (2015) materese2015Materese, CK., Cruikshank, DP., Sandford, SA., Imanaka, H. Nuevo, M.  201510\.  Ice Chemistry on Outer Solar System Bodies: Electron Radiolysis of N2-, CH4-, and CO-Containing Ices Ice Chemistry on Outer Solar System Bodies: Electron Radiolysis of N2-, CH4-, and CO-Containing Ices.  ApJ8122150.  10.1088/0004-637X/812/2/150
  * Materese . (2014) materese2014Materese, CK., Cruikshank, DP., Sandford, SA., Imanaka, H., Nuevo, M. White, DW.  201406\.  Ice Chemistry on Outer Solar System Bodies: Carboxylic Acids, Nitriles, and Urea Detected in Refractory Residues Produced from the UV Photolysis of N2:CH4:CO-Containing Ices Ice Chemistry on Outer Solar System Bodies: Carboxylic Acids, Nitriles, and Urea Detected in Refractory Residues Produced from the UV Photolysis of N2:CH4:CO-Containing Ices.  ApJ7882111.  10.1088/0004-637X/788/2/111
  * McDonald . (1994) mcdonald1994titanandtritontholinMcDonald, GD., Thompson, WR., Heinrich, M., Khare, BN. Sagan, C.  1994Mar.  Chemical Investigation of Titan and Triton Tholins Chemical Investigation of Titan and Triton Tholins.  Icarus1081137-145.  10.1006/icar.1994.1046
  * McKinnon (1984) mckinnon1984McKinnon, WB.  198409\.  On the origin of Triton and Pluto On the origin of Triton and Pluto.  Nature3115984355-358.  10.1038/311355a0
  * Merlin . (2018) merlin2018tritonicemeasurementsMerlin, F., Lellouch, E., Quirico, E. Schmitt, B.  2018Nov.  Triton’s surface ices: Distribution, temperature and mixing state from VLT/SINFONI observations Triton’s surface ices: Distribution, temperature and mixing state from VLT/SINFONI observations.  Icarus314274-293.  10.1016/j.icarus.2018.06.003
  * Moore Hudson (2003) mooreandhudson2003Moore, MH. Hudson, RL.  200302\.  Infrared study of ion-irradiated N 2-dominated ices relevant to Triton and Pluto: formation of HCN and HNC Infrared study of ion-irradiated N 2-dominated ices relevant to Triton and Pluto: formation of HCN and HNC.  Icarus1612486-500.  10.1016/S0019-1035(02)00037-4
  * Moran . (2021) moran2021Moran, SE., Hörst, SM., He, C., Radke, MJ., Sebree, JA., Izenberg, NR.Wolters, C.  2021\.  Data associated with the publication: Triton Haze Analogues: the Role of Carbon Monoxide in Haze Formation Data associated with the publication: Triton Haze Analogues: the Role of Carbon Monoxide in Haze Formation.  Johns Hopkins University Data ArchiveV1.  10.7281/T1/BXJT0B
  * Moran . (2020) moran2020Moran, SE., Hörst, SM., Vuitton, V., He, C., Lewis, NK., Fland inet, L.Valenti, JA.  202006\.  Chemistry of Temperate Super-Earth and Mini-Neptune Atmospheric Hazes from Laboratory Experiments Chemistry of Temperate Super-Earth and Mini-Neptune Atmospheric Hazes from Laboratory Experiments.  The Planetary Science Journal1117.  10.3847/PSJ/ab8eae
  * Neish . (2010) neish2010Neish, CD., Somogyi, Á. Smith, MA.  201004\.  Titan’s Primordial Soup: Formation of Amino Acids via Low-Temperature Hydrolysis of Tholins Titan’s Primordial Soup: Formation of Amino Acids via Low-Temperature Hydrolysis of Tholins.  Astrobiology103337-347.  10.1089/ast.2009.0402
  * Neri . (1987) neri1987fringesremovalNeri, F., Saitta, G. Chiofalo, S.  198707\.  A simple procedure to remove the interference fringes from optical spectra A simple procedure to remove the interference fringes from optical spectra.  Journal of Physics E Scientific Instruments207894-896.  10.1088/0022-3735/20/7/015
  * Nimmo Spencer (2015) nimmoandspencer2015Nimmo, F. Spencer, JR.  201501\.  Powering Triton’s recent geological activity by obliquity tides: Implications for Pluto geology Powering Triton’s recent geological activity by obliquity tides: Implications for Pluto geology.  Icarus2462-10.  10.1016/j.icarus.2014.01.044
  * Ohno . (2021) ohno2021tritonOhno, K., Zhang, X., Tazaki, R. Okuzumi, S.  2021may.  Haze Formation on Triton Haze formation on triton.  The Astrophysical Journal912137.  https://doi.org/10.3847/1538-4357/abee82 10.3847/1538-4357/abee82
  * Oleson Landis (2018) Oleson2018Oleson, SR. Landis, G.  2018\.  Triton Hopper: Exploring Neptune’s Captured Kuiper Belt Object Triton Hopper: Exploring Neptune’s Captured Kuiper Belt Object.  V. Badescu K. Zacny (), Outer Solar System Outer solar system ( 367).  10.1007/978-3-319-73845-1_9
  * Olkin . (1997) olkin1997Olkin, CB., Elliot, JL., Hammel, HB., Cooray, AR., McDonald, SW., Foust, JA.Reitsema, HJ.  199709\.  The Thermal Structure of Triton’s Atmosphere: Results from the 1993 and 1995 Occultations The Thermal Structure of Triton’s Atmosphere: Results from the 1993 and 1995 Occultations.  Icarus1291178-201.  10.1006/icar.1997.5757
  * Orthous-Daunay . (2020) orthousdaunay2020Orthous-Daunay, FR., Thissen, R. Vuitton, V.  202001\.  Measured mass to stoichoimetric formula through exhaustive search Measured mass to stoichoimetric formula through exhaustive search.  F. Salama H. Linnartz (), Laboratory Astrophysics: From Observations to Interpretation Laboratory astrophysics: From observations to interpretation ( 350, 193-199).  10.1017/S1743921319008032
  * Pollack . (1990) pollack1990Pollack, JB., Schwartz, JM. Rages, K.  199010\.  Scatterers in Triton’s Atmosphere: Implications for the Seasonal Volatile Cycle Scatterers in Triton’s Atmosphere: Implications for the Seasonal Volatile Cycle.  Science2504979440-443.  10.1126/science.250.4979.440
  * Porco . (2005) Porco2005Porco, CC., Baker, E., Barbara, J., Beurle, K., Brahic, A., Burns, JA.West, R.  200503\.  Imaging of Titan from the Cassini spacecraft Imaging of Titan from the Cassini spacecraft.  Nature4347030159-168.  10.1038/nature03436
  * Prockter . (2019) prockter2019tridentProckter, LM., Mitchell, KL., Howett, CJA., Smythe, WD., Sutin, BM., Bearden, DA. Frazier, WE.  201903\.  Exploring Triton with Trident: A Discovery Class Mission Exploring Triton with Trident: A Discovery Class Mission.  Lunar and Planetary Science Conference Lunar and planetary science conference ( 3188).
  * Protopapa . (2020) protopapa2020Protopapa, S., Olkin, CB., Grundy, WM., Li, JY., Verbiscer, A., Cruikshank, DP.Singer, K.  202002\.  Disk-resolved Photometric Properties of Pluto and the Coloring Materials across its Surface Disk-resolved Photometric Properties of Pluto and the Coloring Materials across its Surface.  AJ159274.  10.3847/1538-3881/ab5e82
  * Rages Pollack (1992) ragesandpollack1992Rages, K. Pollack, JB.  199210\.  Voyager imaging of Triton’s clouds and hazes Voyager imaging of Triton’s clouds and hazes.  Icarus992289-301.  10.1016/0019-1035(92)90147-Y
  * Ruf . (2018) Ruf2018VKastroRuf, A., Le Sergeant d’Hendecourt, L. Schmitt-Kopplin, P.  201806\.  Data-Driven Astrochemistry: One Step Further within the Origin of Life Puzzle Data-driven astrochemistry: One step further within the origin of life puzzle.  Life818.  10.3390/life8020018
  * Rymer . (2020) rymer2020Rymer, AM., Clyde, B., Runyon, K. the Neptune-Odyssey team.  202009\.  Neptune Odyssey: Mission to the Neptune-Triton System Neptune Odyssey: Mission to the Neptune-Triton System.  LPI Contributions25476031.
  * Schenk Zahnle (2007) schenkandzahnle2007surfaceageSchenk, PM. Zahnle, K.  200712\.  On the negligible surface age of Triton On the negligible surface age of Triton.  Icarus1921135-149.  10.1016/j.icarus.2007.07.004
  * Sciamma-O’Brien . (2010) sciammaobrien2010Sciamma-O’Brien, E., Carrasco, N., Szopa, C., Buch, A. Cernogora, G.  201010\.  Titan’s atmosphere: An optimal gas mixture for aerosol production? Titan’s atmosphere: An optimal gas mixture for aerosol production?  Icarus2092704-714.  10.1016/j.icarus.2010.04.009
  * Sebree . (2018) sebree2018Sebree, JA., Roach, MC., Shipley, ER., He, C. Hörst, SM.  2018Oct.  Detection of Prebiotic Molecules in Plasma and Photochemical Aerosol Analogs Using GC/MS/MS Techniques Detection of Prebiotic Molecules in Plasma and Photochemical Aerosol Analogs Using GC/MS/MS Techniques.  Astrophysical Journal8652133.  10.3847/1538-4357/aadba1
  * Smith . (1989) smith1989Smith, BA., Soderblom, LA., Banfield, D., Barnet, C., Basilevksy, AT., Beebe, RF.Veverka, J.  198912\.  Voyager 2 at Neptune: Imaging Science Results Voyager 2 at Neptune: Imaging Science Results.  Science24649361422-1449.  10.1126/science.246.4936.1422
  * Stansberry . (2015) stansberry2015Stansberry, JA., Spencer, J. Linscott, I.  201511\.  Voyager IRIS Measurements of Triton’s Thermal Emission: Implications for Pluto? Voyager IRIS Measurements of Triton’s Thermal Emission: Implications for Pluto?  AAS/Division for Planetary Sciences Meeting Abstracts #47 Aas/division for planetary sciences meeting abstracts #47 ( 210.32).
  * Stern . (2015) stern2015Stern, SA., Bagenal, F., Ennico, K., Gladstone, GR., Grundy, WM., McKinnon, WB.Zirnstein, E.  201510\.  The Pluto system: Initial results from its exploration by New Horizons The Pluto system: Initial results from its exploration by New Horizons.  Science3506258aad1815.  10.1126/science.aad1815
  * Stern McKinnon (2000) sternandmckinnon2000tritonsurfaceageStern, SA. McKinnon, WB.  200002\.  Triton’s Surface Age and Impactor Population Revisited in Light of Kuiper Belt Fluxes: Evidence for Small Kuiper Belt Objects and Recent Geological Activity Triton’s Surface Age and Impactor Population Revisited in Light of Kuiper Belt Fluxes: Evidence for Small Kuiper Belt Objects and Recent Geological Activity.  Astronomical Journal1192945-952.  10.1086/301207
  * Stern . (1995) sternhstatmosphere1995Stern, SA., Trafton, LM. Flynn, B.  1995Jun.  Rotationally Resolved Studies of the Mid-Ultraviolet Spectrum of Triton. II. HST Surface and Atmospheric Results Rotationally Resolved Studies of the Mid-Ultraviolet Spectrum of Triton. II. HST Surface and Atmospheric Results.  Astronomical Journal1092855.  10.1086/117491
  * Stone . (1989) stone1989Stone, EC., Cummings, AC., Looper, MD., Selesnick, RS., Lal, N., McDonald, FB.Chenette, DL.  198912\.  Energetic Charged Particles in the Magnetosphere of Neptune Energetic Charged Particles in the Magnetosphere of Neptune.  Science24649361489-1494.  10.1126/science.246.4936.1489
  * Strobel Summers (1995) strobel1995tritonatmosandionoStrobel, DF. Summers, ME.  1995Jan.  Triton’s upper atmosphere and ionosphere. Triton’s upper atmosphere and ionosphere.  Neptune and Triton Neptune and triton ( 1107-1148).
  * Strobel Zhu (2017) strobelandzhu2017Strobel, DF. Zhu, X.  201707\.  Comparative planetary nitrogen atmospheres: Density and thermal structures of Pluto and Triton Comparative planetary nitrogen atmospheres: Density and thermal structures of Pluto and Triton.  Icarus29155-64.  10.1016/j.icarus.2017.03.013
  * Szopa . (2006) szopa2006Szopa, C., Cernogora, G., Boufendi, L., Correia, JJ. Coll, P.  2006\.  PAMPRE: A dusty plasma experiment for Titan’s tholins production and study Pampre: A dusty plasma experiment for titan’s tholins production and study.  Planetary and Space Science544394-404.  https://www.sciencedirect.com/science/article/pii/S003206330600002X https://doi.org/10.1016/j.pss.2005.12.012
  * Telfer . (2018) tefler2018dunesplutoTelfer, MW., Parteli, EJR., Radebaugh, J., Beyer, RA., Bertrand, T., Forget, F.aff12  201806\.  Dunes on Pluto Dunes on Pluto.  Science3606392992-997.  10.1126/science.aao2975
  * Thompson . (1989) thompson1989tholinThompson, WR., Singh, SK., Khare, BN. Sagan, C.  198908\.  Triton: Stratospheric molecules and organic sediments Triton: Stratospheric molecules and organic sediments.  Geophyscal Research Letters168981-984.  10.1029/GL016i008p00981
  * Tomasko . (2008) tomasko2008Tomasko, MG., Doose, L., Engel, S., Dafoe, LE., West, R., Lemmon, M.See, C.  200804\.  A model of Titan’s aerosols based on measurements made inside the atmosphere A model of Titan’s aerosols based on measurements made inside the atmosphere.  Planet. Space Sci.565669-707.  10.1016/j.pss.2007.11.019
  * Trainer . (2004) trainer2004Trainer, MG., Pavlov, AA., Curtis, DB., McKay, CP., Worsnop, DR., Delia, AE.Tolbert, MA.  200412\.  Haze Aerosols in the Atmosphere of Early Earth: Manna from Heaven Haze Aerosols in the Atmosphere of Early Earth: Manna from Heaven.  Astrobiology44409-419.  10.1089/ast.2004.4.409
  * Trainer . (2006) trainer2006Trainer, MG., Pavlov, AA., Dewitt, HL., Jimenez, JL., McKay, CP., Toon, OB. Tolbert, MA.  200611\.  Inaugural Article: Organic haze on Titan and the early Earth Inaugural Article: Organic haze on Titan and the early Earth.  Proceedings of the National Academy of Science1034818035-18042.  10.1073/pnas.0608561103
  * Tran . (2008) Tran2008Tran, BN., Force, M., Briggs, RG., Ferris, JP., Persans, P. Chera, JJ.  200801\.  Titan’s atmospheric chemistry: Photolysis of gas mixtures containing hydrogen cyanide and carbon monoxide at 185 and 254 nm Titan’s atmospheric chemistry: Photolysis of gas mixtures containing hydrogen cyanide and carbon monoxide at 185 and 254 nm.  Icarus1931224-232.  10.1016/j.icarus.2007.09.010
  * Tyler . (1989) tyler1989Tyler, GL., Sweetnam, DN., Anderson, JD., Borutzki, SE., Campbell, JK., Eshleman, VR.Wood, GE.  198912\.  Voyager Radio Science Observations of Neptune and Triton Voyager Radio Science Observations of Neptune and Triton.  Science24649361466-1473.  10.1126/science.246.4936.1466
  * van Krevelen (1950) Krevelen1950GraphicalstatisticalMFvan Krevelen.  1950\.  Graphical-statistical method for the study of structure and reaction processes of coal Graphical-statistical method for the study of structure and reaction processes of coal.  Fuel29269-284.
  * Vuitton . (2010) vuitton2010HCNVuitton, V., Bonnet, JY., Frisari, M., Thissen, R., Quirico, E., Dutuit, O.Szopa, C.  201001\.  Very high resolution mass spectrometry of HCN polymers and tholins Very high resolution mass spectrometry of HCN polymers and tholins.  Faraday Discussions147495.  10.1039/c003758c
  * Vuitton . (2021) vuitton2021Vuitton, V., Moran, SE., He, C., Wolters, C., Flandinet, L., Orthous-Daunay, FR.Hörst, SM.  202102\.  H2SO4 and Organosulfur Compounds in Laboratory Analogue Aerosols of Warm High-metallicity Exoplanet Atmospheres H2SO4 and Organosulfur Compounds in Laboratory Analogue Aerosols of Warm High-metallicity Exoplanet Atmospheres.  The Planetary Science Journal212.  10.3847/PSJ/abc558
  * Vuitton . (2019) vuitton2019Vuitton, V., Yelle, RV., Klippenstein, SJ., Hörst, SM. Lavvas, PP.  201905\.  Simulating the density of organic species in the atmosphere of Titan with a coupled ion-neutral photochemical model Simulating the density of organic species in the atmosphere of Titan with a coupled ion-neutral photochemical model.  Icarus324120-197.  10.1016/j.icarus.2018.06.013
  * Wolters . (2020) wolters2020Wolters, C., Flandinet, L., He, C., Isa, J., Orthous-Daunay, FR., Thissen, R.Vuitton, V.  2020\.  Enhancing data acquisition for the analysis of complex organic matter in direct-infusion Orbitrap mass spectrometry using micro-scans Enhancing data acquisition for the analysis of complex organic matter in direct-infusion orbitrap mass spectrometry using micro-scans.  Rapid Communications in Mass Spectrometry3415e8818.  https://analyticalsciencejournals.onlinelibrary.wiley.com/doi/abs/10.1002/rcm.8818 e8818 RCM-20-0022.R2  https://doi.org/10.1002/rcm.8818
  * Wong . (2017) wong2017Wong, ML., Fan, S., Gao, P., Liang, MC., Shia, RL., Yung, YL.New Horizons Science Team  201705\.  The photochemistry of Pluto’s atmosphere as illuminated by New Horizons The photochemistry of Pluto’s atmosphere as illuminated by New Horizons.  Icarus287110-115.  10.1016/j.icarus.2016.09.028
  * Yelle . (1995) yelle1995tritonatmsYelle, RV., Lunine, JI., Pollack, JB. Brown, RH.  1995Jan.  Lower atmospheric structure and surface-atmosphere interactions on Triton. Lower atmospheric structure and surface-atmosphere interactions on Triton.  Neptune and Triton Neptune and triton ( 1031-1105).
  * Young Stern (2001) young2001hsttritonobsYoung, LA. Stern, SA.  2001Jul.  Ultraviolet Observations of Triton in 1999 with the Space Telescope Imaging Spectrograph: 2150-3180 Å Spectroscopy and Disk-integrated Photometry Ultraviolet Observations of Triton in 1999 with the Space Telescope Imaging Spectrograph: 2150-3180 Å Spectroscopy and Disk-integrated Photometry.  Astronomical Journal1221449-456.  10.1086/322062
  * Yu . (2017) yu2017Yu, X., Hörst, SM., He, C., McGuiggan, P. Bridges, NT.  201712\.  Direct Measurement of Interparticle Forces of Titan Aerosol Analogs (“Tholin”) Using Atomic Force Microscopy Direct Measurement of Interparticle Forces of Titan Aerosol Analogs (“Tholin”) Using Atomic Force Microscopy.  Journal of Geophysical Research (Planets)122122610-2622.  10.1002/2017JE005437
  * Zhang . (2017) zhangandstrobel2017Zhang, X., Strobel, DF. Imanaka, H.  201711\.  Haze heats Pluto’s atmosphere yet explains its cold temperature Haze heats Pluto’s atmosphere yet explains its cold temperature.  Nature551352-355.  10.1038/nature24465