{'fraction_non_alphanumeric': 0.04705046197583511, 'fraction_numerical': 0.021535181236673775, 'mean_word_length': 3.583387622149837, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Upper Bounds on the Size of Quantum Codes

Several upper bounds on the size of quantum codes are derived using the linear programming approach. These bounds are strengthened for the linear quantum codes.


Introduction
Recently P.Shor presented a polynomial time algorithm for factoring large numbers on a quantum computer [19]. After this the interest in quantum computations grew dramatically. One of the crucial problems in implementation of quantum computer appeared to be the one of eliminating errors caused by decoherence and inaccuracy. Unlike the classical information, the quantum information can not be duplicated [20], [7]. Since error correcting codes protect classical information by duplicating it, their application for quantum information protection seemed to be impossible. However, in [18] P.Shor has shown that quantum error correction codes do exist and presented the first example of such one-error correcting code encoding one qubit to nine qubits. In [10] M.Knill and R. Laflamme formulated necessary and sufficient conditions for an error to be detectable by a given quantum 1 code, and thus introduced the notion of the minimum distance of a quantum code. In [17] P.Shor and R.Laflamme showed that, similarly to the classical codes, the quantum codes have enumerators related by the MacWilliams identities. Properties of quantum enumerators were extensively studied by E. Rains [14], [15], [16]. In particular, he showed that the minimum distance of the quantum code is determined by its enumerators. In [2], [3] a strong connection between a big class of quantum error-correction codes, which can be seen as an analog of classical linear codes, and self-orthogonal codes over GF (4) was found.
A quantum code, say Q, of length n and dimension K, denoted as ((n, K)) code, is a K−dimensional subspace of the Hilbert space C 2 n . During transmission through a channel a code word can be altered by an error. In general a quantum channel error is an operator E acting on C 2 n . If a codeword v ∈ Q has been effected by an error E then v becomes Ev.
Here we consider one of the most popular channel models -the completely depolarized channel. In this model any error operator E can be represented in the form of the tensor product of Pauli matrices and two by two identity matrices and The error σ x is called the flip error, and the error σ z is called the phase error. Error operators acting on C 2 n form the extraspecial group of order 2 2n+1 . The number of nonidentity matrices in the tensor product (1) is called the weight of E and is denoted by wt(E). A quantum code can detect an error E if and only if [10] v where v i and v j are any two orthogonal vectors from the code. A quantum code has the minimum distance w and is denoted as ((n, K, w)) code if it can detect any error of weight less than or equal to w − 1. Linear codes play a special role in the classical coding theory. Similarly in the quantum coding theory there exist the, so called, stabilizer codes. They can be considered as an analog of the classical linear codes. The formal definition of the quantum stabilizer codes is following. A quantum code Q is called stabilizer code if there exists a subgroup E of the extraspecial group such that for Ev = v for any v ∈ Q and any E ∈ E. In other words, Q forms an eigenspace of E. If the group E has the order 2 t then dim(Q) = 2 n−t and so the dimension of a stabilizer code is always equal to a power of 2. A nice property of the quantum stabilizer codes is that they are strongly related to classical self-orthogonal codes over GF (4) [2] [3]. Namely, there exists a quantum stabilizer [[n, k]] = ((n, 2 k )) code Q with the minimum distance w if and only if there exists a group self-orthogonal code C of length n, cardinality |C| = 2 n−k such that w = min{wt(v) : v ∈ C ⊥ \ C}, where C ⊥ is the dual to C code with respect to the trace inner product. The trace inner product, denoted as * , of vectors v and u is defined as follows where the bar denotes conjugation in GF (4). If code C, assosiated with quantum stabilizer code, is linear over GF (4), then Q is called linear stabilizer code, or just linear quantum code.
A Gilbert-Varshamov type bound was obtained in [2].
Theorem 1 [4] There exist quantum codes of length n and dimension K such that is the binary entropy function and log is the base 2 logarithm.
The goal of the present paper is to obtain upper asymptotic bounds on the minimum distance of an arbitrary quantum code using linear programming approach and some strengthenings of the bounds for linear quantum codes. For earlier known upper bounds see Laflamme and Knill [10], Rains [16], Cleve [5].
The paper is organized as follows. In section 2 we prove the key theorem that allows us to apply the linear programming approach to obtaining bounds for quantum codes. In section 3 we give a short description of properties of Krawtchouk polynomials that we will need later. In section 4.1 and 4.2 we use the key theorem to obtain Singleton and Hamming type bounds for arbitrary quantum codes. In section 4.3 we strengthen the Hamming type bound for the linear quantum codes.

The key inequality
In this section we obtain the key inequality allowing us to reduce the problem of upperbounding the size of codes to a problem of finding polynomials with special properties.
Like in the case of classical codes one can introduce the notion of enumerators of a quantum ((n, K)) code. An ((n, K)) quantum code Q has two enumerators [17], [14] Tr(EP )Tr(EP ), where E is an error operator in C 2 n . It is shown in [17], [14] In [17], [14] it is also shown that the minimum distance of Q equals the maximum integer w such that 2 n , and thus we are interested in estimating the value w for given values n and S.
Let f (x) be a polynomial of degree at most n, Let, moreover, all the coefficients f i be nonnegative, f (x) > 0 for x = 0, . . . , w − 1, and f (x) ≤ 0 for x = w, . . . , n. Then Thus, We formulate now the result as a theorem.
Theorem 2 Let Q be an ((n, K, w)) quantum code. Let

Krawtchouk polynomials
Here we survey some properties of Krawtchouk polynomials. We consider the quaternary case. In this case the Krawtchouk polynomials are defined as follows: 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 The following property (see [12]Chap. 5, Exercise 41) is important: The Krawtchouk polynomials satisfy a recurrent relation, Some useful values of the Krawtchouk polynomials: We will also need Christoffel-Darboux formula for binary Krawtchouk polynomials

Upper bounds
In what follows we present several bounds derived from Theorem 2.

Singleton type bound
Choose in Theorem 2 Then Considering the ratio we find that it is greater than 1 if w ≤ (n + 2)/2. So, the values r(x) are decreasing, and we have the following theorem.
Note that though this bound has been already derived in [10], [16], the proof presented here is different and so could be of interest.

Hamming type bound
Proof The proof of the lemma is a straightforward generalization of the proof of the similar expression in the binary case (see e.g. [11](A.19)). ✷ Using the lemma, we get This yields Taking into account that and denoting ξ = x/n, ν = s/n, and τ = e/n, we get Taking derivative of the last expression, we get It is not difficult to check that this function has only one root on the interval max{0, τ − ξ} ≤ ν ≤ τ − ξ/2. Let α(τ, ξ) be the root of the function in the interval. Then we can estimate 1 n log f (x) as follows To obtain an estimate on f x we need bounds on values of Krawtchouk polynomials. We will also need a bound on r e , the smallest root of P e (j). For t growing linearly in n and e = τ n (see e.g. [8]) The next observation is a generalization of a similar fact in the binary case [9].
Proof Like in the binary case (see, e.g. [12, Lemma 36]) one can show that for ξ < ξ t P t (j + 1) Taking logarithm on both sides, applying this recursively to P t (0) = n t 3 t , and approximating the sum by the integral, we get the claim. ✷ Notice, that the integral in Lemma 2 can be expressed explicitly, namely Using Lemma 2, we can estimate 1 n log f x as follows 1 n log f x = 2τ log 3 + 2H(τ ) Using (7) and (4), we get a Hamming type bound log K n ≤ max 0≤ξ≤δ 1 + ξ + ξH 2ξ + 2α(τ, ξ) − 2τ ξ where δ = 2τ = w/n. Analytical computations with Maple show that this function achieves its maximum at ξ = 0 for any δ ≤ ξ e . From this condition and (5) it follows that δ ≤ ξ e in the interval 0 ≤ δ ≤ a, a ≈ 0.34. Note that when δ ≥ ξ e the coefficient f x can be equal to zero and the bound tends to infinity.
So we conclude that the conventional Hamming bound is valid when δ ≤ 0.34. Theorem 4 If Q is an ((n, K)) quantum code and δ ≤ ξ e , then Notice that would the Hamming type bound be proved for the total range, the value δ n would be equal approximately to 0.38 when log(K)/n = 0. This is worse than the bound δ/n ≤ 1 3 derived by Rains in [16]. We labeled quantum Hamming bound on figure 1 by "H". On the figure  1 we also present so called the first and the secon bounds (bounds LP1 and LP2), though for the time being it is not proved that they are valid. We shall prove in the next section that in the binary case the conventional first linear programming bound is valid for quantum codes.

The First Linear Programming Bound
In the present version of the paper we confine ourselves by the binary case. Work on the quaternary case is under process.
We formulate the problem the same as in the quaternary case. We have numbers B i and B ⊥ i such that 0 ≤ B i ≤ B ⊥ i , B i and B ⊥ i are connected by binary MacWilliams identities, and Like in the quaternary case we are interested in an upper bound for the value S given n and w. Let This polynomial allows to get the so called first linear programming bound for classical codes [11]. Denote by x Using identity , we get Suppose now that t and j are even numbers (in other cases arguments are similar). Estimate the sum in the last expression by the term for i = t.
Then we have and P t+1 (x) by P x (t + 1) , we get Now using the relation [9] , we get Using the estimate [9] where ξ = x/n and τ = t/n, we have Analytical computations with Maple show that for τ ≥ 0.11 this function achieves its maximum at ξ = 0. Since δ = w n = 1 2 − τ (1 − τ ) we have the following theorem.
Note that we are interested in an estimate of w for all S such that 1 n log S ≥ 0.5. Note also that when δ ≤ 0.1865 then 1 n log S ≈ 0.501. So for all 1 ≥ 1 n log S ≥ 0.501 the conventional first linear programming bound is valid. 13

Strengthening in Linear Case
Let now Q be a stabilizer quantum code with associated self-orthogonal code C over GF (4). Recall that if dim(Q) = 2 k then |C| = 2 n−k .
A generator matrix of C can be written in the form [3] G =    where B j is a binary matrix, A j is an arbitrary matrix, and ω is an element of GF(4) of order 3. We will say that G defines a code of type 4 k 0 2 k 1 . If in some l coordinates a group code, say D, of length n contains only 0-s and α-s, α ∈ GF(4), α = 0, then we will say that D is a mixed code of lengths l and n − l. Note that if C is a code of type 4 k 0 2 k 1 of length n then corresponding quantum stabilizer code Q is an

Lemma 3
The minimum distance w of Q is not greater than the minimum distance of the optimal group mixed code of lengths k 1 and n − k 0 − k 1 and cardinality 2 2n−4k 0 −2k 1 . In particular i) if k 1 = 0 then w is not greater than the minimum distance of the optimal group code of length (n + k)/2 and cardinality 4 k .
ii) if k 1 < 2n−4k 0 3 = 2k then w is not greater than the minimum distance of the optimal group code of length n+k−k 1 2 and cardinality 2 2k−k 1 .

Proof
Let G C be a generator matrix of the code C written in the form (8).
Since C ⊆ C ⊥ we can append some rows to the matrix G C to get a generator matrix of C ⊥ . That is Let us call the code generated by the matrix G ′ a complementary code of C to C ⊥ . It is clear that the minimum distance of a complementary code has to be not less than w = min{wt(v) : v ∈ C ⊥ \ C}. Due to the structure (8) of the matrix G we can make elements of G ′ on the first k 0 positions be equal to 0 and elements on the next k 1 positions be equal to 0 or ω. So G ′ will have the form[0 D 1 D 2 ] where D 1 is an 2n − 4k 0 − 2k 1 × k 1 matrix consisting from 0-s and ω-s and D 2 is is an arbitrary 2n − 4k 0 − 2k 1 × n − k 0 − k 1 matrix.
i) Follows from the previous. ii) In the case where A 1 is an k 1 × k 1 matrix consisting form 0-s and ω-s, B 1 and B 2 are arbitrary k 1 × n − k 0 − k 1 and 2n − 4k 0 − 3k 1 × n − k 0 − k 1 matrices. Since the subcode with the generator matrix [0 0 B 2 ] has length n − k 0 − k 1 , dimension 2n − 4k 0 − 3k 1 and its minimum distance has to be not less than w the assertion follows. ✷ Let D be a mixed code of lengths l and n − l and dimension k. To get bounds for Q we have to get bound for the classical mixed code D. Plotkin and Hamming type bounds for mixed codes can formulated as follows.

Proof
Let M be an array of all codewords of D. The total number of nonzero entries of M is equal to l · 2 k−1 + (n − l) · 3 · 2 k−2 . Since the number of nonzero codewords in D is 2 k − 1 we get the assertion. and assertion follows. ✷ Combining Lemma 4 and Lemma 3, we get a Plotkin type bound for a code of given type 4 k 0 2 k 1 .
Combining Lemma 5 and Lemma 3, we get Hamming type bound for a code of given type 4 k 0 2 k 1 . .
Let now k 1 = 0. For example k 1 = 0 if the code C is linear. In this case a complementary code is not a mixed code. So applying the asymptotic version of the second linear programming bound [1] to this code we get a bound on the minimum distance of the code Q. One can see (bound S on fig.1) that this bound is better than the first linear programming and Hamming bounds on some interval.
Let k 1 > 0 and n − k 1 < k < k 1 /2. Then according to Lemma 3 we can estimate the minimum distance of Q as the minimum distance of a group of length n+k−k