Benjamin Audoux
email: benjamin.audoux@univ-amu.fr

Alain Couvreur
email: alain.couvreur@lix.polytechnique.fr

ON TENSOR PRODUCTS OF CSS CODES

CSS codes are in one-to-one correspondance with length 3 chain complexes. The latter are naturally endowed with a tensor product ⊗ which induces a similar operation on the former. We investigate this operation, and in particular its behavior with regard to minimum distances. Given a CSS code C, we give a criterion which provides a lower bound on the minimum distance of C ⊗ D for every CSS code D. From this criterion arises a generic bound for the minimum distance which is twice larger than the single bound previously known in the literature. We apply these results to study the behaviour of iterated tensor powers of codes. Such sequences of codes are logarithmically LDPC and we prove in particular that their minimum distances tend generically to infinity. More precisely, their minimum distance increases as O(n α ) for some α > 0, where n is the code length, while the row weight of their parity-check matrices grows as O(log(n)). This entails a rather surprizing fact: even if a CSS code does not have quantum degeneracy, for a large enough , its -th iterated tensor power does. Different known results are also reinterpretated in terms of tensor products and three new families of LDPC CSS codes are studied.

Introduction

In the last century, error-correcting codes were developed to overcome the emergence of anomalies in data while transmitting or storing them. In the quantum setting, such correction systems are all the more important as quantum decoherence eventually produces such errors. At the end of the XX th century, several constructions were given for quantum error-correcting codes; among them, CSS codes, developped by A.R Calderbank, P. Shor and A . Steane [START_REF] Calderbank | Good quantum error-correcting codes exist[END_REF][START_REF] Steane | Multiple particle interference and quantum error correction[END_REF], are constructed from two classical codes orthogonal to each other. Because of their strong relation with classical codes, they have been the subject of intense study. CSS codes can alternatively be related to the topological notion of chain complexes. Not only does this approach provides a way to construct CSS codes, but parameters such as length, dimension and minimum distance can also be read through the chain complex and its (co)homology. From this perspective, the non detectable error patterns correspond to (co)cycles belonging to nonzero classes in the (co)homology of the chain complex. The dimension of the quantum code is nothing but the dimension of the (co)homology group, and the quantum minimum distance nothing but the minimum weight of a (co)homologically non trivial cycle. This point of view was pioneered by M. Freedman, D. Meyer [START_REF] Michael | Projective plane and planar quantum codes[END_REF] and A. Kitaev [START_REF] Yu | Fault-tolerant quantum computation by anyons[END_REF].

Swiftness in error-correction is crucial since error correction should occur faster than errors arise. In the classical setting, LDPC (Low Density Parity Check) codes, that is codes with sparse parity-check matrices [START_REF] Robert | Low density parity check codes[END_REF] are known to have very efficient decoding algorithms. These so-called iterative decoding algorithms have a very low complexity and can be applied to some LDPC codes with error correction performance very close to the Shannon limit; see for instance [START_REF] Richardson | Design of capacity-approaching irregular lowdensity parity-check codes[END_REF]. The notion of LDPC code can be transposed to the quantum setting and efficient iterative decoding algorithms exist [START_REF] Leverrier | Quantum expander codes[END_REF]. However, while good classical LDPC codes can easily be obtained by random generation, there is no way to generate randomly quantum LDPC codes. Hence, to date, the construction of a quantum LDPC code rests on methods of algebraic topology [START_REF] Yu | Fault-tolerant quantum computation by anyons[END_REF][START_REF] Bombin | Homological error correction: classical and quantum codes[END_REF][START_REF] Zémor | On Cayley graphs, surface codes, and the limits of homological coding for quantum error correction[END_REF][START_REF] Audoux | An application of Khovanov homology to quantum codes[END_REF] or combinatorics [START_REF] Tillich | Quantum LDPC codes with positive rate and minimum distance proportional to the square root of the blocklength[END_REF][START_REF] Couvreur | A construction of quantum LDPC codes from Cayley graphs[END_REF][START_REF]Tradeoffs for reliable quantum information storage in surface codes and color codes[END_REF]. The list of references is far from being exhaustive. Classical and quantum LDPC codes differ in yet another important point. While a generic sequence of classical LDPC codes has a minimum distance which is linear in the code length, the best known families of quantum LDPC codes have a minimum distance in O n √ log n [START_REF] Michael | Z 2 -systolic freedom and quantum codes[END_REF]. The question whether this square root barrier is fortuitous or not remains open. It is worth noting that by "LDPC" we mean that the code has parity check matrices with row weight in O(1) or O(log n) where n denotes the code length. Indeed, a recent result of Bravyi and Hastings [START_REF]Homological product codes[END_REF] proves the existence of MDPC (Moderate Density Parity Check) quantum codes, that is CSS codes described by matrices whose row weight is in O( √ n), with dimensions and minimum distances linear in the code length. Bravyi and Hastings' construction is performed by choosing two CSS codes of the same length and by computing their so-called homological product, that we shall denote here by . It produces a CSS code whose minimum distance is linear in its length with a nonzero probability.

In the present paper, we deepen the interplay between chain complexes and CSS codes by transposing to the latter the standard notion of tensor product ⊗ defined for the former. We also introduce a reduced notion ⊗ r of tensor product which, compared with the standard one, improves the relative parameters since it decreases the length but preserves the dimension and the minimum distance. Though distinct, Bravyi and Hastings' homological product and (reduced) tensor products are closely related. Relationship between them are discussed in Section 3.4.

We study families of codes obtained by iterated tensor powers of a CSS code. This operation does not improve the relative parameters but can reasonably preserve them while providing codes with sparser parity check matrices. Actually, for C 1 and C 2 two CSS codes, the length and the dimension of the product C 1 ⊗ C 2 enjoy closed formulae roughly equal to the product of the corresponding parameters of C 1 and C 2 . The minimum distance d C 1 ⊗C 2 of the product is more difficult to evaluate. Our main result is a criterion that provides a lower bound, using as large as possible sets of (co)homologically non trivial elements with as small as possible overlaps (see Definition 2.6):

Theorem 2.8 and Theorem 3.10. Let C be a CSS code defined as a pair of classical codes C 2 ⊆ C ⊥ 1 given by full rank parity-check matrices. Let g 1 , . . . , g k ∈ C ⊥ 1 and g * 1 , . . . , g * k ∈ C ⊥ 2 be such that

C ⊥ 1 = C 2 ⊕ Span(g 1 , . . . , g k ), C ⊥ 2 = C 1 ⊕ Span(g * 1 , . . . , g * k )
and ∀i, j, g * i , g j = δ i j . If, for any j 0 ∈ {1, . . . , k}, there exists Ω j 0 ⊆ g * j 0 + C 1 and Ω j 0 ⊆ g j 0 + C 2 , with |Ω j 0 |, |Ω j 0 | N and overlap(Ω j 0 ), overlap(Ω j 0 ) K. Then, for any CSS code D:

d C⊗D , d C D N K d D •
As a simple application of our criterion, we obtain then This lower bound is twice better than the previously known lower bound [BH14, Lemma 2]. It follows that the iterated tensor powers of any CSS code described by matrices with no zero column is an LDPC family whose minimum distances have a non trivial growth tending to infinity: Corollary 2.23. If C = (H X , H Z ) is any CSS code such that none of H X or H Z has a zero column, then the family C ⊗ ∈N is logarithmically LDPC with d C ⊗ 2 for every ∈ N * .

In particular, the minimum distance grows exponentially fast compared to the row weight of the parity check matrices. So, even if a CSS code has no quantum degeneracy 1 , for a large enough , its -th iterated power does.

Our criterion for estimating the minimum distance turns out to be quite efficient when applied with construction involving classical codes with a large group of automorphism. We give three such examples:

• binary codes from finite geometry, on which acts PGL(3, F q ), lead to a CSS code QFG(s) for every s ∈ N * ; • binary cyclic codes of length n on which acts Z nZ , lead to a CSS code QCC(4 s , 2 s ) for every s ∈ N * ; • binary Reed-Muller codes RM(r, s) on which acts the affine group Aff(r, F 2 ), lead to a CSS code QRM(s) for each s ∈ N * . For these three examples, the sequence of iterated -th tensor powers have length N tending to infinity and minimum distance which can be larger than N α for any α < 1 2 . Moreover, these codes are logarithmically LDPC, i.e. they have parity check matrices with row weight in O(log N ) and the number of stabilizers 1 i.e. its quantum minimum distance is not larger than the minimum of the distances of the two classical codes defining it. acting nontrivially on a qubit (i.e. the column weight) is in O(log N ) too. The first two examples provide sequences of CSS codes with constant dimension, while the third one has a dimension sequence tending to infinity. Moreover, by diagonal extraction, the latter leads to a family which is almost LDPC, in the sense that the weights grow slower than N ε for any ε > 0, and whose dimensions and minimum distances are respectively larger than N α2 and N α for any α < 1.

Remark. One can note that, for all the LDPC families provided in this paper, the lower bound for the minimum distance culminates at, but does not exceed, the "square root of the length" barrier. Unfortunately, this is no coincidence, since a simple remark (Remark 2.13) shows that if the above criterion is sharp for a given code C, then the minimum distance of C is at most the square root of the length. Without saying anything on the square root barrier conjecture in general (even for iterated tensor powers of codes), the examples given above are hence somehow optimal as corollaries of Theorem 2.8.

Organization. Section 1 contains a brief review of the needed definitions from homological algebra (Section 1.1), classical codes (Section 1.2) and CSS codes (Section 1.3). In particular, we recall there the deep connection between CSS codes and chain complexes. In Section 2, we use the latter connection to transport the notion of tensor product from chain complexes to CSS codes (Section 2.1). We provide then the main theorem, which gives a lower bound for the minimum distance of the product of two CSS codes (Section 2.2), and state a number of direct consequences for rougher, but general, lower bounds and for parameters of iterated tensor powers (Section 2.3). As examples of applications, we provide in Section 3 some elementary interpretations, in term of tensor products, of known results such as the hypergraph product codes given by J.-P. Tillich and G. Zemor in [START_REF] Tillich | Quantum LDPC codes with positive rate and minimum distance proportional to the square root of the blocklength[END_REF] (Section 3.1) or Khovanov codes given by the first author in [START_REF] Audoux | An application of Khovanov homology to quantum codes[END_REF] (Section 3.2). We also relate our tensor product for CSS codes to the homological product defined by S. Bravyi and M. Hastings in [START_REF] Bravyi | Homological product codes[END_REF][START_REF]Homological product codes[END_REF] (Section 3.4), and we discuss the product of Steane codes, already discussed in [BH13, BH14] (Section 3.3).

Note that the relationship of hypergraph and homological products with tensor products was already noticed in [START_REF] Michael | Quantum systems on non-k-hyperfinite complexes: A generalization of classical statistical mechanics on expander graphs[END_REF]. Finally, section 4 is devoted to the description of three new families of LDPC CSS codes, based on finite geometry (Section 4.1), cyclic codes (Section 4.2) and Reed-Muller codes (Section 4.3). The paper ends with two technical appendices with the details of the computation of lengths for iterated tensor powers (Appendix A) and iterated reduced tensor powers (Appendix B).

Notation. We shall consider F 2 -spaces, which are finite-dimensional vector spaces over the field F 2 . All the theoretical material present in this paper can actually be adapted to work over any field but, in order to simplify notation, and since it is sufficient for all the applications we consider here, we restrict this presentation to the F 2 case.

For any F 2 -space C, we denote by C * := Hom(C, F 2 ) the dual space of C. Every map f : A → B induces a dual map f * : B * → A * defined by f * (ϕ) = ϕ • f for every ϕ ∈ B * . For every X ⊆ C, we denote its orthogonal space by

X ⊥ := {ϕ ∈ C * | ϕ |X ≡ 0}. If C is
C -→ C * x -→ y → x, y
is then an isomorphism sending B on B * . For every X ⊂ C, it induces an isomorphism between X ⊥ and x ∈ C ∀y ∈ X, x, y = 0 . In order to reduce the amount of notation, we shall use freely this identification without necessarily mentioning it. The dual of a map f : A → B would hence be seen as f * : B → A.

By convention and unless otherwise specified, F 2 -spaces shall be denoted using roman capital letters, with an index i when it corresponds to the degree i part of a graded 3 space; chain complexes 3 using cursive capital letters; maps of chain complexes by ∂, possibly with a distinctive index or exponent; quantum codes 3 using calligraphic capital letters; and classical codes 3 using calligraphic capital letters of a slightly modified type. A same letter shall be used for associated objects: typically C shall be the CSS code 3 associated to the chain complex C defined as the 2-nilpotent 3 map ∂ (or ∂ C ) defined on C := ⊕ i∈Z C i . The map ∂ i shall be then the restricted map ∂ |C i . If a classical code is involved in the story, then it should be C .

Acknowledgements. The present paper is the fruit of several meetings organized by the TOCQ team and funded by the CNRS (for the PEPS ICQ 2013 grant TOCQ), the Labex Archimède and the INRIA. The authors are hence willing to thank the other members of the team for all the dicussions and all their comments on the paper: Anthony Leverrier, Jean-Pierre Tillich and Gilles Zémor and especially Nicolas Delfosse for his relevant observations. The authors also express their gratitude to Matthew Hastings for his feedback on a first version of the present article and for interesting discussions. Finally, they thank the anonymous referre for all its comments. 1. Some background 1.1. Chain complexes.

1.1.1. Definitions. For the sake of self-containedness, we begin by a review of standard notions of homological algebra (see e.g. [START_REF] Weibel | An introduction to homological algebra[END_REF] for further details).

In the literature, chain complexes are often defined as a sequence of F 2 -spaces (C i ) i∈Z which are all zero but a finite number of them, together with a collection of maps either all of the form ∂ i : C i → C i+1 or all of the form ∂ i : C i → C i-1 . Another way to describe them is to consider the direct sum C := ⊕ i∈Z C i and regard the collection of maps (∂ i ) i∈Z as a graded endomorphism of C. In the present paper, we shall adopt the latter approach.

Definition 1.1. A linear map ∂ ∈ End(C), for some

F 2 -space C, is 2-nilpotent if it satisfies ∂ 2 = 0. An ε-chain complex C , for ε = ±1, is a 2-nilpotent map ∂ ∈ End(C) such that • C is Z-graded, that is decomposes into C := ⊕ i∈Z C i ;
• ∂ increases the degree by exactly ε, that is Im(∂ |C i ) ⊂ C i+ε for every i ∈ Z.

If ommited and unless otherwise specified, ε shall be assumed to be equal to 1. Since C is finite-dimensional, there is only a finite number of degrees i such that C i {0}. The support of a chain complex is the smallest interval {a, a + 1, . . . , b} of integers such that C i = {0} for i < a or i > b and the value ba + 1 is called the length of the chain complex. A basis B for C is the data of a basis for each non zero space C i , that is an identification of C i with a power of F 2 . Notation 1.2. Chain complexes shall be represented as

• • • ∂ i-2 / / C i-1 ∂ i-1 / / C i ∂ i / / C i+1 ∂ i+1 / / C i+2 ∂ i+2 / / • • • .
In explicit cases given with a basis, C i shall be represented by dots, one for each generator, and ∂ i shall be represented by edges joining a generator x to the elements of ∂ i (x). For instance, the following picture:

• • • • • • • • represents the complex Span(w 1 ) ∂ 0 / / Span(x 1 , x 2 , x 3 ) ∂ 1 / / Span(y 1 , y 2 , y 3 ) ∂ 2 / / Span(z 1 )
, where Span denotes the vector space spanned by the given generators and where ∂ 0 (w 1 ) = x 1 + x 2 + x 3 , ∂ 1 (x 1 , x 2 , x 3 ) = (y 1 + y 2 , y 1 + y 3 , y 2 + y 3 ) and ∂ 2 (y 1 ) = ∂ 2 (y 2 ) = ∂(y 3 ) = z 1 .

Definition 1.3. For any ε-chain complex C , we define its dual C * as the (-ε)-chain complex ∂ * ∈ End(C * ) defined by

C * := ⊕ i∈Z Hom(C i , F 2 ) and ∂ * (ϕ) = ϕ • ∂ for every ϕ ∈ C * .
We say that a chain complex is symmetric if it is isomorphic, as a chain complex, to its dual.

Proposition 1.4. If B is a basis for an ε-chain complex C , then Mat B * (∂ * ) = t Mat B (∂), where Mat B ( f ) denotes the matrix representing the linear map in the basis B, with the convention that columns are the images of the generators, and t Mat B ( . ) denotes its transpose.

Remark 1.5. If C is given with a basis, then the maps ∂ i can be given by their matrices. Using the identification between an F 2 -space and its dual mentioned in the Notation section, C * can be seen as the chain complex obtained by reversing all the arrows and transposing all the matrices. Furthermore, over F 2 , Proposition 1.4 is proven by noting that, for every pair of generators x and y,

y ∈ ∂(x) ⇐⇒ y * ∂(x) 0 ⇐⇒ ∂ * (y * )(x) 0 ⇐⇒ x * ∈ ∂ * (y * ).
So, if C is given using Notation 1.2, then C * is obtained by reading the graph from right to left.

Definition 1.6. For any ε-chain complex C and any integer i ∈ Z, we define its i th homology group as

H i (C ) := Ker(∂ i ) Im(∂ i-ε ) ,
H • (C ).
Definition 1.7. If C is an ε-chain complex given with a basis B, then, for each i ∈ Z we denote by 1.1.2. Operations on chain complexes.

• n i (C ) := dim(C i )
Definition 1.9. Let C and D be two ε-chain complexes. We define their direct sum C ⊕ D as the ε-chain

complex ∂ C ⊕ ∂ D ∈ End ⊕ i∈Z C i ⊕ D i .
Proposition 1.10. Let C and D be two ε-chain complexes given with basis. Then

• C ⊕ D * C * ⊕ D * ; and for each i ∈ Z, • H i (C ⊕ D) H i (C ) ⊕ H i (D); • n i (C ⊕ D) = n i (C ) + n i (D), k i (C ⊕ D) = k i (C ) + k i (D), d i (C ⊕ D) = min d i (C ), d i (D) and • w i (C ⊕ D) = max w i (C ), w i (D) .
Proof. All the statements, except the one on minimum distances and the one on weights, are classical results of homological algebra.

For the statement on minimum distances, let x ∈ C i and y ∈ D i be homologically non trivial elements of minimum weight. Then (x, 0) and (0, y) ∈ C i ⊕ D i are homologically non trivial, so d i (C ⊕ D) min d i (C ), d i (D) . Conversely, every homologically non trivial element (a, b) ∈ C i ⊕ D i is such that either a or b is homologically non trivial and its weight is hence larger than either the weigth of (x, 0) or of (0, y).

For the statement on weights, consider the maps ∂ C ,i :

C i → C i+1 and ∂ D,i : D i → D i+1 . Let M C ,i and M D,i be their matrix representations. Then, the map ∂ C ⊕D,i : C i ⊕ D i → C i+1 ⊕ D i+1 is represented by the matrix: M C ,i 0 0 M D,i
which yields the result on the maximum weight of the rows.

In particular, we emphasize the fact that adding a direct summand given with its own basis and which has null homology does not affect the parameters except the length which is increased consequently. But conversely, detecting and removing a direct summand may alter the minimum distance if the basis does not respect the direct sum decomposition.

Definition 1.11. Let C and D be two ε-chain complexes. We define the tensor product C ⊗D as the ε-chain

complex Id C ⊗ ∂ D + ∂ C ⊗ Id D ∈ End ⊕ i∈Z ⊕ r∈Z (C r ⊗ D i-r ) .
Proposition 1.12. Let C and D be two ε-chain complexes. Then

• C ⊗ D * C * ⊗ D * ; and for each i ∈ Z, • H i (C ⊗ D) ⊕ r∈Z H r (C ) ⊗ H i-r (D) (Künneth formula); • n i (C ⊗ D) = r∈Z n r (C ).n i-r (D), k i (C ⊗ D) = r∈Z k r (C ).k i-r (D);
• if C and D were given with bases B C and B D , then

B C ⊗ B D provides a basis for C ⊗ D such that w i (C ⊗ D) = max w j (C ) + w k (D) j + k = i .
Proof. The statements on duals, homologies and lengths are classical results of homological algebra. The statement on weights follows from Mat

B C ⊗B D (∂ C ⊗D ) being obtained as a sum of Kronecker products of the form Mat B C (∂ C ) ⊗ Id and Id ⊗ Mat B D (∂ D ).
The isomorphism of Künneth formula, proven for instance in [Wei94, Thm 3.6.3]4 , is actually induced from maps defined at the chain complex level. It induces hence the following proposition which shall be needed further in the proof of Lemma 2.7.

Proposition 1.13. If, for each r ∈ Z, x r 1 , . . . x r j r ∈ C r and y r 1 , . . . y r j r ∈ D r induce a basis for, respectively, H r (C ) and H r (D), then, for every i ∈ Z, the elements of the form x r j ⊗ y i-r j induce a basis for H i (C ⊗ D). Remark 1.14. Evaluating d i (C ⊗ D) is less straightforward and it shall be the aim of Section 2.2. 1.1.3. Short complexes and reduction. In this paper, we shall be mostly interested in length 3 chain complexes centered around degree zero. This motivates the following definitions.

Definition 1.15. A chain complex C is said to be a short complex if it has a support contained in {-1, 0, 1}.

It is hence of the following form: C

-1 ∂ -1 / / C 0 ∂ 0 / / C 1 .
The chain complex is said to be balanced if it has non trivial homology only in degree zero. A balanced short complex is said to be reduced. For a short complex, being reduced is equivalent to require ∂ -1 to be injective and ∂ 0 to be surjective. So the chain complex is of the form

C -1 1 / / C 0 / / / / C 1 . Equivalently, it consists in requiring that dim H 0 (C ) = dim(C 0 ) -dim(C -1 ) -dim(C 1 ). Note that a short complex C -1 ∂ -1 / / C 0 ∂ 0 / / C 1 is symmetric if and only if C -1 C * 1 and ∂ 0 = ∂ * -1
. Any chain complex C can be turned into a short one by truncating the degrees higher than 1 and lower than -1. More precisely, by shifting beforehand the degree, one can extract any length 3 portion of C . However, the result is generally not balanced, even if C was. There is nonetheless a reduction process to turn a short complex into a reduced one (almost) without altering its parameters. Indeed, if This process is however non canonical since it requires the choice of complement spaces, or equivalently, the choice of the redundant rows to be removed.

C := C -1 ∂ -1 / / C 0 ∂ 0 / / C 1 is
As a conclusion, any length 3 portion of a chain complex can be grading-shifted so it is centred in degree zero, and then the above (non canonical) reduction process can turn it into a reduced complex without altering the parameters, except the weight which may even be decreased.

Remark 1.16. Adding Ker(∂ -1 ) in degree -2 and Coker(∂ 0 ) in degree 2 is another way to turn a short complex into a balanced one. The chain complex is then of length five. This provides a balancing process which is canonical and which preserves all the parameters. However, for length reasons, we shall consider in this paper, only the (non canonical) reduction process, and not the (canonical) balancing one.

1.2. Classical codes. As they shall play a keyrole in several constructions, we set here some notation on classical codes. A classical code C is a subspace of an F 2 -space E given with a basis B E . It can be described by either a generating map g

C : A 1 / / E such that Im(g C ) = C or a parity-check map p C : E / / / / B such that Ker(p C ) = C .
For any such code, we define:

• its length n C as the dimension of E;

• its dimension k C as the dimension of C ;

• its minimum distance d C as the minimum weight for a non trivial element of C , using the basis B E ;

• its weight as the maximal weight of a row of Mat B E ,B B (p C ), where B B is a given basis for B.

We define the dual of C as the code C ⊥ defined by C ⊥ ⊂ E * , which can also be seen, using the identification mentioned in the Notation section, as x ∈ E ∀y ∈ C , x, y = 0 ⊂ E. It is easily checked that p * C and g * C are, respectively, a generating map and a parity-check map for C ⊥ so that, up to transpose, C and C ⊥ exchange their generating and parity-check matrices; and that n

C ⊥ = n C and k C ⊥ = n C -k C .
1.3. CSS codes. CSS codes were developped in [START_REF] Calderbank | Good quantum error-correcting codes exist[END_REF][START_REF] Steane | Multiple particle interference and quantum error correction[END_REF]. They are a special case of stabilizer quantum error correcting codes associated to pairs of orthogonal classical codes, that is codes C 1 and C 2 such that C 2 ⊆ C ⊥ 1 ; or equivalently to matrices H X and H Z such that H X t H Z = 0. A quick review can be found in section 1.1 of [START_REF] Audoux | An application of Khovanov homology to quantum codes[END_REF] but for a more comprehensive treatment, we refer the reader to [NC10, [START_REF] Preskill | Quantum information and computation[END_REF][START_REF] Delfosse | Constructions et performances de codes LDPC quantiques[END_REF].

A CSS code is said to be symmetric if C 1 = C 2 or, equivalently, if H X = H Z .
Remark 1.17. The terminology of symmetric CSS codes is non standard. Such codes are sometimes referred to as weakly self dual CSS codes in the literature. We preferred use the term symmetric since it is coherent with our terminology of symmetric chain complexes. Indeed, if a chain complex is symmetric, then the corresponding CSS code is symmetric.

For a CSS code C, some relevant parameters are

• n C the length of C, that is the common length of the codes C 1 and C 2 ;

• k C the dimension of C, that is the dimension of C ⊥ 1 C 2 • d C the minimum distance of C, that is the minimum weight of an element of (C ⊥ 1 \ C 2 ) ∪ (C ⊥ 2 \ C 1 ); • w C the weight of C, that is the highest weight realized by a row of H X or H Z .
They shall be gathered in the notation n

C ; k C ; d C ; w C .
Chain complexes turn out to be efficient for constructing such CSS codes. Indeed, once equipped with a basis, they not only naturally provide matrices whose product is zero, but parameters can also be read from them, their duals and the associated homologies. The following classical statement reformulates the usual matrix-based description of CSS codes in terms of chain complexes, and this allows a more intrinsic description of these objects. Similar statements appear, for instance, in [Aud14, Prop. 1.7] or [START_REF] Delfosse | Constructions et performances de codes LDPC quantiques[END_REF].

Proposition 1.18. To a short complex

C := C -1 ∂ -1 / / C 0 ∂ 0 / / C 1 given with a basis B, there is an associated CSS code C := Mat B (∂ 0 ), t Mat B (∂ -1 ) with parameters n C = n C , k C = k C , d C = min d C , d C * and w C = max w C , w C * .
Compared to the definition of CSS codes given above, the codes C 1 and

C 2 correspond to C 1 = Ker(∂ 0 ) ⊥ and C 2 = Im(∂ -1 ), or equivalently to C 1 = Im(∂ * 0 ) and C 2 = Ker(∂ * -1 ) ⊥ . Conversely, two matrices H X and H Z such that H X t H Z = 0 provide a chain complex 0 / / F k 1 2 t H Z / / F n C 2 H X / / F k 2 2 / / 0
where k 1 and k 2 are, respectively, the numbers of rows in H Z and H X . There is hence a one-to-one correspondence between CSS codes and, up to isomorphisms, short complexes given with a basis. However, as a consequence of the discussion on reduction given in Section 1.1.3, removing redundant rows in H Z and H X does not affect the parameters, except the weight which may even be decreased. It is hence natural to focus on CSS codes associated to reduced complexes.

Remark 1.19. The data of a 2-nilpotent map ∂ ∈ End(C) is actually sufficient to construct a CSS code as C 1 = Ker(∂) ⊥ and C 2 = Im(∂). This code is actually the code associated to the short complex

C ∂ / / C ∂ / / C . Note that from every pair of classical codes C 1 , C 2 such that C 2 ⊆ C ⊥ 1 , one can always construct a 2-nilpotent map ∂ : F n 2 → F n 2 whose image is C 2 and kernel is C ⊥ 1 .
This means that every quantum code can be represented by a 2-nilpotent chain complex. This description of quantum CSS code from 2-nilpotent map is used in [START_REF]Homological product codes[END_REF] and shall be discussed in Section 3.4.

Tensor products of CSS codes

2.1. Definitions. As mentioned in the previous section, CSS codes are in one-to-one correspondence with short complexes. As such, they inherit the notions of direct sum and tensor product. The former is well defined since it sends short (respectively reduced) complexes to short (respectively reduced) complexes. The latter requires some more attention. Indeed, the tensor product of two short complexes is, in general, not short anymore but of length 5. One way to correct this shortcoming is to roughly truncate. Definition 2.1. For C i i∈I a finite family of CSS codes, we define ⊗ i∈I C i as the CSS code associated to the degrees {-1, 0, 1}-truncation of ⊗ i∈I C i , where, for each i ∈ I, C i is the short complex associated to C i . When the family is made of copies of the same code C, we also denote it by C ⊗ . However, the truncation produces two major drawbacks:

• the operation is not associative in the sense that, in general, (

⊗ i∈I C i ) ⊗ ( ⊗ i∈J C i ) ( ⊗ i∈I J C i );
• the result is, in general, not reduced even if all the factors are. To remedy the second issue, one can use the reduction process described in Section 1.1.3. Definition 2.2. For C i i∈{1,...,k} a finite family of CSS codes, we define recursively ⊗ r i∈{1,...,k} C i as the CSS code associated to the reduction of the degrees {-1, 0, 1}-truncation of

C 1•••(k-1) ⊗ C k , where C 1•••(k-1) is the reduced complex associated to ⊗ r i∈{1,...,k-1}
C i and C k the short complex associated to C k . When the family is made of copies of the same code C, we also denote it by C ⊗ r .

Warning 2.3. The notation ⊗ r is an abuse of notation since it is not canonically defined and requires, at each step, the choice of redundant rows to be removed.

Remark 2.4. In order to get a canonical notion of somehow reduced tensor product, one can use the balancing process mentioned in Remark 1.16. However, it ends with slightly longer codes.

2.2.

A minimum distance result. Let C be a chain complex given with bases (a 1 , . . . , a n -1 ) for

C -1 , (b 1 , . . . , b n 0 ) for C 0 and (c 1 , . . . , c n ) for ⊕ i∈Z\{-1,0} C i . We denote the matrix associated to ∂ -1 by    λ 11 • • • λ 1n -1 . . . . . . λ n 0 1 • • • λ n 0 n -1    = Λ 1 , . . . , Λ n -1 .
We fix g 1 , . . . , g r elements in Ker(∂ 0 ) which generate a basis of H 0 (C ), and set g j := n 0 i=1 γ j i b i for all j ∈ {1, . . . , r}. Then we complete g 1 , . . . , g r in two steps, first into a basis of Ker(∂ 0 ), and then into a basis of C 0 . Finally we define, for all j 0 ∈ {1, . . . , r},

Ker ⊥ j 0 := g * j 0 + Ker(∂ 0 ) ⊥
which, roughly speaking, corresponds to the elements in C 0 which are orthogonal to any generator of Ker(∂ 0 ) but g j 0 .5

Remark 2.5. Elements of Ker ⊥ j 0 are in Im(∂ -1 ) ⊥ = Ker(∂ * -1 ), but not in Ker(∂ 0 ) ⊥ = Im(∂ * 0 ), they are hence cohomologically non trivial elements.

Definition 2.6. For every subset Ω ⊂ C 0 , we define overlap(Ω) := max i∈{1,...,n 0 } p ∈ Ω b i ∈ p . If stacking, as rows of a matrix, the elements of Ω, it corresponds to the maximum weight of a column.

Lemma 2.7. Let N, K ∈ N * . If, for any j 0 ∈ {1, . . . , r}, there exists Ω j 0 ⊂ Ker ⊥ j 0 such that |Ω j 0 | N and overlap(Ω j 0 ) K, then, for every chain complex D such that either C or D is balanced,

d C ⊗D N K d D .
Proof. We consider . . , g r ∈ Ker(∂ D ) and elements x j , y i , z j ∈ D, such that [g j 0 ] is non trivial in H 0 (D) for at least one given j 0 ∈ {1, . . . , r} and

x 0 = n -1 i=1 a i ⊗ a i + n 0 i=1 b i ⊗ b i + n i=1 c i ⊗ c i , with a i , b i , c i ∈ D,
x 0 = r j=1 g j ⊗ g j + ∂ C ⊗D   n -1 j=1 a j ⊗ x j + n 0 i=1 b i ⊗ y i + n i=1 c i ⊗ z i   = r j=1 n 0 i=1 γ j i b i ⊗ g j + n -1 j=1 n 0 i=1 λ i j b i ⊗ x j + n 0 i=1 b i ⊗ ∂ D (y i ) + non relevant terms,
where the non relevant terms are of the form a i ⊗ • or c i ⊗ • for some i.

For every i ∈ {1, . . . , n 0 }, we project on terms of the form b i ⊗ • and obtain then

b i = r j=1 γ j i g j + n -1 j=1 λ i j x j + ∂ D (y i ).
For any p = (p 1 , . . . , p n 0 ) ∈ F n 0 2 , we have then

n 0 i=1 p i b i = r j=1 n 0 i=1 p i γ j i g j + n -1 j=1 n 0 i=1 p i λ i j x j + ∂ D (something),
which can be reformulated as

i∈p b i = r j=1 p, g j g j + n -1 j=1 p, Λ j x j + ∂ D (something).
If p ∈ Ker ⊥ j 0 , we obtain i∈p b i = g j 0 + ∂ D (something) which is non trivial in H 0 (D), and hence

i∈p |b i | i∈p b i d D .
Now we consider Ω j 0 as in the statement of the lemma. We obtain then

Kd C ⊗D = K|x 0 | = K n -1 i=1 |a i | + n 0 i=1 |b i | + n i=1 |c i | K n 0 i=1 |b i | p∈Ω i∈p |b i | Nd D ,
and since d C ⊗D is an integer, it is bounded below by N K d D .

Using the correspondence established in Proposition 1.18, this leads to the following statement, formulated in terms of classical codes and matrices.

Theorem 2.8. Let C be a CSS code defined as a pair of classical codes C 2 ⊆ C ⊥ 1 given by full rank paritycheck matrices. Let g 1 , . . . ,

g k ∈ C ⊥ 1 and g * 1 , . . . , g * k ∈ C ⊥ 2 be such that C ⊥ 1 = C 2 ⊕ Span(g 1 , . . . , g k ), C ⊥ 2 = C 1 ⊕ Span(g * 1 , . . . , g * k )
and ∀i, j, g * i , g j = δ i j . If, for any j 0 ∈ {1, . . . , k}, there exists Ω j 0 ⊆ g * j 0 + C 1 and Ω j 0 ⊆ g j 0 + C 2 , with |Ω j 0 |, |Ω j 0 | N and overlap(Ω j 0 ), overlap(Ω j 0 ) K. Then, for every CSS code D, the minimum distance of C ⊗ D satisfies

d C⊗D N K d D •
Lemma 2.7 implies actually a stronger result since (1) the matrices H X and H Z may not have full rank as long as the matrices of D do;

(2) one may use distinct bases to define the sets Ω's and Ω 's. However, our applications shall use only the statement of Theorem 2.8, and mostly in its one dimensional case, which is even simpler to state.

Corollary 2.9. Let C be a CSS code of dimension 1 associated to a pair of classical codes C 2 ⊆ C ⊥ 1 given by full rank parity-check matrices. Then, if there exists a subset

Ω ⊆ C ⊥ 1 \ C 2 and a subset Ω ⊆ C ⊥ 2 \ C 1 with |Ω|, |Ω | N and overlap(Ω), overlap(Ω ) K. Then for any CSS code D, the minimum distance of C ⊗ D satisfies d C⊗D N K d D •
Remark 2.10. If dealing with a symmetric code described by a symmetric chain complex, then it is sufficient to consider the sets Ω in Theorem 2.8 or Corollary 2.9, since they can be used again as sets Ω .

2.3. Some direct consequences. In this section, we state some direct consequences of Lemma 2.7.

2.3.1. General lower bounds for the minimum distance of tensor products.

Corollary 2.11. If C is a chain complex satisfying the hypothesis of Lemma 2.7, then d C N K . Proof. Apply Lemma 2.7 with the reduced complex D := 0 / / F 2 / / 0 .

Remark 2.12. Applied to the case Im(∂ -1 ) = 0, Corollary 2.11 provides also a lower bound for the minimum distance of a classical code. In this context, the statement essentially follows from the remark that, if an element c of a code has a non trivial scalar product with a vector ω, then c has at least one non trivial entry shared with ω. Now, with the notation of Section 2.2 and for j 0 such that g j 0 ∈ c, c has at least one non trivial entry in common with each of the N elements of Ω j 0 . But each of these entries can appear at most K times. It follows that c has at least N K non trivial entries. Remark 2.13. One may cherish the hope to provide an LDPC family of CSS codes with minimum distances growing faster than the square root of the lengths by applying Corollary 2.11 to evaluate the minimum distance of a CSS code C as some N K . This is however doomed to fail. Indeed, if stacking the elements of Ω into a matrix and counting, column by column, the number V of non trivial entries, we obtain V n C K; but on the other hand, counting V row by row, we obtain V Nd C * since, as noticed in Remark 2.5, elements of Ω are non trivial cohomology classes. It follows that N

K d C * n C . In particular, if N K is close enough to d C , we obtain d C d C * n C and hence d C = min(d C , d C * ) √ n C .
Corollary 2.14. If C and D are two chain complexes such that one of them is balanced, then

max(d C , d D ) d C ⊗D d C d D .
Proof. The right hand side is a direct consequence of Proposition 1.13. The left hand one is obtained by applying Lemma 2.7 with N = K = 1; this always holds when Ω j 0 is a singleton.

As we shall see in several examples, the upper bound is sharp. On the contrary, the lower bound is not, except in some trivial cases. Proof. With the notation of Section 2.2, we consider, for each j 0 ∈ {1, . . . , r}, Ω j 0 := Ker ⊥ j 0 . It can actually be described as ω j 0 + Ker(∂ 0 ) ⊥ with ω j 0 any element in Ker ⊥ j 0 . Now, for any i ∈ {1, . . . , n 0 }, there is at least one element f i ∈ Ker(∂ 0 ) ⊥ such that f i , b i = 1, otherwise b i would be contained in Ker(∂ 0 ) ⊥ ⊥ Ker(∂ 0 ) and ∂ 0 (b i ) would be zero. Furthermore, as a generator, b i ∈ f i , and the map x → x + f i induces a bijection between the elements in Ω j 0 which contain b i and those who do not. It follows that overlap(Ω j 0 ) = 1 2 |Ω j 0 | and the statement is proved using Lemma 2.7. Remark 2.16. Similar results can be obtained for q-ary CSS codes. In this case we would get

d C ⊗D q q-1 max(d C , d D ).
Remark 2.17. The lower bound in Corollary 2.14 can hence be sharp only if ∂ 0 vanishes on some generator. If this generator is not in the image of

∂ -1 , then d C = 1 and d C d D = max(d C , d D ). If it is in the image of ∂ -1 ,
2 max(d C , d D ) d C⊗ r D .
In Section 3.3 we shall see an example where

d C⊗D = 2 + 1 3 max(d C , d D ) < d C d D .
Remark 2.19. For chain complexes, the minimum distance of a tensor product is bounded above by the product of the minimum distances of the summands but, because of the interplay with dual chain complexes, this does not hold anymore for CSS codes. An example is given by the Tillich-Zémor construction, presented in Section 3.1.

Parameters of iterated tensor powers.

Corollary 2.20. Let C be the CSS code associated to

C := F b 1 2 1 / / F a 2 / / / / F b 2 2
, where a, b 1 , b 2 ∈ N. If C and C * satisfy both the hypothesis of Lemma 2.7 for the same integers N, K ∈ N * , then C ⊗ ∈N is a family of CSS codes with parameters

∼ 1 2 a + 2 √ b 1 b 2 π √ b 1 b 2 a + 2 b 1 b 2 ; (a -b 1 -b 2 ) ; N K ; a .
In particular, the family is logarithmically LDPC and the minimum distance grows strictly faster than the

log N-log K log(a+2 √ b 1 b 2 )
-th power of the length. Proof. The statement on

• the length follows from an adaptation of the proofs of Prop. 4.1, A.1 and A.2 in [START_REF] Audoux | An application of Khovanov homology to quantum codes[END_REF], details can be found in Appendix A; • the dimension is a direct consequence of the Künneth formula;

• the bound on the minimum distance follows from an inductive use of Lemma 2.7; • the weight follows from an inductive use of Proposition 1.12 and the fact that b 1 , b 2 a, which is a consequence of the reducedness of C .

Corollary 2.20 can be improved by using the reduced notion of tensor powers defined in Section 2.1: parameters k and d are kept untouched, parameter w is possibly reduced and parameter n is significantly reduced. To avoid making the text cumbersome, we only state here the case b = b 1 = b 2 , but the general statement is given in Appendix B. This provides a family logarithmically LDPC with a minimum distance which grows at least as the log N-log K log(a+b)th power of the length.

Proof. Compared to Corollary 2.20, only the statement on lengths needs a further proof. We set C 1 := C and define recursively C as the tensor product of C with the reduction of C -1 . We define the sequences of integers (a ) ∈N * and (b )

∈N * by C =: F b 2 1 / / F a 2 / / / / F b 2 .
Developping C ⊗ C and using Künneth formula to say that the homology is trivial except in degree zero, we obtain the following -for simplicity, we have written only the dimensions of the different spaces -where the second line corresponds to the result after reduction:

0 / / bb / /
+1 b +1 = A a b with A = a 2b b a -b = 1 -2 1 1 -1 a -2b 0 0 a + b 1 -2 1 1 , and hence that a b = A -1 a b = 1 3 2(a + b) + (a -2b) (a + b) -(a -2b) .
Remark In particular, and even if a CSS code has no quantum degeneracy, i.e. its quantum minimum distance is not larger than the minimum of the distances of the two classical codes defining it, for a large enough , its -th iterated power does.

Remark 2.24. The previous statement asserts that the row weight of the -th iterated tensor power C ⊗ (or C ⊗ r ) is linear in and hence logarithmic in the code length. Very similar arguments would show that the column weights, which are related to the number of stabilizers acting non trivially on a given qubit, are also in O( ) and hence logarithmic in the code length.

Reinterpretation of known results

3.1. Tillich-Zemor codes. In [TZ14], J.-P. Tillich and G. Zémor give a construction of a CSS code from any two classical codes. Their construction is based on a graph point of view. In this section, we give an alternative approach of their construction based on tensor products. Any linear map between two F 2 -spaces can be seen as a chain complex of length 2 and, by adding a null space on the right or on the left, as a short complex. If interested only in reduced complexes, one can apply the reduction process described in Section 1.1.3 or, equivalently, consider only injective maps (with a null space on their right) and surjective map (with a null space on their left). The following two propositions can be straightforwardly verified.

Proposition 3.1. If C := C -1
1 g / / C 0 / / / / 0 is given with a basis B, then

• n C = dim(C 0 ); • H 0 (C ) = Coker(g) so k C = dim(C 0 ) -dim(C -1 ) and, if Coker(g) 0, d C = 1; • w C = 0. Proposition 3.2. If C := 0 1 / / C 0 p / / / / C 1 is
given with a basis B, then

• n C = dim(C 0 ); • H 0 (C ) = Ker(p) so k C = dim(C 0 ) -dim(C 1 ) and, if Ker(p) 0, d C = min x∈Ker(p)\{0}
|x|;

• w C is the maximal weight of a row in Mat B (p).

Now, noting that

C -1 1 g / / C 0 / / / / 0 * = C -1 C 0 g * o o o o 0 c o o and 0 1 / / C 0 p / / / / C 1 * = 0 C 0 o oo o C 1 c p * o o ,
and recalling from Section 1.2 that a classical code C can be given either by an injective generating map g C or by a surjective parity-check map p C , and that, up to transpose, C and C ⊥ exchange their generating and parity-check maps, we obtain as a corollary of Proposition 1.18:

Proposition 3.3. If C is a classical code, then the CSS code C p associated to 0 1 / / C 0 p C / / / / C 1 has parameters n C p = n C , k C p = k C , d C p = 1 and w C p = w C ; and the CSS code C g associated to C -1 1 g C / / C 0 / / / / 0 has parameters n C g = n C ⊥ , k C g = k C ⊥ , d C g = 1 and w C g = w C ⊥ .
It can hence be noted that CSS codes associated to classical codes have very poor minimum distances. However, combining Proposition 1.18 with Proposition 1.12 and Corollary 2.14, we obtain Tillich-Zemor result which can be stated as:

p C / / / / C 1 ⊗ D -1 1 g D / / D 0 has parameters n C⊗D = n C n D ⊥ + k C k D ⊥ , k C⊗D = k C k D ⊥ , d C⊗D = min(d C , d D ⊥ ) and w C⊗D = max w C + w D ⊥ , w C ⊥ + w D .
Remark 3.5. The fact that one has to combine two classical codes described, respectively, by a parity-check and a generating matrix should be compared to the necessity, in Tillich-Zemor construction, to deal with a classical code and the dual of another one. This is pictured by the butterfly crossed polygon in the right-hand side of [TZ14, Figure 5].

Khovanov codes.

Chain complexes arise naturally in the context of topology, and in particular in the framework of knot and link theory. Khovanov homology is an example of link invariant which is defined as the homology of a chain complex Ch(D) associated to any link diagram D. In [START_REF] Audoux | An application of Khovanov homology to quantum codes[END_REF], the first author used it to define CSS codes associated to link diagrams. Khovanov homology is related to tensor products via the following proposition:

Proposition 3.6. For any pointed link diagrams D 1 and D 2 , Ch(D 1 #D 2 ) = Ch(D 1 )⊗Ch(D 2 ) where # denotes the pointed connected sum.

Unknot codes.

The diagrams used in [START_REF] Audoux | An application of Khovanov homology to quantum codes[END_REF] to define the unknot codes are not iterated connected sums of a given diagram. However, their Khovanov chain complexes is isomorphic to that of the following diagrams which are iterated connected sums. It follows that the chain complexes underlying unknot codes are the -th tensor power of

• • • • • • • • • .
We denote the generators in the middle degree, from top to bottom, by positive integers from 1 to 5. Using the subset notation described in the Notation section, the homology is generated by 14. Since the chain complex is symmetric, it is sufficient to use Corollary 2.20 with Ω 14 := 12, 45 to obtain back the parameters 3 2 +1 √ 8π , 1, 2 , 3 . Using Corollary 2.21, it can be improved into a family with asymptotical parameters 2•7 3 , 1, 2 , 3 . 3.2.2. Unlink codes. The diagrams considered in [START_REF] Audoux | An application of Khovanov homology to quantum codes[END_REF] to define unlink codes are iterated connected sums of the following diagram so the associated chain complexes are iterated tensor powers of

• • • • • • .
We denote the generators in the middle degree, from top to bottom, by positive integers from 1 to 4. Using the subset notation, the homology is generated by 12 and 13, and using Corollary 2.20 with Ω 12 := 24, 13 and Ω 13 := 34, 12 , we obtain back the parameters 3 2π 6 , 2 , 2 , 4 . Using Corollary 2.21, it can be improved into a family with asymptotical parameters 2 3 5 , 2 , 2 , 4 . Remark 3.7. Forgetting its Khovanov origin, the above family can be extended to a two-parameters family defined as the -th tensor power of

• • . . . • 2r generators • . . . • • .
From a coding theoretic point of view, the corresponding CSS code is symmetric and associated to the code C ⊆ C ⊥ where C is the repetition code and C ⊥ is the parity code. The homology is generated by 1i | i ∈ {2, . . . , 2r -1} and, using Corollary 2.21 with Ω 1i := i(2r), 2r-1 j=1 j i j , we obtain codes with asymptotical parameters 2 3 (2r + 1) , (2r -2) , 2 , 2r when r is fixed and tends to infinity.

3.3. Product of Steane 7; 1; 3 codes. In [BH13, Section V.A], which is the extended version of [START_REF]Homological product codes[END_REF],

Bravyi and Hastings study in details the Steane code with parameter 7; 1; 3 . In its principal symmetric form, it can be described as the CSS code S 7;1;3 associated to

• • • • • • • • • • • • • .
We denote the generators in the middle degree, from top to bottom, by positive integers from 1 to 7. Using the subset notation, it is easily computed that Ker(∂ 0 )

N.

We shall see in Section 4.1 a generalization of S 7;1;3 .

3.4. Bravyi-Hastings homological product. In [START_REF]Homological product codes[END_REF], Bravyi and Hastings present a notion of homological product for CSS codes which are described by 2-nilpotent maps. This product is closely related to the tensor product of codes. Definition 3.8. Let C, D be two F 2 -spaces, and ∂ C ∈ End(C), ∂ D ∈ End(D) be two 2-nilpotent maps6 . As recalled in Remark 1.19, these data provide two CSS codes C, D and the homological product C D is defined as the CSS code associated to the 2-nilpotent map

∂ C ∂ D := ∂ C ⊗ Id D + Id C ⊗ ∂ D ∈ End(C ⊗ D).
Proposition 3.9 ([BH14]). If C and D are two CSS codes described by 2-nilpotent maps, then k

C D = k C k D and max(d C , d D ) d C D d C d D .
Bravyi and Hastings show moreover that for a random CSS code C of length n, the minimum distance of C 2 is larger than cn 2 for some positive constant c with a probability tending to 1 when n tends to infinity.

In the coming section, we explain how Bravyi and Hastings' homological product can be understood as extracted from the tensor product. It shall follow that our criterion for a lower bound on the minimal distance, as well as all its corollaries, apply in the same way to homological products. From this perspective, homological products appear as an improvement of tensor products since they reduce the length of the outputs while preserving the dimension. Minimum distances are however more difficult to compare, even if they share a same lower bound.

Conversely, we then show that the situation is inverted when starting from chain complexes: tensor products can be understood as extracted from the homological products of the associated ungraded 2-nilpotent maps. In this situation, minimum distances for tensor and homological products are equal, so the tensor product has globally better relative parameters.

3.4.1.

From 2-nilpotent maps to chain complexes. Let C be a CSS code described by a 2-nilpotent map ∂ C ∈ End(C). From the chain complex point of view, C is also the CSS code associated to

C := C ∂ C / / C ∂ C / / C ,
which can be reduced into

C - 1 ∂ C / / C ∂ C / / / / C + ,
where

C =: C -⊕ Ker(∂ C ) and C + := C C + with C := C + ⊕ Im(∂ C ). We set π C : C → C + the canonical projection and ∂ -1 C the inverse map of ∂ C : C -→ C + .
We set similar notation for D, another CSS code described by a 2-nilpotent map.

The length 3 middle part of C ⊗ r D is equal to

C -⊗ D + ∂ C ⊗Id D + + C -⊗ D Id C ⊗∂ D 3 3 ∂ C ⊗Id D + + C ⊗ D + C ⊗ D Id C ⊗∂ D 3 3 ∂ C ⊗Id D + + C ⊗ D - Id C ⊗∂ D 3 3 ∂ C ⊗Id D + + C + ⊗ D C + ⊗ D - Id C ⊗∂ D 3 3
. can be decomposed as the direct sum P 1 ⊕ P 2 ⊕ P 3 , where

• P 1 is the chain subcomplex defined as Span            w ⊗ x + + ⊕ u ⊗ v 3 3 + + ⊕ 0 ⊕ ∂ C (w) ⊗ ∂ -1 D (x) 3 3 + + ⊕ 0 3 3 + + 0 0 3 3            , with u ⊗ v ∈ C -⊗ D -and w ⊗ x ∈ C -⊗ D + .
In other words, P 1 is defined as C -⊗ D -in degree -1; as the space spanned by elements of the form w

⊗ x ⊕ ∂ C (w) ⊗ ∂ -1 D (x) ⊕ 0 ∈ C -⊗ D + ⊕ C ⊗ D ⊕ C + ⊗ D -
for some w ∈ C -and x ∈ D + , in degree 0; and as zero in degree 1;

• P 2 is the chain subcomplex defined as Span             0 + + ⊕ u 1 ⊗ v 1 3 3 + + ⊕ y 1 ⊗ z 1 ⊕ w ⊗ x 3 3 + + ⊕ u 2 ⊗ v 2 3 3 + + y 2 ⊗ z 2 ∂ C (w) ⊗ ∂ -1 D π D (x) 3 3             with u 1 ⊗ v 1 ∈ C -⊗ Ker(∂ D ), u 2 ⊗ v 2 ∈ C ⊗ D -, w ⊗ x ∈ C ⊗ D, y 1 ⊗ z 1 ∈ C ⊗ D + and y 2 ⊗ z 2 ∈ C + ⊗ D + ;
• P 3 is the chain subcomplex defined as Span

           0 + + ⊕ 0 3 3 + + ⊕ 0 ⊕ 0 3 3 + + ⊕ 0 3 3 + + y ⊗ z w ⊗ x 3 3            with w ⊗ x ∈ C + ⊗ D -and y ⊗ z ∈ C + ⊗ Im(∂ D ).
It is easily checked that H 0 (P 1 ) H 0 (P 3 ) {0} and that P 2 is isomorphic, as a chain complex, to

C ⊗ D -⊕ C -⊗ Ker(∂ D ) Id C ⊗∂ D +∂ C ⊗Id D / / C ⊗ D Id C ⊗∂ D +∂ C ⊗Id D / / C ⊗ D C + ⊗ D + ,
which is a partially reduced form of the chain complex associated to ∂ C ∂ D . In degree 0, the isomorphism is nothing but the projection ψ onto the central summand C ⊗D. As a consequence, we obtain that

H(∂ C ∂ D ) H 0 (C ⊗ r D) H 0 (C ⊗ D) H 0 (C ) ⊗ H 0 (D) H(∂ C ) ⊗ H(∂ D ).
The homological product can hence be seen as a subcomplex of the tensor product that all the homology. This provides a substantial reduction of the length, but the variation of the minimum distance is, again, more difficult to estimate. However, the criterion for a lower bound given in Theorem 2.8 still holds.

Theorem 3.10. Let C be a CSS code defined by a 2-nilpotent map ∂ C , and let g 1 , . . . ,

g k ∈ Ker(∂) and g * 1 , . . . , g * k ∈ Im(∂) ⊥ be such that Ker(∂) = Im(∂) ⊕ Span(g 1 , . . . , g k ), Im(∂) ⊥ = Ker(∂) ⊥ ⊕ Span(g * 1 , . . . , g * k )
and ∀i, j, g * i , g j = δ i j . If, for any j 0 ∈ {1, . . . , k}, there exist Ω j 0 ⊆ g * j 0 + Ker(∂) ⊥ and Ω j 0 ⊆ g j 0 + Im(∂), with |Ω j 0 |, |Ω j 0 | N and overlap(Ω j 0 ), overlap(Ω j 0 ) K. Then, for any CSS code D defined by a 2-nilpotent map, we have

d C D N K d D •
Proof. Let C and D denote the chain complexes underlying C and D. Lemma 2.7 gives a lower bound for the weight of homologically non trivial elements in the kernel of ∂ C ⊗D . In particular, it holds for elements in P 2 , and ψ provides a one-to-one correspondence between them and homologically non trivial elements in the kernel of ∂ C D . However, the map ψ does not preserve the weight. Nonetheless, using notation from Section 2.2, ψ(x 0 ) is actually equal to 3.4.2. From chain complexes to 2-nilpotent maps. Forgetting the grading provides a canonical way to produce a 2-nilpotent map from any chain complex. We explain now how the tensor product of two chain complexes can be seen as extracted from the homological product of the associated 2-nilpotent maps. This actually corresponds to the case of 2-nilpotent maps given with a basis such that their matrices are blocksubdiagonal. Given a CSS code C associated to a chain complex

C = • • • / / C i ∂ i / / C i+1 ∂ i+1 / / • • •
where the C i 's are all {0} but finitely many of them, we can define

C := ⊕ i∈Z C i and ∂ C := ⊕ i∈Z ∂ i . The map ∂ C is 2-nilpotent and it is easily checked that Ker(∂ C ) Im(∂ C ) = H • (C ) = ⊕ i∈Z H i (C ).

Comparison between tensor and homological powers.

There are two natural notions of product for CSS codes, namely tensor and homological ones, and we have observed how to switch from one to the other. They both generate LDPC families when used iteratively. It is natural to question whether a construction is better than the other. The answer is actually negative, and the qualities of the family of codes obtained by iterated tensor or homological powers depend on the initial descriptive type of the input codes:

• if the input code is described by a 2-nilpotent map, then one can see it as coming from a chain complex with repeated space and map. In this situation, the homological powers of the original 2-nilpotent map provide shorter codes with same dimensions than the tensor powers. Moreover, the control of the minimum distances provided by the present paper is equal for both. • if the input code is described by a general complex, then one can consider the underlying 2-nilpotent map by forgetting the grading. In this situation, the tensor powers of the original chain complex provide shorter codes with same dimensions and minimum distances, hence better relative parameters, than the homological powers. A good philosophy should hence be to stick to the original nature of the inputs and use homological products when dealing with 2-nilpotent maps and tensor products when dealing with chain complexes.

New families of codes

In this section we present new families of CSS codes defined as iterated tensor powers of some given CSS code. They all share a logarithmic LDPC structure and, for a length N which tends to infinity, their minimum distance can be "as close as possible to √ N " in the sense that, for all α < 1 2 , there is such a family whose minimum distance is larger than N α .

To control minimum distances, we use Theorem 2.8 which requires the construction of large sets of cohomologically non trivial vectors Ω with small overlap. For this sake, it is natural to search among codes with many automorphisms. This feature is indeed shared by our three examples, namely:

• codes from finite geometry, endowed with a natural action of PGL(3, F q ); • cyclic codes, i.e. codes of length n with a natural action of the cyclic group of order n;

• Reed Muller codes, endowed with a natural action of the affine group.

4.1. Quantum finite geometry codes. In this section, we set q = 2 s for some positive integer s. The idea relies on using points/lines incidence structures of affine and projective spaces over finite fields to construct LDPC CSS codes. It has already been used to construct classical LDPC codes in [START_REF] Kou | Low-density parity-check codes based on finite geometries: a rediscovery and new results[END_REF] and moderate density parity check quantum codes in [START_REF] Farinholt | Quantum LDPC codes constructed from point-line subsets of the finite projective plane[END_REF].

Here, we shall consider two incidence structures:

• the point/line incidence structure;

• the point/affine charts incidence structure.

4.1.1. The projective plane. The projective plane P 2 (F q ) is defined as the set of lines of F 3 q passing through the origin. Let us recall classical facts of this finite geometry: Proposition 4.1.

(i) The plane contains q 2 + q + 1 points and q 2 + q + 1 lines.

(ii) Every line contains q + 1 points and every point is contained in q + 1 lines.

(iii) Every two distinct points are contained in a unique line and every two distinct lines meet at a unique point.

Note that each of the above statements express the principle of duality in projective planes, which swaps point and lines and reverses inclusions.

Example 4.2. For q = 2, the projective plane is also called Fano plane. It contains 7 points and 7 lines and the point/line incidence structure is usually represented by the picture given in Figure 1 in which the 6 lines and the circle represent the 7 lines of P 2 (F 2 ).

Additionally we consider the affine charts of the projective plane. Definition 4.3. An affine chart of P 2 (F q ) is the complement of a line. (i) An affine chart is isomorphic to the affine plane over F q ; in particular it contains q 2 elements.

(ii) Let L be a line in P 2 (F q ) and U an affine chart. Then,

• either L is the complement of U and hence L ∩ U = ∅;

• or L ∩ U is an affine line and hence has q elements. In particular, since q is even, the number of points of L ∩ U is always even. (iii) The number of affine charts of P 2 (F q ) equals the number of lines and hence equals q 2 + q + 1. 4.1.2. Classical codes associated to projective planes in characteristic 2. We construct two binary codes associated to the projective space 2 (F q ), with length |P 2 (F q )| = q 2 +q+1. Vectors of F q 2 +q+1 2 can be regarded as subsets of P 2 (F q ) and we shall freely speak of either vectors or subsets of P 2 (F q ). From this point of view, the canonical inner product on F q 2 +q+1 2 can be given a geometric interpretation since, for S , S ⊆ P 2 (F q ):

S , S = |S ∩ S | mod 2.
We introduce the codes • C lines (s), spanned by lines of P 2 (F q ); • C planes (s), spanned by the affine charts of P 2 (F q ).

Warning 4.5. We want to stress the fact that, even though the projective spaces are defined over F q , the associated classical codes, and hence the quantum codes to follow, are defined over F 2 .

The dimension of C lines (s) is well-known.

Proposition 4.6 ([Smi69]

). For all s > 0, we have dim F 2 C lines (s) = 3 s + 1.

Proposition 4.7. For all s 1,

(i) C planes (s) ⊆ C planes (s) ⊥ ; (ii) C planes (s) ⊆ C lines (s); (iii) C planes (s) ⊆ C lines (s) ⊥ ; (iv) C lines (s) = C planes (s) ⊕ Span(L) for every line L ⊆ P 2 (F q ); (v) dim C lines (s) -dim C planes (s) = 1.
Proof. To prove (i), note first that an affine chart has an even number of points and hence is orthogonal to itself. Let A 1 , A 2 be two distinct affine charts. Then, there exist two distinct lines L 1 , L 2 such that if we denote by c X the complement of a subset X of P 2 (F q ), then

A 1 = c L 1 and A 2 = c L 2 . Thus, A 1 ∩ A 2 = c (L 1 ∪ L 2 ) Next, since L 1 , L 2 are distinct to each other, |L 1 ∪ L 2 | = 2q + 1 and hence A 1 , A 2 ≡ |A 1 ∩ A 2 | ≡ |P 2 (F q )| -|L 1 ∪ L 2 | ≡ q 2 -q ≡ 0 mod 2.
To prove (ii), consider an affine chart A and let L be the line such that A = c L. Let P ∈ L be a point and L 1 , . . . , L q be all the lines containing P but L. Then

A = L 1 + • • • + L q .
Indeed, every point Q ∈ A is in exactly one of the L i 's. Moreover, the L i 's all meet at P which is the only point in c A contained in the union of L i 's. Since the number of the L i 's is q and hence is even, then P L 1 + • • • + L q . This proves that every affine chart is a sum of lines.

Point (iii) is a direct consequence of Proposition 4.4(ii).

To prove (iv), denote by 1 the all-one vector (1, . . . , 1). Then for every affine chart A, there is a line L such that c A = L. In terms of vectors, we get A = L + 1. Then, let L, L be two lines of P 2 (F q ) and A, A be respectively the affine charts c L and c L , then

L + L = L + L + 1 + 1 = A + A .
Thus, L = A + A + L . So far, we have proved that every line L of P 2 (F q ) is a sum of L and an element of C planes (s). This proves that C lines (s) = C planes (s) + Span(L). But L, L ≡ |L| ≡ 1 mod 2, so L C ⊥ lines and it follows hence, from (iii), that L C planes (s). Finally, (v) is a direct consequence of (iv).

Remark 4.8. Actually, C planes (s) is nothing but the even subcode of C lines (s) i.e. the subcode of vectors of even weight. 4.1.3. Quantum CSS codes from the projective plane in characteristic 2. Definition 4.9. We define QFG(s) as the quantum code of length q 2 + q + 1 associated to C planes (s) ⊆ C lines (s).

After reduction, the corresponding chain complex is

C FG (s) := F 3 s 2 1 / / F 2 2s +2 s +1 2 / / / / F 2 2s +2 s -3 s 2 .
Indeed, Proposition 4.7(v) together with Proposition 4.6 assert that dim F 2 C planes (s) = 3 s .

Remark 4.10. The code QFG(1) is nothing but the 7, 1, 3 Steane code. This fact is actually well-known, since the Steane code is known to be constructed from the Hamming code and its dual while the Hamming code is already known to be the code C lines (1) spanned by the lines of P 2 (F 2 ).

Lemma 4.11. Let Ω be the set of lines of P 2 (F q ). We have

Ω ⊂ C lines (s) \ C planes (s) and Ω ⊂ C planes (s) ⊥ \ C lines (s) ⊥ .
Proof. The first inclusion is a direct consequence of Proposition 4.7(iv). From Proposition 4.4(ii) every line of P 2 (F q ) is in C planes (s) ⊥ . But a line L is not in C lines (s) ⊥ . Indeed, let L be a line distinct from L, then L, L ≡ |L ∩ L | ≡ 1 mod 2.

Lemma 4.12. |Ω| = q 2 + q + 1 and overlap(Ω) = q + 1.

Proof. It is a direct consequence of Proposition 4.1.

Proposition 4.13. For every s 1, the family of iterated tensor powers QFG(s) ⊗ has parameters

∼ K s √ 2 2s + 2 s + 1 + 2 2 √ 3 s 1 + 1 2 s -3 4 s , 1, 2 s + 1 2 s + 1 , (2 2s + 2 s + 1)
for some constant K s depending only on s and the family of iterated reduced tensor powers QFG(s) ⊗ r has parameters

∼ K s 2 2s + 2 s + 1 + 2 √ 3 s 1 + 1 2 s -3 4 s , 1, 2 s + 1 2 s + 1 , (2 2s + 2 s + 1)
for some constant K s depending only on s.

Proof. The minimum distance is a consequence of Lemma 4.12 and Corollary 2.9. The other parameters are obtained using Corollary 2.20 and Proposition B.1.

Proof. It follows from Proposition 4.19 that Ker(φ * 2r,r-1 ) = RM(2r, r). But, on the other hand, Im(φ 2r,r-1 ) = RM(2r, r -1); the homology of C RM (r) is hence generated by the images through φ 2r of the elements of Pol 2r which are of degree exactly r. Now, let us consider such a generator φ 2r (X I 0 ), with I 0 ⊂ {1, . . . , 2r} of cardinality r; and set I c 0 := {1, . . . , 2r} \ I 0 . For every I, J ⊂ {1, . . . , 2r}, φ 2r (X I ), φ 2r (X J ) =

(X i + ε i ) ∀i ∈ I c 0 , ε i ∈ F 2 .
The elements of Ω φ 2r (X I 0 ) have indeed disjoint support: the x-th coordinate of φ 2r i∈I c 0 (X i + ε i ) , where x = (x i ) i∈{1,...,2r} ∈ F 2r 2 , is 1 if and only if x i = 1 -ε i for every i ∈ I c 0 . On the other hand, φ 2r (X {1,...,r} ) is an element of weight 2 r which survives in homology.

By extracting the diagonal subfamily = r, it follows from Stirling series that we obtain an r-indexed family with parameters √ πr r , 2 r 2 , 4 r r .

The family is not, stricto sensu, logarithmically LDPC, but the weight grows slower than any positive power of the length, the dimension faster than any "< 1"-power of the length, and the minimum distance faster than any "< 1 2 "-power of the length.

It is directly checked that y + + y -= 1+2x

x , y +y -= with the convention that r = 0 whenever < 0 or r {0, . . . , }.

Lemma A.3. For every ∈ N and x 0, T (x) = P + (x) = P -(x).

Proof. For every ∈ N * and every x > 0, ( Finally, T 0 (x) = 1 = P + 0 (x) and T 1 (x) = 1 + 2x = x(y + + y -) = P + 1 (x), so T (x) = P + (x) for every ∈ N.

Corollary A.4. For every x 0, when tends to infinity,

T (x) ∼ 1 2 1 + 4x π x 1 + 4x .
Proof. Applying Proposition A.1 in [START_REF] Audoux | An application of Khovanov homology to quantum codes[END_REF] to Lemma A.3 (for ε = 1), we get

T (x) ∼ x y + 1 + 1 y + 2 +1 2 π y + = x 2 √ π √ y + + 1 √ y + 2 +1
But, since y -1 + = y -, √ y + + 1 The result follows by considering the -th power.

Corollary 2 .

 2 18 and Corollary 3.11. If C and D are two CSS codes described by matrices which have no columns of zeros, then 2 max(d C , d D ) d C⊗D , d C D .

  given with a basis B, then the bijection A ⊂ B → b∈A b ∈ C identifies the elements of C with the subsets of B. We shall use freely this identification, denoting subsets {a 1 , . . . , a s } ⊂ B, and the related elements of C, by concatenations a 1 a 2 • • • a s . 2 Associated to B, there is a natural dual basis B * := {b * | b ∈ B} for C * , where b * is defined by b * (b ) = δ bb for all b ∈ B. Here, δ stands for the Kronecker delta. Using the subset identification mentioned above, we shall denote by b ∈ x, where x ∈ C and b ∈ B, the fact that b * (x) 0, which means that b appears in the decomposition of x. In the same spirit, we denote by |x| the Hamming weight of x ∈ C, that is the number of b ∈ B such that b ∈ x. We shall also denote with brackets the usual bilinear form defined on C by b 1 , b 2 := δ b 1 b 2 for all b 1 , b 2 ∈ B. The following map:

  and define the length of C as n C := n 0 (C );• k i (C ) := dim H i (C ) and define the dimension of C as k C := k 0 (C ); • d i (C ) := min |x| [x] ∈ H i (C ) \ {0}and define the minimum distance of C as d C := d 0 (C ); • w i (C ) := max |x| x row of Mat B (∂ i ) and define the weight of C as w C := w 0 (C ). Remark 1.8. The above parameters have only a relative dependency with regard to the basis. Indeed, w C depends on the entire B, d C depends only on its restriction B |C 0 , n C and k C are independent of B.

  given with a basis B, and if D is obtained from C by removing all redundant rows of t Mat B (∂ -1 ) and/or Mat B (∂ 0 ) and by modifying C -1 and C 1 consequently, then D is reduced and it is mostly a consequence of Remark 1.8 that n D = n C , k D = k C , d D = d C and w D w C . From a linear algebraic point of view, it consists in replacing C -1 by a complement space for Ker(∂ -1 ) spanned by vectors of B, and replacing C 1 by its quotient under a complement space of Im(∂ 0 ) spanned by vectors of B.

  a minimally weighted representative of a non trivial class in H 0 (C ⊗ D). As a consequence of Künneth formula, and since either C or D is balanced, H 0 (C ⊗ D) H 0 (C ) ⊗ H 0 (D) and there exist g 1 , .

  Proposition 2.15. If C and D are two chain complexes such that C :C -1 1 ∂ -1 / / C 0 ∂ 0 / / / / C 1 is balancedand ∂ 0 is non zero on every element of the basis of C 0 , then d C ⊗D 2d D .

1 / / F a 2 /

 12 Corollary 2.21. Let C be the CSS code associated to C := F b 2 / / / F b 2 , where a, b ∈ N. If C and C * satisfy both the hypothesis of Lemma 2.7 for the same integers N, K ∈ N * , then for every ∈ N, C ⊗ r is a CSS code with parameters 2(a + b) + (a -2b) 3 ; (a -2b) ; N K ; a .

  Theorem 3.4. [TZ14] If C and D are two classical codes given, respectively, by a parity-check map p C and a generating map g D , then the CSS code C ⊗ D associated to C 0

⊗ b i so its weight is n 0 j=1

 0 |b i |, and this is precisely the part of |x 0 | which is bounded below in the proof of Lemma 2.7. Corollary 3.11. If C and D are CSS codes described by 2-nilpotent matrices which have no columns of zeros, then 2 max(d C , d D ) d C D .

1 / / F a 2 /

 2 In particular, ker(∂ C ) Im(∂ C ) H 0 (C ) whenever C is balanced.If C and D are two reduced complexes, then C ⊗ D ∂ C ∂ D / / C ⊗ D ∂ C ∂ D / / C ⊗ D decomposes into the direct sum ⊕ i∈Z C ⊗ D i ,where C ⊗ D i is the length three truncature of C ⊗ D centered in degree i. They all have null homology except for the summand i = 0 which actually corresponds to the central part of C ⊗ D. Moreover, any basis induced from bases of C and D respects this direct sum decomposition. It follows that k C D = k C ⊗D and d C D = d C ⊗D . Besides, it is easily checked that n C D = n C n D . Consequently, for C := F b 1 2 / / / F b 2 2 a reduced complex defining a CSS code C, the iterated powers C , C ⊗ and C ⊗ r have same dimensions and minimum distances but differents lengths, which are respectively (a + b 1 + b 2 ) , O (a+2 √ b 1 b 2 ) √ and O (a + √ b 1 b 2 ) .

Figure 1 .

 1 Figure 1. The projective plane P 2 (F 2 ).

x∈F 4 r 2 X 0 +

 20 I X J (x) = 1 if and only if I ∪ J = {1, . . . , 2r}. Using notation from Section 2.2, it follows then that Ker ⊥ 2r (X I 0 ) = φ 2r X I c RM(2r, r) ⊥ = φ 2r X I c 0 + Pol 2r,r-1 . Since QRM(r) is symmetric, it is now sufficient to apply Corollary 2.20 or 2.21 with Ω φ 2r (X I 0 ) := φ 2r i∈I c 0

  and y + y -= 1. It follows from the latter equality that P + (x) = P -(x) = x y + r=0 r 2 y 2r -. Moreover, it can be straightforwardly computed that:Lemma A.2. For every , r ∈ Z,• (2 + 1)

  1)T +1 (x) -(2 + 1)(1 + 2x)T (x) + (1 + 4x)T -1 (x) = 0.Indeed,(2 + 1)(1 + 2x)T (x) = (2 + 1) order to avoid heavy notation, the dependence on x shall be ommited so, using Lemma A.2,(2 + 1)(1 + 2x)T (x) -(1 + 4x)T -1 (x) = ( + 1) ( + 1)T +1 (x).But on the other hand,( + 1)P + +1 (x) -(2 + 1)(1 + 2x)P + (x) + (1 + 4x)P + -1 (x) = 0. Indeed, (2 + 1)(1 + 2x)P + (x) = (2 + 1)x(y + + y -)x y + 4x)P + -1 (x) = x 2 (y +y -) 2x -1 y -1 1)(1 + 2x)P + (x) -(1 + 4x)P + -1 (x) = ( + 1)x +1 y

√ y + 2 = 1 / / F a 2 / 1 / / F a 2 /

 21212 y + + 2 + y -= 1+4x x , and the result follows. Proposition A.5. Let a, b, b > 0. For every ∈ N, we denote by c the constant term in (bt -1 + a + b t) . Then, when tends to infinity, Following closely the arguments given in the proof of Proposition 4.1 in [Aud14], we begin by (bt -1 + a + b t) In this sum, only the terms with s = r contribute to the constant term. We obtain hence that c = a -2 Length of reduced tensor powers Using the same technique as in its proof, Corollary 2.21 can be generalized to the case b b : Proposition B.1. Let C be the CSS code associated to C := F b 2 / / / F b 2 , where a, b, b ∈ N. If C and C * satisfy both the hypothesis of Lemma 2.7 for the same integers N, K ∈ N * , then for every ∈ N, C ⊗ r is a CSS code with parameters n , (abb ) , d , w , where N abb + b 2 + b 2 + (b + b ) √ bb a + √ bb + b 2 + b 2 -(b + b ) √ bb a -√ bb 2 b 2 + bb + b 2 • This provides a family logarithmically LDPC with a minimum distance which grows at least as the log N-log K log(a+ √ bb )th power of the length. Proof. As for Corollary 2.21, only the statement on the length needs some attention. We define the sequences of integers (a ) ∈N * , (b ) ∈N * and (b ) ∈N * by C =: F b 2 / / / F b 2 . Developping C ⊗ C as in the proof of Corollary 2.21, we obtain 

  then C is the direct sum of a chain complex with a (useless) summand of the formSpan b i 1 / / / / Span(b i ) / / 0 ,where b i is the unique preimage of b i ; and this summand can be removed without altering the minimum distance. It follows that the lower bound of Corollary 2.14 is sharp if and only if it is equal to the upper bound. Corollary 2.18. If C and D are two CSS codes described by matrices which have no columns of zeros, then

	Corollary 2.14 and Proposition 2.15 have the following consequence for the (reduced) tensor product of
	CSS codes.

  Corollary 2.23. If C = (H X , H Z ) is a CSS code such that none of H X or H Z has a zero column, then the families C ⊗ ∈N and C ⊗ r

	sharpened into • • • N K	N K	N K • • • . It provides, in general, a slightly better constant.
	Proposition 2.15 together with either Corollary 2.20 or 2.21 imply that, by considering its tensor powers,
	any CSS code, even the poorest one (as soon as it is not defined with matrices containing columns of zeros),
	provides a logarithmically LDPC family with a minimum distance tending to infinity:

2.22. The value N K given as a lower bound for d in Corollaries 2.20 and 2.21 can actually be ∈N are logarithmically LDPC with d C ⊗ , d C ⊗r 2 for every ∈ N * .

  = F 2 1235, 2346, 3567, 124 and Im(∂ -1 ) = F 2 1235, 2346, 3567 . The homology is hence generated by 124.

	Bravyi and Hastings computed that d S ⊗2 7;1;3 = 7, and indeed, using Theorem 2.7 with
		Ω 124 := 124, 136, 157, 237, 256, 345, 467 ,
	we obtain that d S ⊗2 7;1;3	7 3 d S 7;1;3 = 7. This an example where Theorem 2.7 gives a sharp lower bound whereas
	K 1 and N K

note that the order of the a i 's in this notation is irrelevant

Noting that, since we are working over a field, any module is flat and hence Tor is zero.

Note that, since we are working over F 2 , Ker ⊥ j 0 is an affine subspace, but over any other field, it should be the union of affine subspaces ∪ λ∈K * λg * j 0 + Ker(∂ 0 ) ⊥ .

Recall from Definition 1.1 that a 2-nilpotent map is an endomorphism ∂ satisfying ∂ 2 = 0.

y -2r ε .

4.2. Quantum cyclic codes. The following example is based on classical cyclic codes. 4.2.1. Cyclic codes. Here we recall very classical facts about cyclic codes. For further details we refer the reader to [START_REF] Macwilliams | The theory of error-correcting codes[END_REF]Chapter 7].

A binary cyclic code C ⊆ F n 2 is a code which is stable under the action of the automorphism σ :

In what follows we identify F n 2 and F 2 [X] (X n -1) using the F 2 -linear isomorphism

and we define the weight of a polynomial as the number of its nonzero coefficents. Using this identification, the automorphism σ corresponds in F 2 [X] (X n -1) to the multiplication by

is defined as the code corresponding to the ideal generated by h. It is well-known that this code has dimension ndeg(h). The polynomial h is referred to as a generating polynomial of the code. It is unique up to multiplication by an invertible element of

The dual of a cyclic code is cyclic and its generating polynomial can be obtained as follows. Given a

and referred to as the reciprocal polynomial of f . Over F 2 , X n -1 is equal to its reciprocal polynomial so, if f | X n -1, then f | X n -1. Let h be the polynomial such that f h = X n -1, then

A construction of CSS codes.

The case n = 2 s is actually never considered in the study of classical cyclic codes since, in that case, the polynomial X n -1 is completely inseparable and all the constructions based on choosing divisors of X n -1 having a prescribed set of roots, such as BCH codes (see for instance [MS77, Chapter 9]), are not possible. But oddly enough, this is precisely the case which shall lead to interesting families of CSS codes defined by iterated tensor powers. In this situation X 2 s -1 = (X -1) 2 s and hence the divisors of X n -1 are of the form (X -1) r for all r ∈ {0, . . . , 2 s }. The corresponding cyclic codes are thus Cyc (X -1) r . Such a code has dimension nr and Cyc (X -1) r ⊥ = Cyc (X -1) n-r . Definition 4.14. For any r < n, we define QCC(n, r) as the CSS code of dimension 1 associated to the pair of codes Cyc (X -

, respectively, generating maps for Cyc (X -1) r and Cyc (X -1) r-1 ⊥ = Cyc (X -1) n-r+1 , then QCC(n, r) is also defined as the CSS code associated to

Lemma 4.15. Let r n be a non negative integer. Then, the weight of (X -1) r ∈ F 2 [X] equals 2 w 2 (r) , where w 2 (r) denotes the binary weight of r, i.e. the weight of its decomposition in base 2.

Proof. We prove it by induction on w 2 (r). If w 2 (r) = 1, then r = 2 a for some non negative integer a and (X -1) 2 a = X 2 a -1 has weight 2. For w 2 (r) > 1 then let a := log 2 (r) . Then r = 2 a + r where r < 2 a and w 2 (r ) = w 2 (r) -1. By induction, the weight of (X -1) r equals 2 w 2 (r ) . Hence (X -1) r = (X -1) 2 a (X -1) r = X 2 a (X -1) r + (X -1) r .

Since r < 2 a , the polynomials X 2 a (X -1) r and (X -1) r have no common monomials and hence, the weight of (X -1) r is twice that of (X -1) r . This concludes the proof. Proposition 4.16. For every ∈ N, the -th tensor power of QCC(n, r) has dimension 1 and minimum distance at least 2 (s-w) , where w = max w 2 (r -1), w 2 (nr) .

Proof. To prove the statement, we apply Corollary 2.9 with Ω := X i (X -1) r-1 mod (X -1) n i ∈ {0, . . . , n -1} Ω := X i (X -1) n-r mod (X -1) n i ∈ {0, . . . , n -1} .

Both sets have cardinality n = 2 s , and their respective overlaps are overlap(Ω) = w 2 (r -1) and overlap(Ω ) = w 2 (nr).

Indeed, stacking the elements of Ω, we obtain a circulant matrix whose column weight equals the row weight. But the latter is given by Lemma 4.15. This concludes the proof.

Corollary 4.17. For n = 2 s and r = 2

√ n, where s is an even integer, the family of iterated tensor powers QCC(n, r) ⊗ has parameters

for some constant K n depending only on n and the family of iterated reduced tensor powers QCC(n, r) ⊗ has parameters

for some constant K n depending only on n.

Proof. We have r -

The minimum distance is thus a consequence of Corollary 2.9 and the length a consequence of Corollary 2.20 and Proposition B.1. 4.3. Quantum Reed-Muller codes. In this section, we define a two-parameters family of CSS codes based on classical Reed-Muller codes. Such CSS codes have been studied in [START_REF] Zhang | Quantum reed-muller codes[END_REF]. Another construction of stabilizer codes (which are not CSS) based on Reed-Muller codes was also proposed by Steane in [START_REF]Quantum reed-muller codes[END_REF].

To this end, we define, for every r ∈ N * and s ∈ {0, . . . , r}:

• Pol r := F 2 [X 1 , . . . , X r ] (X 2 1 -X 1 , . . . , X 2 r -X r ) given with the basis X I := i∈I X i I ⊂ {1, . . . , r} ;

• Pol r,s the restriction of Pol r to elements of degree 7 at most s;

• φ r : Pol r → F 2 r 2 the map which sends a polynomial P to P(x) x∈F r 2 ; • φ r,s the restriction of φ r to Pol r,s . In this appendix, we prove the length part of Corollary 2.20. Using inductively Proposition 1.12, it is easily seen that the length of C ⊗ is equal to the constant term in the Laurent polynomial (bt -1 + a + b t) . The statement is hence a consequence of Proposition A.5 given below. But before proving it, we set some technical lemmata.


Scoping the risks associated with accelerated coastal permafrost thaw: lessons from Bykovsky (Sakha Republic, Russian Federation) and Tuktoyaktuk (Northwest Territories, Canada) 0. Highlights

I. Why is permafrost thaw a challenge?

Jean-Paul Vanderlinden (1), Paul Overduin (2), Donald L. Forbes (3), Vyacheslav Shadrin (4), and Natalia Doloisio (1) (jean-paul.vanderlinden@uvsq.fr)

(1) Laboratoire CEARC, Observatoire de Versailles Saint-Quentin, Université de Versailles Saint-Quentin-en-Yvelines, Guyancourt, France, ( 2 (i) cultural sites and community infrastructure, (ii) marine transportation and subsistence access to terrestrial and marine resources, (iii) food resource species and community food security, (iv) identity, and even (v) worldviews.

Permafrost thaw renders the coastline and associated communities more susceptible to these changes and releases nutrients and contaminants to coastal ecosystems.

1.b. Arctic communities are not homogeneous, they differ in their: (i) cultural, (ii) economic, and (iii) governance contexts.

III. Comparing Tuktoyaktuk and Bykovsky

Changes in landscape and weather

Loss of sense of place, reliability of traditional knowledge, changing ice conditions risk to hunters

• Indigenous culture is adaptable, but changing environment challenges customary practices and traditional knowledge, with negative impacts on the well-being of northern residents.

Ecosystem changes and food resources Loss of access to traditional resources

• These changes affect the subsistence economy, health (food security and quality), and cultural identity. Finding alternate sources of income is not necessarily a satisfactory solution.

Transport infrastructure destabilized

Shortened ice-road season; increased costs, need for capital investment

• Alternate infrastructure (permanent roads, bridges, harbour facilities) are expensive (e.g. newly opened Inuvik-Tuktoyaktuk Highway).

Contaminant release

Impaired safety of water and country food and related health risks.

• While this pertains directly to physical health, related concern and stress can have direct impacts on mental health and thus community well-being.

The Has seen major investment to address some key challenges (e.g., building of Inuvik-Tuktoyaktuk all-weather road); provides shallow-draft NWT harbour.

Has not seen significant development; potential development as access point for Lena River and nature reserve and proximity to regional center (Tiksi).

Growing potential for a relatively diversified economy. Current economic base is limited to whitefish fishery, sensitive to environmental changes.

Sees the institutional future as relatively predictable

Institutional future creating a level of perceived uncertainty.

III. b. Where do Tuktoyaktuk and Bykovsky differ? -> Mostly in their institutional contexts 50 km

Result

We need a risk model that takes into the account the breadth of the impacts of permafrost thaw, including the cultural dimension, as well as the economic and institutional contexts as a critical source of uncertainty and isolation as a fundamental challenge.

Model

  ) Alfred Wegener Institute Helmholtz Centre for Polar and Marine Research, Potsdam, Germany, (3) Geological Survey of Canada, Natural Resources Canada, Bedford Institute of Oceanography, Dartmouth, NS, Canada, (4) Institute of Humanities and Northern Indigenous Peoples, Siberian Branch of the Russian Academy of Sciences, Yakutsk, Sakha Republic, Russian Federation Permafrost thaw generates risks for Arctic communities that are broad and cross-cutting Current models of risk under climate change may not be able to address such categories of risk We propose an initial scoping of existing risk models using field observations. 1.a. Climate warming in the Arctic has severe and multidimensional local consequences: and poses a direct threat to:

•

  As permafrost thaw and erosion are widespread and variable, foundation suitability and longevity of relocation sites need careful consideration. Other amenities such as shore access are important. • Space is limited and retreat may entail more distant redevelopment (e.g new Tuktoyaktuk suburb) • Cemetery or other places of cultural significance may not be relocated Coastline erosion Abandonment/relocation of buildings and other infrastructure; erosion of island a concern for harbour maintenance.

  NUNATARYUK project has received funding from the European Union's Horizon 2020 research and innovation programme grant agreement No. 773421 III. a. What do Tuktoyaktuk and Bykovsky have in common? -> The mechanisms and impacts of permafrost thaw Tuktoyaktuk Bykovsky Its status has been stabilized under the Inuvialuit Final Agreement (IFA 1984) Economic uncertainty of Perestroika following collapse of the Soviet Union has changed demographic and economic base. Increasing northern autonomy, economic capacity, and research leadership under the auspices of the Inuvialuit Regional Corporation. Current rapid institutional changes both at the Sakha Republic level and at the federal level.

  et al. 2017) Takes into account cultural dimensions as a central feature, acknowledges the importance of local values. Core of argument on perceptions, need to clarify the role for facts. System centered resilience models (Wardekker et al. 2010, Vanderlinden et al. 2015) System thinking, consideration of institutions and governance. Centrality of the concept of events as singular occurrences IV. Assessing current risk models against the specifics of permafrost thaw?

Conclusion

Current models of risk are not yet attuned to the specific risks of permafrost thaw, more integration work is needed.