{'fraction_non_alphanumeric': 0.07834360471402314, 'fraction_numerical': 0.01755865498972862, 'mean_word_length': 3.274517053332101, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 53, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Information Rates Achievable with Algebraic Codes on Quantum Discrete Memoryless Channels

The highest information rate at which quantum error-correction schemes work reliably on a channel, which is called the quantum capacity, is proven to be lower bounded by the limit of the quantity termed coherent information maximized over the set of input density operators which are proportional to the projections onto the code spaces of symplectic stabilizer codes. Quantum channels to be considered are those subject to independent errors and modeled as tensor products of copies of a completely positive linear map on a Hilbert space of finite dimension, and the codes that are proven to have the desired performance are symplectic stabilizer codes. On the depolarizing channel, this work's bound is actually the highest possible rate at which symplectic stabilizer codes work reliably.


I. Introduction
The problem of determining the capacity of quantum channels was posed by Shor [1] in the first paper on quantum error-correcting codes (quantum codes, or codes, hereafter). He discussed it in the context of preservation of quantum states, which are to be used for quantum computation in the presence of quantum noise. There is a known upper bound on the quantum capacity based on the quantity called coherent information, and some authors conjecture that this bound is tight [2], [3, Section VI], [4], [5], [6]. On the other hand, known lower bounds appear to have left much room for improvement. For example, on the capacity of the depolarizing channel, which suffers uniform depolarization and can be specified by Kraus operators √ 1 − pI, p/3X, p/3Y, p/3Z with I and X, Y, Z being the identity and Pauli operators, respectively, the highest lower bound known is 1 − h(p) − p log 2 3 for a wide range of p, where h is the binary entropy function [7], [8], [9], [10], [11]. Shor and Smolin [12] argued this bound is not tight showing the existence of concatenated quantum codes that slightly go beyond it for a limited range of p, which revealed a remarkable feature of the issue of the quantum capacity. While their work and the subsequent analysis of DiVincenzo and these authors [13] abounded with suggestions, their code construction was apparently restricted, and explorations into the general nature behind their code construction and further analysis were awaited [13]. The aim of this work is to give a more general lower bound which partially closes the gap between the upper and lower bounds, at least qualitatively. The bound to be presented is expressed as the limit of coherent information maximized over the set of input density operators which are proportional to the projections onto the code spaces of standard algebraic quantum codes. This limit closely resembles the known upper bound on the capacity, which is the one defined in the same way but with the restriction on input density operators removed. The result is obtained by developing Shor and Smolin's idea on the basis of the geometric property of quantum codes, and incorporating a methodology from classical information theory. In other words, this work establishes an exponential lower bound on the highest fidelity of concatenated quantum codes used on a memoryless channel in an elementary enumerative manner employing the method of types [14], [15]. This fidelity bound then gives the new lower bound on the quantum capacity of memoryless channels. Unlike Shor and Smolin's or DiVincenzo and these authors' coding schemes [12], [13], the codes in this work do not rely on purification protocols and fall in the class of standard 'in-place' quantum ones called stabilizer codes, which would be desirable for its simplicity of coding processes and the possibility to be used in quantum computation [16], [17], [8]. Moreover, for the depolarizing channel, which has often been adopted as a channel model for analysis of quantum codes, it will be shown that this bound on the capacity is the highest possible that can be attained with standard quantum codes.
Concatenated quantum codes are, in a sense, analogous to classical concatenated codes [18] and form a subclass of the class of standard algebraic quantum codes, which are called stabilizer, additive or symplectic codes in the literature [19], [8], [20], [21], [22], [10]. While the term stabilizer codes is prevailing, it would rather be called symplectic (quantum) codes or symplectic stabilizer codes with emphasis on the role of symplectic geometry in this work. A symplectic quantum code is a simultaneous eigenspace of a set of commuting operators, which is called a stabilizer. A stabilizer is obtained by constructing a code over a finite field which is self-orthogonal with respect to a symplectic bilinear form and then transforming it into operators on a Hilbert space through a one-to-one correspondence (a projective representation). A stabilizer of a concatenated quantum code, which will simply be called a concatenated code in what follows, is obtained by concatenating two such self-orthogonal codes and putting it through the representation. We refer to these two codes, or the corresponding quantum codes, an inner code and an outer one following Forney's terminology [18]. Shor and Smolin's concatenated code uses an inner code with restricted parameters. Namely, their inner code is an [[n, k = 1]] code, where an [[n, k]] code is a 2 k -dimensional subspace of the tensor product of n copies of a two-dimensional Hilbert space. This paper develops DiVincenzo, Shor and Smolin's analysis [12], [13] to include that of concatenated codes with general inner [[n, k]] codes with 1 ≤ k ≤ n.
The argument below proceeds as follows. After stating the result (Section II), we first recapitulate the framework of symplectic codes in a self-contained manner assuming no formidable prerequisite such as knowledges on representation theory, though a few basic facts from geometric algebra [33], [34] are used (Section III). Then, concatenated codes are explicated in this framework (Section IV), and the lower bound on the capacity is proven in an elementary manner with the aid of the method of types (Section V and Appendix D). Thereafter, it is shown that this bound is the highest possible on the depolarizing channel if we restrict the coding schemes to symplectic stabilizer codes (Section VI). Finally, some remarks are given on the case of general channels and so on (Sections VII and VIII). Appendices are given to prove lemmas and a theorem.

II. Quantum Capacity and New Lower Bound
As usual, all quantum channels and decoding (state-recovery) operations in coding systems are described in terms of trace-preserving completely positive (TPCP) linear maps [35], [36], [37], [3], [38]. Given a Hilbert space H of finite dimension, let L(H) denote the set of linear operators on H. In general, every completely positive (CP) linear map M : L(H) → L(H) has an operator-sum representation M(ρ) = i∈I M i ρM † i with some M i ∈ L(H), i ∈ I [35], [36], [37], [38]. When M is specified by a set of operators {M i } i∈I in this way, we write M ∼ {M i } i∈I . 1 Hereafter, H denotes an arbitrarily fixed Hilbert space of dimension d, which is a prime number. A quantum memoryless channel is a TPCP linear map A : L(H) → L(H). A memoryless channel A is supposed to act on a state or a density operator ρ in L(H ⊗n ) as A ⊗n (ρ). A pair (C n , R n ) consisting of a subspace C n ⊆ H ⊗n and a TPCP linear map R n : L(H ⊗n ) → L(H ⊗n ), which is supposed to serve as a recovery operator, is called a (quantum) code, its information rate (or simply rate) is defined to be n −1 log d dim C n , and its performance is evaluated in terms of minimum fidelity [39], [13], [3] F (C n , R n A ⊗n ) = min |ψ ∈Cn where R n A ⊗n denotes the composition of A ⊗n and R n . Throughout, bras ·| and kets |· are assumed normalized. A subspace C n alone is also called a code assuming implicitly some recovery operator. For simplicity, we will work on a special class of channels that are specified as follows though the lower bound to be presented is applicable to general channels (Section VII). Fix an orthonormal basis where X, Z ∈ L(H) are Weyl's unitary operators defined by with ω being a primitive d-th root of unity [40], [41], [42], [43]. Observe the relation The set N = {N u } u∈X is a basis of L(H) and could be viewed as a generalization of the Pauli operators (including the identity). We will treat channels that can be written as A ∼ { P (u)N u } u∈X , which will be called Pauli channels or N-channels, where P is a probability distribution on X . From the basis . , x n ) ∈ X n . With this notation, we can write A ⊗n (ρ) = x∈X n P n (x)N x ρN † x for A ∼ { P (u)N u } u∈X , where for a probability distribution Q on a finite set Y, the product measure Q n is defined by Q n (y) = n i=1 Q(y i ), y = (y 1 , . . . , y n ) ∈ Y n . Since A ⊗n (ρ) = x∈X n P n (x)N x ρN † x can be viewed as the probabilistic mixture of states N x ρN † x with probabilities P n (x), we often say that an error N x occurs with probability P n (x) describing the action of the Pauli channel A.
We can define the capacity of a quantum channel as in classical information theory. Definition 1: Let F ⋆ n,k (A ⊗n ) denote the supremum of F (C, RA ⊗n ) such that there exists a code (C ⊆ H ⊗n , R) with log d dim C ≥ k, where n > 0 is an integer and k, 0 ≤ k ≤ n, is a real number. The supremum of nonnegative numbers R satisfying lim sup n→∞ F ⋆ n,Rn (A ⊗n ) = 1 is called the quantum capacity of A and denoted by C(A). ✸ Remarks. The term quantum capacity is used when one needs to distinguish it from other capacities (such as classical capacity) of a quantum channel [44]. Variations exist in definitions of capacity concepts. Especially, besides the definition of quantum capacity above, there exists a seemingly different one based on entanglement fidelity, but actually they are the same [3]. In the above definition, the stipulation lim sup n F ⋆ n,Rn (A ⊗n ) = 1 may be replaced by lim inf n F ⋆ n,Rn (A ⊗n ) = 1; by slightly modifying matter as in operator-sum representations.
the proof of Theorem 1 to be presented below, it easily follows that the main result holds true if the limit superior is replaced by the limit inferior. ✷ Given a probability distribution Q on Y × Z, we define Q by which is a marginal distribution of Q, and define ← − Q (·|u) by The classical Kullback-Leibler information (informational divergence or relative entropy) is denoted by D and (conditional) Shannon entropy by H. Specifically, for probability distributions P and Q on a finite set Y, we define D(P ||Q) by D(P ||Q) = u∈Y P (u) log d [P (u)/Q(u)] and H(Q) by H(Q) = − u∈Y Q(u) log d Q(u). In addition, for a stochastic matrix P (·|·), i.e., a set of probability distributions P (·|u), u ∈ Y, and a probability distribution p on Y, we define H(P |p) by which is called the entropy of P (·|·) conditional on p. By convention, we assume log(a/0) = ∞ for a > 0 and 0 log 0 = 0 log(0/0) = 0.
For a density operator ρ ∈ L(H ′ ) and a TPCP map where S(σ) denotes the von Neumann entropy of σ, I is the identity map on L(H ′ ), and |Ψ ∈ H ′′ ⊗H ′ is a purification of ρ [37], [3]. For consistency, we assume that all logarithms appearing in these entropic quantities are to base d throughout the paper. This work's main result is the next one. Theorem 1: Let the basis N = {N u } u∈X = {X i Z j } (i,j)∈X be specified as above. For a memoryless channel A ∼ { P (u)N u } u∈X , where P is a probability distribution on X , we have where Π C is the projection onto C and S n (N) is the set of symplectic stabilizer codes, the precise definition of which will be given in Definition 2 in Section III-A. ✸ After proving this, we argue that this bound is actually the 'conditional' capacity of the depolarizing channel on symplectic codes, which indicates the supremum of information rates at which symplectic codes work reliably.

A. Basics of Symplectic Stabilizer Codes
In this section, the framework of symplectic codes is rebuilt on the theory of geometric algebra [33, Chapter III], [34]. In designing symplectic codes, we use Weyl's unitary basis [40], N = {N u } u∈X , which has been specified by (2) and (3). We can regard the index of N (i,j) = X i Z j , (i, j) ∈ X as a pair of elements from F = F d = Z/dZ, the finite field consisting of d elements. Recall that we have The index (u 1 , v 1 ), . . . , (u n , v n ) ∈ (F 2 ) n of a basis element can be regarded as the plain 2n-dimensional vector We can equip the vector space F 2n over F with the standard symplectic bilinear form (symplectic paring) which is defined by for the above x and y = ( [33], [34]. For a subspace L ∈ F 2n , let L ⊥ be defined by A subspace L ∈ F 2n is said to be self-orthogonal (with respect to the symplectic bilinear form) if L ⊆ L ⊥ . The relation (4) implies the following two important properties of N n (see, e.g., [40], [45]): for some constants ζ xy with |ζ xy | = 1, x, y ∈ F 2n , and The latter implies that (x, y) sp = 0 if and only if N x and N y commute. The statement of the following lemma can be found in Gottesman [8, Section 3.2], [46]. A simple constructive proof based on the very basics of symplectic geometry [33], [34] is given in Appendix A.
Lemma 1: Let L be a self-orthogonal subspace with dim L = n − k and L = span {g 1 , . . . , g n−k }. Then, we can find vectors g n−k+1 , . . . , g n and h 1 , . . . , h n such that for i, j = 1, . . . , n, where δ ij is the Kronecker delta. ✸ Remark. In Gottesman's dissertation [8], N ′ g i and N ′ h i , i = n − k + 1, . . . , n (see Section III-E), appear as Z i and X i , respectively, with examples of them for a number of symplectic stabilizer codes. ✷ A pair of linearly independent vectors (g, h) with (g, h) sp = 1 is called a hyperbolic pair , and it is known that a space with a nondegenerate symplectic form, such as the one defined by (5), can be decomposed into an orthogonal sum of the form span {w 1 , z 1 } ⊥ · · · ⊥ span {w n , z n } in such a way that (w i , z i ), i = 1, . . . , n, are hyperbolic pairs [33]. Following Artin [33], we have referred and will refer to the direct sum of U 1 , . . . , U n as the orthogonal sum of spaces U 1 , . . . , U n if U 1 , . . . , U n are orthogonal. The three equations in the above lemma say that F 2n is the orthogonal sum of span {g i , h i }, i = 1, . . . , n. In the present case with the bilinear form in (5), the simplest example of such a decomposition of the space F 2n is span {e 1 , e 2 } ⊥ · · · ⊥ span {e 2n−1 , e 2n }, where {e i } 1≤i≤2n is the standard basis of F 2n that consists of e i = (δ ij ) 0≤j≤2n ∈ F 2n , 1 ≤ i ≤ 2n.
For the remainder of this section, we fix an arbitrary self-orthogonal subspace L with dim L = n − k as in Lemma 1 and such hyperbolic pairs (g 1 , h 1 ), . . . , (g n , h n ) as just constructed. We define a linear map γ : F 2n → F 2n , which depends on the basis {g 1 , h 1 , . . . , g n , h n }, by γ(x) = (w 1 , z 1 , . . . , w n , z n ) (9) for a vector x ∈ F 2n expanded into The j-th coordinate of γ(x) is denoted by γ j (x). In other words, we define γ j by where the product on the left-hand side is unambiguous because (N h i ) z i , i = 1, . . . , m, commute with each other. Note that by (6), Similarly, for w = (w 1 , . . . , w m ) ∈ F m , 1 ≤ m ≤ n, we write We have seen that any basis {g 1 , . . . , g n−k } of a self-orthogonal space can be extended to {g 1 , . . . , g n } in such a way that span {g 1 , . . . , g n } is self-orthogonal. Since N g i , i = 1, . . . , n, commute with each other by (7), we can find a basis of L(H) on which N g i are simultaneously diagonalized in matrix forms (e.g., [47]). Hence, we can find an n-tuple of scalars (µ i ) 1≤i≤n for which the space consisting of ψ with is not empty. We call a nonzero vector (respectively, the set of vectors) satisfying (14) an eigenvector (respectively, the eigenspace) of {N g i } 1≤i≤n with eigenvalue list (µ i ) 1≤i≤n . Take a normalized vector |0, . . . , 0 from this eigenspace, where the label (0, . . . , 0) belongs to F n . Applying an operator N x on both side of (14) from left and using (7) as well as the symplectic property This means that N x ψ is an eigenvector with eigenvalue list (µ i ω (g i ,x)sp ) 1≤i≤n . If we expand x as in (10), then we have (g i , x) sp = z i , i = 1, . . . , n, and hence there are, at least, d n possible eigenvalue lists for {N g i } 1≤i≤n . However, for any pair of distinct eigenvalue lists, the corresponding eigenspaces of {N g i } 1≤i≤n are orthogonal, and hence there are no more eigenvalue lists. Thus, we have an orthonormal basis {|s 1 , . . . , s n } (s 1 ,...,sn)∈F n defined by Note that the basis {|s 1 , . . . , s n } (s 1 ,...,sn)∈F n depends on (g i , h i ), i = 1, . . . , n, as well as (µ i ) 1≤i≤n . Now we are ready to see the principle of symplectic codes. Lemma 2: [20], [21], [19]. Let a subspace L ⊆ F 2n satisfy In addition, let J 0 ⊆ F 2n be a set satisfying and put Then, the d k -dimensional subspaces of the form where τ (M) are eigenvalues of M ∈ N L , are N J -correcting codes. ✸ In fact, the subspace with a fixed (n − k)-tuple s = (s 1 , . . . , s n−k ) ∈ F n−k is such a quantum code. The equivalence of (19) and (20) follows from (6). Since there are d n−k possible choices for (s 1 , . . . , s n−k ), we have d n−k codes. The term codes is applied to both a self-orthogonal subspace L ⊆ F 2n , and quantum codes C (s) associated with L, which we will call symplectic (stabilizer) codes with stabilizer N L . Since L ⊥ is spanned by g 1 , . . . , g n and h n−k+1 , . . . , h n , any coset of L ⊥ in F 2n is of the form with some (n − k)-tuple s = (s 1 , . . . , s n−k ). In terms of γ j defined by (11), the coset in (21) can be rewritten as The set of cosets of are in a one-to-one correspondence when J 0 is a transversal (a complete set of coset representatives), i.e., when |J 0 | = d n−k . In fact, for any vector x in the coset in (21) or (22), we have (cf. Section III-B below) The (n − k)-tuple (s i ) 1≤i≤n−k is called a syndrome on the analogy with classical linear codes.
To show that the subspace, say C, in (19) or (20) is really N J -correcting, we may use Theorem III.2 of Knill and Laflamme [39]. Alternatively, we can directly check the error-correcting capability using the recovery operator R defined by where Σ x is the projection onto N x C = {N x ψ | ψ ∈ C}, and Σ res is the projection onto the orthogonal To be specific about which class of codes we are treating, we define the next. Definition 2: We define S n (N), n ≥ 1, to be the set of all symplectic stabilizer codes with stabilizer N L , i.e., all d k -dimensional subspaces of H ⊗n of the form (19) or (20), with some subspace L ⊆ F 2n satisfying (17) for some k, 0 ≤ k ≤ n. ✸

B. Tracing Errors
Viewing index vectors in terms of the basis {g 1 , h 1 , . . . , g n , h n } is also useful to trace the action of an error in N n on a state in the code space. The view introduced in this subsection, as well as that in the next one, will underlie the proof of the main result to be given later. Let us consider the code C (s) in (20) assuming s 1 = · · · = s n−k = 0, which loses no generality since (µ i ) 1≤i≤n is arbitrary.
Suppose an error N x has occurred on a state ρ whose range (image, or support) is contained in the code space C (s) . We expand x as in (10) and put Then, for the purpose of analysis, we interpret the action of N x as follows: First, N [t] occurred to make no change on ρ, second, N (s) occurred to change ρ, which is a linear combination of with the same coefficients by (16), and finally, where the actions of X u and Z u ′ , u, u ′ ∈ F k , are defined by In other words, we have the next. Lemma 3: Let us given L and {g 1 , h 1 , . . . , g n , h n } as above. Then, we have for any operator ρ such that the ranges of ρ and ρ † are contained in the code space in (20) and for any x ∈ F 2n , where t, s, u, u ′ are determined from x through (25). This is clear from (6) and . For a general operator ρ, we should consider phase factors as is done in Appendix B.
Observe that the action of

C. Coset Arrays and Probability Arrays
To understand the action of errors in N n on symplectic codes associated with the self-orthogonal subspace L ∈ F 2n , it is helpful to consider cosets of L. Since dim L = n − k implies dim L ⊥ = n + k (Lemma 1), we have d n−k cosets of L ⊥ in F 2n , and each coset is a union of d 2k cosets of L in F 2n . To grasp the situation, we write down an array of cosets, which we will call a coset array of L, as follows: In the array, each entry is a coset of L in F 2n , and each row form a coset of L ⊥ in F 2n . This array, which has appeared in Fig. 1 of DiVincenzo et al. [13] in a different configuration, resembles standard arrays often used in classical coding theory [48], [49] though they differ in that elements of standard arrays are vectors rather than cosets.
We have already seen that cosets of L ⊥ can be labeled with s ∈ F n−k as in (21) or (22). Furthermore, using hyperbolic pairs (g i , h i ), i = 1, . . . , n, as in Lemma 1, we can label cosets of L in L ⊥ by . . , n, together with the basis elements As a result, each coset of L in F 2n can be specified by some (s 1 , . . . , s n−k ) ∈ F n−k and (u 1 , u ′ 1 , . . . , u k , u ′ k ) ∈ F 2k as the set that consists of the vectors x ∈ F 2n satisfying Keeping this labeling in mind, we will introduce another important quantities, in terms of which our bound on the capacity will be described. Given a channel A ∼ { P (u)N u } u∈X , we define a probability distribution P L by . . . . . . . . .
where 0 m denotes the zero vector in F m and an m-tuple (b 1 , . . . , b m ) ∈ F m is simply written as b 1 . . . b m . We have assumed here d = 2 in order that it may not look complicated, the general description being obvious. We will call this a probability array of L. Each probability P L (s, u) is the probability of the corresponding entry in (27) if the coset representatives x i and y j are chosen accordingly. Note that the index s in Section III-B corresponds to the row index s in the probability array, and u i , u ′ i are used for the column index. We remark that P L depends on the choice of hyperbolic pairs (g i , h i ), i = 1, . . . , n, but the probability array of L is unique up to permutations of rows and columns.

D. Decoding Symplectic Stabilizer Codes
Coset arrays are useful to understand the decoding principle of symplectic stabilizer codes. Let us given a code with stabilizer N L . As explained in Section III-A, once we specify J 0 , (a subset of) a transversal of the cosets of L ⊥ in F 2n , the recovery operator of symplectic codes is determined from J 0 as in (24) in such a way that the code can correct errors in N J , where J = J 0 + L. The set J = J 0 + L is a union of some cosets of L, and in view of (27), each row of the coset arrays has exactly one coset (or none) which is a constituent of J. Thus, the design of a decoder of symplectic codes with stabilizer N L is accomplished by choosing a coset from each row of the array. When the code in Lemma 2 is used on a memoryless channel A ∼ { P (u)N u } u∈X , a natural choice for such a coset in each row may be one that has the largest value of P L in the row, since it is analogous to maximum likelihood decoding, which is an optimum strategy for classical coding. Our codes to be proven to have the desired performance are concatenated codes, and our choice for J 0 will turn out to be more technical exploiting the structure of concatenated codes.

E. Remarks on Symplectic Stabilizer Codes
, [8]. The arguments below all work if N ′ is used instead of N for d = 2.
As already mentioned, the recovery operator for an N J -correcting code in Lemma 2 is given by R ∼ {N † x Σ x } x∈J 0 , where we assume |J 0 | = d n−k for simplicity. A physical meaning of this recovery process is simple: It can be described as the orthogonal measurement {Σ x } x∈J 0 followed by the unitary operation N † x , which is chosen accordingly to the measurement result x. The measurement {Σ x } x∈J 0 is realized by the observables N ′ g i , i = 1, . . . , n − k, when d = 2 (and similar self-adjoint operators that correspond to N g , i = 1, . . . , n−k, for d > 2). In this case, the syndrome is obtained as a measurement result.

IV. Concatenated Codes
The very first quantum code discovered by Shor [1] is an example of a concatenated code. The idea of the following general code construction can be found in [8,Section 3.5]. Let L ⊆ F 2n and L out ⊆ F 2kν be self-orthogonal codes with dim L = n − k and dim L out = kν − κ. Let {g 1 , . . . , g n−k } and {g ′ 1 , . . . , g ′ kν−κ } be bases of L and L out , respectively. Let {g 1 , . . . , g n−k } be supplemented by g n−k+1 , . . . , g n and h 1 , . . . , h n to form a basis of the property in Lemma 1. We will construct a new self-orthogonal code of length 2nν from L and L out .
Examples of codes with inner codes having parameter k = 1 can be found in the literature [12], [13], [8]. For instance, a code with n = ν = 5 and L = L out was given by Gottesman [8, Section 3.5, Table 3.7] with a table of {N ′ g | g ∈ cat(L, L out )}.

A. Proof of Theorem 1
The theorem can be obtained as a consequence of the next stronger statement, which is proved in Appendix C.
Theorem 2: Let a function E n,k be defined by where |x| + = max{x, 0} and the minimum with respect to P ′ is taken over all probability distributions on F n−k × F 2k . Let R ′ satisfy 0 ≤ R ′ ≤ 1. Then, for a memoryless channel A ∼ { P (u)N u } u∈X and any self-orthogonal code L ⊆ F 2n with dimension n − k, 1 ≤ k ≤ n, we have lim sup where P L is the probability distribution on F n−k × F 2k defined by (28). ✸ From the general property of the Kullback-Leibler information D that D(P ||Q) ≥ 0 with equality if and only if P = Q, it follows that E n,k (R, P L ) is positive if kR < k−H( ← − P L |P L ). Hence, [k−H( ← − P L |P L )]/n is a lower bound on the capacity of the channel. Thus, the next corollary follows.
Corollary 1: For the memoryless channel A, we have where the maximum with respect to L is over all k with 1 ≤ k ≤ n and all L ⊆ F 2n with dim L = n − k and L ⊆ L ⊥ . Remark. When n = k, a coset array of L consists of a single row, and H( ← − P L |P L ) is to be understood as H(P L ) = nH(P ). In this case, [k − H( ← − P L |P L )]/n = 1 − H(P ), which is the known lower bound [9], [10], [11]. ✷ We also have the next. Lemma 4: Let A be the one in Theorem 1, viz., A ∼ { P (u)N u } u∈X , L be a self-orthogonal code satisfying (17), and P L be defined by (28). Then, we have where C is a symplectic code with stabilizer N L . ✸ [12] and DiVincenzo and these authors [13], who restricted L to those of quantum repetition codes having parameter k = 1.

A proof is given in Appendix D. Corollary 1 and Lemma 4 are extensions of the facts established by Shor and Smolin
Corollary 1, together with Lemma 4, establishes Theorem 1.

B. Remarks on Theorems 1 and 2
The quantity H( ← − P L |P L ) appearing Corollary 1 can be written solely in terms of L, which specifies the quantum code, and P , which specifies the channels, and it does not depend on the choice of hyperbolic pairs (g i , h i ), i = 1, . . . , n, since H( ← − P L |P L ) is a function of the array or matrix in (29) as is mentioned in the proof of Lemma 4, Appendix D, and its value does not change if we permute rows or columns of the array. Similarly, E n,k (R, P L ) do not depend on the choice of hyperbolic pairs (g i , h i ), i = 1, . . . , n.

C. Idea for Proof of Theorem 2
The theorem is proved with a random coding argument similar to those in [10], [11], the main difference being in the decoding strategy. A concatenated code associated with cat(L, L out ) is a symplectic stabilizer code, so that we can apply the decoding strategy described in Section III-D to it. Especially, minimum entropy decoder employed in [10], [11] can be used. In the proof of Theorem 2, however, we modify this decoding strategy incorporating Shor and Smolin's idea. Namely, we choose a vector that minimizes the conditional entropy of the type of it in each coset of cat(L, L out ) ⊥ in F 2nν , where the conditioning is on the result of measuring the observables N ′ g , g ∈ G, when d = 2, or similar ones for d > 2, which form a part of the syndrome of the concatenated code.

A. Conditional Capacity and Upper Bound
In discussing capacity problems on classical channels, we sometimes put restriction on coding schemes. For example, there are works on the highest information rate achievable by linear codes [50], the conditional capacity with cost or power constraints and so on. In a similar way, we discuss a conditional quantum capacity in this section. Suppose for each n > 0, a set T n of subspaces of H ⊗n is given. We imagine the situation in which only subspaces belonging to T n can be used as codes.
Definition 3: Let a sequence of code classes {T n } be given, and F ⋆ n,k (A ⊗n |T n ) denote the supremum of F (C, RA ⊗n ) such that there exists a code (C, R) with C ∈ T n and log d dim C ≥ k, where n > 0 is an integer while k, 0 ≤ k ≤ n, is a real number. The supremum of nonnegative numbers R satisfying lim sup n→∞ F ⋆ n,Rn (A ⊗n |T n ) = 1 is called the conditional quantum capacity of A on {T n } and denoted by C(A|{T n }). ✸ Comparing this with Definition 1, we see C(A) = C(A|{T n }) when we put no restriction on coding schemes, i.e., when T n is the set of all subspaces of H ⊗n for each n > 0.
We have an upper bound on the conditional capacity, a proof of which is given in Appendix E. Lemma 5: Let a sequence of code classes {T n } be given. Then, where Π C is the projection onto C. ✸

B. Conditional Capacity of the Depolarizing Channel on Stabilizer Codes
In this subsection, we will see that the lower bound on the capacity obtained in the previous section is, in fact, a lower bound on the conditional capacity C(A|{S n }) of the depolarizing channel, where S n is the set of all symplectic stabilizer codes. To be precise, we put for some 0 ≤ p ≤ 1 a (d-dimensional) p-depolarizing channel. Then, we have the next. Theorem 3: For the p-depolarizing channel with 0 ≤ p ≤ 1 and for the present choice of S n , i.e., for S n = N S n (N), we have where the maximum with respect to L is over all L ⊆ F 2n with dim L = n − k, 1 ≤ k ≤ n, and L ⊆ L ⊥ . Here, the probability distribution P L is defined by (28) with (34).
where the maximum with respect to L is over all L ⊆ F 2n with dim L = n − k, 1 ≤ k ≤ n, and L ⊆ L ⊥ . Here, the probability distribution P L is given by (28). ✸ A poof of this lemma is given in Appendix F. From the proof, it is clear that Theorem 3 remains true even if we extend S n = N S n (N) so that it includes the symplectic codes designed with N n = {N (1) u } is defined as N with some basis {|0 , . . . , |d − 1 } and some ω, which may vary according to i.

C. Superadditivity of Coherent Information
The conditional capacity in Theorem 3 is the limit of c n /n, where A natural question is whether lim n c n /n > c 1 or not. Shor and Smolin numerically demonstrated that lim n c n /n > c 1 for very noisy 2-dimensional depolarizing channels, which showed the remarkable feature of c n , or its counterpart c ′ n that is defined by (35) with S n replaced by the set of all subspaces of H ⊗n . Note that lim n c ′ n /n is an upper bound on the unconditional capacity C(A) by Lemma 5. For the erasure channel, lim n c ′ n /n is known to equal c ′ 1 [52], which is indeed the capacity. Here this paper reports that superadditivity of c n has been observed for very noisy 3-dimensional p-depolarizing channel. Specifically, a numerical evaluation using the repetition code span {1100000, 1010000, . . . , 1000001} as an inner code, where 1100000 ∈ Z 7 9 denotes the vector (1, 0, 1, 0, 0, 0, . . . , 0, 0) ∈ F 14 3 and so on, has shown that for 0.2552 ≤ p ≤ 0.2557, c 7 > 0 while c 1 < 0.

VII. Bounds for General Discrete Channels
We remark that this work's bound holds true for general discrete memoryless channels (TPCP maps) as treated in [11]. Namely, if we associate the probability distribution P = P A with a channel A [or P = P U A with some TPCP map U on L(H)] as in [11,Section II], then the bound in (32) and that in Corollary 1 are true for this channel. This can be shown in a quite similar way to that in [11]. That is, if the minimum fidelity F in (37) is replaced by the minimum average fidelity F a introduced in [11], the same bound holds on F a for general memoryless channels. Then, owing to the fact [11] that a lower bound on F a gives asymptotically the same bound on F , we obtain the lower bound on the minimum fidelity F of the best codes used on general channels. These bounds also apply to 'blockwise' memoryless channels (TPCP maps) A n on L(H ⊗n ) if we associate the probability distribution P n = P An on X n [or P n = P U An with some TPCP map U on L(H ⊗n )] with A n as in [11, Section V, Definition 2] and use P n in place of P n in (28).

VIII. Concluding Remarks
This paper has presented a lower bound on the quantum capacity which has a close relation to the known upper bound based on coherent information [3]. This author conjectures that this bound is actually the conditional capacity of general Pauli or N-channels on all symplectic stabilizer codes. It might even be true that the lower bound is tight as one on the usual (unconditional) quantum capacity for Pauli channels, which would be proved by showing that the maximum of coherent information were nearly achieved by an input state proportional to the projections onto the code space of a symplectic stabilizer code for large enough n. If the quantum capacity were proven to be the coherentinformation upper bound lim n c ′ n /n, it would still leave room for investigation since the bound is a limiting expression and we do not know how to calculate it except for few cases [52].
In the previous work [10], this author conjectured that the exponent appearing in the fidelity bound in [10] is not the optimum for some channels. Now this fact has been established at least numerically since the bound in [10] is the same as the right-hand side of (32) when n = k = 1, in which case P L = P , and we have Shor and Smolin's numerical evaluation for the depolarizing channel, from which it follows that there exist some n ≥ 3 and relatively large p such that E n,1 (Rn, P L ) is positive while E 1,1 (R, P ) vanishes. The problem of determining the quantity in the left-hand side of (32) would deserve investigations in view of the great attention paid to the corresponding problem in classical information theory; an improvement on E 1,1 (R, P ) for P with large P (0, 0) can be found in [53].

I. Appendix A: Proof of Lemma 1
In this proof, we use the property of a nondegenerate bilinear form (·, ·) ′ on V with dim V = 2l that dim W + dim W ⊥ ′ = 2l (36) for any subspace W ⊆ V , where W ⊥ ′ = {y ∈ V | ∀x ∈ W, (x, y) ′ = 0} [33], [34]. We construct pairs (g i , h i ) of the property in (8) in the following two-stage algorithmic process.

II. Appendix B: Proof of Lemma 3
In this proof, when x ∈ F 2n is of the form where the product on the left-hand side is unambiguous because (N h i ) z i , i = 1, . . . , n, commute with each other. Similarly, when x ∈ F 2n is of the form x = n i=1 w i g i , we write N x = n i=1 (N g i ) w i . Due to (6), , where i runs from 1 to k in the summations, are the same up to a factor of modulus one that solely depends on x, so that N x ρN † x = MρM † . Hence, if X u and Z u ′ differ only by phase factors from N Σ i u i h i+n−k and N Σ i u ′ i g i+n−k , respectively, and the factors do not depend on (b i ) 1≤i≤k when they act on |z 1 , . . . , z n−k , b 1 , . . . , b k , then we will obtain the lemma.
It is seen from (16) that the action of X u is the same as N Σ i u i h i+n−k . On the other hand, the action of Z u ′ is the same as N Σ i u ′ i g i+n−k up to an irrelevant phase factor. This can be seen by the following chain of equalities, where (7), (14) and (16) are used, and in all summations, i runs from 1 to k, and j from 1 to n − k, and λ, λ ′ , which depend on x and b i , are defined by which is possible owing to (6):

III. Appendix C: Proof of Theorem 2
In this appendix, the lower bound in Theorem 2 will be established using the concatenated code in Section IV as well as the notation therein. In the proof, the random coding proof method is employed, where as in DiVincenzo, Shor and Smolin [12], [13], an inner code L having parameters k and n, 1 ≤ k ≤ n, is fixed and the average fidelity over all possible outer codes L out is evaluated. Namely, we evaluate where F is defined in (1), the ensemble A is specified below in (45), and C(L out ) is one of the d nν−κ symplectic quantum codes of dimension d κ associated with cat(L, L out ), and R is determined from J 0 which will be given below. It will be helpful to notice that span G is contained in cat(L, L out ), which, in turn, is contained in cat(L, L out ) ⊥ , so that any coset of cat(L, L out ) ⊥ in F 2nν is a union of some cosets of span G. We will work largely with cosets of span G rather than individual sequences in F 2νn because due to Lemma 3, error operators indexed by sequences in a fixed coset act on the states exactly in the same way. It is convenient to view y = (y 1,1 , . . . , y 1,2n , . . . , y ν,1 , . . . , y ν,2n ) ∈ F 2nν in terms of the basis Let us expand y ∈ F 2n as and consider the transformation that maps y to y ′ = (w 1,1 , z 1,1 , . . . , w 1,n , z 1,n , . . . , w ν,1 , z ν,1 , . . . , w ν,n , z ν,n ).
Note that the vectors y ∈ F 2nν which, when expanded as in (38), have the same z j,i for j = 1, . . . , ν, i = 1, . . . , n, and the same w j,i for j = 1, . . . , ν, i = n − k + 1, . . . , n, form a coset of span G in F 2nν . In other words, the set With the decomposition of an error operator in Lemma 3 in mind, we rather write a coset of span G as where the two sequences z(y) and v(y) are defined by and z j = (z j,1 , . . . , z j,n−k ) and v j = (w j,n−k+1 , z j,n−k+1 , . . . , w j,n , z j,n ), j = 1, . . . , ν, with (38). We denote by Γ(z(y), v(y)) the coset of span G in F 2nν that contains y for any y ∈ F 2nν . The simplest coset representative of a coset Γ( z, v) is the vector y with w j,i = 0 for 1 ≤ j ≤ ν, 1 ≤ i ≤ n − k when represented as in (38). The set (transversal) consisting of these coset representatives is denoted by Y G . On the other hand, cosets of cat(L, L out ) ⊥ in F 2nν can be specified as follows in view of (21): A coset of cat(L, L out ) ⊥ has the form with fixed z = ( z j,i ) 1≤i≤n−k 1≤j≤ν and σ = (σ i ) 1≤i≤kν−κ . We denote this coset by Λ( z, σ). Given z = (z 1 , . . . , z ν ) ∈ (F n−k ) ν and v = (v 1 , . . . , v ν ) ∈ (F 2k ) ν , we denote the rearranged sequence (z 1 , v 1 ), . . . , (z ν , v ν ) ∈ (F n−k × F 2k ) ν by [z, v], and define a probability distribution P z,v , which is called the type of the sequence [z, v], by and put which are the types of z and v, respectively. To make use of Lemma 2, we choose a representative from each coset Λ( z, σ) as follows. Among those sequences y that belong to both Y G and Λ( z, σ), we choose one that minimizes H c (P z,v(y) ) = H( We apply Lemma 2 defining J 0 = J 0 (L out ) as the set of these representatives. Denote J in the lemma by J(L out ), viz., and put Then, we have where 1[T ] = 1 if a statement T is true and 1[T ] = 0 otherwise, and The fraction |B(y)|/|A| is trivially bounded as We use the next lemma [11], which is a variant of a fact established by Calderbank et al. [20].
From the design of J 0 (L out ) specified above, it follows that [This can be seen as follows. First, we consider the case where y ∈ Y G . Recall Λ( z, σ) was defined by (42), and observe (g ′ i , v(y)) sp = (g ′ i , v(y)) sp = (g ′ i , y) sp from (30), where again v = v(y) and z = z(y) are specified by (38), (40) and (41). Hence, x ∈ Y G and y ∈ Y G are in the same coset of cat(L, L out ) ⊥ if and only if (42), which can be restated as Since, at the beginning of the paragraph containing (44), we have chosen a coset representative that minimizes H c in Λ( z, σ) ∩ Y G for each coset Λ( z, σ), it follows that for any y ∈ Λ(z(y), σ) ∩ Y G , the condition y / ∈ J(L out ) occurs only if there exists a vector other than y in Λ(z(y), σ) ∩ Y G that has conditional entropy H c as small as y, which implies (48). To see this for a general y ∈ F 2nν , note that for a fixed coset of cat(L, L out ), either each element y of the coset satisfies L out ∈ B(y) or each satisfies L out / ∈ B(y) because of Lemma 2, or specifically, (44) in this case. Especially, L out ∈ B(y) if and only if L out ∈ B(x) for the vector y ∈ Y G with y − y ∈ span G, so that we can judge whether y / ∈ J(L out ) occurs or not by checking the condition y / ∈ J(L out ) for y ∈ Y G with y − y ∈ span G.] Owing to (48), we have where the second inequality is due to Lemma 7. Then, from (46), (47) and (49), it follows that Recalling the probability distribution P L defined by (28) and the transformation that converts y into y ′ in (39), we have where P ν L denotes the product of ν copies of P L , and hence, the above bound can be rewritten as Now, we will go into an argument using the method of types [14], [15]. We put For a type Q ∈ P ν , we define a set of stochastic matrices W ν (Q) by Here, the probability distribution V (·|s) is allowed to be undefined for some (but not all) s ∈ F n−k , the equality between stochastic matrices V and V ′ means V (u|s) = V ′ (u|s) for all u, s for which either V (u|s) or V ′ (u|s) is defined. For a type Q ∈ P ν of a sequence in (F n−k ) ν and V ∈ W ν (Q), a probability distribution Q × V on F n−k × F 2k is defined by which is the type of a sequence in (F n−k × F 2k ) ν . Here we understand [Q × V ] (s, u) = 0 for s with Q(s) = 0. The set of all possible types Q × V of sequences [z, v] ∈ (F n−k × F 2k ) ν is denoted by For Q ∈ P ν and V ∈ W ν (Q), i.e., for Q × V ∈ P ν (F n−k × F 2k ), a set of sequences T ν Q×V is defined by Hereafter, we write P L (s, v) and [Q × V ](s, v) in place of P L (s, v) and [Q × V ] (s, v) , respectively. For a fixed sequence z ∈ F n−k , and a stochastic matrix V ∈ W ν (P z ), we define which is called the V -shell of z [14]. Clearly, the cardinality of T ν V (z) is uniform over sequences z of a fixed type Q, and hence, we can put T ν V (Q) = |T ν V (z)|, where P z = Q. We use the following two basic estimates [ where Q ∈ P ν , V ∈ W ν (Q) and the sequence of random variables [z, v] that takes values in (F n−k ×F 2k ) ν is drawn according to P ν L ; We arbitrarily fix R, 0 ≤ R < 1, and put κ = ⌈kRν⌉, so that the information rate κ/(nν) of the concatenated code is not less than kR/n. From (50), (51), (52) and the inequality min{a + b, 1} ≤ min{a, 1} + min{b, 1} for a, b ≥ 0, we have This bound on 1 − F is trivially true for R ≥ 1. Note that |P ν | and W ν are polynomial in ν. We see the bound in the theorem upon putting R = R ′ n/k.

IV. Appendix D: Proof of Lemma 4
Let ρ = (dim C) −1 Π C and assume C = C (0) without loss of generality as in Section III-B. To prove the lemma, we will show two equalities and where |Ψ is a purification of ρ, which will establish the statement. The interpretation of errors N x , x ∈ F 2n , in terms of the basis {g 1 , h 1 , . . . , g n , h n } in Section III-B is useful to see (53) and (54). Namely, we trace the action of an error N x , which can be viewed as X u Z u ′ N (s) N [t] as discussed in Section III-B. Equation (53) holds because (dim C) −1 Π C is conveyed to (dim C (s) ) −1 Π C (s) by N (s) with probability P L (s), where γ(x) 2i = s i for 1 ≤ i ≤ n − k and C (s) has been given in (20) or (23), the subspaces C (s) , s ∈ F n−k , are mutually orthogonal, and the action of X u Z u ′ is similar to that of a tensor product of Pauli matrices or Weyl unitaries, which leaves the operator Π C (s) unchanged.
Similar reasoning results in (54). In this case, we trace the action of errors I ⊗ N x on the state |Ψ Ψ|, where |Ψ = 1 d k/2 (b 1 ,...,b k )∈F k |b 1 , . . . , b k ⊗ |0, . . . , 0, b 1 , . . . , b k is a purification of (dim C) −1 Π C . The action of N (s) N [t] (in fact, I ⊗ N (s) N [t] in this case) is similar to the previous case. To see how X u Z u ′ acts on the states, we use the next fundamental lemma on CP linear maps.

VI. Appendix F: Proof of Lemma 6
First, note that in the proof of Theorem 1 (Section V and Appendix D), we have assumed that the operator basis N = {N u } u∈X employed for code design is exactly the same as that used in the representation { P (u)N u } u∈X of the Pauli channel, and that the proof has actually shown where the second equality is due to Lemma 4. From (56) and Lemma 5 with T n = S n (N), we will obtain the lemma if we show that the limit of c n /n exists and lim n→∞ c n /n = sup n≥1 c n /n.
To do this, we will show c n+n ′ ≥ c n + c n ′ .
The fact that (58), together with the boundedness of c n /n, implies (57) for a general sequence of real numbers {c n } has often been used in (quantum) information theory [54], [2], [55]. Now let L ⊆ F 2n and L ′ ⊆ F 2n ′ with dim L = n − k and dim L ′ = n ′ − k ′ achieve the maxima of k − H( ← − P L |P L ) and k ′ − H( ← − P L ′ |P L ′ ), respectively. Recall that H( ← − P L |P L ) and H( ← − P L ′ |P L ′ ) are determined from coset arrays of L and L ′ defined in Section III-C. All we have to show is the existence of a self-orthogonal subspace L ′′ ⊆ F 2(n+n ′ ) with dim L ′′ = n + n ′ − k ′′ such that We can see that LL ′ def = {xy ∈ F n+n ′ | x ∈ L, y ∈ L ′ } with dim LL ′ = n + n ′ − (k + k ′ ), where xy denotes the vector obtained by pasting x and y together, is such a code as follows. We consider probability arrays of L and L ′ as in (29). Then, it is easy to see that the d n+n ′ −k−k ′ × d 2(k+k ′ ) array whose (s, u)-entry is P LL ′ (ss ′ , uu ′ ) = P L (s, u)P L ′ (s ′ , u ′ ), (s, u) ∈ F n−k × F 2k , (s ′ , u ′ ) ∈ F n ′ −k ′ × F 2k ′ , is a probability array of LL ′ . From this array, we have [To see these equalities, introduce random variables X, Y, X ′ , Y ′ such that Pr{X = s, Y = u, X ′ = s ′ , Y ′ = u ′ } = P L (s, u)P L ′ (s ′ , u ′ ).] Hence, we have (58) and consequently the lemma.