Table III

Bounds on dmin for additive [[n,k,d]] QECC

Extended version of Table III of R. Calderbank, E. Rains, P. Shor, and N. Sloane, based on the preprint version quant-ph/9608006
Thanks to Eric Rains for corrections and additions (in particular, the upper bounds for n=31,32).

n\k 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
3 2 1 1 1                                                      
4 2 2 2 1 1                                                    
5 3 h3 2 1 1 1                                                  
6 a4 3A 2 2 2 1 1                                                
7 3B s3 2 2 2 1 1 1                                              
8 b4 s3 s3 f3 2 2 2 1 1                                            
9 4 s3 s3 s3 2 2 2 1 1 1                                          
10 b4 4 4 s3 s3 2 2 2 2 1 1                                        
11 5 5 4 s3 s3 s3 2 2 2 1 1 1                                      
12 e6 5A 4 4 i4 s3 s3 2 2 2 2 1 1                                    
13 5B 5 4 4 4 3-4 s3 s3 2 2 2 1 1 1                                  
14 b6 5 g,c5 4-5 4 4 i4 s3 s3 2 2 2 2 1 1                                
15 c6 5 5 5 g4B 4 4 s3B s3 s3 2 2 2 1 1 1                              
16 b6 6 6 5 k5 4-5 4 li4 s3B s3 s3 2 2 2 2 1 1                            
17 7 7 6 5-6 5 4-5 4-5 4 4 j4 s3 v3 2 2 2 1 1 1                          
18 b8 7 6 5-6 5-6 5 g5 4 4 4 s3 s3 2B 2 2 2 2 1 1                        
19 7B 7 6 5-6 5-6 5-6 5 4-5 4C 4 3-4 s3 s3 2B 2 2 2 1 1 1                      
20 b8 7 6-7 6-7 z6 5-6 5-6 4-5 4-5 4 g4 3-4 s3 s3 2 2 2 2 2 1 1                    
21 c8 7 6-7 6-7 6-7 c6 5-6 c5-6A 4-5 4-5 4 s4 3-4 s3 s3 h3 2 2 2 1 1 1                  
22 b8 7-8 6-8 6-7 6-7 6-7 5-6 5-6 mg5-6 4-5 4-5 4 s4 3-4 s3B s3 2 2 2 2 2 1 1                
23 c8-9 7-9 7-8 6-8 6-7 6-7 5-7 5-6 5-6 4-6 4-5 4-5 c4 s4 3-4 s3 s3 2 2 2 2 1 1 1              
24 b8-10 8-9A 7-8 y7-8 6-8 6-7 6-7 5-7 z5-6 5-6 r5-6 4-5 4-5 4 s4 3-4 s3 s3 2 2 2 2 2 1 1            
25 c8-9B d9 7-8 7-8 7-8 7-8 6-7 5-7 5-7 5-6 5-6 4-6 4-5 4-5 4 g4 3-4 s3 s3 2 2 2 2 1 1 1          
26 8-10 9 8-9 8-9 8 7-8 6-8 6-8 r6-7 5-7 5-6 5-6 z5-6 4-5 4-5 4 s4 3-4 s3 s3 2 2 2 2 2 1 1        
27 9-10 9 9 9 8-9 7-8 6-8 6-8 6-8 z6-7 5-7 5-6 5-6 to5 4-5 4-5 4 s4 3-4 s3 s3 2 2 2 2 1 1 1      
28 10 10 10 9 8-9 7-9 6-8 6-8 u6-8 6-8 z6-7 5-7 5-6 5-6 g5-6 4-5 4 4 s4 3-4 s3 s3 2 2 2 2 2 1 1    
29 11 11 10 9-10 8-9 7-9 7-9 6-8 6-8 6-8 6-7 5-7 5-6 5-6 5-6 4-5 4-5 4 4 s4 3-4 s3 s3 2 2 2 2 1 1 1  
30 b12 11A 10 9-10 8-10 y8-9 7-9 7-9 y7-8 6-8 6-8 y6-7 z6-7 5-6 5-6 5-6 z5 4-5 4 4 g4 3-4 s3 s3 2 2 2 2 2 1 1
31 y10-12 11 10 9-10 8-10 8-10 7-9 7-9 7-9 6-8 6-8 6-8 6-7 5-7 5-6 5-6 y5-6 4-5 4-5 4 4 4 3-4 s3 s3 2 2 2 2 1 1
32 10-12 11 10-11 9-11 8-10 8-10 z8-10 7-10 7-9 t7-9 7-8 6-8 n6-8 6-7 6-7 t6 5-6 4-6 4-5 4-5 4 4 s4 3-4 s3 s3 2 2 2 2 2
33 10-12 11 10-11 9-11 8-11 8-10 8-10 7-10 7-10 7-9 7-9 6-8 6-8 6-8 6-7 6-7 5-6 5-6 4-6 4-5 4-5 4 4 s4 3-4 s3 s3 2 2 2 2
34 10-12 11-12 10-12 9-11 8-11 8-11 8-10 8-10 8-10 7-10 7-9 6-9 6-8 6-8 6-8 6-7 6-7 5-6 5-6 4-6 4-5 4-5 4 4 z4 3-4 s3 s3 2 2 2
35 11-13 11-13 10-12 9-12 9-11 8-11 8-11 8-10 8-10 7-10 7-10 7-9 7-9 7-8 6-8 6-8 6-7 5-7 5-6 5-6 5-6 4-5 4-5 4 4 4 3-4 s3 3 2 2
36 12-14 11-13 10-12 y10-12 9-12 8-11 8-11 8-11 8-11 8-10 8-10 8-10 mg8-9 7-9 6-8 6-8 6-8 5-7 5-7 5-6 5-6 4-6 4-5 4-5 4 4 3-4 3-4 s3 2-3 2
n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Notes on Table III

(Mainly those of [CRSS98], plus some updates, especially on cylic codesy)

When the exact value of d is not known, the lower and upper bounds are separated by a dash.

All unmarked upper bounds in the table come from the linear programming bound of Theorem 21. (A few of these bounds can also be obtained from Eq. (14) or from Theorem 16.) Unmarked lower bounds are from Theorem 6.

Theorem 6
Suppose an [[n,k,d]] code exists.
(a) If k>0 then an [[n+1,k,d]] code exists.
(b) If the code is pure and n > 1 then an [[n-1, k+1,d-1]] code exists.
(c) If k>1 or if k=1 and the code is pure, then an [[n,k-1,d]] code exists.
(d) If n>1 then an [[n-1,k,d-1 ]] code exists.
(e) If n>1 and the associated code C contains a vector of weight 1 then an [[n-1,k,d]] code exists.
Note in particular that, except in the k=0 column, once a particular value of d has been achieved, the same value holds for all lower entries in the same column using Theorem 6(a).
A A code meeting this upper bound must be impure (this follows from integer programming by an argument similar to that used in Section 7 to show that no [[13,0,6]] code exists).
B A special upper bound given in Section 7. These bounds do not apply to nonadditive codes, for which the upper bound must be increased by 1.
C This is the unique other entry in the table (besides those marked B) where the known upper bound for nonadditive codes is different from the bound for additive codes: if we omit (21) (which says that the code is either odd or even) from the linear program, the bound increases by 1. In all other entries in the table, condition (21) is superfluous. However, we will be surprised if a ((19,28,5)) nonadditive code exists.

a The hexacode, a (6,26,4) classical code that can be taken to be the GF(4) span of <001111, 0101ww2, 1001w2w> (see Chapter 3 of [CoSl93]). Aut(h6)=3.S6, of order 2160.
b A classical self-dual code over GF(4) - see [MOSW78], [CPS79].
c A cyclic code, see Table I;
Cylic additive codes [[14,2,5]], [[21,7,5]] (see here)
d A [[25,1,9]] code obtained by concatenating the [[5,1,3]] Hamming code with itself (Fig. 1 of Section 4).
e The dodecacode defined in Section 6.
f An [[8,3,3]] code, discovered independently in [CRSS97], [Got96], and [Ste96]. The (8,25) additive code may be generated by vectors ((01www21w2))0, 11111111, wwwwwwww (where the double parentheses mean that all cyclic shifts of the enclosed string are to be used). Exhaustive search shows that this code is unique. Another version is obtained from Theorem 10. The automorphism group has order 168, and is the semidirect product of a cyclic group of order 3 and the general affine group AGL(1,8)={ x \to ax+b : a,b,x \in GF(8), a \neq 0 }.
g A quasicyclic code found by T. A. Gulliver - see Table II of Section 5.
h A Hamming code, see Section 5.
i Use the (12,28) and (14,28) linear codes with generator matrices
0 0 0 0 0 0 1 1 1 1 1 1
0 0 1 1 1 1 0 0 1 1 w w
0 1 0 1 w w2 0 1 0 w 1 w
1 0 0 1 w2 w 0 1 w 0 w 1

and
0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 1 1 1 1 0 0 0 0 1 1 1 1
0 1 0 1 w w2 0 1 w w2 0 1 w w2
1 0 0 1 w2 w 0 1 w2 w 1 0 w w2
respectively. Their automorphism groups have orders 720 and 8064, and both act transitively on the coordinates. The first of these can be obtained from the u|u+v construction (c.f. Theorem 12) applied to the unique [[6,4,2]] and [[6,0,4]] codes.
j A [[17,9,4]] code, for which the corresponding (17,28,12) code C is a well-known linear code, a two-weight code of class TF3 [CaKa86]. The columns of the generator matrix of C represent the 17 points of an ovoid in PG(3,4). Both C and C^\perp are cyclic, a generator for C^\perp being 1w1w1000000000000. The weight distribution of C is A0=1, A12=204, A16=51, and its automorphism group has order 48 960.
k The [[16,4,5]] extended cyclic code spanned by ((w^2w^20w1w1111001111))0, together with vectors of all 1's and all w's .
n A [[32,12,6]] code obtained from an extended BCH code over GF(16).
r From classical linear codes [40,7,24] and [45,10,18] via Rains' puncture code.
s By shortening one of the following codes using Theorem 7 or its additive analogue: the [[21,15,3]] or [[85,77,3]] Hamming codes (see Section 5), the [[32,25,3]] Gottesman code (Theorem 10), the [[40,30,4]] code given in Table II or [[40,33,3]] code shown in Fig. 2.
Additionally, there is a linear quantum code [[41,31,4]] found by Vladimir Tonchev that can be shortened to codes of length n=10, 12, 14, 15, 16, 17, 18, 19, 20,21, 22, 23, 24, 25, 26, 27, 29, 31, 33, 35, 41.
t A quantum twisted code (see J. Bierbrauer and Y. Edel)
u From the u|u+v construction (see Theorem 12).
v The following (17,26) code with trivial automorphism group found by random search:
0010ww2ww211ww20011w2
00w10w0w2w2w211ww2w211
01001w1ww2w2w20w21w0w2
0w0ww0w21w21ww2w1ww1
100ww2001www21w2w0w21
w001w2w2w20w20w21011ww2
y Cyclic codes [[24,3,7]], [[31,0,10]], [[30,5,8]],[[30,6,7]], [[30,8,7]], [[30,11,6]], [[31,16,5]], and [[36,3,10]]
z Quasi-cyclic codes [[20,4,6]], [[24,8,5]], [[27,9,6]], [[28,10,6]], [[30,7,16]], [[30,12,6]], [[32,6,8]], and [[34,24,4]] by M. Grassl and Zlatko Varbanov, Faculty of Mathematics and Informatics, Veliko Tarnovo University, Bulgaria
li A code [[16,7,4]] found by Li Yu, Carnegie-Mellon University, 2007-03-13.
to A code [[27,13,15]] found by Vladimir D. Tonchev, Quantum codes from caps, Discrete Mathematics (2008), doi: 10.1016/j.disc.2007.12.007
mg From a cyclic linear code [43,36,5] over GF(4) which does not contain its Hermitian dual using the puncture code of Eric Rains, or from a linear code [36,24,8] over GF(4).

Copyright © Markus Grassl (grassl@ira.uka.de) 04.10.2008