New Quantum Codes from CSS Codes

. We present a new propagation rule for CSS codes. Starting with a CSS code [[ n, k, d ]] q , we construct a CSS code with parameters [[ n − 2 , k, d − 1]] q . In general, one would only obtain a code with parameters [[ n − 2 , k, d − 2]] q . The construction applies to asymmetric quantum codes from the CSS construction as well.


Introduction
Quantum error-correcting codes are an essential ingredient for the realization of universal fault-tolerant quantum computers. It turns out that, compared to general stablizer codes, the class of so-called CSS codes [1,2] allows more simple, direct implementations of a larger class of fault-tolerant operations. For example, any CSS code allows the transversal implementation of the CNOT gate [3].
While the error-correcting capabilities of CSS codes are in general less than those of the larger class of stabilizer codes [4], there are also a couple of advantages in terms of error-correction. The complexity of error correction is exponential in the number of independent syndromes [5]. For CSS codes, the syndromes can be grouped into syndromes for X-and Z-errors, and error correction can be performed independently for the two types of errors. This yields a square-root speedup. Likewise, in order to determine the minimum distance of a CSS code, one has to compute that of two codes over an alphabet of size q, while for stabilizer codes, the alphabet size is q 2 . There is again a square-root advantage.
After a short summary of the required basic notions of both classical and quantum codes in the next section, we present our main results in Section 3. Then we apply the new construction to CSS codes [[n, 0, d]] 2 for qubits, yielding explicit constructions of codes with the best parameters known to date.

Background
In this section, we recall basic definitions and properties of both classical and quantum error-correcting codes. For more details, see, e.g., the book [6] for classical codes and the articles [7,8] for quantum codes.

Classical codes
Let q = p m be a prime power. Then there is a finite field F q with q elements. By C = [n, k, d] q we denote a linear block code of length n, dimension k, and minimum distance (at least) d. The minimum (Hamming) distance is the minimum number of positions in which two codewords of C differ. For linear codes, the minimum distance equals the minimum (Hamming) weight of the code, i.e., the minimum number of positions at which a non-zero codeword of C is non-zero.
The (Euclidean) dual code C ⊥ = [n, n − k, d ⊥ ] q is defined as For 1 ≤ i ≤ n, the shortened code σ i (C) is obtained by selecting all codewords c ∈ C that are zero at the i-th position, and then deleting that position, i.e., Similarly, the punctured code π i (C) is obtained by deleting the i-th coordinated of C, i.e., When we omit the index i, σ(C) and π(C) refer to the shortened/punctured code with respect to the last position i = n.
The following proposition summarizes properties of the shortened and punctured code.
Proposition 1 For a linear code C = [n, k, d] q with d > 1 and coordinate i not being identically zero, the shortened and punctured code have parameters and Moreover, shortening the dual code equals the dual of the punctured code and vice versa: and When coordinate i of the code C is identically zero, the dimension of the shortened code remains k. Likewise, for d = 1, when puncturing the code at the position i where a codeword of weight 1 is non-zero, the dimension drops to k − 1. Moreover, in some cases the minimum distance of the shortened or punctured code might be larger. Later, we will use so-called quadratic residue (QR) codes. Their properties are summarized as follows (see, e.g., [6,Chapter 16] for prime fields and [9, Section 2.7] for the general case).
Proposition 2 (QR codes) Let q be a prime power and n > 2 a prime such that q is a quadratic residue modulo n (i.e., q = a 2 mod n for some a). The quadratic residue codes Q, Q, N , and N are cyclic codes over F q with the following properties: The extended QR codes Q and N are obtained adding one coordinate to Q and N , respectively, such that Q ⊥ = N for n ≡ 1 mod 4, while Q ⊥ = Q and N ⊥ = N for n ≡ 3 mod 4. The extended QR codes have the following properties: (vi) Q = [n + 1, (n + 1)/2, d + 1] q and N = [n + 1, (n + 1)/2, d + 1] q (vii) The automorphism group of the extended QR code Q contains the projective special linear group P SL 2 (n).

Quantum codes
By C = [[n, k, d]] q we denote a quantum-error correcting code (QECC) that is a subspace of dimension q k of the complex vector space H = (C q ) ⊗n ∼ = C q n . When the minimum distance is d, all errors acting on at most d − 1 of the n subsystems (tensor components) can be detected or act trivially on the code. Alternatively, one can correct up to d − 1 erasures or up to (d − 1)/2 errors. Most of the QECCs in the literature are so-called stabilizer codes which can be constructed from certain additive codes over the field F q 2 [7]. Here we focus on so-called CSS codes, named after Calderbank & Shor [1] and Steane [2]. and As CSS codes are a subclass of stabilizer codes, their parameters need not be optimal. On the other hand, CSS codes allow to correct X-and Z-errors independently. Steane [2] uses the notation {n, k, d 1 , d 2 } in order to stress that for d 1 > d 2 , the code can correct more, say, Z-errors than X-errors. Such codes are known as asymmetric quantum codes [10], and the notation [[n, k, d 1 /d 2 ]] q is used in the literature [11]. To avoid possible confusion, we will use the notation [[n, k, {d 1 , d 2 }]] q , which indicates both minimum distances and also stresses that the role of the codes C 1 and C 2 in the CSS construction can be swapped.

Main results
For a quantum code C = [[n, k, d]] q that is not the tensor product of quantum codes of lengths n − 1 and 1, deleting any coordinate results in a code C = [[n − 1, k, d − 1]] q (see [12,Theorem 6]). If the code is C = [[n, k, d]] q a tensor product C = C n−1 ⊗ C 1 of codes of lengths n − 1 and 1, respectively, then deleting the last coordinate yields the code C n−1 which has parameters In the latter case, the original code has distance d = 1.
In the following, we show that for CSS codes, we can reduce the length by 2 while the minimum distance is decreased only by 1.
Proof: Let C 1 = [n, k 1 , d 1 ] q and C 2 = [n, k 2 , d 2 ] q be the classical codes used for the construction of the CSS code C = [[n, k, {d 1 , d 2 }]] q . Then C ⊥ 2 ≤ C 1 and k = k 1 + k 2 − n. For a fixed position i ∈ {1, . . . , n}, consider the codes π i (C 1 ) and σ i (C 2 ) of length n − 1. By Proposition 1, (σ i (C 2 )) ⊥ = π i (C ⊥ 2 ), and hence (σ i (C 2 )) ⊥ ≤ π i (C 1 ). Using the codes σ i (C 2 ) and π i (C 1 ) in the CSS construction, we obtain a code It remains to show that the code has the claimed parameters. Concerning the dimension k, we distinguish two cases.
(i) When the coordinate i in the code C 2 is identically zero, then the shortened code has parameters σ i (C 2 ) = [n − 1, k 2 , d 2 ] q . Moreover, the dual code C ⊥ 2 ≤ C 1 contains a word of weight one that is non-zero at position i. Then the punctured code has parameters π i (C 1 ) = [n − 1, k 1 − 1, d 1 ] q . The dimension of the CSS code is k = (k 1 − 1) + k 2 − (n − 1) = k 1 + k 2 − n = k.
(ii) When the coordinate i in the code C 2 is not identically zero, the shortened code has parameters σ i (C 2 ) = [n − 1, k 2 − 1, d 2 ] q . Moreover, the dual code C ⊥ 2 ≤ C 1 does not contain a word that is non-zero only at position i. As d 1 > 1, C 1 does not contain such a word either. Then the punctured code has parameters Concerning the minimum distances d 1 and d 1 , first consider the case k = 0. In this case, the parameters of the CSS codes equal those of the classical codes, and hence d 1 = d 1 −1 and d 2 = d 2 as claimed. For k > 0, we distinguish two cases. To simplify notation, we set i = n.
Proof: Using Theorem 4, we obtain a CSS code Switching the roles of C 1 and C 2 in the CSS construction, again using Theorem 4 we obtain a CSS
Proposition 7 (quantum QR codes) Let q be a prime power and n > 2 a prime such that q is a quadratic residue modulo n. Then there are CSS codes with parameters and where d is the minimum distance of the classical QR code Q = [n, (n + 1)/2, d] q .

Proof (sketch):
For the code C QR = [[n, 1, d]] q , in the case n ≡ 3 mod 4, we use C 1 = C 2 = Q. By Proposition 2 (i) and (iv), C ⊥ 2 = Q ⊥ = Q < Q = C 1 . When n ≡ 1 mod 4, we use C 1 = Q and C 2 = N . By Proposition 2 (i) and (v), For the code C QR = [[n + 1, 0, d + 1]] q , we use C 1 = C ⊥ 2 = Q. Then C ⊥ 1 = C 2 equals either Q for n ≡ 3 mod 4, or N for n ≡ 3 mod 1. Both Q and N have parameters [n + 1, (n + 1)/2, d + 1] q . Applying Theorem 5 repeatedly to quantum QR codes C QR , we obtain CSS codes with the parameters shown in Table 1. The parameters of the codes in the first column of the table can also be found in [13], together with references for particular codes. All codes in Table 1 have the largest minimum distance among the explicitly known stabilizer codes (see [14]).  2 , the true minimum distance is larger than what is guaranteed by Theorem 5. This is related to the fact that when puncturing a classical code at m positions, the minimum distance will be larger than d − m in case every codeword of minimum weight has at least one zero at the m positions [15]. For the code [[202, 0, 24 * ]] 2 , by Theorem 5, the minimum distance is at least 21. Using Magma V2.27-3 [16], we have verified that the minimum distance is 24. The calculation took about one day using 48 cores. When we apply Theorem 5 repeatedly, then the minimum distance of the codes in the sequence is monotonically decreasing. This implies that the codes of length 206 and 204 have minimum distance at least 24 as well, while the lower bounds are 23 and 22, respectively.
In general, to compute the minimum distance of a CSS code C = [[n, 0, {d 1 , d 2 }]] q derived from classical codes C 1 = [n, k, d 1 ] q and C 2 = [n, n − k, d 2 ] q with C ⊥ 2 = C 1 , one would have to compute the minimum distance of both C 1 and C 2 . By Proposition 2 (vii), the automorphism group of an extended QR code Q = [n + 1, (n + 1)/2, d + 1] q contains the group P SL 2 (n). In turn P SL 2 (n) contains an involution τ with zero (n ≡ 3 mod 4) or two (n ≡ 1 mod 4) fixed points. We can select the positions I s for shortening and the positions I p for puncturing such that I τ s = I p . In this case, the shortened and punctured codes C 1 and C 2 will be permutation equivalent, i.e., they have the same parameters. Hence we have to compute the minimum distance of only one of the codes.
The true minimum distance of the code [[208, 0, 24]] 2 might be 25, but we have not yet computationally verified this.
The minimum distance of the codes in Tables 1 and 2 is the largest among the codes that have been explictly constructed [14]. At the same time, for n > 100, the Gilbert-Varshamov bound in [17, Corollary 2.3, 1)] implies the existence of quantum codes [[n, 0, d]] q for even n with larger minimum distance. However, for length n > 100 it is essentially infeasible to determine the minimum distance of a random quantum code.

Conclusions
We have presented a propagation rule for the parameters of CSS codes that results in better parameters than the corresponding construction for general quantum errorcorrecting codes. In the case of qubit codes [[n, 0, d]] 2 , this allows us to explicitly construct CSS codes with the largest minimum distance among the known codes. As already pointed out at the end of the last section, counting arguments imply the existence of codes with even larger minimum distance, but these have yet to be constructed.
The new construction can also be applied to asymmetric codes obtained via the CSS construction [18]. We leave it to future research to determine the resulting parameters.