Degenerate Quantum LDPC Codes With Good Finite Length
Performance
Pavel Panteleev and Gleb Kalachev

arXiv:1904.02703v3 [quant-ph] 12 Nov 2021

Faculty of Mechanics and Mathematics, Moscow State University, GSP-1, Leninskie Gory, Moscow, 119991, Russian Federation

We study the performance of medium-length
quantum LDPC (QLDPC) codes in the depolarizing channel. Only degenerate codes withthe maximal stabilizer weight much smaller thantheir minimum distance are considered. It isshown that with the help of OSD-like postprocessing 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 westudy the performance of several known classesof degenerate QLDPC codes including hypergraph product codes, hyperbicycle codes, homological product codes, and Haah’s cubic codes.
We also construct several interesting examplesof short generalized bicycle codes. Some ofthem have an additional property that theirsyndromes are protected by small BCH codes,
which may be useful for the fault-tolerant syndrome measurement. We also propose a newlarge family of QLDPC codes that contains theclass of hypergraph product codes, where oneof the used parity-check matrices is square. It isshown that in some cases such codes have better
performance than hypergraph product codes.
Finally, we demonstrate that the performance ofthe proposed BP-OSD decoder for some of theconstructed codes is better than for a relatively
large surface code decoded by a near-optimal decoder.

1 Introduction
Quantum error-correcting codes are considered as
an essential component in the current architectures ofquantum computers due to the inherently faulty nature of the quantum hardware. Topological quantum codes [1, 2, 3] are among the quantum codeswith the highest known noise thresholds. These codes
have sparse parity-check matrices and thus belong to
the class of quantum LDPC (QLDPC) codes. Moreover, they are highly degenerate, which means that theminimum distance is much higher than the weight ofthe stabilizers. It is important that these codes also

have decoding algorithms with near to optimal performance [1, 4, 5]. Though the thresholds of topologicalcodes are relatively high, their dimensions are usuallymuch smaller than for general QLDPC codes of thesame length (it is constant for the surface and color
codes). There are also interesting classes of topologicalquantum codes with very large dimensions (e.g., hyperbolic codes [6] have a constant rate). However, such
codes usually have much smaller minimum distances
compared to the surface and color codes.
Recently there have been proposed a number of interesting families of degenerate QLDPC codes (e.g., hypergraph product codes [7] and homological productcodes [8]) with very good asymptotic parameters. Nevertheless their practical error-correcting performancefor relatively small code lengths (n < 1000) is largely
unexplored, and it is not clear whether their performance is competitive to the best known topologicalcodes. From our point of view, the difficulty of constructing degenerate QLDPC codes with good practical
performance is mostly related to the following two issues.
1. Asymptotically good constructions may not necessarily produce the best QLDPC codes for relatively
small code lengths. Indeed, in [9, 10] the construction of 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 andthe minimum distance are much better for smaller
lengths.
2. The performance of the known QLDPC codes is far
from optimal under the state-of-the-art decoders(including the binary and non-binary BP decoders,
and their modifications). The performance degradation is usually attributed [11] to the unavoidable
4-cycles in the corresponding Tanner graphs andto a large number of degenerate errors. While thenumber of 4-cycles can be significantly reduced byusing CSS codes [12] without 4-cycles in the paritycheck matrices HX and HZ , the number of degenerate errors can not be easily reduced for highlydegenerate codes.

Accepted in Quantum 2021-11-02, click title to verify. Published under CC-BY 4.0.

1

In this paper, we try to address both mentioned issues. In the first part of the paper, we introduce a newenhancement of the standard BP decoder for QLDPC
codes (both binary and non-binary versions are allowed)
using a variant of the well-known decoding algorithm forshort classical codes called the ordered statistics decoding (OSD) [13, 14]. This new post-processing algorithm
works only if the BP decoder fails to find a recovery
Pauli operator that gives the correct syndrome. We
suppose here that the QLDPC parity-check matrix H
is represented in the binary form1 . The algorithm starts
from finding a reliable information set [15] for H basedon the soft decisions obtained by the BP decoder. Thenit makes hard decisions for the bits from this information set and flips the w most unreliable of them in order
to find the 2w corresponding recovery Pauli operatorsthat return the corrupted quantum state to the coding space. Finally, it selects a recovery operator withthe 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 recovery operator that moves the corrupted codeword back to the code space. We show that with thehelp of this OSD-like post-processing the performance ofthe standard BP decoder on many degenerate QLDPC
codes can be improved by several orders of magnitude.
As we can see 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 ofdegenerate codes: the generalized bicycle (GB ) codes
introduced in [10] and a new large family2 of QLDPC
codes introduced in this paper. We call this new family
generalized hypergraph product (GHP ) codes. It contains the GB codes and the class of hypergraph product(HP) codes [7], where one of the two parity-check matrices used in the product is square. We also derive new
formulas for the dimension of GB and GHP codes andshow how to design codes of high dimension with gooderror correction performance. It is interesting to notethat some of the constructed GB codes have an additional property that their syndromes are protected bysmall BCH codes, which may be useful for the faulttolerant syndrome measurement.
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, hyperbicycle codes [9, 10],the homological product codes [8], and Haah’s cubic
codes [20]. We compare their performance with theperformance of the codes, constructed in this work. 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 modificationsof the BP decoder such as the random perturbation [21],the enhanced feedback [22], and the matrix augmentation [23] algorithms. We compare all the above mentioned algorithms on the new [[1270, 28]] code from theclass of GHP codes mentioned earlier3 . We show thatthe performance of the new decoding algorithm on thiscode is significantly better. Moreover, we also show thatthe performance of this code under the BP-OSD is evenbetter than the performance of the [[1201, 1, 25]] surface code under the near-optimal MPS-based decoder
proposed in [5]. We also demonstrate that the performance under BP-OSD of one of Haah’s cubic codes,
which have local stabilizers in 3D, is also very good.
The remainder of the paper is organized as follows.
Section 2 contains some background material, where we
review standard definitions and fix notations. In Section 3, we describe the BP-OSD algorithm and compare
its performance with other known modifications of BP.
In Section 4, we study GB codes and construct somenew codes with good performance. In Section 5, we
introduce and study a new large family of GHP codesand show that it generalizes the class of hypergraphproduct codes in the case when one of the parity-checkmatrices is square. In the last section, we give some final remarks. The paper also contains three appendixes.
Appendix A has some supplementary material on thering of circulants. Appendix B contains a description of
all the codes used in the simulations. Finally, we show
some additional simulations in Appendix C.

2 Basic facts and definitions
In this section, we fix notations and briefly recall somestandard definitions related to classical and quantum
LDPC codes. See [11] for a good review of these topics.

2.1 Classical codes
1 For a QLDPC code on n qubits with m stabilizers the matrix

2 Since the first version of the current work was released, theLet n be a natural number. In what follows, we denote by [n] the set {1, . . . , n}. Consider a finite field Fq

codes from this family have been shown to have very large minimal distances [16, 17, 18] and found interesting applications ingeometry [19]. In [17] they were further generalized and called
lifted product codes.

3 Since this GHP code is quasi-cyclic, it can also be obtained(up to some qubit permutations) as a special case of the hyperbicycle code construction.

H is an m × 2n binary matrix.

Accepted in Quantum 2021-11-02, click title to verify. Published under CC-BY 4.0.

2

and an n-dimensional vector space Fnq over Fq . A linear [n, k]q code is a k-dimensional subspace C ⊆ Fnq ,where the parameters n and k are called the length andthe dimension of C, respectively. We denote the dimension k of the code C by dim C. The rate of the code C
is equal to k/n. The elements of C are called codewords. The Hamming distance d(v, v 0 ) between vectors
v, v 0 ∈ Fnq is the number of positions in which they differ. The parameterd(C) = min{d(c, c0 ) | c 6= c0 ; c, c0 ∈ C}
is called the minimal distance of C. By definition, we
put d(C) = ∞ when k = 0. It is easy to see that d(C) isequal to the minimal weight |c| of non-zero codewords,
where the weight |c| is the number of non-zero components in c. When d(C) = d for a linear [n, k]q code C, we
say that C is an [n, k, d]q code. A linear [n, k, d]q codeis usually defined either as the row space of a matrix G
called the generator matrix or as the kernel of a matrix
H called the parity-check matrix. It is easy to see thatGH T = 0, rk G = k, and rk H = n − k. In what follows
we mostly consider binary linear codes (i.e., q = 2), in
which case we use a shorter notation: [n, k] or [n, k, d].

2.2 Quantum stabilizer codes
The quantum analogs of classical linear codes are quantum stabilizer codes introduced in [24]. To define them
we need a number of supporting definitions. Considern
an n-qubit Hilbert space C2 = (C2 )⊗n . A Pauli operator on n qubits is an operator P = αP1 ⊗· · ·⊗Pn on thenspace C2 , where α ∈ {±1, ±i}, Pi ∈ {I, X, Y, Z}. HereI is the identity and X, Y, Z are the Pauli 2 × 2 matrices. The weight wt (P ) of a Pauli operator P is thenumber of non-identity components in the tensor product. The set Pn 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
Pn is non-commutative, if we forget about the global
phase factors α of Pauli operators we obtain the quotient group Pn /{±I, ±iI}, where I is the identity opern
ator on C2 . This quotient group is isomorphic to thecommutative group Z2n2 , and the isomorphism is givenby the following map:
αnO

X xi Z zi 7→ (x1 , . . . , xn | z1 , . . . , zn ).

(1)

i=1

It is well known that two n-qubit Pauli operators P
and P 0 commute if‌f for their binary representations(x|z), (x0 |z 0 ) ∈ F22n we havehx, z 0 i + hz, x0 i = 0,
where ha, bi =Pni ai bi is the dot product in F2 .

(2)

Denote by Pn∗ the subset of Pauli operators P ∈ Pn
with the global phase factor α = 1. A stabilizer group S
is a commutative subgroup of the Pauli group Pn suchthat −I 6∈ S. The group S is usually generated by mPauli operators S1 , . . . , Sm ∈ Pn∗ called stabilizers generators, i.e., S = hS1 , . . . , Sm i. We say that S1 , . . . , Sm
are independent if none of them can be obtained (up toa global phase factor α) from the others by the group
multiplication.
Let us recall that a quantum stabilizer [[n, k, d]] coden
is a 2k -dimensional subspace of the n-qubit space C2
defined as the common +1-eigenspace for a set of mstabilizers S1 , . . . , Sm ∈ Pn∗ :n

C = {|ψi ∈ C2 | Si |ψi = |ψi, i = 1, . . . , m},where the group S(C) = hS1 , . . . , Sm i is called the stabilizer group of C. It can be shown that m > n − k. But
if the stabilizers are independent, we get m = n − k.
Here the parameter d = d(C) is called the minimal distance 4 of C and is equal to the minimal possible weightof a Pauli operator P ∈ Pn∗ that commutes with all thestabilizers S1 , . . . , Sm but P 6∈ S(C).
A Pauli operator P ∈ Pn∗ 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 |ψi
to P |ψi. However, for every quantum stabilizer code C,
it is not hard to show that P |ψi = |ψi for all |ψi ∈ C
if‌f P ∈ S(C). Hence we see that in this case, not all
Pauli errors P ∈ Pn∗ can harm the state |ψi. We calla Pauli error P ∈ Pn∗ degenerate for a code C if P |ψi =|ψi for all |ψi ∈ C and non-degenerate otherwise. We
see that the elements from P ∈ S(C) are precisely thedegenerate Pauli errors and the minimum distance d(C)is the minimal possible weight of a non-degenerate Paulierror. A stabilizer code C is called degenerate if it has
degenerate Pauli errors P of weight wt (P ) < d(C).
If we apply the binary mapping (1) to the stabilizer
generators S1 , . . . , Sm of an [[n, k, d]] code C, we obtainthe m × 2n binary matrix
H = (HX | HZ )(3)called the parity-check matrix of C, where each row corresponds to a stabilizer generator. We do not require
for the matrix H to be full rank (i.e, rk H = n−k 6 m).
Using (2) it is not hard to see that the null space of H
is exactly the set of all vectors (z, x) ∈ F2n
2 such that(x, z) is the binary mapping of a Pauli error P ∈ Pn∗ that
commutes with all the stabilizer generators S1 , . . . , Sm .
We see that the matrix H = (HX | HZ ) is not an arbitrary binary m × 2n matrix since the stabilizer generators S1 , . . . , Sm corresponding to its rows should com4 We write [[n, k]] if the minimal distance is not known.

Accepted in Quantum 2021-11-02, click title to verify. Published under CC-BY 4.0.

3

mute with each other. From equation (2) it easily follows that this restriction can be formulated as the following commutativity condition:T
HX HZT + HZ HX
= 0.

(4)

A very important subclass of quantum stabilizer codes is
Calderbank-Shor-Steane (CSS) codes introduced in [25,26]. A quantum CSS code is a stabilizer code, where
non-identity components in the tensor product of eachstabilizer generator are either all equal to X or all equalto Z. Hence the parity-check matrix H of a CSS codeof length n can be represented in the following form:


0
HX
,
H=
HZ
0
where HX , HZ are binary matrices with n columns.
In this special case, commutativity condition (4) canbe rewritten as:
HX HZT = 0.
(5)
We can easily verify that the dimension k of the corresponding CSS code of length n is given by the formula:k = n − rk HX − rk HZ .

(6)

2.3 Classical and quantum LDPC codes
A classical low density parity check (LDPC) code [27]is a linear code defined by a sparse binary parity-checkmatrix H = (hij )m×n . The sparseness usually meansthat the weights of all rows and columns in H are upperbounded by some universal constant as the code lengthn grows in an infinite family of codes.
When we consider an LDPC code defined by a paritycheck matrix H, it is helpful to define the bipartite
graph T = T (H) called the Tanner graph [28]. In thisgraph the first part of nodes v1 , . . . , vn (called the vnodes) corresponds to the columns of H (the variables),the second part of nodes c1 , . . . , cm (called the c-nodes)
corresponds to the rows of H (the checks), and we connect a v-node vi with a c-node cj whenever hij = 1,i ∈ [m], j ∈ [n]. If the parity-check matrix H is
(wc , wr )-regular (i.e., each column has weight wc andeach row has weight wr ), then the corresponding Tanner graph is also (wc , wr )-regular (i.e., each v-node has
degree wc and each c-node has degree wr ). We say thatan LDPC code is w-limited if the degree of each node in
its Tanner graph is upper bounded by w. It is obviousthat any LDPC code with (wc , wr )-regular parity-checkmatrix is max(wc , wr )-limited.
There are a number of decoding algorithms for classical LDPC codes, but the most frequently used oneis the belief propagation (BP) decoder [27], also known

as the message passing decoder or the sum-product decoder [29]. It assigns the a priori probability distributions of individual bits in the codeword (obtained fromthe channel) to the v-nodes of the Tanner graph anditeratively updates the posterior probability distributions for each bit. Once some maximal iteration number limit is reached, the decoder combines the a priori
and the calculated posterior probability distributions(the soft decisions) to produce the optimal binary decision (called the hard decision) for each individual bit.
An important property of a parity-check matrix H
defining an LDPC code is the girth of the corresponding
Tanner graph T = T (H), which is equal to the lengthof the shortest cycle in T . It is well known that shortcycles in the Tanner graph degrade the performance of
the BP decoder. At the same time, it was observedthat LDPC codes without 4-cycles (i.e., when the girthis at least 6) perform very well in practice. However,this practical observation is not fully investigated fromtheoretical 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 T = T (S) for any stabilizer[[n, k, d]] code C defined by a set of stabilizer generators
S = {S1 , . . . , Sm }. In the case of stabilizer codes, thev-nodes correspond to n qubits and the c-nodes to thestabilizer generators S1 , . . . , Sm , and we connect a cnode with a v-node if the corresponding stabilizer acts
nontrivially on the corresponding qubit. As in the caseof classical LDPC codes, we say that a QLDPC code is
w-limited if the degree of each node in its Tanner graphis upper bounded by w. This property is much more
important in the quantum case due to the faulty natureof the current quantum hardware. It is clear that any
CSS code with (wc , wr )-regular matrices HX and HZ ismax(2wc , wr )-limited.

3 OSD-like post-processing for BP
In this section, we describe a new OSD-like postprocessing 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 usedin the OSD post-processing algorithm (called qOSD) for
quantum codes described in Section 3.2. For example,
one of the main differences between classical and quantum codes is that we have to use the syndrome decoder

Accepted in Quantum 2021-11-02, click title to verify. Published under CC-BY 4.0.

4

in the quantum case. Hence we consider only syndrome
OSD decoders here since we are going to use them ascomponents of the decoder for quantum codes.

then for any positive real numbers w1 , . . . , wk we canefficiently findXX
arg max
wi = arg minwi(7)I∈B(G) i∈I

3.1 Syndrome OSD post-processing algorithm

J∈B(H) i∈J

Starting from this section we will often use the following
notations:in a greedy fashion [31, 32]. Here in the right part we
used that I ∈ B(G) iff J = I¯ ∈ B(H).

• If M is a matrix, then Mi denotes its i-th column.

The main idea of the syndrome OSD decoder is as follows. Consider a linear [n, k] code C defined by a paritycheck matrix H. Let c0 = c + e be a corrupted version of a codeword c ∈ C, where e ∈ Fn2 is the corresponding random error vector. Given the syndromes = Hc0 = He we want to find the error vector e andthus recover the codeword c = c0 − e. Suppose that inaddition we are given an estimate6 of the error probability pi = P(ei = 1) for each i ∈ [n]. From theseestimates our best guess of the error vector e would be
the hard decisions vector ê, where êi = 1 when pi > 1/2,
and êi = 0 otherwise7 . However, when we only use theerror probability estimates, we often have that H ê 6= s,and thus ê 6= e. Nevertheless, even in such cases, somecomponents of ê are equal to e, and we can still try touse ê to find e if we also take into account that

• If I = {i1 , . . . , ik } is some index set, i1 < · · · < ik ,and π ∈ Sn is a permutation, then for every vectorv = (v1 , . . . , vn ) and matrix M = (M1 , . . . , Mn ) we
define:vI = (vi1 , . . . , vik ),MI = (Mi1 , . . . , Mik ),π(v) = (vπ(1) , . . . , vπ(n) ),π(M ) = (Mπ(1) , . . . , Mπ(n) ).
• If I ⊆ [n] is an index set, then the index set I¯ =[n] \ I is called its complement.
Now let us recall the definition of an information
set [30] of a code, which has an important role in
the OSD decoding. A set of indices I ⊆ [n] is called
an information set of a classical linear [n, k] code C if
CI = {cI | c ∈ C} = Fk2 . Clearly, I is an information
set of C if‌f |I| = k, and for any two codewords c, c0 ∈ Csuch that cI = c0I we always have c = c0 . Therefore forany information set I the corresponding k bits can beused to uniquely recover any vector v ∈ Fn2 if we also
know its syndrome s = Hv. Hence we can consider thecorresponding encoding map EIs : Fk2 → Fn2 such that for
any u, v, and s we have:vI = u, Hv = s⇐⇒

v = EIs (u).

It is easy to verify that EI0 is the systematic encoding
map for the code C where the information bits u are atthe positions corresponding to I.
Remark. If G is a generator matrix, and H is a paritycheck matrix of a linear code C; then it can be shownthat a k-element index set I is an information set of C
¯ Thus if
iff rk GI = rk G iff rk HJ = rk H, where J = I.
B(M ) denotes the family of indices I such that the collection of columns {Mi }i∈I is a basis for the column
space of M ; then the family of all information sets of C
coincides with B(G), while the family of their complements coincides with B(H). Since the set of all linearly
independent columns of any matrix gives us a matroid5 ,5 A matroid is defined by a non-empty collection I of subsets(called the independent sets) from some set E (called the groundset) such that: (1) I is closed under taking subsets; (2) for any
two A, B ∈ I if |A| < |B| then A ∪ {b} ∈ I for some b ∈ B \ A.
Any maximal (by inclusion) independent set is called a basis.

He = s.

(8)

Therefore, to recover e, one may try to traverse throughdifferent information sets I in the hope that for one ofthem we have êI = eI , and thuse = EIs (êI ).

(9)

Unfortunately we do not know for which indices i ∈ [n]we have êi = ei . Hence it makes sense to find an information set I with the indices that are as reliable aspossible, where the reliability of an index i ∈ [n] is
the probability
ρi = P(êi = ei ) = max(pi , 1 − pi ).
If we assume that the components in the random error
vector e are mutually independent, then it follows thatthe probability of successful
decoding P(e = EIs (êI )) forQ
I is equal to ρ(I) = i∈I ρi . Thus if we want to maximize this probability we need the most reliable information set I, i.e., the one8 with the maximal possible valueof ρ(I). Finding such a set may at first sight look likea prohibitively hard task.
P However, if instead of ρ(I)we consider ln ρ(I) = i∈I wi , where wi = ln ρi ; then
6 For example, one can use a syndrome BP decoder for thispurpose (see Section 3.3).
7 When p = 1/2 we can set ê randomly to either 0 or 1 withiiequal probability.
8 If there are several such sets, we can use any of them.

Accepted in Quantum 2021-11-02, click title to verify. Published under CC-BY 4.0.

5

Algorithm 1: Syndrome OSD-w algorithm
Input: target weight function wt (·),
binary parity-check matrix H,
syndrome vector s ∈ Fm
2 ,vector of hard decisions ê ∈ Fn2 ;Output: error vector e ∈ Fn2 such that He = s;
1 J ← ∅;
2 for i ← 1 to n do3
J 0 ← J ∪ {i};4
if rk HJ 0 > rk HJ then5
J ← J 0;
6
end
7 end

s
x
¯
8 x̂ ← arg min wt EI (R[w] êI ) , where I = J;
x∈Fw
2

9

return e = EIs (Rx̂[w] êI );we can see that the most reliable information set I isgiven by (7), and, as we mentioned earlier, it is possible
to find I using a greedy algorithm [31, 32].
This greedy algorithm is the main part of the OSD
decoder. Since in our case the code is defined bya parity-check matrix H, it is more convenient to use
the right part of (7), which means that we want tofind the index set J corresponding to the least reliable basis {Hi }i∈J for the column space of H, i.e.,J ∈ B(H) with the smallest ρ(J). For simplicity, we
assume that the columns of H are already rearranged
such that the reliability of the corresponding positions
increases: ρ1 6 · · · 6 ρn . In this case, it is not hard
to see that the collection {Hi }i∈J of the first r = rk H
linearly independent columns is the least reliable basis [32]. We can find J by applying Gaussian elimination to equation (8), which gives us, in time O(n3 ), thefollowing equation:H̃e = s̃.
(10)Then J is the index set of the first r pivot columns in H̃,i.e., H̃J = (δij )r×r . Moreover, from (7) it follows thatthe index set I = J¯ is the most reliable information set,
and we can find the error vector e from (10) in a verystraightforward way since H̃J is the identity matrix.
The described above syndrome decoding algorithm isusually called order-0 OSD decoder. As we see, it firstfinds the most reliable information set I and then recovers the unique vector e ∈ Fn2 subject to the following
conditions:eI = êI , He = s.
(11)
In fact, we can further improve the error-correcting performance by using order-w OSD decoder (abbreviatedas OSD-w). In this modification, after we find the mostreliable information set I, we look at all error vectors e
obtained from equation (10) by setting the first w least

Algorithm 2: Fast syndrome OSD-0 algorithm
Input: binary parity-check matrix H,
syndrome vector s ∈ Fm
2 ,vector of hard decisions ê ∈ Fn2 ;Output: error vector e ∈ Fn2 such that He = s;
1 J ← ∅;
02 s ← s + H ê;
3 for i ← 1 to n do
4
if rk [HJ , s0 ] = rk HJ then5
break;
6end
7
J 0 ← J ∪ {i};8
if rk HJ 0 > rk HJ then9J ← J 0;10
s0 ← s0 + êi Hi ;11end
12 end0
13 x ← the solution of HJ x = s ;x
14 return e = RJ ê;reliable positions from I to all possible values x ∈ Fw
2
(we can obtain them using the encoding operator EIs ).
Finally, we select an error vector e of the minimal weightwt (e) among all the 2w obtained error vectors. Herethe weight function wt (·) depends on the specific channel we use. In the case of depolarizing noise, this weightfunction is just the weight of the corresponding Pauli
operator.
A simplified pseudocode of the above OSD-w algorithm is shown in Algorithm 1. Here in the two lastlines, we used a shorthand notation RxI v for the resultof the replacement of the subvector vI in the vector v|I|by x ∈ F2 . Therefore, Rx[w] êI is obtained from êI if
we replace its first w bits by x ∈ Fw
2 . Since we assume
that the columns of H are already sorted according to
the reliabilities, these first w positions in I are the least
reliable ones. We should also note that the main cycle of this algorithm, which finds J (lines 1–7), can be
efficiently implemented using Gaussian elimination, as
already discussed above.
Remark. There are some differences between the standard order-w OSD decoder from [13, 14] and the proposed OSD-w post-processing algorithm. For example,
we try all 2w bit flips of the w least reliable informationbits 8), while in the standard OSD we try all the
P (lineki6w i bit flips of no more than w bits.
As we will see in Section 3.3, if the OSD-w decoder
is used as a post-processing algorithm after the BP decoder for QLDPC codes, then it can radically improvethe error correcting performance. In fact, in many caseseven OSD-0 is enough, and thus the computational costof the decoding is O(n3 ). Moreover, in the case of the

Accepted in Quantum 2021-11-02, click title to verify. Published under CC-BY 4.0.

6

OSD-0, there is no need to do full Gaussian eliminationfor H. Let I be the most reliable information set foundby the OSD-0 algorithm, then we can stop extending theindex set J in Algorithm 2 when rk [HJ , s0 ] = rk HJ ,and put e = RxJ ê, where s0 = s + HJ¯êJ¯, and x is
the unique9 solution of HJ x = s0 . Indeed, we get• If v ∈ Fn4 is a Pauli vector, and vi = viX x + viZ z,
where viX , viZ ∈ F2 , i ∈ [n]; then we can define
the binary vectors:

He = HJ x + HJ¯êJ¯ = s0 + HJ¯êJ¯ = s.

We also need the inverse mapping b−1 (·) for b(·)
nthat maps vectors from F2n2 back to F4 .

¯ then e satisfies conditions (11)Since we also have I ⊆ J,
and thus is the error vector found by the OSD-0 algorithm. This observation gives us a faster version of the
OSD-0 algorithm (see Algorithm 2).

3.2 Modified OSD post-processing algorithm forstabilizer codes
In this subsection, we show how to adapt the OSD decoder from the previous subsection to a scenario where
it is used as a post-processing algorithm after the BP
decoder for QLDPC 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,na quantum state |ψi ∈ C2 is subject to a random Paulierror
E = E1 ⊗ · · · ⊗ En ∈ Pn∗ ,where all Ei are i.i.d, and for all i ∈ [n] we have:b(v) = (v1X , v1Z , v2X , v2Z , ..., vnX , vnZ ) ∈ F2n
2 ,
∗
Z
X
Z
X
Z
X
2n
b (v) = (v1 , v1 , v2 , v2 , ..., vn , vn ) ∈ F2 .

• If H is an m × n stabilizer matrix over F4 , thenb(H) denote the m × 2n binary matrix obtainedby mapping each row h from H to the row b∗ (h).
The main motivation for these, not very standard,
notations is as follows. If e ∈ Fn4 is a Pauli error, thenit is easy to check thats = b(H)b(v)is the corresponding syndrome vector, i.e., for everyi ∈ [m] we get si = 0 if‌f the i-th stabilizer from H commutes with the Pauli error e. Let us emphasize thatthe binary representations b(v) and b(H) can be also
obtained from the binary representations (1) and (3) bya permutation of indices and columns, respectively.
Example. Let us illustrate the above notations on thewell-known non-CSS [[5, 1, 3]] code [33] defined by theparity-check matrix
1 0 0 1 0 0 1 1 0 0
H = (HX |HZ ) = 01 10 01 00 10 00 00 10 11 01 ,01010

P(Ei = X) = P(Ei = Y ) = P(Ei = Z) = p/3.
In what follows, it is convenient for our goals to represent (with a small abuse of notation and terminology)
the set of matrices P1∗ = {I, X, Y, Z} by the elementsof the finite field F4 , where I is represented by 0 ∈ F4 ,and the Pauli matrices X, Y, Z by the three non-zeroelements from F4 . To distinguish these finite field elements from the corresponding matrices we denote theformer using a different font: i, x, y, z. Further, we represent a Pauli vector from Pn∗ by the corresponding vector from Fn4 , which we also call a Pauli vector. Using
this conventions, we represent the binary m×2n paritycheck matrix of a stabilizer code C (see equation (3)) by
the corresponding m × n matrix over F4 and call it thestabilizer matrix of C.
Since we consider the depolarizing channel, for thebest performance, it is better to use the non-binary version of the syndrome BP decoder (see [21], [11, Algorithm 1]), which also takes into account the correlations
between X and Z errors in qubits. To describe the OSD
algorithm in this case we need some extra notations.
9 The solution is unique since rk H = |J|.
J

10001

which corresponds to the matrices
x z z x i 
0 1 1 0 1 0 0 1 0 0
i x z z x
H = x i x z z , b(H) = 00 01 00 10 10 01 11 00 01 10 .
z x i x z

10 01 00 01 10

If we have the Z error in the second qubit, then we getthe error vector e = (i, z, i, i, i) ∈ F54 , its binary representation b(e) = (0, 0, 0, 1, 0, 0, 0, 0, 0, 0) ∈ F10
2 , and thecorresponding syndrome vector s = (0, 1, 0, 1).
Since the depolarizing channel is non-binary, we needsome further adjustments in the syndrome OSD decoder(Algorithms 1 and 2) to use it as a post-processor after
the non-binary BP decoder. We call this modified version the order-w qOSD algorithm, which is defined via
the order-w OSD algorithm from the previous section
as follows:
qOSDw (H, s, ê) = b−1 OSDw (|·|Sp , b(H), s, b(ê)) .
Here we use the symplectic weight 10 |·|Sp as the target
weight function wt (·) for the OSD algorithm, which is
10 It is easy to see that the symplectic weight |x|
Sp is equal to
the weight wt (E) of the Pauli error E ∈ Pn∗ represented in thebinary form by the vector x ∈ F2n
2 .

Accepted in Quantum 2021-11-02, click title to verify. Published under CC-BY 4.0.

7

defined as:nX|x|Sp =
(x2i−1 ∨ x2i ).
i=1

As we see, the input for the qOSD algorithm includes
the m × n stabilizer matrix H over F4 , the syndromes ∈ Fm
2 , and the error vector ê ∈ F4 , which is the harddecisions vector for the result of the non-binary BP decoder (see the next subsection).
Remark. The symplectic weight |·|Sp is used above forthe depolarizing channel. For the variant of the depolarizing channel, where the X and Z errors are independent, the standard binary Hamming weight |·| should
be used instead. In general, the optimal choice of thetarget weight function wt (·) is the one, where the mostprobable errors are of the least possible weight.

3.3 Main decoding algorithm (BP-OSD)
In this subsection, we describe our main decoding algorithm (see Algorithm 3) called the BP-OSD or BPOSD-w (if we want to emphasize the OSD order w).
It consists of two stages: the non-binary BP decoding (lines 1–4) and the OSD post-processing (lines 6–8).
In fact, at the first stage, any decoding algorithm may
be used instead of BP if it can provide soft decisions.
The goal of this stage is either to find the error vectore ∈ Fn4 or to obtain the probabilities P(ei = E), i ∈ [n],for each type of the Pauli error E ∈ {i, x, y, z}.
First, we run the BP decoder and obtain the soft decisions (line 1), i.e., for ever i ∈ [n] we get the 4 numbers (pi,i , pi,x , pi,y , pi,z ), where pi,E can be interpreted
as the probability P(ei = E) of the error E ∈ {i, x, y, z}
in the i-th qubit. Next, we find the hard decisions for
all qubits by the formula (line 2):

the qubit positions (line 7), the qOSD algorithm fromthe previous subsection is used to recover the errors
in the least reliable qubits from the hard decisions forthe remaining qubits (line 8).
Algorithm 3: BP with OSD-w post-processing
Input: stabilizer matrix H,
syndrome vector s ∈ Fm
2 ;Output: error vector e ∈ Fn4 ;n
1 (pi,i , pi,x , pi,y , pi,z )i=1 ← BP(s);2 Make hard decisions:êi ← arg maxE∈{i,x,y,z} pi,E , i ∈ [n];3 if b(H)b(ê) = s then4
return e = ê;
5 else6
Calculate the reliabilities:
ρi ← ρ(pi,i , pi,x , pi,y , pi,z ), i ∈ [n];7Sort the qubits by their reliabilities:
ρσ(1) 6 ρσ(2) 6 ... 6 ρσ(n) , σ ∈ Sn ;8return e = σ −1 qOSDw (σ(H), s, σ(ê)) ;9 end
In Algorithm 3, we used the qOSD algorithm, which
is a good choice for the standard depolarizing channel.
If we have a channel with independent X and Z errors,then for a CSS code defined by a pair of parity-checkmatrices HX , HZ we can also use the standard OSD(Algorithms 1 and 2) for the X and Z components ofthe error vector e separately. In this case, lines 6–8 in
Algorithm 3 can be replaced by the following steps:
1. Calculate the X and Z error probabilities:pX
i = pi,x + pi,y ,pZ
i = pi,y + pi,z .

êi = arg max pi,E , i ∈ [n].
E∈{i,x,y,z}

If the BP decoding is successful (i.e., we have the correct
syndrome vector), then there is no need in the postprocessing, and the BP-OSD decoder returns the resultof the BP decoder (line 4).
After the first stage, the probabilities pi,E are also
used in the BP-OSD algorithm to sort the qubits inthe order of increasing reliability ρ(pi,i , pi,x , pi,y , pi,z ),where we can define the reliability of the i-th qubit asρ(pi,i , pi,x , pi,y , pi,z ) = P(êi = ei ) =max
E∈{i,x,y,z}pi,E .

However, in all our simulations we used the formulaρ(pi,i , pi,x , pi,y , pi,z ) = pi,i ,
which gives similar error-correcting performance, but
it is a little bit easier to calculate. After we sorted

2. Sort the qubits in the decreasing order of their X
error and Z error probabilities and let σX , σZ ∈ Sn
be the corresponding permutations such that:XX
pX
σX (1) > pσX (2) > ... > pσX (n) ,Z
Z
pZ
σZ (1) > pσZ (2) > ... > pσZ (n) .

3. Let ê = êX x + êZ z, sX = HX êZ , and sZ = HZ êX .
It is clear that s = [sX , sZ ]. Run the OSD decoder
separately for the X and Z components of ê:−1eX = σX
OSDw (| · |, σX (HZ ), sZ , σX (êX )) ,−1eZ = σZ
OSDw (| · |, σZ (HX ), sX , σZ (êZ )) .
4. Return e = eX x + eZ z.

Accepted in Quantum 2021-11-02, click title to verify. Published under CC-BY 4.0.

8

BP-OSD of different order w

The effect of OSD-0 for different QLDPC codes
100

100
10−1
10−2

A1, BP
B1, BP
C1, BP
D, BP

A1, BP-OSD
B1, BP-OSD
C1, BP-OSD
D, BP-OSD

10−1

no OSD
OSD-4
OSD-15

OSD-0
OSD-10

10−2

WER

WER

10−3
10−4

10−3
10−4

10−5
10−5

10−6

10−6

10−7

5 · 10−2

10−8

10−2

10−1

Physical error rate
Physical error rate

10−1

Figure 1: The WER performance of several QLDPC codes under the BP and BP-OSD-0 decoders, where: A1 is the 10limited generalized bicycle [[254,28]] code; B1 is the 6-limited
generalized hypergraph product [[882,24]] code; C1 is the 10limited hypergraph product [[7938,578,16]] code; D is the 8limited Haah’s cubic [[1024,30]] code (see Appendix B).

For all our simulations we used the normalized minsum (NMS) decoder with the normalization factor
0.625, which approximates the non-binary BP decoderfrom [21], [11, Algorithm 1] in log-domain and is more
numerically stable in some cases. The maximal numberof iterations was set to 32. We used the layered scheduling in order to increase the convergence speed of the decoder by approximately two times11 . For a good review
of practical aspects of the BP decoder implementation,see [35, Chapter 4]. The error-correcting performance inour simulations is measured either in terms of the logicalerror rate or the word error rate 12 (WER). We should
also stress that in many cases we use only the OSD-0
algorithm (Algorithm 2), which has complexity O(n3 ),while the complexity in the general case is O(n3 + n2w ).
In Fig. 1 we show the effect of the OSD-0 postprocessing after the BP decoder for different QLDPC
codes, including some known and new codes describedin the next sections. As you can see, the gain of the BPOSD over the BP decoder in terms of WER for some
11 Since the first version of the current work was released, thelayered (serial) schedule of the BP decoder for QLDPC codes was
also studied in [34].
12 Recall that the word error rate, also known as the block error

rate or frame error rate, is the rate of codewords where the decoder does not give a correct answer (i.e., it either fails to decodeor we have at least one logical error after the decoding).

Figure 2: The impact of the OSD order w on the WER performance of the 8-limited [[882,48,16]] code B2 in Appendix B.

codes is up to 5 orders of magnitude (code B1). However, for code A1 the difference between BP-OSD and
BP is quite small. We think that this is because the column weight of the matrices HX and HZ is quite high(it is equal to 5), and hence the performance of the BP
decoder is very good even without the post-processing.
Remark. It is interesting to note that 8-limited Haah’s[[1024,30]] code, which has local stabilizers in 3D, also
performs very well under the BP-OSD decoder. To thebest of our knowledge, this is the first such demonstration on the depolarizing channel. From our point ofview, this observation implicitly suggests that some ofHaah’s cubic codes may have very good minimum distances. In fact, even after very long runs of the BP-OSD
decoder on this [[1024,30]] code, we have not found any
non-degenerate codewords of weight less than 32.
In Fig. 2 we show the impact of the OSD order w on
the WER performance of the 8-limited [[882,48,16]] code
(Appendix B, code B2) under the BP-OSD decoder.
We see that the WER performance in this case can befurther improved by increasing the OSD order w. At thesame time, from our experiments with the OSD postprocessing on different QLDPC codes, we observed thatin many cases the impact of the OSD order on the WER
performance is quite small.

3.4 Different post-processing algorithms
In this section, the OSD post-processing algorithm
is compared against the other known post-processing
methods that also significantly improve the performance of the BP decoder. We assume that the prob-

Accepted in Quantum 2021-11-02, click title to verify. Published under CC-BY 4.0.

9• Random perturbation [21]. If the syndrome isnon-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 thisc-node. The main parameter of this method is thevariance of the perturbation magnitude. After thechanges are done, the BP decoder runs with theperturbed input LLRs.
• Enhanced feedback [22]. It is similar to theprevious approach but the perturbations are notrandom 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. Then for all the v-nodes adjacent to this cnode, we set the initial LLRs using the BP decoder
output for these nodes. After this is done the BP
decoder runs with the perturbed input LLRs.
• Matrix augmentation [23]. In this method instead of modification of the input LLRs, the paritycheck matrix itself is modified by random duplication of some rows. The fraction δ of the duplicated rows is called the augmentation density.
Then a new decoding attempt with the augmented
matrix is performed.
To compare the performance of all the describedmethods with the BP-OSD decoder we use the 6-limited[[1270, 28]] QLDPC code (B3 in Appendix B). This
code belongs to the new class of codes described in Section 5. For all these methods we used na = 100. We
can see in Fig. 3 that the OSD post-processing outperforms all the above-mentioned post-processing methods
and also outperforms the 4-limited [[1201, 1, 25]] surface code on the MPS decoder from [5], which is almost
optimal for this code. Let us note that all the otherpost-processing methods also have the WER gain thatis more than 103 over the BP decoder for code B3. In
fact, we observed a similar WER gain for many othercodes from the class of (3, 6)-regular CSS QLDPC codeswith a sufficiently large minimum distance. We thinkthat this is mainly because the classical (3, 6)-regular
LDPC codes defined by the matrices HX and HZ ofsuch CSS codes themselves have many harmful trapping sets. Thus these (3, 6)-regular QLDPC codes additionally have a lot of degenerate codewords of very
low weight starting from 6.

BP post-processing algorithms

10−1
10−2

Pure BPEFB
OSD-0
Surf. MPS

Pert.
Aug.
Surf. MWM

10−3
WER

ability distributions in the BP decoder are represented
in terms of the log-likelihood ratios (LLRs). Below you
can find a brief description of these methods, where eachmethod can be applied repeatedly after the BP decoder
until all the parity-checks are satisfied or the maximal
number of attempts na is reached.

10−4
10−5
10−6
10−7
5 · 10−2

10−1

2 · 10−1

Physical error rate

Figure 3: The WER performance of different post-processing
algorithms for the BP decoder on the 6-limited [[1270,28]]
QLDPC code (B3 in Appendix B). The red curves are for the
4-limited [[1201,1,25]] surface code under the minimum weightmatching (MWM) and the MPS-based decoders [36, 5].

4 New generalized bicycle codes
4.1 Ansatz with commuting matrices
The commutativity conditions such as (4) and (5) area serious obstacle to designing good QLDPC codes using
random-like constructions similar to the constructions
used for classical LDPC codes. Thus it makes sense toconsider large families of matrices of some particularform 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 thebicycle QLDPC codes [37]. Let us briefly remind thisansatz. Consider two commuting binary n × n matrices
A and B, i.e., AB = BA. Let
HX = [A, B] and HZ = [B T , AT ].

(12)

Then we see that HX HZT = AB + BA = 0, and thecommutativity condition (5) is always satisfied. It was
proposed in [10] to use binary circulant matrices A andB since they always commute. The corresponding classof codes is called the generalized bicycle (GB) codes,
where the bicycle codes [37] are obtained as a special
case when B = AT .

Accepted in Quantum 2021-11-02, click title to verify. Published under CC-BY 4.0.

10

4.2 Ring of circulants
Let us recall that an ` × ` circulant matrix A over Fq
takes the form
a0
al−1 . . . a1
 a1a0
. . . a2 
A=. . . . . . . . . . . . . . . . . . . . ,a`−1 a`−2 . . . a0
where a0 , . . . , a`−1 ∈ Fq . It is readily seen that thematrix A can be represented in the form
A = a0 I + a1 P + . . . a`−1 P `−1 ,{Au + Bv | u, v ∈ F`2 }.
Using the described above polynomial representation ofcolumn vectors and circulant matrices we can considerh`ithis set as the following set of polynomials from F2 :h`i{a(x)u(x) + b(x)v(x) | u(x), v(x) ∈ F2 }.

where I is the ` × ` identity matrix and
0 0 ... 1
1 0 . . . 0



P =
0 1 . . . 0. . . . . . . . . . . . .
0 0 ... 0

is the ` × ` permutation matrix representing the rightcyclic shift by one position. Since P ` = I, we see thatthe ring of all ` × ` circulant matrices over Fq is isomorh`iphic to the ring Fq = Fq [x]/(x` − 1) of polynomials
over Fq modulo the polynomial x` − 1.
Hence the circulant matrix A can be uniquely represented by the polynomial a(x) = a0 + a1 x + · · · +a`−1 x`−1 and the product C = AB of two circulant matrices represented by polynomials a(x), b(x) ∈ R` corresponds to the polynomial
c(x) = a(x)b(x) mod x` − 1

To prove this formula we show that rk HX = rk HZ =n − deg g(x) and use CSS dimension formula (6).
Let us first find the rank of the matrix HX = [A, B],
which is equal to the dimension of its column space. It
is easy to see that the column space of HX (called its
syndrome space) is equal to the following set:

(13)

which is called the cyclic convolution of a(x) and b(x).
Likewise, if we want to find a matrix-vector productc = Ab, where b = (b0 , . . . , b`−1 ) and c = (c0 , . . . , c`−1 )are (column) vectors corresponding to b(x) and c(x), we
can also use the cyclic convolution (13).

4.3 Dimension of generalized bicycle codes
As we saw before, to define two binary circulant ` × `matrices A and B we need to provide two binary polyh`inomials a(x), b(x) ∈ F2 . The dimension13 k of thecorresponding CSS [[2`, k]] code is given by the following proposition.
Proposition 1. The dimension k of the the generalizedh`ibicycle [[2`, k]] code defined by a(x), b(x) ∈ F2 is givenby the formula:k = 2 deg g(x),(14)
where g(x) = gcd(a(x), b(x), x` − 1).
13 Let us point out that this dimension formula was given in thepaper [10, Theorem 2] in a slightly more complex form. A similar
formula was proved only in the special case of single generator
codes.

It is easy to verify that this set is the principal14 idealh`iof the ring F2 generated by g(x). Hence it is the cyclic
code Cg with generator polynomial g(x), and we provedthat rk HX = dim Cg = n − deg g(x). We call this cyclic
code Cg the syndrome code of HX since its codewords
are precisely the polynomial representations of the syndrome space of HX .
To complete the proof we also need to show thatrk HZ = n − deg g(x). Using similar arguments asabove we can consider the syndrome code for HZ andshow 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 GT have the same rank. Hence wealso proved that rk HZ = n − deg g(x), and the proof offormula (14) is complete.

4.4 Construction methods
The proof of Proposition 1 gives us also some valuable
information on how to find generalized bicycle codes ofhigh dimension. If we fix the circulant size ` then all
possible dimensions k of the generalized bicycle codeswith this circulant size are characterized by the degreesof all possible factors of the polynomial x` − 1. Indeed,for each factor g(x) of the polynomial x` − 1 we canh`ialways choose polynomials a(x), b(x) ∈ F2 such that:a(x) mod g(x) = b(x) mod g(x) = 0(15)

since these polynomials are just two codewords from thecyclic code Cg generated by g(x), which we called the
syndrome code of HX . To produce a w-limited QLDPC
we just need to find low weight polynomials a(x) andb(x) that are the codewords of Cg . In practice, thiscan be accomplished by several methods. If the circulant size ` is relatively small, we can find a(x), b(x) by
14 An ideal I in a ring R is principal if I = {au | u ∈ R} forsome a ∈ R.

Accepted in Quantum 2021-11-02, click title to verify. Published under CC-BY 4.0.

11

HMP vs GB (BP-OSD-10)
100
HMP [[49,1,9]]10−1

GB [[48,6,8]]
GB [[46,2,9]]

10−2
WER

an exhaustive search over all polynomials of the given
weight.
Another alternative is to generate random polynoh`imials of a given weight from F2 until we find a pairof polynomials that satisfies condition (15). Since theprobability that a random polynomial of a given weight
belongs to Cg is equal approximately to 2− deg g(x) ; thenif we test more then 2deg g(x) random polynomials wewill find a polynomial from Cg with high probability.
When we find a pair of polynomials a(x), b(x) we alsoneed 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 generalized bicycle codes from Appendix B
were found by the described above methods.

10−3
10−4
10−5

10−2

4.5 GB codes with syndrome protection
Another important observation, made in the proof of
Proposition 1, is that the syndrome codes of the paritycheck matrices HX and HZ are the cyclic codes withthe generator polynomials g(x) and g ∗ (x), respectively.
Let us mention that the syndrome code of a paritycheck 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 HX and HZ are protected by these cyclic codes.
Since the syndrome measurements for quantum codes
are performed by faulty hardware, some additional protection of the syndromes may be used to improve thereliability of the syndrome measurements [38, 39]. Let
us also mention that the polynomials g(x) and g ∗ (x)always produce cyclic codes Cg and Cg∗ with the same
minimum distance since the “transpose” mapc(x) =`−1X
i=0

ci xi 7→ c∗ (x) =`−1X

ci x`−i mod x` − 1

i=0
h`i

is an automorphism of the ring F2 that respects theweight of the polynomials, and therefore we have thatCg∗ = {c∗ (x) | c(x) ∈ Cg }.
Hence we can use any cyclic code with generator polynomial g(x) and minimum distance d to construct a CSS
code, where the syndromes for HX and HZ are protected by cyclic codes of minimum distance d. It is
important to note that since a(x), b(x) ∈ Cg , the weightof the polynomials a(x), b(x) can not be smaller than
this minimum distance d.

4.6 Comparison with other codes
In this subsection, we consider several new examples
of generalized bicycle codes and compare their perfor-

10−1
Physical error rate

Figure 4: The WER performance of the 8-limited generalized
bicycle (GB) codes (A3 and A4 in Appendix B) and the 8limited [[49, 1, 9]] homological product (HMP) code from [8]under the BP decoder with the OSD-10 post-processing.

mance under the BP-OSD decoder against some otheralready known QLDPC codes.
Example 1. Let us consider the primitive narrow-sense
BCH [127, 14, 5] code Cg with the generator polynomial:g(x) = (x7 + x + 1) · (x7 + x5 + x3 + x + 1).
If we set a(x) = 1 + x15 + x20 + x28 + x66 and b(x) = 1 +x58 +x59 +x100 +x121 , then we obtain the 10-limited generalized bicycle [[254, 28]] code. Its minimum distanceis not available, but the performance of this code (seeFig. 1, code A1) is almost the same as the performanceof the 10-limited hypergraph product [[7938, 578, 16]]
code15 obtained from the two identical circulant paritycheck matrices H of the cyclic code [63, 17, 16] code defined by the polynomial h(x) = 1 + x3 + x34 + x41 + x57 .
This particular code was chosen in order to match thehigh rate of the [[254, 28]] code. It is important to notethat both codes do not have 4-cycles in matrices HXand HZ , 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 sets16 with
15 The definition of these codes is given in Section 5.
16 An (a, b) trapping set or a near-codeword for a parity-check

Accepted in Quantum 2021-11-02, click title to verify. Published under CC-BY 4.0.

12

Bicycle vs Generalized Bicycle (NBP and BP)

HB vs GB (BP-OSD-10)

100

100
[[256,32]] BP (binary)

HB [[900,50,14]][[256,32]] NBP

10−1

10−1

10−2

GB [[180,10, d > 15]]
GB [[900,50,15]][[126,28]] BP

10−2
WER

Logical error rate[[126,28]] BP (binary)

10−3

10−3
10−4

10−4
10−5
10−5
10−6
10−6
10−4

10−3

10−2

10−1

10−7

Figure 5: The logical error rate performance of the 16-limited[[256, 32]] bicycle code under the neural BP (NBP) decoderfrom [41] and the 10-limited [[126, 28, 8]] generalized bicycle
code (A2 in Appendix B) under the BP decoder (binary andnon-binary) without the OSD post-processing.

b < 5. It is very well known [40] that (a, b) trapping
sets with small a and b may greatly decrease the performance of the BP decoder. And the [[254, 28]] can nothave the most harmful trapping sets.
Example 2. Let us consider the cyclic [63, 14, 5] codewith the generator polynomial
2

6

5

6

5 · 10−2

10−1

Physical error rate

Physical error rate

54g(x) = (x + x + 1) · (x + x + 1) · (x + x + x + x + 1)
If we set a(x) = 1 + x + x14 + x16 + x22 , b(x) =1 + x3 + x13 + x20 + x42 we obtain the 10-limited generalized bicycle [[126, 28]] code. Its performance with thestandard BP decoder (binary and non-binary) is shownin Fig. 5, code A2. We compared its performance withthe performance of the neural BP decoder for the bicycle [[256, 32]] code constructed in [41]. Such a big difference in the performance is mostly because the QLDPC[[256, 32]] code used in [41] has a small minimum distance compared to the [[126, 28]] code, which minimum
distance is 8. This minimum distance was found by
an exhaustive search (see Appendix B). Another possible reason is that the neural BP decoder proposed in [41]was based on the binary BP, which usually has worse
performance than its non-binary version.
Example 3. In this example we constructed two verysmall 8-limited generalized bicycle codes (the [[48, 6, 8]]
matrix H is a vector v of weight a such that the corresponding
syndrome s = Hv has weight b.

Figure 6: The WER performance of the 8-limited hyperbicycle(HB) [[900,50,14]] code and two 8-limited generalized bicycle(GB) codes (A5 and A6 in Appendix B) under the BP-OSD-10
decoder.

code A3 and the [[46, 2, 9]] code A4, see Appendix B).
We compared their performance (see Fig. 4) with theperformance of an 8-limited [[49, 1, 9]] homological product (HMP) code from [8] using the BP with OSD-likepost-processing. As we can see the performance of the
newly constructed codes is similar to the [[49, 1, 9]] code.
At the same time, their rates are higher.
Example 4. In Fig. 6 we compared the performance of
the 8-limited hyperbicycle [[900, 50, 14]] code from [9,10] with two new 8-limited generalized bicycle codes(A5 and A6 in Appendix B). We can see that the performance of the generalized bicycle [[180, 10, d]] code,
15 6 d 6 18, is similar to the hyperbicycle [[900, 50,
14]] code. At the same time, it has the same weight ofstabilizers, and its code length is 5 times smaller.

5 Generalization of HP codes
5.1 Hypergraph product (HP) codes
In this section, we propose a new generalization of hypergraph product codes [7] in the case when one of theparity-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 [na , ka , da ] linear code Ca
and an [nb , kb , db ] linear code Cb defined by parity-checkmatrices17 a ∈ Mma ×na (F2 ) and b ∈ Mmb ×nb (F2 ) respectively. Then the hypergraph product code is the17 The parity-check matrices are not necessary full rank.

Accepted in Quantum 2021-11-02, click title to verify. Published under CC-BY 4.0.

13

CSS [[N, K, d]] code with HX = (a ⊗ Imb , Ima ⊗ b) and
HZ = (Ina ⊗ bT , aT ⊗ Inb ), where N = na mb + nb ma ,K = 2ka kb −ka (nb −mb )−kb (na −ma ). As it was shownin [7], the minimum distance d of the hypergraph product code C satisfies the following lower bound:Td > min(da , db , dT
a , db ),T
where dTa and db are the minimal distances of the“transposed” codes CaT and CbT defined by the paritycheck matrices aT and bT respectively. It is important
to note that if the matrices a and b are w-limited, thenthe corresponding CSS code C is 2w-limited. Hence,using known asymptotically good families of classical LDPC codes with (wc , wr )-limited parity checkmatrices, it is possible [7] to construct w-limited CSS√
codes with asymptotically non-zero rate and d = Θ( n)as n → ∞. In [9] the hypergraph product construction was further improved, and it was shown that one
can construct good hypergraph product codes usingsquare parity-check matrices a and b. In fact, many ofthe best-known small-length hypergraph product codes
are constructed using square parity check matrices ofcyclic codes (see [9, 10]). In [10] hyperbicycle CSS
codes, which generalize both generalized bicycle andhypergraph product codes, were proposed. Here we
consider another generalization of hypergraph productcodes where the matrix b is square.

5.2 Generalized hypergraph product codes
In what follows by a ring we always mean a ring withidentity. Let R be a ring. We denote the ring of all
m × n matrices over R by Mm×n (R) or by Mn (R)when m = n. If R is the ring of ` × ` matrices over somefield F we identify the elements of Mm×n (R) with thecorresponding block matrices from Mm`×n` (F).
Consider a binary matrix b ∈ M` (F2 ). We say thatthe matrix b and a ring R ⊆ M` (F2 ) commute if all
matrices from R commute with b.
Example 5. Consider b ∈ M` (F2 ) and R = {0, I},
where 0 and I are the zero and the identity matrices
from M` (F2 ) 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 ∈ M` (F2 ) and a ring R ⊆M` (F2 ) commute. Consider a matrix A = (aij )m×n ∈Mm×n (R). We denote by C(A, b) the CSS code called
a generalized hypergraph product (GHP ) code with thefollowing parity-check matrices18 :HX = [A, bIm ], HZ = [bT In , A∗ ],(16)

18 Let us warn the reader that we understand H

and HZ as

X

where A∗ = (aTji )n×m , and Im , In are the identity matrices over R of size m and n respectively. The correctnessof this definition follows from the following:
 
I b
T
HX HZ = [A, bIm ] n = Ab + bA = 0.
A
The code length N of the CSS code C(A, b) is given
by N = (m + n)`. We will show later how to find thedimension K of the code C(A, b) in a special case.
One can easily verify that if we take a matrix b ∈M` (F2 ) and the ring R = {0, I} (as in Example 5)then the CSS code C(A, b) is the hypergraph productcode defined by the binary m × n matrix ã = (ãij )m×n
and the binary ` × ` matrix b, where for all i ∈ [m],j ∈ [n] we have:(0, if aij = 0;ãij =
1, if aij = I.
We can also see that the ansatz with two commuting
matrices A and B given in (12) is also a special case of
the new ansatz described in (16), where the matrix A
is a 1 × 1 block matrix.

5.3 Quasi-cyclic generalized hypergraph productcodes
In this subsection, we describe quasi-cyclic (QC) GHP
codes. In fact, it can be shown that this particular subclass of GHP codes is equivalent (up to some permutation of qubits) to a special case of hyperbicycle codesfrom [10, Eq. (19), χ = r2 = n2 = 1]. However, we
believe that the concise language of polynomial matrices adopted in the current work is much more suitablefor our examples, which are essentially sparse random
QC GHP codes subject to some additional constrains.
Now, let us take b and R as in Example 6. Henceb is a binary circulant matrix, and R is the ring of allbinary circulant matrices of the same size. In this case,the matrices HX and HZ defined by (16) are block matrices, where each block is a binary circulant matrix ofsize `. Such matrices are called quasi-cyclic. Let us
note that quasi-cyclic (QC) matrices are well known inclassical coding theory. In fact, most of the best-known
practical classical LDPC codes have QC parity-checkmatrices. We will show in this section how to find thedimension of generalized hypergraph product codes defined by (16). For simplicity, we consider here only thecase when the circulant size ` is odd. Before we canprovide the formula for the dimension we need some
supplementary definitions from algebra.
the corresponding binary block matrices (not as matrices overM` (F2 )).

Accepted in Quantum 2021-11-02, click title to verify. Published under CC-BY 4.0.

14

Here we adopt the polynomial representation of QC
matrices used in [42, 43]. For any polynomial p(x) ∈Fq [x] of degree d we consider the ring Fq [x]/(p(x))
of polynomials f0 + f1 x + · · · + fd−1 xd−1 ∈ Fq [x] withaddition and multiplication modulo p(x). By Fdq wedenote the d-dimensional space of the d × 1 column
vectors over Fq . We also identify an element f (x) ∈Fq [x]/(p(x)) with the corresponding column vector f =(f0 , . . . , fd−1 ) ∈ Fdq .
h`i

Let us recall that by F2 we denote the ring of circulants F2 [x]/(x` − 1). We use the standard identificationof the circulant ` × ` matrices over F2 with the elementsh`iof the ring F2 (see Subsection 4.2), where a columnh`ivector a ∈ F2 corresponds to the circulant matrix withthe first column equal to a. Using this identification wecan consider an m` × n` QC matrix over F2 of circuh`ilant size ` as an m × n matrix over the ring F2 . Weh`ialso consider n × 1 column vectors over F2 as n` × 1
column vectors over F2 . Given the above identification
we consider multiplication of an m` × n` QC matrix byan n` × 1 column vector over F2 as multiplication of anh`im × n matrix by an n × 1 column vector over F2 .
h`i
The algebraic structure of the ring F2 is very wellstudied in the literature (see Appendix A for further
details). Since we consider the case when ` is odd, thepolynomial x` − 1 factors into a product of irreducible
polynomials over F2 :the fields F1 , . . . , Fs . Indeed, let ri = rkFi ϕi (A), i ∈ [s].
If A1 , . . . , An are the columns of A, then each vector vthat belongs to the column space of the matrix A canbe represented as follows:v = u 1 A1 + · · · + u n An ,h`iwhere u1 , . . . , un ∈ F2 . Therefore we see that the cardinality of the column space of the non-binary matrix
ϕi (A) over the field Fi is equal to (2di )ri = 2di ri . Henceusing isomorphism (18) we conclude that the number ofdifferent vectors in the column space of the matrix A isequal tos
Ps
Y
2di ri = 2 i=1 di ri ,i=1

and we proved that rkF2 A =Ps

i=1 di ri .

The following proposition provides the formula forthe dimension of the QC CSS code C(A, b) if ` is odd.
h`i

h`i

Proposition 2. Let b(x) ∈ F2 , A ∈ Mm×n (F2 ),where` is odd. Let g(x) = gcd(b(x), x` − 1) =Q
i∈S fi (x), S ⊆ [s], where fi (x) are some irreducible
polynomials from (17), and Fi = F2 [x]/(fi (x)), i ∈ S,
are the corresponding finite fields. Then C(A, b) is
a CSS [[N, K]] code, where N = (m + n)` andXK=
deg fi (x)(m + n − 2 rkFi ϕi (A)).
i∈Sx` − 1 = f1 (x) · · · fs (x).

(17)

h`i
Hence the ring F2 is isomorphic to the direct productof finite fields:
h`i
(18)
F2 ∼
= F1 × · · · × Fs ,
where the field Fi = F2 [x]/ fi (x) has the size 2di ;di = deg fi (x), i ∈ [s]. Let us consider the mapsh`iϕi : F2 → Fi given by the formula:

Proof. The proof idea is the following. Let us mention
that ϕi (HX ) = [ϕi (A), 0] for all i ∈ S. Hence we haverkFi ϕi (HX ) = rkFi ϕi (A), for all i ∈ S. At the sametime for i ∈ [s] \ S, we obtainrkFi ϕi (HX ) = rkFi [ϕi (A), ϕi (b)Im ] = m,since for all i ∈ [s] \ S we have that ϕi (b) 6= 0 and therefore the non-binary matrix ϕi (HX ) is full rank. Henceby applying Lemma 1 to the matrix HX we have:

ϕi : u(x) 7→ u(x) mod fi (x), i ∈ [s].
m` − rk HX =We also naturally extend this map to any vectors andh`imatrices over F2 . The following lemma is the key tothe dimension formula for the QC generalized hypergraph product codes.
h`iLemma 1. Let A ∈ Mm×n (F2 ) be a binary QC matrix. Then its rank (over F2 ) is given by:
rkF2 A =s
X

di rkFi ϕi (A)i=1

Proof. The lemma easily follows from the isomorphismh`ishown in (18) between F2 and the direct product ofsXdeg fi (x)(m − rkFi ϕi (HX ))

i=1

=

X

deg fi (x)(m − rkFi ϕi (A)).

i∈S

To complete the proof we need also to find the rankof the matrix HZ . It is easier to find the rank of thematrix HZ0 obtained from HZ by the application of the“transpose” map u 7→ u∗ to each element. Since theh`itranspose map is an automorphism on the ring F2 wesee that the number of vectors in the row space of HZ
and the row space of HZ0 is the same. Hence rk HZ =rk HZ0 . The rank of the matrix HZ0 = [bIn , AT ], can befound in the same way as for the matrix HX :Accepted in Quantum 2021-11-02, click title to verify. Published under CC-BY 4.0.

15

as a parity-check matrix, a non-binary linear code over
F of dimension

GHP vs HP (BP and BP-OSD-10)
HP [[1922,50,16]]

10−1

kA = n − rkF ϕ(A).

HP, OSD [[1922,50,16]]
GHP [[882,24]]

10−2

At the same time, b(x) defines the cyclic code

GHP, OSD [[882,24]]

WER

10−3

h`i

Cb = Cg = {g(x)u(x) | u(x) ∈ F2 }10−4of dimension kb = deg g(x) as a check polynomial. Thus
formula (19) gives us the dimension K of C(A, b) interms of the dimensions kA and kb for the two special
cases shown below:

10−5
10−6

1. if A is a square matrix, i.e. m = n, we have

10−7
10−2

Physical error rate

10−1

K = 2kA kb ;Figure 7:
The WER performance of the 6-limited[[1922, 50, 16]] hypergraph product (HP) code and the 6limited [[882, 24]] generalized hypergraph product (GHP) code
(C2 and B1 in Appendix B). The HP code has an error floor
even under the BP-OSD-10 decoder.

n` − rk HZ0 =sX

deg fi (x)(n − rkFi ϕi (HZ0 ))

i=1

=

X

=

X

deg fi (x)(n − rkFi ϕi (AT ))i∈S

deg fi (x)(n − rkFi ϕi (A)).

i∈S

Now we apply formula (6) for the CSS dimension andobtain:K = N − rk HX − rk HZ= (m` − rk HX ) + (n` − rk HZ0 )X=
deg fi (x)(m + n − 2 rkFi ϕi (A)).
i∈S

This concludes the proof.
Let us note that if the polynomial b(x) is such thatg(x) = gcd(b(x), x` −1) is an irreducible factor of x` −1,then we can give a more elegant formula for the dimension of the code C(A, b) in some special cases. Indeed,in this case we have:
K = deg g(x)(m + n − 2 rkF ϕ(A)),(19)

where F is the finite field F2 [x]/(g(x)) and ϕ(A) is theF -image of A under the action of the map ϕ : u(x) 7→
u(x) mod g(x). Since ϕ(A) is a matrix over F , it defines,(20)

2. if A is a full rank matrix, i.e. m = rkF ϕ(A), wehave
K = kA kb = (n − m)kb .
(21)
In the current work, we construct only codes that
correspond to case 1 above. Such codes are defined byan irreducible factor b(x) of x` − 1 and a square matrixh`iA over F2 . To construct all the examples of QC GHP
codes given in Appendix B (codes B1, B2, and B3),
we used the following procedure. First we fix a low
weight irreducible polynomial b(x) ∈ F2 [x] such thatb(x) | x` − 1, and then randomly choose a polynomial
matrix A subject to some constraints. Since we wantto obtain sparse parity-check matrices HX and HZ for
the code C(A, b), we restrict each entry of A to be either
0 or a monomial xi , 0 6 i < `. When the number of
non-zero entries in each row and each column of A isbounded above by w, this restriction guaranties thatboth HX and HZ are (w + deg b(x))-limited matrices.
Another restriction is related to the girth of the Tanner graphs TX , TZ for HX , HZ . As you can see from
Tab. 1 in Appendix B, the girth of the Tanner graphs
TX , TZ for all the constructed QC GHP codes is equal
to 6, which means that TX , TZ do not contain 4-cycles.
This restriction helps to improve the error-correcting
performance under the BP decoder.
Example 7. In Fig. 7 you can see the WER performance (under the BP-OSD decoder) of the two codes:
the 6-limited [[1922,50,16]] hypergraph product (HP)code (C2 in Appendix B) and the 6-limited [[882,24]]
generalized hypergraph product (GHP) code (B1 in
Appendix B). You can see from Fig. 7 that the HP[[1922,50,16]] code has some error floor even under the
BP-OSD decoder. We believe that this is due to a large
amount of low-weight non-degenerate codewords in thiscode.

Accepted in Quantum 2021-11-02, click title to verify. Published under CC-BY 4.0.

16

Deep simulations of two GHP codes
10−1

GHP [[882,24]]

10−2

GHP [[1270,28]]
Surf. MPS

10−3

some of the best known QLDPC codes, and their practical performance under the BP-OSD decoder is alsoquite good. Finally, we compared the performance of
one of our codes from the new family and showed thatit has better performance than a relatively large surface
code of similar code length even if this code is decoded
by a near-optimal decoder.

WER

10−4

Acknowledgments

10−5
10−6

The authors would like to thank Dr. Xuecang Zhang
from Huawei Technologies for the support of this workand for useful discussions. This work was also supportedby the Ministry of Science and Higher Education of theRussian Federation (Grant № 075-15-2020-801).

10−7
10−8
10−9
10−10

0.04

0.06

0.08

0.1

0.12

0.14

0.16

0.18

Physical error rate

Figure 8: A deep simulation on the depolarizing channel of
the 6-limited [[882,24]] and [[1270,28]] QC GHP codes (B1and B3 in Appendix B) under the BP-OSD-0 decoder. These
codes do not have error floor down to WER = 10−10 . The red
curve is for the [[1201,1,25]] surface code on the MPS-based
decoder from [5].

In Fig 8 we can see the WER performance of the 6limited [[882,24]] and [[1270,28]] QC GHP codes (codes
B1 and B3 in Appendix B) under the BP-OSD-0 decoder. We see that these codes do not have the error floor down to WER = 10−10 . The red curveshows the corresponding WER performance of the 4limited [[1201,1,25]] surface code under the almost optimal MPS-based decoder from [5].

6 Conclusion
We proposed new OSD-like post-processing for the BP
decoder 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 comparedto the other known codes with similar parameters. We
proposed a new ansatz for quantum CSS codes andshowed how to estimate the dimension of such codes insome special cases. Unfortunately, we have not found
any nontrivial general lower bound on the minimum distance of such codes. We think that to find such a boundis an interesting open problem19 since this class contains
19 Since the first version of this work appeared in arXiv, somelower bounds on the minimal distance have been obtained in [16,17, 18] for special cases of QC GHP codes C(A, 1 + x).

References[1] Eric Dennis, Alexei Kitaev, Andrew Landahl,
and John Preskill. Topological quantum memory.
Journal of Mathematical Physics, 43(9):4452–4505,
2002. doi:10.1063/1.1499754.
[2] Michael H. Freedman and David A. Meyer. Projective plane and planar quantum codes. Foundationsof Computational Mathematics, 1(3):325–332, Jul
2001. doi:10.1007/s102080010013.
[3] H. Bombin and M. A. Martin-Delgado. Topological quantum distillation. Phys. Rev. Lett.,
97:180501, Oct 2006. doi:10.1103/PhysRevLett.
97.180501.
[4] David S. Wang, Austin G. Fowler, and Lloyd C. L.
Hollenberg. Surface code quantum computing witherror rates over 1%. Phys. Rev. A, 83:020302, Feb
2011. doi:10.1103/PhysRevA.83.020302.
[5] Sergey Bravyi, Martin Suchara, and Alexander
Vargo. Efficient algorithms for maximum likelihood decoding in the surface code. Phys. Rev. A,
90:032326, Sep 2014. doi:10.1103/PhysRevA.90.
032326.
[6] Nikolas P. Breuckmann and Barbara M. Terhal.
Constructions and noise threshold of hyperbolic
surface codes. IEEE Transactions on Information Theory, 62(6):3731–3744, June 2016. doi:
10.1109/TIT.2016.2555700.
[7] J. Tillich and G. Zémor. Quantum LDPC codeswith positive rate and minimum distance proportional to n1/2 . In 2009 IEEE International Symposium on Information Theory, pages 799–803, June
2009. doi:10.1109/ISIT.2009.5205648.
[8] Sergey Bravyi and Matthew B. Hastings. Homological product codes. In Proceedings of the

Accepted in Quantum 2021-11-02, click title to verify. Published under CC-BY 4.0.

17Forty-sixth Annual ACM Symposium on Theory ofComputing, STOC ’14, pages 273–282, New York,NY, USA, 2014. ACM. doi:10.1145/2591796.
2591870.

[18] Nikolas P. Breuckmann and Jens N. Eberhardt.
Balanced product quantum codes. IEEE Transactions on Information Theory, 67(10):6653–6674,
October 2021. doi:10.1109/TIT.2021.3097347.

[9] A. A. Kovalev and L. P. Pryadko. Improved
quantum hypergraph-product LDPC codes. In
2012 IEEE International Symposium on Information Theory Proceedings, pages 348–352, July 2012.
doi:10.1109/ISIT.2012.6284206.

[19] Michael Freedman and Matthew Hastings. Building manifolds from quantum codes. Geometric andFunctional Analysis, June 2021. doi:10.1007/
s00039-021-00567-3.

[10] Alexey A. Kovalev and Leonid P. Pryadko. Quantum kronecker sum-product low-density paritycheck codes with finite rate.
Phys. Rev. A,
88:012311, Jul 2013. 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,3:2492–2519, 2015. doi:10.1109/ACCESS.2015.
2503267.
[12] M. Hagiwara and H. Imai. Quantum quasi-cyclic
LDPC codes. In 2007 IEEE International Symposium on Information Theory, pages 806–810, June
2007. doi:10.1109/ISIT.2007.4557323.
[13] M. P. C. Fossorier and Shu Lin. Soft-decision
decoding of linear block codes based on ordered
statistics. IEEE Transactions on Information Theory, 41(5):1379–1396, Sep. 1995. doi:10.1109/
18.412683.
[14] M. P. C. Fossorier. Iterative reliability-based decoding of low-density parity check codes. IEEE
Journal on Selected Areas in Communications,19(5):908–917, may 2001.
doi:10.1109/49.
924874.
[15] B. Dorsch. A decoding algorithm for binary block
codes and j-ary output channels (corresp.). IEEE
Transactions on Information Theory, 20(3):391–
394, may 1974. doi:10.1109/TIT.1974.1055217.
[16] Matthew B. Hastings, Jeongwan Haah, and Ryan
O’Donnell. Fiber bundle codes: Breaking the n 1/2polylog(n) barrier for quantum LDPC codes. In
Proceedings of the 53rd Annual ACM SIGACT
Symposium on Theory of Computing, pages 1276–
1288. Association for Computing Machinery, New
York, NY, USA, June 2021.
doi:10.1145/
3406325.3451005.
[17] Pavel Panteleev and Gleb Kalachev. Quantum
LDPC codes with almost linear minimum distance.
IEEE Transactions on Information Theory, pages
1–1, 2021. doi:10.1109/TIT.2021.3119384.

[20] Jeongwan Haah. Local stabilizer codes in three dimensions without string logical operators. Phys.
Rev. A, 83:042330, Apr 2011. doi:10.1103/
PhysRevA.83.042330.
[21] D. Poulin and Yeojin C. On the iterative decoding of sparse quantum codes. Quantum Info.
Comput., 8(10):987–1000, November 2008. doi:
10.5555/2016985.2016993.
[22] Y. Wang, B. C. Sanders, B. Bai, and X. Wang.
Enhanced feedback iterative decoding of sparse
quantum codes. IEEE Transactions on Information Theory, 58(2):1231–1241, Feb 2012. doi:
10.1109/TIT.2011.2169534.
[23] Alex Rigby, J. C. Olivier, and Peter Jarvis.
Modified belief propagation decoders for quantum low-density parity-check codes. Physical Review A, 100(1):012330, July 2019. doi:10.1103/
PhysRevA.100.012330.
[24] Daniel Gottesman. Stabilizer Codes and Quantum
Error Correction. PhD thesis, California Instituteof Technology, 1997. doi:10.7907/rzr7-dt72.
[25] A. R. Calderbank and Peter W. Shor. Good quantum error-correcting codes exist. Phys. Rev. A,
54:1098–1105, Aug 1996. doi:10.1103/PhysRevA.
54.1098.
[26] A. M. Steane. Error correcting codes in quantum
theory. Phys. Rev. Lett., 77:793–797, Jul 1996.
doi:10.1103/PhysRevLett.77.793.
[27] R. G. Gallager. Low-Density Parity-Check Codes.
M.I.T. Press, Cambridge, MA, 1963. doi:10.
7551/mitpress/4347.001.0001.
[28] R. Tanner. A recursive approach to low complexity codes. IEEE Transactions on Information Theory, 27(5):533–547, September 1981. doi:
10.1109/TIT.1981.1056404.
[29] F.R. Kschischang, B.J. Frey, and H.-A.
Loeliger. Factor graphs and the sum-productalgorithm.
IEEE Transactions on Information Theory, 47(2):498–519, February 2001.
doi:10.1109/18.910572.

Accepted in Quantum 2021-11-02, click title to verify. Published under CC-BY 4.0.

18

[30] E. Prange. The use of information sets in decoding cyclic codes. IRE Transactions on Information Theory, 8(5):5–9, September 1962. doi:
10.1109/TIT.1962.1057777.

[42] Kristine Lally and Patrick Fitzpatrick. Algebraic
structure of quasicyclic codes. Discrete Applied
Mathematics, 111(1):157–175, July 2001. doi:
10.1016/S0166-218X(00)00350-4.

[31] Jack Edmonds. Matroids and the greedy algorithm. Mathematical Programming, 1(1):127–136,
December 1971. doi:10.1007/BF01584082.

[43] Roxana Smarandache and Pascal O. Vontobel.
Quasi-cyclic LDPC codes: Influence of proto- andtanner-graph structure on minimum hamming distance upper bounds. IEEE Transactions on Information Theory, 58(2):585–607, February 2012.
doi:10.1109/TIT.2011.2173244.

[32] M.P.C. Fossorier, Shu Lin, and J. Snyders.
Reliability-based syndrome decoding of linear
block codes. IEEE Transactions on Information
Theory, 44(1):388–398, January 1998. doi:10.
1109/18.651070.
[33] Raymond Laflamme, Cesar Miquel, Juan Pablo
Paz, and Wojciech Hubert Zurek. Perfect quantum error correcting code. Physical Review Letters, 77(1):198–201, July 1996. doi:10.1103/
PhysRevLett.77.198.
[34] Kao-Yueh Kuo and Ching-Yi Lai. Refined belief propagation decoding of sparse-graph quantum codes. IEEE Journal on Selected Areas inInformation Theory, 1(2):487–498, August 2020.
doi:10.1109/JSAIT.2020.3011758.
[35] Marc Fossorier, David Declercq, and Ezio Biglieri.
Channel Coding: Theory, Algorithms, and Applications. Academic Press, July 2014. doi:10.1016/
C2011-0-07211-3.
[36] Jack Edmonds. Paths, Trees, and Flowers. Canadian Journal of Mathematics, 17:449–467, 1965/ed.
doi:10.4153/CJM-1965-045-4.
[37] D. J. C. MacKay, G. Mitchison, and P. L. McFadden. Sparse-graph codes for quantum error correction. IEEE Transactions on Information Theory,50(10):2315–2330, Oct 2004. doi:10.1109/TIT.
2004.834737.
[38] H Bombin, R W Chhajlany, M Horodecki, and M A
Martin-Delgado. Self-correcting quantum computers. New Journal of Physics, 15(5):055023, may
2013. doi:10.1088/1367-2630/15/5/055023.
[39] Yuichiro Fujiwara. Ability of stabilizer quantum
error correction to protect itself from its own imperfection. Phys. Rev. A, 90:062304, Dec 2014.
doi:10.1103/PhysRevA.90.062304.
[40] Tom Richardson. Error-floors of LDPC codes.
In Proceedings of the 41st Annual Conference on
Communication, Control and Computing, pages
1426–1435, 2003.
[41] Ye-Hua Liu and David Poulin. Neural beliefpropagation decoders for quantum error-correcting
codes. Physical Review Letters, 122(20):200501,
May 2019.
doi:10.1103/PhysRevLett.122.
200501.

[44] San Ling, Harald Niederreiter, and PatrickSolé. On the algebraic structure of quasi-cyclic
codes IV: Repeated roots. Designs, Codes andCryptography, 38:337–361, 2006. doi:10.1007/
s10623-005-1431-7.
[45] I. Dumer, A. A. Kovalev, and L. P. Pryadko. Distance verification for classical and quantum LDPC
codes. IEEE Transactions on Information Theory,
63(7):4675–4686, 2017. doi:10.1109/TIT.2017.
2690381.

A Algebraic structure of the ring Fh`iq
Let Fq be a finite field of characteristics 2. The algebraic
h`istructure of the ring Fq is well studied in the coding
literature (see, e.g., [44]). Below we briefly review it.
First, let us consider the special case when ` is odd.
In this case the polynomial x` − 1 factors into a productof different irreducible polynomials over Fqx` − 1 = f1 (x) · · · fs (x).

(22)

This is true, since
gcd (x` − 1)0 , x` − 1 = gcd `x`−1 , x` − 1 = 1,
and the polynomial x` − 1 is square-free.
In the general case, we have ` = 2e `0 , where `0 is odd.
Hence it follows that
e 0

0

e

x` − 1 = x2 ` − 1 = (x` − 1)2 .
Moreover, since `0 is odd, we can apply factoriza0tion (22) to the polynomial x` − 1 and obtain that2e2ex` − 1 = f1 (x) · · · fs (x) .
(23)
 2e
2e
Since the polynomials (f1 (x) , . . . , (fs (x)arepairwise coprime, from the Chinese remainder theoremh`i
it follows that the ring Fq is isomorphic to the direct
product
R1 × · · · × Rs
(24)
2eof the rings Ri = Fq [x]/ fi (x) , i ∈ [s].
When ` is odd we have e = 0 and the rings R1 , . . . , Rs
are in fact fields, since the polynomials f1 (x), . . . , fs (x)are irreducible over Fq .

Accepted in Quantum 2021-11-02, click title to verify. Published under CC-BY 4.0.

19

B Matrices used for simulations
All matrices for generalized hypergraph product andgeneralized bicycle codes that we used for simulations
have the form HX = [A, B], HZ = [B T , AT ] where A
and B are quasi-cyclic matrices. Thus, to define thecode, we specify matrices A and B in the polynomialh`iform as matrices over F2 .
For all codes presented here, we also provide lower
and upper bounds on the minimum distance obtained
either by methods similar to the ones from [45] or bya straightforward reduction of the minimum distanceproblem to a mixed integer linear program and using the GNU Linear Programming Kit, Version 4.63,
http://www.gnu.org/software/glpk/glpk.html.

B1) [[882, 24, d]] code, 18 6 d 6 24. The matrices
HX and HZ are (3,6)-regular (` = 63).
 x27

0
0
0
0
1 x54
x54 x27 00001
 1 x54 x27 0 0 0 0 54
27
A= 0 1 x x 0 0 0 ,00
1 x54 x27 000001 x54 x27 000001 x54 x27
6
B = (1 + x + x )I7 .

B2) [[882, 48, 16]] code. Half of the columns forboth HX and HZ matrices have weight 3, another half have weight 5. All the rows haveweight 8 (` = 63).
 x27

0
0
1 x18 x27 1
1 x27 00
1 x18 x27
 x27 1 x27 0 0 1 x18 

18
27
27
A=
 x1 xx18 x127 x1 x027 00 01  ,0
1 x18 x27 1 x27 000
1 x18 x27 1 x27
B = (1 + x + x6 )I7 .

A. Generalized bicycle (GB) codes. The matrices
A and B have form A = (a(x)), B = (b(x)), sohere we specify the polynomials a(x), b(x), and thecirculant size `.
A1) [[254, 28, d]] code (` = 127), 14 6 d 6 20.
a(x) = 1 + x15 + x20 + x28 + x66 ,b(x) = 1 + x58 + x59 + x100 + x121 .

1 0 x
x
0
0 1
0 x111 x20
98
122
,
A = 1 0 x
0 x
1 x80 0 x119 0
5
106
0 1 x
0 x
B = (1 + x + x7 )I5 .

a(x) = 1 + x + x14 + x16 + x22 ,A3) [[48, 6, 8]] code (` = 24).
a(x) = 1 + x2 + x8 + x15 ,b(x) = 1 + x2 + x12 + x17 .
A4) [[46, 2, 9]] code (` = 23).

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 `.
C1) [[7938, 578, 16]] code. The matrices HX andHZ are (5,10)-regular, and we have:` = 63,a(x) = 1 + x5 + x8 + x12 ,b(x) = 1 + x + x5 + x7 .

h(x) = 1 + x3 + x34 + x41 + x57 .

C2) [[1922, 50, 16]] code. The matrices HX andHZ are (3,6)-regular, and we have:A5) [[180, 10, d]] code (` = 90), 15 6 d 6 18.
` = 31,a(x) = 1 + x28 + x80 + x89 ,b(x) = 1 + x2 + x21 + x25 .
A6) [[900, 50, 15]] code (` = 450).
a(x) = 1 + x97 + x372 + x425 ,b(x) = 1 + x50 + x265 + x390 .
B. Generalized hypergraph product (GHP)
codes. Here the matrix B is diagonal; B = b(x)In ,where In is the n × n identity matrix over the ring
h`i
F2 .



B3) [[1270, 28, d]] code, 16 6 d 6 46. The matrices
HX and HZ are (3,6)-regular (` = 127).


51
52

A2) [[126, 28, 8]] code (` = 63).

b(x) = 1 + x3 + x13 + x20 + x42 .

h(x) = 1 + x2 + x5 .

D. Haah’s cubic codes. We used the [[1024, 30, d]]Haah’s cubic code on the 8 × 8 × 8 lattice from [20,Code 1], 13 6 d 6 32.
E. Hyperbicycle (HB) codes.
We used the[[900, 50, 14]] hyperbicycle code from [9, Example 8], [10, Example 6].
F. Homological product (HMP) codes. We used
one of the randomly constructed [[49, 1, 9]] homological product codes from [8].

Accepted in Quantum 2021-11-02, click title to verify. Published under CC-BY 4.0.

20

Table 1: Codes parameters
N
254
126
48
46
180
900
882
882
1270
7938
1922
1024
900
49

K
28
28
6
2
10
50
24
48
28
578
50
30
50
1

d
14–20
8
8
9
15–18
15
18–24
16
16–46
16
16
13–32
14
9

rate
0.110
0.222
0.125
0.043
0.056
0.056
0.027
0.054
0.022
0.073
0.026
0.029
0.056
0.020

wr
10
10
8
8
8
8
6
8
6
10
6
8
8
6,8

wc
5
5
4
4
4
4
3
3,5
3
5
3
4
4
6,8

girth
6
4
4
4
6
6
6
6
6
6
6
4
4
4

[[126,12]][[254,14]][[510,16]][[1022,18]][[8190,24]]

WER

Code
A1
A2
A3
A4
A5
A6
B1
B2
B3
C1
C2
D
E
F

Threshold for GB codes (BP-OSD-0)
100

10−1

0.1

0.11

0.12

0.13

0.14

0.15

0.16

Physical error rate

C Additional Simulations
Figure 9: The WER performance on the depolarizing channel
for five 6-limited GB codes under the BP-OSD-0 decoder. The
threshold is pGB ≈ 15%. The corresponding threshold of the
4-limited surface codes [5] is pS ≈ 18%.

Cyclic non-CSS code (BP-OSD-0)
BP
BP-OSD-0

10−1
10−2
10−3
WER

In this appendix, we show some additional simulation
results of the BP-OSD decoder on the depolarizing
channel.
In Fig. 9, we demonstrate the WER performance ofseveral 6-limited generalized bicycle (GB) codes withthe parameters [[2s+1 − 2, 2s]], s ∈ N, under the BPOSD-0 decoder. As one can see from the curves, thesecodes have the threshold pGB ≈ 15%, which is quite
close to the corresponding threshold pS ≈ 18% of thesurface codes from [5]. The codes from this family wereconstructed in the same way as the GB codes from Subsection 4.6, where for each s ∈ N the corresponding syndrome code Cg is the cyclic Hamming [2s − 1, s, 3] code
defined by some irreducible polynomial g(x) ∈ F2 [x]of degree s.
In all our previous examples, we considered only CSS
codes. In fact, as it is shown in Subsection 3.3, theBP-OSD decoder can be applied to any stabilizer code.
In Fig. 10, we demonstrate the WER performance of
the BP-OSD-0 decoder on the 5-limited cyclic non-CSS[[126,2,12]] code. This code is defined by the paritycheck matrix H = [HX | HZ ], where HX and HZ are
the 126×126 circulant matrices represented respectively
by the polynomials: 1 + x71 + x55 and 1 + x40 + x86 .
As we can see, the WER gain of OSD-0 post-processingin this case is at least three orders of magnitude.

10−4
10−5
10−6
10−7
10−2

5 · 10−2

10−1

Physical error rate

Figure 10: The WER performance of the BP-OSD-0 decoder
on the 5-limited cyclic non-CSS [[126,2,12]] code defined by
the parity-check matrix H = [HX | HZ ], where HX and HZ
are the 126 × 126 circulant matrices represented respectively
by the polynomials: 1 + x71 + x55 and 1 + x40 + x86 .

Accepted in Quantum 2021-11-02, click title to verify. Published under CC-BY 4.0.

21