Linear Programming Bounds for Entanglement-Assisted Quantum Error-Correcting
Codes by Split Weight Enumerators
Ching-Yi Lai and Alexei Ashikhmin

arXiv:1602.00413v3 [cs.IT] 17 May 2017

Abstract
Linear programming approaches have been applied to derive upper bounds on the size of classical and quantum codes. In
this paper, we derive similar results for general quantum codes with entanglement assistance by considering a type of split weight
enumerator. After deriving the MacWilliams identities for these enumerators, we are able to prove algebraic linear programming
bounds, such as the Singleton bound, the Hamming bound, and the first linear programming bound. Our Singleton bound and
Hamming bound are more general than the previous bounds for entanglement-assisted quantum stabilizer codes. In addition, we
show that the first linear programming bound improves the Hamming bound when the relative distance is sufficiently large.
On the other hand, we obtain additional constraints on the size of Pauli subgroups for quantum codes, which allow us to improve
the linear programming bounds on the minimum distance of quantum codes of small length. In particular, we show that there
is no [[27, 15, 5]] or [[28, 14, 6]] stabilizer code. We also discuss the existence of some entanglement-assisted quantum stabilizer
codes with maximal entanglement. As a result, the upper and lower bounds on the minimum distance of maximal-entanglement
quantum stabilizer codes with length up to 20 are significantly improved.

I. I NTRODUCTION
The theory of quantum error-correcting codes has been developed over two decades for the purpose of protecting quantum
information from noise in computation or communication [1], [2], [3], [4], [5], [6], [7], [8], [9], [10]. Classical coding techniques,
such as code constructions, encoding and decoding procedures, have been generalized to the quantum case in the literature [11],
[12]. An important question in coding theory is to determine how much redundancy is needed so that a certain amount of errors
can be tolerated [13]. The error-correcting capability of a code is usually quantified by the notion of its minimum distance,
which can be determined by the weight enumerator of the code. Delsarte applied the duality theorem of linear programming to
find universal upper bounds on the size of classical codes [14]. A key step is to use the MacWilliams identities that relate the
weight enumerators of a code and its dual code [13]. These linear programming bounds have been generalized to the quantum
case by Ashikhmin and Litsyn [15], based on the existence of quantum MacWilliams identities [16], [17]. We would like to
extend these results to the case of quantum codes with entanglement assistance.
Entanglement-assisted (EA) quantum stabilizer codes are a coding scheme with an additional resource—entanglement—
shared between the sender and receiver [18]. These codes have some advantages over standard stabilizer codes [19], [20], [21],
[22]. In the scheme of an EA stabilizer code, it is assumed that the receiver’s qubits are error-free, which makes the analysis
of error correction slightly more complicated. Previously, Lai, Brun, and Wilde discussed the MacWilliams identities for the
case of EA stabilizer codes [23], [24], which naturally follow from the MacWilliams identities for orthogonal groups [13]. Two
dualities (see Eqs. (43) and (44) below) are used to find linear programming bounds on the minimum distance of small EA
stabilizer codes. However, only one duality (see Eq. (4) below) appears in standard stabilizer codes, and thus we cannot directly
apply the method in [15] to obtain algebraic linear programming bounds for EA stabilizer codes. In addition, examples of
nonadditive EA quantum codes have recently been found in [25], which apparently do not fit the EA stabilizer formalism [18].
Consequently, previous upper bounds for EA stabilizer codes, such as the Singleton bound and Hamming bound, do not work
for nonadditive EA quantum codes.
In this paper, we will first define general EA quantum codes and discuss their error correction conditions. Two split weight
enumerators of an EA quantum code are defined accordingly and they are proved to obey a MacWilliams identity, similarly
to nonadditive quantum codes [16], [17]. These weight enumerators bear sufficient information about the error correction
conditions of the EA code (see Theorem 2). Recently the notion of data-and-syndrome correction codes is introduced [26],
and algebraic linear programming bounds for these codes are derived from a type of weight enumerators over the product
space of F4 and Z2 . We use similar techniques to derive algebraic linear programming bounds on the size of EA quantum
codes of given length, minimum distance, and entanglement, and obtain the Singleton bound, the Hamming bound, and the
first linear programming (LP-1) bound for unrestricted (degenerate or nondegenerate, additive or nonadditive) EA quantum
codes. In addition, we show that the LP-1 bound improves the Hamming bound when the ratio of code distance to code length
(relative distance) is sufficiently large. Also the previous Singleton bound for EA stabilizer codes in [18] does not work for
large minimum distance (i.e., d > n+2
2 ; see definitions below). Recently examples of EA stabilizer codes that violate the
Singleton bound have been constructed [42]. We will provide a refined Singleton bound for the general case.
A part of this work was presented at the IEEE International Symposium on Information Theory 2017.
CYL is with the Institute of Information Science, Academia Sinica, No 128, Academia Road, Section 2 Nankang, Taipei 11529, Taiwan. (email:
cylai0616@iis.sinica.edu.tw)
AA is with the Bell Laboratories, Nokia, 600 Mountain Ave, Murray Hill, NJ 07974. (email: alexei.ashikhmin@nokia-bell-labs.com)

2

In the case of EA stabilizer codes, the MacWilliams identities for split weight enumerators provide more constraints in
the linear program of an EA stabilizer code than those in [23], and thus the resulting upper bound on the minimum distance
could be potentially tighter for EA stabilizer codes of small length. Other than that, we also find additional constraints on the
weight distributions of EA stabilizer codes. Rains introduced the notion of shadow enumerator for additive quantum codes. In
the case of a quantum stabilizer code, a type of MacWilliams identity between the weight enumerators of a stabilizer group
and its shadow (see Eq. (48)) provides additional constraints on the weight distribution of its stabilizer group and hence the
linear programming bound can be improved [27]. However, this method cannot be applied to non-Abelian groups, such as the
normalizer group of a stabilizer code or the simplified stabilizer group of an EA stabilizer code. We will derive additional
constraints on the weight enumerators of non-Abelian Pauli groups and improve the linear programming bounds on the minimum
distance of small EA stabilizer codes. In particular, this helps to exclude the existence of [[27, 15, 5]] and [[28, 14, 6]] quantum
codes. As for EA stabilizer codes, the improved linear programming bounds rule out the existence of several EA stabilizer
codes. We also prove the nonexistence of certain codes and construct several EA stabilizer codes with previously unknown
parameters. To sum up, the table of upper and lower bounds on the minimum distance of maximal entanglement EA stabilizer
codes of length up to 20 given in [24] (with lower bounds improved in [28]) is greatly improved in Table II.
This paper is organized as follows. Preliminaries are given in the next section. In Sec. III we discuss general EA quantum
codes and their properties, including two split weight enumerators and their MacWilliams identities. In particular, we prove a
Gilbert-Varshamov type lower bound for the case of EA stabilizer codes. Then we derive algebraic linear programming bounds
in Sec. IV, including the Singleton-type, Hamming-type, and the first-linear-programming-type bounds. We will compare the
Hamming bound and the first linear programming bound in Subsec. IV-C. The linear programming bounds for small EA
stabilizer codes are discussed in Sec. V, including the additional constraints, and nonexistence and existence of certain EA
stabilizer codes. Then the discussion section follows.
II. P RELIMINARIES
In this section we give notation and briefly introduce Pauli operators, quantum error-correcting codes, the MacWilliams
identities for orthogonal groups, and properties of the Krawtchouk polynomials.
A. Pauli Operators
A single-qubit state space is a two-dimensional complex Hilbert space C2 , and a multiple-qubit state space is simply the
tensor product space of single-qubit spaces. The Pauli matrices






1 0
0 1
1 0
I2 =
,X =
,Z =
, Y = iXZ
0 1
1 0
0 −1
form a basis of the linear operators on a single-qubit state space. Let
G n = {M1 ⊗ M2 ⊗ · · · ⊗ Mn : Mj ∈ {I2 , X, Y, Z}},
n

which is a basis of the linear operators on the n-qubit state space C2 . Let
Gn = {ie g : g ∈ G n , e ∈ {0, 1, 2, 3}}
be the n-fold Pauli group. The weight of g = ie M1 ⊗ M2 ⊗ · · · ⊗ Mn ∈ Gn is the number of Mj ’s that are nonidentity matrices
and is denoted by wt (g). Note that all elements in Ḡn have only eigenvalues ±1 and they either commute or anticommute
with each other.
Since the overall phase of a quantum state is not important, it suffices to consider error operators in G n . For a subgroup
V ⊂ Gn , we define
V = {g ∈ G n : ie g ∈ V for e ∈ {0, 1, 2, 3}}.

(1)

That is, V is the collection of the elements in V with coefficient +1 instead. Sometimes it is convenient to consider the quantum
coding problem in terms of binary strings [6]. For two binary n-tuples u, v ∈ Zn2 , define
Z uX v =

n
O

Z [u]j X [v]j ,

j=1

where [u]j denotes the j-th entry of u. Thus any element g ∈ Gn can be expressed as g = ie Z u X v for some e ∈ {0, 1, 2, 3}
and u, v ∈ Zn2 . For example, we may denote X ⊗ Y ⊗ Z by Z 011 X 110 up to some phase. Let I denote the identity operator
of appropriate dimensions. We may also use the notation Xj to denote the operator I2 ⊗ · · · ⊗ I2 ⊗ X ⊗ I2 ⊗ · · · ⊗ I2 (of
appropriate dimensions) with an X on the j-th qubit and identities on the others, and similarly for Zj and Yj . We define a
homomorphism τ : Gn → Z2n
2 by
ie Z u X v 7→ (u, v).

(2)

3

Define an inner product in Gn by
hg, hiGn =

n
X
([u1 ]i [v2 ]i + [v1 ]i [u2 ]i ),
i=1

e

u1

v1

e0

u2

where g = i Z X , h = i Z X
hg, hiGn = 1, otherwise.

v2

∈ Gn and the addition is considered in Z2 . Then hg, hiGn = 0 if they commute, and

B. Quantum Error-Correcting Codes
n

An ((n, M, d)) quantum code Q of length n and size M is an M -dimensional subspace of the n-qubit state space C2 ,
such that any error E ∈ G n of wt (E) ≤ d − 1 is detectable. The parameter d is called the minimum distance of Q. From the
error correction conditions [29], [3], E is detectable if and only if hv|E|wi = 0 for orthogonal codewords |vi, |wi ∈ Q.
Suppose S = hg1 , . . . , gn−k i is an Abelian subgroup of Gn , where gj are independent generators of S, such that the minus
identity −I ∈
/ S. Then S defines a quantum stabilizer code
n

C(S) = {|ψi ∈ C2 : g|ψi = |ψi, ∀g ∈ S}
of dimension 2k . The vectors |ψi ∈ C(S) are called the codewords of C(S) and the operators g ∈ S are called the stabilizers
of C(S). Quantum stabilizer codes are analogues of classical additive codes. As opposed to stabilizer codes, others are called
nonadditive quantum codes [30], [31], [32], [33], [34], [35], [12].
Suppose an error E ∈ G n occurs on a codeword |ψi ∈ C(S). If E anticommutes with some gj ’s, it can be detected by
measuring the eigenvalues of gj ’s without disturbing the state of E|ψi. Let
S ⊥ = {h ∈ Gn : hh, giGn = 0, ∀g ∈ S},

(3)

which is the normalizer group of S in Gn . It is clear that for E ∈ S ⊥ , E cannot be detected. Thus the minimum distance d
of C(S) is defined as the minimum weight of any element in
S ⊥ \ S,

(4)

since errors in S are not harmful. Then C(S) is called an [[n, k, d]] quantum stabilizer code. If there exists g ∈ S with
wt (g) < d, C(S) is called degenerate; otherwise, it is nondegenerate.
The weight enumerator of a group S is
n
X
WS (x, y) =
Bw xn−w y w ,
w=0

where Bw is the number of elements of weight w in S. We may simply say that {Bw } is the weight distribution of S. The
weight enumerators of an additive group V and its orthogonal group V ⊥ are related by the MacWilliams identities [13], [36]:
WV ⊥ (x, y) =

1
WV (x + 3y, x − y),
|V|

(5)

Thus we have the MacWilliams identities for stabilizer codes.1 Note that the MacWilliams identities for nonadditive quantum
codes also exist [16], [17]. As a consequence, linear programming techniques can be applied to find upper bounds on the
minimum distance of small quantum stabilizer codes [7], [23] or to derive Delsarte’s algebraic upper bounds on the dimension
of general quantum codes [15].
C. Krawtchouk Polynomials
The i-th quaternary Krawtchouk polynomial is defined as
Ki (x; n) =

i
X

(−1)j 3i−j

j=0

 

x n−x
,
j
i−j

(6)

which satisfies
(1 − y)x (1 + 3y)n−x =

n
X

Ki (x; n)y i .

i=0
1 More precisely, when we apply the MacWilliams identities for orthogonal groups, we are considering the stabilizer subgroup defined in the quotient of
the n-fold Pauli group by its center: Gn /{±I, ±iI} as in [23]. Or one can consider the group τ (S) and its orthogonal group in Z2n
2 instead.

4

The Krawtchouk polynomials satisfy the following orthogonality relation
n
X

Kr (i; n)Ki (s; n) = 4n δr,s .

(7)

i=0

where δr,s is the Kronecker delta function. Thus they form a basis of polynomials with finite degree n. They are especially
useful in the MacWilliams theory and algebraic linear programming bounds. Details of Krawtchouk polynomials can be found
in [13], [37], [15]. Here we survey some properties of the quaternary Krawtchouk polynomials. For convenience, sometimes
we may simply write Ki (x) = Ki (x; n) when the underlying n is clear from the context.
⊥
Let {Bw } and {Bw
} be the weight distributions of a stabilizer group S and its orthogonal subset S ⊥ in G n , respectively.
Thus Eqs. (5) and (6) imply
n
1 X
Bi⊥ =
Bj Ki (j; n), i = 0, . . . , n.
|S| j=0
A symmetry relation is satisfied by the polynomials
 
 
i n
s n
3
Ks (i; n) = 3
Ki (s; n).
i
s
The following property is needed in the proof of Singleton bound later (Sec. IV-A)



n 
X
n−i
n−x
Ki (x; n) = 4j
.
n−j
j
i=0

(8)

(9)

Every polynomial of degree at most n has a unique expansion in the basis of Krawtchouk polynomials. If a polynomial
f (x) has the expansion
t
X
f (x) =
fi Ki (x),
i=0

then
fi = 4−n

n
X

f (j)Kj (i).

j=0

The Christoffel-Darboux formula is of importance [37]:
  t
4(a − x) t n X Ki (x)Ki (a)

Kt+1 (x)Kt (a) − Kt (x)Kt+1 (a) =
3
.
t i=0
t+1
3i ni

(10)

The Krawtchouk polynomials satisfy a recurrence relation,
(i + 1)Ki+1 (x) = (3n − 2i − 4x)Ki (x) − 3(n − i + 1)Ki−1 (x).

(11)

The following equation is derived in [15, Lemma 2]
Ki (x)Kj (x) =

n
X

Kl (x)

l=0

n−l
X

α(l, i, j, r),

(12)

r=0

where

α(l, i, j, r) =

l
2l + 2r − i − j



n−l
r




2l + 2r − i − j i+j−2r−l r
2
3 .
l+r−j

(13)

Denote by rt the smallest root of Kt (x). It is well known that rt > rt+1 [13] and that when t grows linearly with n we
have
r
rt
3
t
1
t
t
= −
−
3 (n − ) + o(1).
n
4 2n 2
n
n
Define
1
2
f (x) =
{Kt+1 (x)Kt (a) − Kt (x)Kt+1 (a)} .
(14)
a−x
This polynomial yields the first linear programming bound for classical codes over F4 [38],[37]. To get the first linear
programming bound in the asymptotic case, for large n, we choose
t
3 1
1p
= − δ−
3δ(1 − δ) + o(1),
n
4 2
2

5

t (a)
where δ = d/n, and a so that rt+1 < a < rt and KKt+1
(a) = −1.
The Krawtchouk polynomials also form a basis for multivariate polynomials. In our case, we will need the basis of bivariate
polynomials of degrees at most n, c in x, y, respectively:

{Ki (x; n)Kj (y; c)}.
Then a polynomial f (x, y) of degree at most n, c in x, y has a unique Krawtchouk expansion
f (x, y) =

n X
c
X

fi,j Ki (x; n)Kj (y; c),

i=0 j=0

where
fi,j =

1
4n+c

n X
c
X

f (u, v)Ku (i; n)Kv (j; c).

(15)

u=0 v=0

III. E NTANGLEMENT-A SSISTED Q UANTUM C ODES
In the following we consider Pauli operators of the form
E A ⊗ F B ∈ G n+c
for E A ∈ G n , F B ∈ G c , where the superscripts A and B denote two parties Alice and Bob, respectively. We may implicitly
write E ⊗ F for simplicity when it is clear from the context. We will define two split weight enumerators for EA quantum
codes that count weights on Alice and Bob’s qubits separately, and then derive their MacWilliams identities, which is a key
step to prove algebraic linear programming bounds for general EA quantum codes. √
Assume Alice and Bob share c pairs of maximally-entangled states (|00i + |11i)/ 2, called ebits. In addition, Alice has
other n − c qubits in the state |0i. Then Alice will encode information in her qubits (a total of n qubits) and send them to
Bob through a noisy channel. Bob’s c qubits are assumed to be error-free during the whole process. Since the qubits of Alice
and Bob are entangled, the encoded quantum state lies in an (n + c)-qubit state space. (Details of the encoding procedure can
be found in [25].) Thus we define an EA quantum code as follows.
n+c

Definition 1. An ((n, M, d; c)) EA quantum code Q is an M -dimensional subspace of the (n + c)-qubit state space C2
such that
1 B
1) for |ψi ∈ Q, TrA (|ψihψ|)
 = 2c I ; 0
A
A
2) for E ∈ G n of wt E ≤ d − 1, E = E A ⊗ IB is detectable.

The first condition in Def. 1 ensures that Alice and Bob share c ebits and that the encoding is locally performed by Alice. The
parameter d is called the minimum distance of Q, which quantifies the maximum weight of a detectable Pauli error. Denote
by R = logn2 M the code rate, by δ = nd the relative distance, and by ρ = nc the entanglement-assistance rate. If Q is defined
by a stabilizer group (of Gn+c ) of size 2n+c−k , we have M = 2k and Q is called an [[n, k, d; c]] EA stabilizer code [18]. If,
furthermore, c = n − k, Q is called a maximal-entanglement
P EA stabilizer code.
Suppose Q has an orthonormal basis {|ψi i} and P = i |ψi ihψi | is the orthogonal projector onto Q. The quantum error
correction conditions [29], [3] say that an error operator E ∈ G n+c is detectable by Q if and only if
hψi |E|ψj i = λE δi,j
or P EP = λE P for some constant λE depending on E. An error operator E is called a degenerate error if λE 6= 0; otherwise,
it is nondegenerate.
⊥
Similarly to the case of quantum codes [16], we define two split weight enumerators {Bi,j } and {Bi,j
} of Q by
X
1
Bi,j = 2
(Tr ((Ei ⊗ Ej )P ))2 , i = 0, . . . , n; j = 0, . . . , c;
(16)
M
Ei ∈G n ,wt(Ei )=i
Ej ∈G c ,wt(Ej )=j

⊥
Bi,j
=

1
M

X
Ei ∈G n ,wt(Ei )=i
Ej ∈G c ,wt(Ej )=j

Tr ((Ei ⊗ Ej )P (Ei ⊗ Ej )P ) , i = 0, . . . , n; j = 0, . . . , c.

(17)

6

Since P =

P

i

⊥
as
|ψi ihψi |, we can rewrite Bi,j and Bi,j
X
1
Bi,j = 2
M

|

X
hψl |Ei ⊗ Ej |ψl i|2 ,
l

Ei ∈G n ,wt(Ei )=i
Ej ∈G c ,wt(Ej )=j

⊥
Bi,j
=

1
M

X

X

Ei ∈G n ,wt(Ei )=i
Ej ∈G c ,wt(Ej )=j

l,m

|hψl |Ei ⊗ Ej |ψm i|2 .

⊥
Thus {Bi,j } is a distribution of errors that do not corrupt the code space of Q, while {Bi,j
} is a distribution of errors that
are undetectable by Q.

Theorem 2. Suppose Q is an ((n, M, d; c)) EA quantum code with projector P and split weight enumerators {Bi,j } and
⊥
{Bi,j
}, defined in (16) and (17), respectively. Then
⊥
⊥
≥ Bi,j ≥ 0;
1) B0,0 = B0,0
= 1; Bi,j
2) B0,j = 0 for j = 1, . . . , c;
3)

⊥
Bi,0 = Bi,0
,
i = 1, . . . , d − 1;
(18)
⊥
Bd,0 < Bd,0
;
4)
⊥
Bi,j
=

c
n
M XX
Bu,v Ki (u; n)Kj (v; c);
2n+c u=0 v=0
n X
c
X

1

Bi,j =

2n+c M

⊥
Bu,v
Ki (u; n)Kj (v; c).

(19)

(20)

u=0 v=0

Proof. 1) The first part is straightforward and the second part is from the Cauchy-Schwartz inequality.
B
2) By Definition 1, we have TrA (P ) = M
2c I . Then for j > 0,
X

1
B0,j = 2
(Tr (IA ⊗ Ej )P )2
M
Ej ∈G c ,wt(Ej )=j

1
= 2
M

X

2

(Tr (Ej TrA (P ))) = 0,

Ej ∈G c ,wt(Ej )=j

since Tr (E) = 0 for a nonidentity Pauli operator E.
⊥
3) We have Bi,0 = Bi,0
if and only if hψl |E A ⊗ IB |ψm i = 0 for E ∈ G n with wt (E) = i and for all l 6= m.
4) The proof is similar to that in [16]. The projector P can be expressed as
P =

c
n X
X
u=0 v=0

X
Du ∈G n ,wt(Du )=u
Dv ∈G c ,wt(Dv )=v

Tr ((Du ⊗ Dv )P )
Du ⊗ Dv ,
2n+c

n+c

since {Du ⊗ Dv }u,v is a basis of linear operators on C2 . For convenience, we will simply write Du ⊗ Dv as the index of
summation and similarly for Ei ⊗ Ej . By definition,
1 X X X Tr ((Du ⊗ Dv )P ) Tr ((Du0 ⊗ Dv0 )P )
⊥
Bi,j
=
· Tr ((Ei ⊗ Ej )(Du ⊗ Dv )(Ei ⊗ Ej )(Du0 ⊗ Dv0 ))
2(n+c)
M
2
u,v
D
⊗D
u
v
E ⊗E
i

(a)

=

j

u0 ,v 0 D 0 ⊗D 0
u
v

1 X X X (Tr ((Du ⊗ Dv )P ))2
· Tr ((Ei ⊗ Ej )(Du ⊗ Dv )(Ei ⊗ Ej )(Du0 ⊗ Dv0 ))
M
22(n+c)
u,v
Ei ⊗Ej

Du ⊗Dv

M X X (Tr ((Du ⊗ Dv )P ))2 X Tr (Ei Du Ei Du ) X Tr (Ej Dv Ej Dv )
·
= n+c
2
M2
2n
2c
u,v
Du ⊗Dv

Ei

Ej

M X
= n+c
Bu,v Ki (u; n)Kj (v; c),
2
u,v

(b)

where (a) is because the trace of a nonidentity Pauli operator is zero. To prove (b), note that Tr (Ei Du Ei Du ) /2n = 1 if Ei
and Du commute; and Tr (Ei Du Ei Du ) /2n = 1, otherwise. The rest is simply to determine the number of Ei that commute
with Du .

7

Eq. (20) is obtained by applying (7) twice to (19).
Definition 3. An ((n, M, d; c)) EA quantum code is called degenerate if its split weight enumerator Bi,0 > 0 for some
0 < i < d, and nondegenerate, otherwise.
⊥
Remark: The converse of Theorem 2 is not necessarily true; given two distributions {Bi,j } and {Bi,j
} satisfying the
conditions 1), 2), 3), and 4) in Theorem 2, it may still be the case that no corresponding EA quantum code exists. In particular,
we will derive additional constraints for the case of EA stabilizer codes in Theorem 16 later.
Usually the existence of a code is shown by construction. The Gilbert-Varshamov bound provides a nonconstructive proof of
the existence of classical codes [13]. Next we will prove a Gilbert-Varshamov-type bound on the size of EA stabilizer codes2
for fixed n, d, c in Theorem 4. We start by defining three Pauli subgroups associated with an EA stabilizer code.
Let S 0 be an Abelian subgroup of Gn+c generated by

g10 = g1A ⊗ Z1B , . . . , gc0 = gcA ⊗ ZcB ,
B
0
A
B
h01 = hA
1 ⊗ X1 , . . . , hc = hc ⊗ Xc ,
0
A
0
B
gc+1
= gc+1
⊗ IB , . . . , gn−k
= gn−k
⊗ IB ,

where ZjB , XjB ∈ Gc , gjA , hA
j ∈ Gn , 0 ≤ c ≤ n − k, and gj and hj satisfy the commutation relations:
hgi , gj iGn = 0 for i 6= j,

(21)

hhi , hj iGn = 0 for i 6= j,

(22)

hgi , hj iGn = 0 for i 6= j,

(23)

hgi , hi iGn = 1 for all i.
0

(24)
0

(We say that gi and hi are symplectic partners.) Then S defines an [[n, k, d; c]] EA stabilizer code C(S ) by
{|ψi ∈ C2

n+c

: g|ψi = |ψi, ∀g ∈ S 0 }

A
B
A
B
of dimension 2k . We can introduce another 2k independent generators gn−k+1
⊗ IB , . . . , gnA ⊗ IB , hA
n−k+1 ⊗ I , . . . , hn ⊗ I ∈
0
Gn+c , where gj and hj also satisfy the commutation relations. Since these 2k generators commute with the stabilizers in S , they
operate on the logical level of the encoded states. Thus we define a logical subgroup L = hgn−k+1 , . . . , gn , hn−k+1 , . . . , hn i.
Let SI = hgc+1 , . . . , gn−k i ⊂ Gn be the isotropic subgroup, which is Abelian. Let SS = hg1 , h1 , . . . , gc , hc i ⊂ Gn be the
symplectic subgroup, which is non-Abelian. Since gi hi = −hi gi , −I ∈ SS . Let S = {g1 g2 : g1 ∈ SS , g2 ∈ SI } be the simplified
stabilizer group, which is non-Abelian. Since the elements in SS commute with the elements in SI , we can safely denote S
by the notation SS × SI and similarly in the following. Then the minimum distance d of C(S 0 ) is the minimum weight of any
element in

S ⊥ \ SI .

(25)

Now we prove a Gilbert-Varshamov bound for EA stabilizer codes.
Theorem 4. There exists an [[n, k, d; c]] EA stabilizer code provided that
d−1  
X
n j
2n+k−c − 2n−k−c
3 ≤ 4n − 1.
j
j=0
As n becomes large, we have
R = 1 + ρ − δ log2 3 − H2 (δ),
where H2 (x) = −x log2 x − (1 − x) log2 (1 − x) is the binary entropy function.
Proof. The first part is similar to the proof of the Gilbert-Varshamov bound for quantum stabilizer codes [6], [39]. Let Nk be
the number of all [[n, k; c]] EA stabilizer codes. Let M denote the multiset
[
S ⊥ \ SI ,
S

where the union is over
 all simplified stabilizer subgroups S = SS × SI of [[n, k; c]] EA stabilizer codes. For each S, there
are 2n+k−c − 2n−k−c elements in S ⊥ \ SI . Recall that the n-fold Clifford group is the set of unitary operators that preserve
the n-fold Pauli group Gn by conjugation. It is known that the n-fold Clifford group is transitive on Gn \ {I}. That is, for
2A

similar result has been provided in [24], but the argument there was incomplete.

8

E, F ∈ Gn \ {I}, there exists an n-fold Clifford operator U such that U EU † = F . If E ∈ S, then F ∈ U SU † , where
U SU † , {U gU † : g ∈ S}. Thus each nonidentity element E ∈ Gn appears
Nk ·

2n+k−c − 2n−k−c
4n − 1

times in M. Now we delete from M those S ⊥ \ SI with at least one nonidentity element of weight less than d. At most
d−1  
X
n j
2n+k−c − 2n−k−c
3 ·N ·
j
4n − 1
j=0
S are removed from the union of M. If this number is smaller than Nk , there exists an [[n, k, d; c]] EA stabilizer code.
The second part is from Stirling’s approximation:
 
 
1
n
d
log2
= H2
+ o(1),
(26)
n
d
n
where o(1) tends to 0 as n increases.
The Gilbert-Varshamov bound for EA stabilizer codes suggests that entanglement-assisted quantum codes may have higher
code dimension than codes without entanglement assistance for fixed n and d.
IV. U PPER B OUNDS FOR EA Q UANTUM C ODES
In this section, we will derive Delsarte’s algebraic linear programming bounds for general quantum codes with entanglement
assistance. We first derive the main theorem, similar to [15, Theorem 4] and [26, Theorem 3].
Theorem 5. Let Q be an ((n, M, d; c)) EA quantum code. Let
f (x, y) =

c
n X
X

fi,j Ki (x; n)Kj (y; c)

i=0 j=0

be a polynomial with nonnegative coefficients {fi,j } in the Krawtchouk expansion (15). Assume that
fi,0 > 0, for 0 ≤ i ≤ d − 1;

(27)

f (x, y) ≤ 0, for x ≥ d or y ≥ 1.
Then

1

M≤

max

2n+c 0≤l≤d−1

(28)

f (l, 0)
.
fl,0

If Q is nondegenerate, then
M≤

1 f (0, 0)
.
f0,0

(29)

2n+c

⊥
Proof. Suppose Q is an ((n, M, d; c)) EA quantum code with split weight enumerators {Bi,j } and {Bi,j
}. Then

2n+c M

d−1
X

fi,0 Bi,0 ≤2n+c M

i=0
(a) n+c

=2

M

n X
c
X
i=0 j=0
n X
c
X

fi,j Bi,j
fi,j ·

i=0 j=0

=

d−1
X

⊥
Bi,0
f (i, 0) +

1
2n+c M

n
X

i=0

i=d

d−1
(b) X

d−1
X

≤

i=0

⊥
Bi,0
f (i, 0) =

n X
c
X

⊥
Bu,v
Ki (u; n)Kj (v; c) =

u=0 v=0

⊥
Bi,0
f (i, 0) +

n X
c
X

n X
c
X

⊥
Bu,v
f (u, v)

u=0 v=0
⊥
Bi,j
f (i, j)

i=0 j=1

Bi,0 f (i, 0),

i=0

where (a) is by (20) from Theorem 2; (b) follows from assumption (28). The last equality is by (18) from Theorem 2. Thus
Pd−1
1
f (l, 0)
1
i=0 Bi,0 f (i, 0)
M ≤ n+c P
≤ n+c max
.
d−1
0≤l≤d−1
2
2
fl,0
l=0 fl,0 Bl,0
If Q is nondegenerate, we have its split weight enumerator Bi,0 = 0 for 0 < i < d. Using this additional constraint in the
above proof, we have (29).

9

It remains to find good polynomials f (x, y) that satisfy (27) and (28).
A. Singleton Bound for EA Quantum Codes
The Singleton bound for EA stabilizer codes was proposed in [18], which is obtained by an information-theoretical
approach [40]. Herein we prove a Singleton bound for EA quantum codes. Our bound applies to nonadditive EA quantum
codes as well, and is thus more general than the one in [18].
Theorem 6. For an ((n, M, d; c)) EA quantum code Q, if d ≤ (n + 2)/2, then
M ≤ 2n+c−2(d−1) .
If Q is nondegenerate, the bound holds for any d.
Proof. Let
f (x, y) = 4

n−d+1

n 
Y
i=d

c
x c Y
·4
(y − j) = 4n+c−d+1
1−
i
j=1

n−x
n−d+1

n
d−1



c
Y

(y − j).

(30)

j=1

From (15), (7), and (9), after some calculation, we have
n−i
d−1

n
d−1



fi,j =

≥ 0.

It can be easily checked that fi,0 > 0 for 0 ≤ i ≤ d − 1 and f (x, y) = 0 if x ≥ d or y ≥ 1. Also f (0, 0)/f0,0 ≥ f (i, 0)/fi,0
1 f (0,0)
n+c−2(d−1)
.
for 1 ≤ i ≤ d − 1 if d ≤ (n + 2)/2. Thus by Theorem 5, we have M ≤ 2n+c
f0,0 = 2
The assumption d ≤ (n + 2)/2 is reasonable for quantum codes [15] because of the no-cloning theorem [41]; however,
entanglement can increase the error-correcting ability of quantum codes as Grassl has proposed a construction of EA stabilizer
codes with d > (n + 2)/2 [42].
The argument used in [18] does not generalize to this case of d > (n + 2)/2. Also, the polynomial f (x, y) in Eq. (30) does
n−l
)
(d−1
= 0 if n − l < d − 1, which will lead to a trivial upper bound M < ∞. To solve
not work for d > n+2
since
f
=
l,0
n
2
)
(d−1
this problem, a possible way is to introduce another polynomial h(x, y) , f (x, y) + g(x, y) such that gl,0 > 0 for those l with
fl,0 = 0. A candidate is
n
c
Y
Y
g a (x, y) = 4a
(x − i)
(y − j)
i=1

j=1

with coefficient
a
gx,y
= 4a−n−c

in the Krawtchouk expansion, where a is some real number chosen appropriately. Apparently, we can apply Theorem 5 with
polynomial g a (x, y) and obtain another trivial bound
M ≤ 2n+c .
Now define
ha (x, y) = f (x, y) + g a (x, y)
with coefficient
a
hax,y = fx,y + gx,y
.

By linearity, we can apply Theorem 5 with ha (x, y). Optimizing over appropriate real numbers a, we have the following
theorem.
Theorem 7. (Refined Singleton Bound) For an ((n, M, d; c)) EA quantum code Q, then
(
)
1
f (l, 0)
ha (l, 0)
M ≤ n+c min
max
, min
max
.
0≤a≤n+c 0≤l≤d−1
0≤l≤d−1 fl,0
2
hal,0
Note that the range 0 ≤ a ≤ n + c can be enlarged.

10

The smallest EA quantum code with d > (n + 2)/2 in [42] has parameters [[9, 1, 6; 1]]. Applying this theorem with
n = 9, d = 6, c = 1, and optimizing over a from 0 to 10 with increment 0.001, we have
M ≤ 3.73 · · · .
Therefore, the [[9, 1, 6; 1]] EA quantum code is optimal.
Remark: The refined Singleton bound for EA quantum codes in Theorem 7 is not monotonic in d, while it appears to be
monotonic in c. For n = 9, d = 7, c = 1, we have M ≤ 5.63; for n = 9, d = 8, c = 1, we have M ≤ 5.18. Thus the quest for
a good general bound remains open. It is our future direction to find suitable auxiliary polynomials.
B. Hamming Bounds for EA Quantum Codes
It is known that a nondegenerate [[n, k, d; c]] EA stabilizer code satisfies the EA Hamming bound [43], [44]. Herein we
derive a Hamming bound for general EA quantum codes.
Theorem 8. For an unrestricted (nondegenerate or degenerate) ((n, M, d; c)) EA quantum code Q,
Pt Pt Pn−l
r=0 α(l, i, j, r)
j=0
i=0
n+c
M ≤2
max
,
P
2
0≤l≤d−1
t
K
(l;
n)
i
i=0

(31)

where t = b d−1
2 c and α(l, i, j, r) is defined in (13).
If Q is nondegenerate,
t
X

 
n
≤ 2n+c .
M
3
j
j=0
j

(32)

H
Proof. Let fl,j
= FlH , where

FlH

=

t
X

!2
Ki (l; n)

.

(33)

i=0

Using (7) and (12), one can show that
f H (x, y) = 4n+c

t X
t n−x
X
X

α(x, i, j, r)

i=0 j=0 r=0
H
is the polynomial with coefficients fl,j
in the Krawtchouk expansion. It can be checked easily that f H (x, y) = 0 if x ≥ d or
y ≥ 1. Thus we can apply Theorem 5.
H

is achieved at l = 0. The
For degenerate ((n, M, d; c)) EA quantum codes, (31) and (32) coincide if max0≤l≤d−1 f f (l,0)
H
l,0
region of n, d where the quantum Hamming bound holds for degenerate quantum stabilizer codes has been discussed in [45],
[26]. So far, there is no evidence of degenerate quantum codes that violate the nondegenerate Hamming bound (32). The same
H
analysis can be considered here. Note that for fixed n, d, the value of l that maximizes f f (l,0)
does not depend on c. In Fig. 1,
H
l,0
we plot the degenerate and nondegenerate Hamming bounds at d = 9 and c = 3. The two bounds coincide after n = 19. We
have observed similar behaviors for several values of d and t. Thus we have the following conjecture:
Conjecture 9. The nondegenerate Hamming bound (32) holds for degenerate ((n, M, d; c)) EA quantum codes for n ≥ N (t),
where N (t) does not depend on c.
The first few values of N (t) are listed in Table I. Similar results have been observed for data-syndrome codes [26].
t
N(t)

2
9

3
14

4
19

5
24

6
30

7
35

8
40

9
46

10
51

TABLE I: Values of N (t) for 2 ≤ t ≤ 10.
Recall that Theorem 4 suggests that M can be larger by introducing entanglement assistance. Also the degenerate and
nondegenerate Hamming bounds diverge at low code rate from the above discussion. Consequently, it is likely that EA
quantum codes violate the nondegenerate Hamming bound, as evidences have been provided in [46]: A family of degenerate
[[n = 4t, 1, 2t + 1; 1]] EA stabilizer codes for t ≥ 2 has been constructed, which violate (32).
On the other hand, the nondegenerate Hamming bound is valid for quantum codes in the asymptotic case for δ = d/n <
1/3 [15], and similarly for EA quantum codes. Then applying (26) to (32), we have the following corollary.

11








 



















Fig. 1: Plots of the degenerate and nondegenerate Hamming bounds at d = 9 and c = 3.

Corollary 10. For any ((n, M, d; c)) EA quantum code with large n,
log2 M
δ
δ
≤ 1 + ρ − log2 3 − H2 ( ) + o(1),
n
2
2
where ρ = c/n and δ = d/n < 1/3.
By introducing entanglement assistance, distance can be increased [47]. Again consider the family of [[n = 4t, 1, 2t + 1; 1]]
EA stabilizer codes. These codes have relative distance δ = 0.5, which is beyond the working region of the Hamming bound.
C. The First Linear Programming Bound for EA Quantum Codes
The following polynomial is used to prove the first linear programming bound of classical binary or nonbinary codes [48],
[38], [37] and also quantum codes [15]
1
2
(Kt+1 (x; n)Kt (a; n)− Kt (x; n)Kt+1 (a; n))
(34)
a−x
for some suitable a. Herein we will first discuss the LP-1 bound for quantum
Qc codes of finite lengths. It is straightforward to
generalize the results to EA quantum codes by choosing f (x, y) = 4c F (x) j=1 (y − j) and fj,l = Fj . In particular, we will
show that the LP-1 bound is better than the Hamming bound for large d/n.
1) LP-1 bound for quantum codes of finite lengths:
F (x) =

Theorem 11. For an unrestricted (nondegenerate or degenerate) ((n, M, d; c)) EA quantum code Q,
M≤

1

max

2n−c 0≤l≤d−1

F (l)
,
Fj

where F (x) is defined in (34) with t = b d−1
2 c. If Q is nondegenerate,


n
3t+1 t+1
Kt (a) − 3t
1
M ≤ n−c
2
aF0

n
t



Kt+1 (a)

(35)

2
.

Proof. By the Christoffel-Darboux formula (10),
 
t
X
Ki (x)Ki (a)
4 · 3t n

{Kt+1 (x)Kt (a) − Kt (x)Kt+1 (a)}
F (x) =
t+1 t
3i ni
i=0
!
 
t
t
X
X
4 · 3t n
Ki (a)
Ki (a)
 Kt+1 (x)Ki (x) − Kt+1 (a)
 Kt (x)Ki (x) .
=
Kt (a)
t+1 t
3i ni
3i ni
i=0
i=0
Using (12) we obtain
F (x)

c
Y

(y − j) = 4

j=1

c

n
X
j=0

Fj Kj (x),

(36)

12

with
!
 
n−j
n−j
t
t
X
X
4 · 3t n
Ki (a) X
Ki (a) X


Fj =
α(j, t + 1, i, s) −Kt+1 (a)
α(j, t, i, s) .
Kt (a)
t+1 t
3i ni s=0
3i ni s=0
i=0
i=0

(37)

From (37) it follows that by choosing
appropriate a ∈ (rt+1 , rt ), we can guarantee that Fj ≥ 0. Then we can apply
Qc
Theorem 5 with f (x, y) = 4c F (x) j=1 (y − j) and fj,l = Fj .
Even for small values of n we have to manipulate by very large numbers during computation of the bound
max F (j)/Fj .

0≤j≤d−1

The values of Krawtchouk polynomials and binomial coefficients in (37) grow very rapidly with n. Though packages like Maple
and Mathematica allow one to operate with very large numbers by increasing the precision of computations, straightforward
computations of F (j) and Fj are getting very slow even at relatively small n. The following simple tricks allow to speed up
Maple computations significantly.
First, the analysis of (37) shows the limits of summations can be computed more accurately, leading to the equation:

 
min{n−j,(t+i+1−j)/2}
t
X
X
4 · 3t n 
Ki (a)

α(j, t + 1, i, s)
Kt (a)
Fj =
n
t+1 t
3i i
i=0
s=max{0,(t+i+1−2j)/2,t+1−j}

min{n−j,(t+i−j)/2}
t
X
X
Ki (a)

−Kt+1 (a)
α(j, t, i, s) .
(38)
3i ni
i=0
s=max{0,(t+i−2j)/2,t+1−j}

Second, in (38) the two summations over s do not depend on a. So, for given j and i, we can pre-compute and reuse them
for getting Fj for different values of a.
Third, computation of Kt (x) according to (11) is much faster than according to (6).
To get a good bound for a particular value of n, we have to optimize the choice of parameters t and a in (34). The following
procedure is used:
p
d
1
3d(n − d) and increase t until
1. Find the smallest t such that rt < d. In order of doing this, we start with t0 = 3n
4 − 2 − 2
Kt (d) < 0.
2. Find rt and rt+1 .
3. Find
F (j)
aopt = arg min max
.
(39)
0≤j≤d−1
Fj
a∈(rt+1 ,rt )
For example, for n = 50 and d = 15, we have t = 15 and rt+1 ≈ 13.543, rt ≈ 14.510. The behavior of max0≤j≤d−1 F (j)/Fj
as a function of a is shown in Fig. 2. In all our computations this function was convex. So, we conjecture that this is always
the case.



  


























Fig. 2: maxj F (j)/Fj as a function of parameter a for n = 50 and d = 15
The analysis of (37) shows that if we fix n and start increasing d, then at a certain moment we will have Fj = 0 for some
j ≤ d − 1. For instance, for n = 30 this happens when d ≥ 15 and for n = 60 this happens for d ≥ 25. To overcome this

13

problem one may try to choose larger t so that it is not the first t for which rt < d. We leave this possibility, however, for
future work. In this work we assume that if Fj = 0, j < d, then LP-1 bound is not applicable.
In the asymptotic regime, for sufficiently large δ = d/n, the LP-1 bound is better than the Hamming bound. Similarly, the
LP-1 bound improves the Hamming bound for codes of finite length. In Fig. 3, we show bounds on the code rate R, which
is defined as


log2 M
F (j)
≤ log2
− 1 + ρ,
max
R=
0≤j≤d−1 Fj
n
where ρ = c/n and F (j) is either the LP-1 polynomial defined in (34) or the Hamming polynomial defined in (33). In this
figure, we have ρ = 0 and n = 1000.

Fig. 3: The LP-1 and Hamming Upper Bounds for n = 1000, ρ = 0 and d = 200, . . . , 350.
One can see that for large values of d, the LP-1 bound visibly improves the Hamming bound.
2) LP-1 bound for large values of n: Packages like Maple and Mathematica allow one to increase the precision of
computations over real numbers by increasing the number of digits for representing real numbers. For example, in Maple
the precision can be increased by assigning larger values to the system variable DIGITS (its default value is 10). For large
values of n, however, the needed precision becomes overwhelming.
To overcome the above problem, we can compute LP-1 bound using only integers as follows. When n grows, the roots rt+1
and rt are getting closer and closer to each other. Numerical computations show that choosing a such that Kt (a) = −Kt+1 (a)
in this case, we get a value very close to aopt defined in (39). Let us denote this a by a∗ . Then we have
1
2
Kt (a∗ )2 {Kt+1 (j) − Kt (j)} .
a∗ − x
Next we lower bound Fj by using only the term with i = t in (38):

min{n−j,(2t+1−j)/2}
X
4 
(low.bnd.)
α(j, t + 1, t, s) +
Fj ≥Fj
= Kt (a∗ )2
t+1
F (j) =

s=max{0,(2t+1−2j)/2,t+1−j}

,Kt (a∗ )2

min{n−j,(2t−j)/2}

X


α(j, t, t, s)

s=max{0,(2t−2j)/2,t+1−j}

4
· cj .
t+1

(40)

Finally, we find the largest integer a0 < d such that Kt+1 (a0 ) > 0. Since a∗ lies somewhere between rt+1 and rt , we have
a ≤ a∗ . Hence using a0 in the denominator of (34), we make our LP-1 bound larger (worse).
Summarizing these arguments, we obtain that for the optimal LP-1 polynomial F (j) (with aopt ) we have
0

F (j)
1
2
≤ 0
(Kt+1 (j) − Kt (j)) · cj ,
Fj
a −j

(41)

where cj is defined in (40). During computation of (41) we need to operate only with integers, no operations over real numbers
are needed until the very end of computing:
log2 ( max

0≤j≤d−1

a0

1
2
{Kt+1 (j) − Kt (j)} · cj ) − 1 + ρ.
−j

14

Thus we do not lose any precision in computations. Using this approach we obtained the results presented in Fig. 4 for ρ = 0.
We consider the case when the code length grows, but the ratio d/n = 0.3 is fixed. We again observed that starting with some
small value of n, LP-1 bound visibly improves the Hamming bound.

Fig. 4: LP-1 and Hamming Upper Bounds for code lengths n = 30, . . . , 1000, ρ = 0, and d = 0.3n.
3) Asymptotic case: Following the same procedure (see [15], for details), we can show that the conventional first linear
programming bound holds for EA quantum codes asymptotically.
Theorem 12. For any ((n, M, d; c)) EA quantum code Q with 0 ≤ δ ≤ 0.3152,
 


1p
1p
3 δ
3 δ
− −
− −
R ≤ρ − 1 + H2
3δ(1 − δ) +
3δ(1 − δ) log2 3 + o(1)
4 2 2
4 2 2

(42)

for large n. If Q is nondegenerate, (42) holds for all δ.
Note that this upper bound differs from that for classical quaternary codes by a constant (ρ − 1).
Let us consider again the family of degenerate [[4t, 1, 2t + 1; 1]] EA stabilizer codes. These codes have asymptotic R = 0,
ρ = 0, and δ = 0.5, which are beyond the working region of the first linear programming bound.
D. Bounds for Maximal-entanglement EA Stabilizer Codes
In this subsection we consider [[n, k, d; c = n − k]] maximal-entanglement EA stabilizer codes, where there is no degeneracy [23]. Lai et al. proved a Plotkin bound for maximal-entanglement EA stabilizer codes [24] and its asymptotic version
is:
δ ≤ 0.75 + o(1).
The asymptotic Gilbert-Varshamov bound, Singleton bound, Hamming bound, first linear programming bound are as follows:
δ
1
log2 3 − H2 (δ),
2
2
R ≤1 − δ,
δ
1
δ
R ≤1 − log2 3 − H2 ( ) + o(1),
4
2
2



1
3 δ
1p
1 3 δ
1p
− −
3δ(1 − δ) +
− −
3δ(1 − δ) log2 3 + o(1).
R ≤ H2
2
4 2 2
2 4 2 2
R ≥1 −

Thus we have shown that conventional bounds for classical quaternary codes hold for maximal-entanglement EA stabilizer
codes. These bounds are plotted in Fig. 5.
V. U PPER B OUNDS FOR Q UANTUM S TABILIZER C ODES OF S MALL L ENGTH
In the previous section we have introduced algebraic linear programming bounds for EA quantum codes. We will discuss
linear programming bounds on the minimum distance of EA stabilizer codes of small length. In particular, we find additional
constraints on a stabilizer group and its orthogonal group so that the linear programming bounds can be strengthened. A table

15













































Fig. 5: Plots of the Singleton bound, Hamming bound, first linear programming bound, and the Gilbert-Varshamov bound. The
x-axis ranges from 0 to 0.75 because of the Plotkin bound.

of upper and lower bounds for any maximal-entanglement EA stabilizer codes with length n up to 15 is given in [23]. However,
there are many “gaps” between the upper and lower bounds. We will improve that table in this section.
We would like to apply linear programming techniques to upper bound the minimum distance of EA stabilizer codes.
However, since S ⊥ 6= SI , we cannot use a MacWilliams identity to connect the weight distributions of these two groups.
Observe that
(SS × SI )⊥ = L × SI

(43)

SI⊥ = L × SS × SI .

(44)

and

In [24], [23], these two dualities are considered to obtain the linear programming bounds on the minimum distance of small
EA stabilizer codes.
⊥
Interestingly, the split weight enumerators {Bi,j } and {Bi,j
} of EA quantum codes defined in (16), (17) have enough
0
0
0
, . . . , gn−k
i, and L0 = {g A ⊗ IB :
information for our linear programming problem. Let SS = hg10 , h01 , . . . , gc0 , h0c i, SI0 = hgc+1
g ∈ L}. Define
Ai,j = |{E1 ⊗ E2 ∈ SS0 × SI0 : E1 ∈ G n , wt (E1 ) = i, E2 ∈ G c , wt (E2 ) = j}|,

(45)

A⊥
i,j

(46)

= |{E1 ⊗ E2 ∈

L0

×

SS0

×

SI0

: E1 ∈ G n , wt (E1 ) = i, E2 ∈ G c , wt (E2 ) = j}|.

⊥
Observe that Bi,j = Ai,j and Bi,j
= A⊥
i,j in the case of EA stabilizer codes. Thus we have the following corollary.

Corollary 13. Suppose Q is an [[n, k, d; c]] EA stabilizer code with stabilizer group SS0 × SI0 . Let {Ai,j } and {A⊥
i,j } be the
0
0
0
0
⊥
split weight distributions of SS × SI and (SS × SI ) , respectively. Then
A⊥
i,j =

1
2n+c−k

n X
c
X

Au,v Ki (u; n)Kj (v; c).

u=0 v=0

Furthermore, the weight distribution of SI is {Ai,0 } and the weight distribution of S ⊥ is {A⊥
i,0 }. Since the minimum distance
of C(S 0 ) is d, we have
⊥
Ai,0 = A⊥
i,0 , i = 1, . . . , d − 1; Ad,0 > Ad,0 .

(47)

Now we can build a linear program with variables Ai,j , A⊥
i,j and constraints from Corollary 13 and (47). The least d such that
this linear program has no feasible solution is an upper bound on the minimum distance for given n, k, c, and this is called
the linear programming bound on the minimum distance of [[n, k; c]] EA stabilizer codes. The resulting linear programming
bound is at least as tight as the one from (43) and (44) used in [24], [23], since this linear program has more constraints and
variables.

16

A. Additional Constraints on the Weight Enumerator Associated with an Non-Abelian Pauli Subgroup
Rains introduced the idea of shadow enumerators to obtain additional constraints in the linear program of quantum codes [27].
The shadow Sh(V) of a group V(⊆ Gn ) is the set
{E ∈ G n : hE, giGn = wt (g)

mod 2, ∀g ∈ V}.

If V is Abelian, Rains showed that
WSh(V) (x, y) =

1
WV (x + 3y, y − x),
|V|

(48)

where WV (x, y) and WSh(V) (x, y) are the weight enumerators of V and Sh(V), respectively [27]. For an EA stabilizer code,
the isotropic subgroup SI is Abelian. Thus
WSh(SI ) (x, y) =

1
WSI (x + 3y, y − x).
|SI |

Recall that {Ai,0 } is the weight distribution of SI . This implies
n
X

0

(−1)w Aw0 ,0 Kw (w0 ; n) ≥ 0, i = 0, . . . , n.

(49)

w0 =0

However, the situation is more complicated when V is not Abelian, which is the case of the simplified stabilizer group
S = SS × SI and its orthogonal group. Herein we derive additional constraints for an non-Abelian Pauli subgroup.
Suppose V ⊂ Gn is non-Abelian and V can be decomposed as V = VS × VI , where VS = hg1 , h1 , . . . , gc , hc i and VI =
hgc+1 , . . . , gc+r i for some c such that the commutation relations (21)-(24) hold [49]. We categorize different V’s into the
following three types:
I. All the generators of V are of even weight.
II. wt (gc+1 ) is odd and all the other generators of VI and VS are of even weight.
III. wt (g1 ) and wt (h1 ) are odd and all the other generators of VS and VI are of even weight.
For convenience, we have the following lemma, which can be easily verified.
Lemma 14. For g, h ∈ Gn ,
wt (gh) ≡ wt (g) + wt (h) + hg, hiGn

mod 2.

This lemma shows that the weight of the product of two operators depends on their inner product.
Lemma 15. Suppose V = VS × VI , where VS = hg1 , h1 , . . . , gc , hc i and VI = hgc+1 , . . . , gc+r i for some c such that (21)-(24)
hold. Then the generators are of type I, II, or III.
Proof. Suppose VI contains some elements of odd weight, say gc+1 without loss of generality. If gj or hj is of odd weight
for j 6= c + 1, it is replaced by gj gc+1 or hj gc+1 , which is of even weight by (21), (23), and Lemma 14. Eqs. (21)-(24) hold
for the new set of generators. This is type II.
Next, suppose VI contains no elements of odd weight. Consider the generators of VS . We know that VS has some elements
of odd weight, because one of g1 , h1 , and g1 h1 must be of odd weight. Assume g1 is of odd weight without loss of generality.
If gi is of odd weight for i = 2, . . . , c, we replace it with gi gc+1 , which is of even weight by (21) and Lemma 14. Notice
that h1 has to be replaced by h1 hi at the same time to maintain the commutation relation in (23). Thus wt (g1 ) is odd and
wt (g2 ) , . . . , wt (gc ) are even. If hi has odd weight for i = 2, . . . , c, we replace it with hi g1 , which is of even weight by (22)
and Lemma 14. Similarly, h1 has to be replaced by h1 gi to maintain the commutation relation in (22). Therefore, we can
assume h2 , . . . , hc are of even weight.
It remains to check whether h1 is of odd weight or not. If wt (h1 ) is odd, this is type III. If wt (h1 ) is even, we replace g1
with g1 h1 , which is of even weight by Eq. (24) and Lemma 14. This case is type I.
Suppose V ⊂ Gn is generated by c pairs of symplectic partners and r isotropic generators of type i. Let Nieven (c, r) and
be the number of elements in V of even and odd weight, respectively. Below we derive formulas for these two
numbers for the three types of generators in Lemma 15.
Niodd (c, r)

17

Theorem 16. For c, r ≥ 0,
NIeven (c, r) = 2r−1 (4c + 2c ),
NIodd (c, r) = 2r−1 (4c − 2c ),
even
NIII
(c, r) = 2r−1 (4c − 2c ),
odd
(c, r) = 2r−1 (4c + 2c ).
NIII

For c ≥ 0 and r > 0,
even
odd
(c, r) = 22c+r−1 .
NII
(c, r) = NII

Proof. These formulas can be derived by recursion. We first consider the case of type I. It is obvious that NIeven (0, 0) = 1 and
NIodd (0, 0) = 0. (In this case, V is the trivial subgroup.) For c = 1, we have two generators g1 and h1 of even weight such that
hg1 , h1 iGn = 1. Thus wt (g1 h1 ) ≡ wt (g1 ) + wt (h1 ) + hg1 , h1 iGn ≡ 1 mod 2. We have NIeven (1, 0) = 3 and NIodd (1, 0) = 1.
Since VI ⊆ VS⊥ and the generators of VI are of even weight (hence every element of VI is of even weight), it follows that
NIeven (1, r) = 3 · 2r and NIodd (1, r) = 2r .
Let Sc denote a group generated by c pairs of symplectic partners. Now we add a new pair of symplectic partners g 0 and h0
of even weight and g 0 , h0 ∈ Sc⊥ . An element E in the new group Sc+1 is of even weight if one of the following cases hold:
E ∈ Sc and wt (E) ≡ 0 mod 2 ; E = g 0 E 0 for some E 0 ∈ Sc and wt (E 0 ) ≡ 0 mod 2 ; E = h0 E 0 for some E 0 ∈ Sc and
wt (E 0 ) ≡ 0 mod 2 ; or E = g 0 h0 E 0 for some E 0 ∈ Sc and wt (E 0 ) ≡ 1 mod 2. Therefore
NIeven (c + 1, r) = 3NIeven (c, r) + NIodd (c, r).
Similarly, we have
NIodd (c + 1, r) = 3NIodd (c, r) + NIeven (c, r).
Solving this system of two recursive equations, we have
NIeven (c, r) = 2r−1 (4c + 2c ),
NIodd (c, r) = 2r−1 (4c − 2c ).
We can find the formula for the generators of type III along the same lines.
Now we consider the case of type II for r > 0. Let Sc denote a group generated by c pairs of symplectic partners of even
weight. From above, we have NIeven (c, 0) and NIodd (c, 0). Now we add a new generator g ∈ Sc⊥ and wt (g) is odd. An element
E in the new group g × Sc is of even weight if one of the following two cases hold: E ∈ Sc and wt (E) ≡ 0 mod 2; or
E = gE 0 for some E 0 ∈ Sc and wt (E 0 ) ≡ 1 mod 2. Thus
even
even
odd
NII
(c, 1) = NII
(c, 0) + NII
(c, 0).

Similarly,
odd
even
odd
even
NII
(c, 1) = NII
(c, 0) + NII
(c, 0) = NII
(c, 1).
odd
odd
It implies NII
(c, 1) = NII
(c, 1) = 2c . Therefore, we have
even
odd
NII
(c, r) = NII
(c, r) = 22c+r−1 .

These formulas serve as constraints on the weight distributions of subgroups that are Abelian or non-Abelian. Note that
Nieven (c, 0) − Niodd (c, 0) = 2c for i = I, III.
In the case of standard stabilizer codes, we have Abelian stabilizer group S and non-Abelian normalizer group S ⊥ . Thus
we have the following corollary.
Corollary 17. Suppose S is an Abelian subgroup of Gn with n − k generators. Let {Aj } and {A⊥
j } be the weight distributions
of S and S ⊥ , respectively. Then one of the following three cases holds:
P
P
⊥
n+k−1
1.
A = 2n−k−1 ,
;
j:j even Aj = 2

Pj:j even j
P
n−k
⊥
n−k−1
2.
A =2
,
4k + 2 k  ;
j:j even Aj = 2
Pj:j even j
P
n−k
⊥
n−k−1
3.
,
4k − 2k .
j:j even Aj = 2
j:j even Aj = 2

18

B. Linear Program for EA Stabilizer Codes
Now we provide a linear program for EA stabilizer codes in this subsection. Let n, k, d, c be integers. Define integer variables
Ai,j , A⊥
i,j , i = 0, . . . , n, j = 0, . . . , c.
The following constraints are from Theorem 2, Corollary 13, Eq. (49), and Theorem 16:
⊥
A0,0 = A⊥
0,0 = 1, Ai,j ≥ Ai,j ≥ 0;
⊥
Ai,0 = A⊥
i,0 , i = 1, . . . , d − 1; A0,j = A0,j = 0, j = 1, . . . , c;
n
n X
c
n
n X
c
X
X
X
X
n+k−c
n+k+c
Aw,0 = 2n−k−c ,
Aw,w0 = 2n−k+c ,
A⊥
=
2
,
;
A⊥
w,0
w,w0 = 2
w=0 w0 =0

w=0

A⊥
i,j =
n
X

1
2n+c−k

n X
c
X

w=0 w0 =0

w=0

Au,v Ki (u; n)Kj (v; c);

u=0 v=0

0

(−1)w Aw0 ,0 Kw (w0 ; n) ≥ 0, i = 0, . . . , n;

w0 =0

X X
w:even w0

Aw,w0 = Nieven (c, n − k − c), for i = I or III,

X

even
(k, n − k − c), for i = I or III,
A⊥
w,0 = Ni

w:even

!
X X

A⊥
w,w0

w:even w0

or

even

= Ni

X

(k + c, n − k − c), for i = I or III, and

n−k−c

Aw,0 = 2

w:even

X X
w:even

w0

even
Aw,w0 = NII
(c, n − k − c),

X

even
A⊥
w,0 = NII (k, n − k − c),

w:even

!
X X
w:even w0

A⊥
w,w0

even

= NII (k + c, n − k − c), and

X

n−k−c−1

Aw,0 = 2

.

w:even

If there is no solution to the integer program with variables Ai,j , A⊥
i,j and the above constraints for given n, k, d, and c, then
there is no [[n, k, d; c]] EA stabilizer code.
We can introduce additional constraints from MacWilliams identities for general split weight enumerators [36]. In the
following, we use the notation in [36]. Let HG 1 be the complex Hilbert space with an orthonormal basis |Ii, |Xi, |Y i, |Zi.
Let HG n = HG⊗n . Then S ⊂ G n has an exact weight generator
1
X
gSE =
|gi ∈ HG n .
g∈S

The MacWilliams identity says that
gSE⊥ =

1 ⊗n E
F gS ,
|S|

(50)

where F is the Fourier transform operator on HG 1 and its matrix representation in the ordered basis |Ii, |Xi, |Y i, |Zi is


1
1
1
1
 1
1 −1 −1 
.
F =
(51)
 1 −1
1 −1 
1 −1 −1
1
Let γ : HG n → C be a linear functional. Then applying γ to (50), we have the MacWilliams identities for general split weight
enumerators defined by γ. (See [36] for more details.) For example, let
X
γH (x, y) = xhI| +
yhα|,
α∈{X,Y,Z}

where x, y ∈ C. Then the general Hamming weight enumerator of S and its MacWilliams identity are defined by γH⊗n (x, y).
The split weight enumerators (45), (46) are defined by γH⊗n (x, y) ⊗ γH⊗c (u, v).
In general, an arbitrary γ and its induced MacWilliams identity will lead to more constraints on the coefficients of S and
S ⊥ . However, these general split weight enumerators usually introduce too many variables to solve in a computer program.
If we know more about a stabilizer group, we can design an effective γ. In [7], the idea of refined weight enumerator is

19

introduced when S is known to have an element of weight u. Let
γre (y0 , y1 , y2 ) = y0 hI| + y1 hX| +

X

y2 hα|.

α∈{Y,Z}

Then a refined weight enumerator is defined as
γH⊗n−u (x0 , x1 ) ⊗ γre⊗u (y0 , y1 , y2 )gSE =

X

Ai,j,l x0n−u−i xi1 y0u−j−l y1j y2l .

(52)

i,j,l

Suppose {Ai } is the weight distribution of S. Then
Aw =

X

Ai,j,l .

i,j,l:i+j+l=w

Without loss of generality, we may assume S has the element I ⊗n−u ⊗ X ⊗u of weight u. Since S is Abelian, we must have
⊥
Ai,j,l = 0 for l 6= 0 mod 2. Similar constraints can be found for the distribution A⊥
i,j,l of S . From (50), we have additional
⊥
constraints from the MacWilliams identities on Ai,j,l and Ai,j,l .
Next we use Mathematica [50] to see if the integer program has a feasible solution for some parameters. Since Mathematica
is a symbolic manipulation program, the results are reliable.
Example 1. (Nonexistence of [[27,15,5]] quantum codes.) In the case of c = 0, SS is trivial and it reduces to the case of
standard stabilizer codes. Solving the linear program for stabilizer codes [7] with additional constraints from Corollary 17,
we found that a [[27, 15, 5]] stabilizer code, if it exists, must have S ⊥ generated by type III generators and the only possible
weight distribution of S is
A0 = 1, A16 = 81, A18 = 1800, A22 = 1944, A24 = 270,
and Aw = 0, otherwise.
Using refined weight enumerators with respect to u = 24, we have additional constraints from the MacWilliams identities
for the refined weight enumerators, which produce a linear program with no feasible solution. Thus we improved the quantum
code table at n = 27, k = 15 [51].
Example 2. (Nonexistence of [[28,14,6]] quantum codes.) We found that a [[28, 14, 6]] stabilizer code, if it exists, must have
S ⊥ generated by type I generators and the only possible weight distribution of S is
A0 = 1, A16 = 189, A18 = 5040, A22 = 9072, A24 = 1890, A28 = 192,
and Aw = 0, otherwise. This implies that a [[28, 14, 6]] code must be nondegenerate. By the propagation rule that the existence
of a nondegenerate [[n, k, d]] code implies the existence of an [[n − 1, k + 1, d − 1]] code [7, Theorem 6], if we have a
nondegenerate [[28, 14, 6]] code, there is a [[27, 15, 5]] code. However, the existence of a [[27, 15, 5]] code has been excluded
in Example 1. Thus there is no [[28, 14, 6]] code.
Example 3. Similarly, a [[23, 1, 9]] stabilizer code, if it exists, must have S ⊥ generated by type III generators and the only
possible weight distribution of S is
A0 = 1, A10 = 10626, A12 = 78246, A14 = 478170, A16 = 1245519, A18 = 1562022, A20 = 733194, A22 = 86526
and Aw = 0, otherwise. Unfortunately, we do not know how to exclude these possibilities. Some other techniques are needed.
We also found that several quantum codes, such as the parameters [[14, 3, 5]], [[17, 3, 6]], [[17, 6, 5]], [[19, 5, 6]], [[21, 7, 6]],
[[23, 3, 8]] and so on, must have S ⊥ with generators of type II, if they exist.
Next we consider maximal-entanglement EA stabilizer codes, where SI is trivial, in the following example.
Example 4. Solving the integer program, we eliminate the existence of [[4, 2, 3; 2]], [[5, 3, 3; 2]], [[5, 2, 4; 3]], [[6, 3, 4; 3]],
[[9, 2, 7; 7]], [[10, 2, 8; 8]], [[10, 3, 7; 7]], [[11, 3, 8; 8]], [[14, 2, 11; 12]], [[14, 3, 10; 11]], [[15, 2, 12; 13]], [[15, 3, 11; 12]], [[15, 8, 7; 7]],
[[15, 9, 6; 6]],[[16, 4, 11; 12]], [[17, 4, 12; 13]],[[20, 3, 15; 17]] EA stabilizer codes. The constraints from Theorem 16 are effective
in the case of maximal-entanglement EA stabilizer codes.
C. Nonexistence of [[5, 3, 3; 2]], [[4, 2, 3; 2]], [[5, 2, 4; 3]], and [[6, 3, 4; 3]] EA stabilizer Codes
A general method to prove or disprove the existence of a code of certain parameters is to use computer search over all
possibilities. It is applicable when the search space is small. Here we consider a general form of the check matrix of quantum
codes and use computer search to rule out the existence of some small EA stabilizer codes.

20

The parity-check matrix corresponding to a simplified stabilizer group S = hg1 , . . . , gn−k , h1 , . . . , hc i is defined as


τ (g1 )


..


.


τ (gn−k )

H=
 τ (h1 ) 




..


.
τ (hc )



0
In
with rank HΛ2n H T = 2c [52], where the superscript T means transpose and Λ2n = n×n
. Recall that τ : Gn →
In
0n×n
Z2n
2 is defined in (2).
Theorem 
2 in Ref. [53] states that a check matrix of a nondegenerate [[n, k, d; c]] code can be transformed into a standard
Is A D 0
form H =  0 C Is B , where Is is the s × s identity matrix and s ≥ d − 1. Since a maximal-entanglement EA
0 E 0 F
stabilizer code is nondegenerate, we can construct a check matrix in that form. The check matrix of an [[5, 3, 3; 2]] code, if it
exists, can be written as


1 0 ∗ ∗ ∗ 0 0 ∗ ∗ ∗
 0 1 ∗ ∗ ∗ 0 0 ∗ ∗ ∗ 

H = [HX |HZ ] = 
 0 0 ∗ ∗ ∗ 1 0 ∗ ∗ ∗ ,
0 0 ∗ ∗ ∗ 0 1 ∗ ∗ ∗
where a “ ∗ ” can be 0 or 1. The error syndromes of single-qubit Pauli errors Xi and Zj are the i-th column and j-th column
of HX and HZ , respectively. If the syndromes of Xi and Zi are sxi , and szi , respectively, then the syndrome of Yi is sxi + szi .
Our goal is to fill in the missing columns such that rank(HΛH T ) = 4 and each single-qubit Pauli error has a unique error
syndrome, since the minimum distance is three [54].
P3
Let the integer number corresponding to a column vector [a0 a1 a2 a3 ]T be i=0 a0 23−i . The columns 8, 4, 2, and 1 have
appeared in the above standard form, and hence so have the columns 10 and 5 (the syndromes of Y1 and Y2 ). The remaining
candidates are 3, 6, 7, 9, 11, 12, 13, 14, and 15. We group these columns as follows:
G1 : 3, 12, 15;
G4 : 6, 11, 13;

G2 : 3, 13, 14;
G5 : 7, 9, 14;

G3 : 6, 9, 15;
G6 : 7, 11, 12.

The three columns in any one of the six groups are candidates of the syndromes of Xi , Zi , and Yi for a fixed i. We further
divide these six groups into two non-overlapping sets: S1 = {G1 , G4 , G5 } and S2 = {G2 , G3 , G6 }. To fill in the missing
columns of H, we first choose a set Sj , and then choose two columns from each of the three groups in Sj . Consequently, the
total number of candidates for H is
 
3
2×(
× 2!)3 = 432.
2
We verified that none of them has rank(HΛH T ) = 4. Hence there is no [[5, 3, 3; 2]] EA stabilizer code.
The same technique shows that there are no [[4, 2, 3; 2]], [[5, 2, 4; 3]], or [[6, 3, 4; 3]] EA stabilizer codes.
D. Nonexistence of other EA stabilizer Codes
A maximal-entanglement EA code can also be uniquely defined by a logical group L. Like the check matrix, we can define
a logical matrix L corresponding to L with
rank(LΛ2n LT ) = 2k.
Thus maximal-entanglement EA codes are a special case of classical additive quaternary code [7], [47].
Lemma 18. An upper bound on the minimum distance of a classical (n, 22k ) additive quaternary code is an upper bound on
the minimum distance of an [[n, k; n − k]] EA stabilizer code.
A table of upper bounds on the minimum distance of additive quaternary codes for length n ≤ 13 is given in [55], [56].
From that table, we learn that there are no [[11, 4, 7; 7]], [[12, 5, 7; 7]], [[12, 7, 5; 5]], [[13, 6, 7; 7]], [[13, 7, 6; 6]], or [[13, 8, 5; 5]]
EA stabilizer codes. As pointed out in [28], there is no [[15, 5, 9; 10]] EA stabilizer code since there is no (15, 210 , 9) additive
quaternary code [57].
Lemma 19. An upper bound on the minimum distance of a classical (n, 22k ) additive quaternary code is an upper bound on
the minimum distance of an (n + 1, 22(k+1) ) additive quaternary code, and hence an upper bound on the minimum distance
of an [[n + 1, k + 1; n − k]] EA stabilizer code.

21

n\k
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
n\k
11
12
13
14
15
16
17
18
19
20

1
3
3
5
5
7
7
9
9
11
11
13
13
15
15
17
17
19
19
10
2
2
3
4
4
5
6
6-7
7
7-8

2
2
2
3
4
5
6
6
7
8
9
10
10
11
12
13
14
14
15
11

3

4

5

6

7

8

9

1
2
3
4
5
6
6
7
8
9
9
10
11
12
13
13-14
14
12

2
2
3
4
5
6
6
7
8
8
9-10
10
11
11-12
12-13
13
13

1
2
3
4
5
6
6
7
7-8
8
9
9-10
10-11
11
12
14

2
2
3
4
5
5-6
6
6-7
7-8
8
8-9
9-10
10-11
11-12
15

1
2
3
4
4
5
6
6-7
7-8
7-8
8-9
8-9
9-10
16

2
2
3
4
4
5
6
6-7
7-8
8-9
8-9
8-10
17

1
2
3
4
4
5
6
6-7
7-8
8
8-9
18

1
2
3
4
4
5
5-6
6-7
6-7

2
2
3
4
4
5
5-6
6-7

1
2
3
3-4
4
5
5-6

2
2
3
3
4
5

1
2
3
3
4

2
2
3
3

1
2
2

2
2

TABLE II: Upper and lower bounds on the minimum distance of any [[n, k, d; n − k]] maximal-entanglement EA stabilizer
codes.
Lemma 19 is because that an (n + 1, 22(k+1) ) code has the same number of parity checks as an (n, 22k ) code. Hence there
are no [[14, 7, 7; 7]], [[14, 8, 6; 6]], or [[14, 9, 5; 5]] EA stabilizer codes.
E. Existence of other EA stabilizer Codes
We say an [[n, k, d; c]] EA stabilizer code is optimal if d achieves any upper bound on the minimum distance for fixed
n, k, c. By constructing check matrices as in the proof of nonexistence of [[5, 2, 4; 3]] EA stabilizer codes in Subsec. V-C, we
found optimal EA stabilizer codes with the following parameters: [[10, 5, 5; 5]], [[11, 7, 4; 4]], [[15, 12, 3; 3]], and [[15, 11, 4; 4]].
By the EA stabilizer code construction in [18], the [9, 4, 5] linear quaternary code can be transformed into a [[9, 4, 5; 5]]
EA stabilizer code, which is optimal. In the same way, we obtain the following EA stabilizer codes: [[9, 5, 4; 4]], [[10, 4, 6; 6]],
[[11, 6, 5; 5]], [[11, 5, 6; 6]], [[11, 4, 6; 7]], [[12, 8, 4; 4]], [[12, 5, 6; 7]], [[12, 2, 9; 10]], [[13, 2, 10; 11]], [[13, 6, 6; 7]], [[14, 7, 6; 7]],
and [[14, 8, 5; 6]]. A [[14, 6, 6; 8]] follows naturally. By deleting the fourth column and the 18-th column of the check matrix of
the [[14, 8, 5; 6]] code, we obtain a [[13, 7, 5; 6]] EA stabilizer code. From the [12, 6, 6] linear quaternary code, we can obtain
a [[12, 5, 6; 5]] EA stabilizer code. By adding two more ebits, we obtain a [[12, 5, 6; 7]] EA stabilizer code.
Using the circulant construction in [47], we found an optimal [[11, 3, 7; 8]] EA stabilizer code. We also obtained a [[15, 5, 8; 10]]
and a [[15, 6, 7; 9]] EA stabilizer code, which improves the lower bounds on minimum distance for fixed n, k, c.
Finally, several optimal maximal-entanglement EA stabilizer codes have been constructed from classical quaternary zeroradical codes in [28].
The existence of these codes demonstrate that the corresponding linear programming bounds are tight.
F. Table of Lower and Upper Bounds on the Minimum Distance of Maximal-Entanglement EA stabilizer Codes
Combining the results in the previous subsections, we improved the table of lower and upper bounds on the minimum
distance of maximal-entanglement EA stabilizer codes for n ≤ 20 ([23], [28]) in Table II.

22

VI. D ISCUSSION
We have discussed general EA quantum codes, including nonadditive codes, and proposed their algebraic linear programming
bounds, including Singleton-type, Hamming-type, and the first-linear-programming-type bounds. The degenerate and nondegenerate bounds differ for some δ when degeneracy exists. It is known that degenerate EA stabilizer codes can violate the
(nondegenerate) Hamming bound. Can we construct such a family of EA stabilizer codes with R > 0? Another interesting
question is: are there families of degenerate [[n, k, d; c]] EA quantum codes with R > 0, ρ > 0 and 1/3 < δ < 0.75 that
violate the conventional first linear programming bound? We can also consider the case of imperfect ebits, which should be
similar to the study in [26]. Finally, these results could be strengthened in the case of linear EA stabilizer codes [58], [59].
We provided a refined Singleton bound for EA quantum codes that works for d > (n + 2)/2; however, it is not monotonic
and may not fully characterize the case of large c. A better Singleton bound for EA stabilizer codes with d > (n + 2)/2
remains open.
In the setting of usual EA quantum codes, it is assumed that Bob’s qubits are error-free. Thus we chose in Theorem 5 a
polynomial of the form
c
Y
f (x, y) = F (x)
(y − j),
j=1

where F (x) is a polynomial that is used to derive a certain upper bound for general stabilizer codes. The case that Bob’s
qubits are imperfect [53] can be developed similarly to the split bounds for data-syndrome codes [26], where two types of
errors are considered on two disjoint sets of locations.
The linear programming bounds for small quantum codes are improved. The additional constraints in Theorem 16 are
especially effective for maximal-entanglement EA stabilizer codes, where the generators of a symplectic subgroup or a logical
group are of type I or type III. However, they are not that helpful in the case of standard stabilizer codes, where the normalizer
groups often have weight distributions of type II. It is possible that the linear programming bounds for standard stabilizer
codes can be improved for n ≥ 30.
The EA stabilizer code table in [23] has been significantly improved. Most of the check matrices of the EA stabilizer codes
constructed in this article are omitted because of limited space. All of the gaps between the lower bound and upper bound in
Table II are now closed for d ≤ 5 or n ≤ 8. The grouping techniques used in [56] may be generalized to find upper bounds
on classical additive quaternary codes for n = 15 to 20, which can be used as bounds on maximal-entanglement EA stabilizer
codes by Lemma 18.
Other types of split weight enumerators can be introduced into the linear programm for EA stabilizer codes. However,
they usually induce too many variables so that the integer program is untraceable when n becomes large. The refined weight
enumerator (52) has already introduced too many variables for large n.
The method used in Subsec. V-C is difficult to apply for larger codes because the computational complexity grows
exponentially. Perhaps we can construct standard stabilizer codes using this grouping method together with Theorem 2 in [53].
The approach here can be applied to other type of quantum codes, for example, the data-syndrome quantum codes [60],
[26], [61], which are codes in the space Fn4 × Fm
2 . Split weight enumerators for these codes can be derived easily. We can also
apply these techniques to other asymmetric quantum codes.
ACKNOWLEDGMENT
We thank Todd Brun for helpful discussion. We are grateful to Markus Grassl for his comments and suggestions that help
to improve this paper.
R EFERENCES
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12]
[13]
[14]
[15]
[16]

P. W. Shor, “Scheme for reducing decoherence in quantum computer memory,” Phys. Rev. A, vol. 52, no. 4, pp. 2493–2496, 1995.
A. Ekert and C. Macchiavello, “Quantum error-correction for communication,” Phys. Rev. Lett., vol. 77, no. 12, pp. 2585–2588, 1996.
E. Knill and R. Laflamme, “A theory of quantum error-correcting codes,” Phys. Rev. A, vol. 55, no. 2, pp. 900–911, 1997.
A. M. Steane, “Multiple particle interference and quantum error correction,” Proc. R. Soc. London A, vol. 452, pp. 2551–2576, 1996.
D. Gottesman, “Stabilizer codes and quantum error correction,” Ph.D. dissertation, California Institute of Technology, Pasadena, CA, 1997.
A. R. Calderbank, E. M. Rains, P. W. Shor, and N. J. A. Sloane, “Quantum error correction and orthogonal geometry,” Phys. Rev. Lett., vol. 78, no. 3,
pp. 405–408, 1997.
——, “Quantum error correction via codes over GF (4),” IEEE Trans. Inf. Theory, vol. 44, no. 4, pp. 1369–1387, 1998.
M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information. Cambridge, UK: Cambridge University Press, 2000.
A. E. Ashikhmin, A. M. Barg, E. Knill, and S. N. Litsyn, “Quantum error detection .I. statement of the problem,” IEEE Trans. Inf. Theory, vol. 46,
no. 3, pp. 778–788, May 2000.
——, “Quantum error detection .II. bounds,” IEEE Trans. Inf. Theory, vol. 46, no. 3, pp. 789–800, May 2000.
F. Gaitan, Quantum error correction and fault tolerant quantum computing. Boca Raton, FL: CRC Press, 2008.
D. A. Lidar and T. A. Brun, Eds., Quantum Error Correction. Cambridge University Press, October 2013.
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes. Amsterdam, The Netherlands: North-Holland, 1977.
P. Delsarte, “An algebraic approach to the association schemes of coding theory,” Philips Res. Rep. Suppl., vol. 10, 1973.
A. Ashikhmin and S. Litsyn, “Upper bounds on the size of quantum codes,” IEEE Trans. Inf. Theory, vol. 45, no. 4, pp. 1206 – 1215, 1999.
P. Shor and R. Laflamme, “Quantum analog of the MacWilliams identities for classical coding theory,” Phys. Rev. Lett., vol. 78, no. 8, pp. 1600–1602,
Feb 1997.

23

[17] E. M. Rains, “Quantum weight enumerators,” IEEE Trans. Inf. Theory, vol. 44, no. 4, pp. 1388 – 1394, 1995.
[18] T. A. Brun, I. Devetak, and M.-H. Hsieh, “Correcting quantum errors with entanglement,” Science, vol. 314, pp. 436–439, 2006.
[19] M.-H. Hsieh, T. A. Brun, and I. Devetak, “Entanglement-assisted quantum quasi-cyclic low-density parity-check codes,” Phys. Rev. A, vol. 79, p. 032340,
2009.
[20] M.-H. Hsieh, W.-T. Yen, and L.-Y. Hsu, “High performance entanglement-assisted quantum LDPC codes need little entanglement,” IEEE Trans. Inf.
Theory, vol. 57, no. 3, pp. 1761–1769, 2011.
[21] Y. Fujiwara, D. Clark, P. Vandendriessche, M. De Boeck, and V. D. Tonchev, “Entanglement-assisted quantum low-density parity-check codes,” Phys.
Rev. A, vol. 82, p. 042338, Oct 2010.
[22] M. M. Wilde, M. H. Hsieh, and Z. Babar, “Entanglement-assisted quantum turbo codes,” IEEE Transactions on Information Theory, vol. 60, no. 2, pp.
1203–1222, Feb 2014.
[23] C.-Y. Lai, T. A. Brun, and M. M. Wilde, “Duality in entanglement-assisted quantum error correction,” IEEE Trans. Inf. Theory, vol. 59, no. 6, pp.
4020–4024, 2013.
[24] ——, “Dualities and identities for entanglement-assisted quantum codes,” Quant. Inf. Proc., pp. 1–34, 2013.
[25] J. Shin, J. Heo, and T. A. Brun, “Entanglement-assisted codeword stabilized quantum codes,” Phys. Rev. A, vol. 84, p. 062321, Dec 2011.
[26] A. Ashikhmin, C.-Y. Lai, and T. A. Brun, “Correction of data and syndrome errors by stabilizer codes,” in Proc. IEEE Int. Symp. Inf. Theory, 2016, pp.
2274 – 2278.
[27] E. M. Rains, “Quantum shadow enumerators,” IEEE Trans. Inf. Theory, vol. 45, no. 7, pp. 2361 – 2366, 1999.
[28] L. Lu, R. Li, L. Guo, and Q. Fu, “Maximal entanglement entanglement-assisted quantum codes constructed from linear codes,” Quant. Inf. Proc., vol. 14,
no. 1, pp. 165–182, 2015.
[29] C. H. Bennett, D. P. DiVincenzo, J. A. Smolin, and W. K. Wootters, “Mixed state entanglement and quantum error correction,” Phys. Rev. A, vol. 54,
no. 5, pp. 3824–3851, 1996.
[30] E. M. Rains, R. H. Hardin, P. W. Shor, and N. J. A. Sloane, “A nonadditive quantum code,” Phys. Rev. Lett., vol. 79, pp. 953–954, Aug 1997.
[31] M. B. Ruskai, “Pauli exchange errors in quantum computation,” Phys. Rev. Lett., vol. 85, pp. 194–197, Jul 2000.
[32] J. A. Smolin, G. Smith, and S. Wehner, “Simple family of nonadditive quantum codes,” Phys. Rev. Lett., vol. 99, p. 130505, Sep 2007.
[33] S. Yu, Q. Chen, C. H. Lai, and C. H. Oh, “Nonadditive quantum error-correcting code,” Phys. Rev. Lett., vol. 101, p. 090501, Aug 2008.
[34] A. Cross, G. Smith, J. Smolin, and B. Zeng, “Codeword stabilized quantum codes,” IEEE Trans. Inf. Theory, vol. 55, no. 1, pp. 433–438, Jan 2009.
[35] Y. Ouyang, “Permutation-invariant quantum codes,” Phys. Rev. A, vol. 90, p. 062317, Dec 2014.
[36] C. Y. Lai, M. H. Hsieh, and H. F. Lu, “On the Macwilliams identity for classical and quantum convolutional codes,” IEEE Trans. Commun., vol. 64,
no. 8, pp. 3148–3159, Aug 2016.
[37] V. Levenshtein, “Krawtchouk polynomials and universal bounds for codes and designs in Hamming spaces,” IEEE Trans. Inf. Theory, vol. 41, no. 5, pp.
1303–1321, Sep 1995.
[38] M. Aaltonen, “Linear programming bounds for tree codes,” IEEE Trans. Inf. Theory, vol. 25, no. 1, pp. 85–90, Jan 1979.
[39] A. Ketkar, A. Klappenecker, S. Kumar, and P. K. Sarvepalli, “Nonbinary stabilizer codes over finite fields,” IEEE Trans. Inf. Theory, vol. 52, no. 11,
pp. 4892–4914, 2006.
[40] J. Preskill, Physics 229: Advanced Mathematical Methods of Physics - Quantum Computation and Information. California Institute of Technology,
1998.
[41] W. K. Wootters and W. H. Zurek, “A single quantum cannot be cloned,” Nature, vol. 299, pp. 802–803, October 1982.
[42] M. Grassl, “Entanglement-assisted quantum communication beating the quantum Singleton bound,” 2017, in preparation; talk at AQIS 2016, Taiwan.
[43] G. Bowen, “Entanglement required in achieving entanglement-assisted channel capacities,” Phys. Rev. A, vol. 66, p. 052313, 2002.
[44] T. Brun, I. Devetak, and M.-H. Hsieh, “Catalytic quantum error correction,” IEEE Trans. Inf. Theory, vol. 60, no. 6, pp. 3073–3089, June 2014.
[45] Z. Li and L. Xing, “On a problem concerning the quantum Hamming bound for impure quantum codes,” IEEE Trans. Inf. Theory, vol. 56, no. 9, pp.
4731–4734, Sept 2010.
[46] R. Li, L. Guo, and Z. Xu, “Entanglement-assisted quantum codes achieving the quantum Singleton bound but violating the quantum Hamming bound,”
Quant. Inf. Comp., vol. 14, no. 13-14, pp. 1107–1116, Oct. 2014.
[47] C.-Y. Lai and T. A. Brun, “Entanglement increases the error-correcting ability of quantum error-correcting codes,” Phys. Rev. A, vol. 88, p. 012320, Jul
2013.
[48] R. McEliece, E. R. Rodemich, H. Rumsey, and L. Welch, “New upper bounds on the rate of a code via the Delsarte-Macwilliams inequalities,” IEEE
Trans. Inf. Theory, vol. 23, no. 2, pp. 157–166, Mar 1977.
[49] D. Fattal, T. S. Cubitt, Y. Yamamoto, S. Bravyi, and I. L. Chuang, “Entanglement in the stabilizer formalism,” 2004. [Online]. Available:
http://arxiv.org/abs/quant-ph/0406168
[50] I. Wolfram Research, Mathematica, 8th ed. Champaign, Illinois: Wolfram Research, Inc., 2010.
[51] M. Grassl, “Bounds on the minimum distance of linear codes and quantum codes,” accessed on 2010-12-01. [Online]. Available: http://www.codetables.de/
[52] M. M. Wilde and T. A. Brun, “Optimal entanglement formulas for entanglement-assisted quantum coding,” Phys. Rev. A, vol. 77, p. 064302, 2008.
[53] C.-Y. Lai and T. A. Brun, “Entanglement-assisted quantum error-correcting codes with imperfect ebits,” Phys. Rev. A, vol. 86, p. 032319, Sep 2012.
[54] C.-Y. Lai and C.-C. Lu, “A construction of quantum stabilizer codes based on syndrome assignment by classical parity-check matrices,” IEEE Trans.
Inf. Theory, vol. 57, no. 3, pp. 7163 – 7179, 2011.
[55] A. Blokhuis and A. E. Brouwer, “Small additive quaternary codes,” European Journal of Combinatorics, vol. 25, pp. 161 – 167, 2004.
[56] J. Bierbrauer, Y. Edel, G. Faina, S. Marcugini, and F. Pambianco, “Short additive quaternary codes,” IEEE Trans. Inf. Theory, vol. 55, no. 3, pp. 952 –
954, 2009.
[57] G. F. S. M. F. P. Daniele Bartoli, Juergen Bierbrauer, “The nonexistence of an additive quaternary [15,5,9] code,” 2013. [Online]. Available:
arXiv:1308.2108
[58] L. Guo and R. Li, “Linear Plotkin bound for entanglement-assisted quantum codes,” Phys. Rev. A, vol. 87, p. 032309, Mar 2013.
[59] R. Li, X. Li, and L. Guo, “On entanglement-assisted quantum codes achieving the entanglement-assisted Griesmer bound,” Quant. Inf. Proc., vol. 14,
no. 12, pp. 4427–4447, 2015.
[60] A. Ashikhmin, C.-Y. Lai, and T. A. Brun, “Robust quantum error syndrome extraction by classical coding,” in Proc. IEEE Int. Symp. Inf. Theory, 2014,
pp. 546–550.
[61] Y. Fujiwara, “Ability of stabilizer quantum error correction to protect itself from its own imperfection,” Phys. Rev. A, vol. 90, p. 062304, Dec 2014.

