Approaches for approximate additivity of the Holevo information of quantum channels

We study quantum channels that are close to another channel with weakly additive Holevo information and derive upper bounds on their classical capacity. Examples of channels with weakly additive Holevo information are entanglement-breaking channels, unital qubit channels, and Hadamard channels. Related to the method of approximate degradability, we define approximation parameters for each class above that measure how close an arbitrary channel is to satisfying the respective property. This gives us upper bounds on the classical capacity in terms of functions of the approximation parameters, as well as an outer bound on the dynamic capacity region of a quantum channel. Since these parameters are defined in terms of the diamond distance, the upper bounds can be computed efficiently using semidefinite programming (SDP). We exhibit the usefulness of our method with two example channels: a convex mixture of amplitude damping and depolarizing noise, and a composition of amplitude damping and dephasing noise. For both channels, our bounds perform well in certain regimes of the noise parameters in comparison to a recently derived SDP upper bound on the classical capacity. Along the way, we define the notion of a generalized channel divergence (which includes the diamond distance as an example), and we prove that for jointly covariant channels these quantities are maximized by purifications of a state invariant under the covariance group. This latter result may be of independent interest.

I. INTRODUCTION
In information theory, an imperfect communication link between a sender and a receiver is modeled as a noisy channel. The capacity of such a channel is defined as the largest rate at which information can be sent through the channel reliably. In his 1948 paper that founded information theory, Shannon [1] gave a simple formula for the capacity of a channel in terms of the mutual information between an input random variable and the corresponding channel output random variable, maximized over all possible input distributions. One of the most remarkable aspects of Shannon's formula is its single-letter nature, meaning that the capacity of a channel only depends on the output statistics of a single use of it.
Quantum information theory generalizes the classical theory, incorporating quantum phenomena like entanglement that have the potential of enhancing communication capabilities. Communication is modeled by quantum channels. Depending on the type of information to be sent through a quantum channel, and the resources available to the sender and the receiver, there are various capacities characterizing a channel's capabilities. In this paper, we focus on the task of unassisted classical information transmission through a quantum channel.
One may define a quantum analogue of the channel mutual information mentioned above, the Holevo information (see (4) in Section II D), which again quantifies the maximal possible mutual information between a (classical) input random variable to a quantum channel and its (quantum) output state. Restricting the encoding in the information-processing task so that entangled inputs across different channel uses are not allowed, the Holevo information of a quantum channel is indeed equal to the product-state classical capacity of the channel [2,3].
In quantum information theory, it is natural to allow for general encodings that entangle inputs to the channel across different channel uses, since this potentially improves communication rates. In this scenario, the situation is more complicated, as the classical capacity of a quantum channel is now given by the regularized Holevo information [2,3]. The regularization here means that the Holevo information needs to be evaluated for an arbitrary (unbounded) number n of channel uses; the largest such value normalized by n is then equal to the classical capacity. The evaluation of the Holevo information for an unbounded number of uses of the channel renders the classical capacity intractable to compute, unless the Holevo information is additive. In this latter case, the normalized Holevo information is the same for all n.
Additivity of the Holevo information is known to hold for certain classes of channels such as entanglementbreaking channels [4], unital qubit channels [5], depolarizing channels [6], and Hadamard channels [7,8]. Moreover, a covariant qubit channel whose symmetry group forms a one-design on the output space also has additive Holevo information (see Section III A for details). However, Hastings [9] found an example of a channel that violates additivity of the Holevo information. Thus, the regularization in the classical capacity formula seems to be necessary in general. A well-known example of a qubit channel with unknown classical capacity is the amplitude damping channel. Deriving a tractable expression for its classical capacity remains a major open problem in quantum information theory.
A quantum channel can also be used to transmit other types of information besides classical information. For example, the quantum capacity of a quantum channel quantifies the highest rate at which quantum information can be sent through the channel reliably. Similar to the classical capacity, the quantum capacity was shown to be equal to the regularization of a quantity called the coherent information [10][11][12][13][14][15][16]. However, the coherent information can be superadditive [17] (see also [18] for an extreme form of this). Thus, the regularization in the quantum capacity formula is generally necessary, rendering the capacity intractable to compute in most cases.
A similar situation holds when a quantum channel is used to transmit private classical information. The corresponding private capacity can again be expressed as the regularization of a quantity called the private information [16,19], and the latter was found to be superadditive as well [20]. However, for the class of degradable quantum channels [21] both the coherent information and the private information are additive ( [21] resp. [22]), and in fact equal to each other [22]. Subsequently, for these channels both the quantum and private capacity are equal to the coherent information.
Due to the non-additivity of the Holevo information, the coherent information, and the private information, the corresponding capacities (classical, quantum, private) are poorly understood except in a few particular cases. Thus, to characterize the communication capabilities of most quantum channels we are left with finding good (lower and) upper bounds on their various capacities. A powerful method to find such upper bounds on the quantum and private capacity of a channel was recently developed by Sutter et al. [23]. For an arbitrary channel, they defined an approximate degradability parameter, which measures how close a channel is to being degradable (in which case it would have additive coherent and private information). Approximately degradable channels have approximately additive coherent and private information, and this fact can be used to obtain strong upper bounds on the quantum and private capacity, respectively. Moreover, these bounds can be easily evaluated as the degradability parameter is the solution to a semidefinite program (SDP). The method has also been applied recently to bound various capacities of bosonic thermal channels [24].
A. Main results and organization of the paper In the current work, we apply techniques similar to those developed in [23] to the task of classical information transmission, in order to obtain upper bounds on the classical capacity of a channel. The main mathematical tool is a continuity result for the classical capacity of quantum channels recently proved in [25]. This result can be used to obtain upper bounds on the classical capacity of a channel that is close (in diamond distance) to a quantum channel with weakly additive Holevo information (Corollary II.7). We then define notions of approximate covariance, approximate entanglement-breaking, and approximate Hadamard-ness, that measure how far a given arbitrary channel is from satisfying the respective defining property. In each case, Corollary II.7 gives upper bounds on the classical capacity of the channel (Corollaries III.5, III.7, and III.11, respectively). In addition, we define an alternative notion of approximate Hadamardness in the spirit of [23], and derive an analogous upper bound on the classical capacity in Theorem III.14. This alternative approximate Hadamard-ness parameter can also be used to obtain an outer bound on the "dynamic capcaity region" of a channel (Theorem III.16), characterizing the ability of a quantum channel to simultaneously transmit classical and quantum information as well as generate entanglement between sender and receiver. In all cases above, the corresponding approximation parameters can be computed (or bounded) via SDPs, and thus evaluated efficiently.
We demonstrate the usefulness of our approach on two examples of channels for which additivity of the Holevo information is not known to hold: a convex mixture of an amplitude damping channel and a depolarizing channel, and the composition of an amplitude damping channel and a Z-dephasing channel. For both channels, we compare our upper bounds to an SDP upper bound on the classical capacity recently derived by Wang et al. [26]. Along the way, we define the notion of a generalized channel divergence that includes the diamond distance between quantum channels. We prove in Proposition II.4 that for jointly covariant channels (i.e., two channels that are covariant with respect to the same group) any generalized channel divergence is maximized by purifications of a covariant state, i.e., a state invariant under the covariance group. This result may be of independent interest and has been employed recently in [24]. Specializing it to the diamond distance, we obtain an analytical formula for the covariance parameter of the amplitude damping channel (Proposition IV.2).
The rest of the paper is organized as follows: In Section II we first fix some notation, and then define and discuss the following central objects of our paper: quantum channels, the diamond norm, generalized channel divergences, the Holevo information of a quantum channel, and the classical capacity of a quantum channel. In Section III, we introduce four different notions of approximate additivity of the Holevo information of a quan-tum channel, based on how close the channel is to being covariant, entanglement-breaking, or Hadamard, respectively. We show how these notions lead to upper bounds on the classical capacity of a quantum channel, as well as an outer bound on the dynamic capacity region of a quantum channel. In Section IV we apply our results to two examples of channels and furthermore discuss why our methods do not give useful bounds for the amplitude damping channel. Finally, we give some concluding remarks in Section V. Appendices A, B and C contain the proofs of some technical results.

II. PRELIMINARIES
In this paper, we use the following notation: For a finite dimensional Hilbert space H, we denote by B (H) where log is taken to base 2.

A. Quantum channels
A quantum channel N : A → B is a linear, completely positive, and trace-preserving map from B(H A ) to B(H B ), where H A and H B are Hilbert spaces associated to the quantum systems A and B. We also use the notation N A→B . We denote the identity channel on B(H A ) by id A . If a quantum channel acts on one system of a bipartite operator, we occasionally omit the identity channel, i.e., we write N A→B (ρ RA ) ≡ (id R ⊗N A→B )(ρ RA ). For every quantum channel N : A → B we can choose an auxiliary Hilbert space H E , the environment, and an isometry V : [27]. The isometry V is unique up to left multiplication by a unitary operator acting on and unique up to a unitary operator acting on the output.
Let {|i A } |A| i=1 be a basis for H A , and define the unnormalized maximally entangled vector where A ∼ = A (by which we mean H A ∼ = H A as Hilbert spaces). The Choi operator N AB of a quantum channel N : A ∼ = A → B is defined as for all g ∈ G. We drop direct reference to the representations {(U A (g), V B (g))} g∈G whenever their choice is clear from the context.

B. Diamond norm
The trace norm X 1 of an operator X ∈ B(H) is defined as The diamond norm Φ of a linear map Φ : A → B is defined as where A ∼ = A. For two quantum channels N , M : A → B, the diamond norm 1 2 N − M of half their difference is the solution to the following semidefinite program (SDP) [28]: where N AB and M AB denote the Choi operators of the quantum channels N and M, respectively.

C. Generalized channel divergences
In the following, we use the notation D ≡ D(H) and P ≡ P(H) for the sets of density matrices and positive semidefinite operators on a generic Hilbert space H, respectively.
Definition II.1 (Generalized divergence; [29,30]). A functional D : D × P → R is a generalized divergence if it satisfies the monotonicity (data processing) inequality Particular examples of a generalized divergence are the quantum relative entropy D(ρ σ) := Tr(ρ(log ρ − log σ)) [31] and the trace distance ρ − σ 1 . It follows directly from monotonicity that any generalized divergence is invariant with respect to isometries, in the sense that D(ρ σ) = D(U ρU † U σU † ), where U is an isometry, and that it is invariant under tensoring with another quantum state τ , namely D(ρ σ) = D(ρ ⊗ τ σ ⊗ τ ). Note that to establish isometric invariance from monotonicity, we require a channel that can reverse the action of an isometry (see, e.g., [32,Section 4.6.3] for this standard construction).
We say that a generalized channel divergence satisfies the direct-sum property with respect to classicalquantum states if the following equality holds: where p X is a probability distribution, {|x } x is an orthonormal basis, and {ρ x } x and {σ x } x are sets of states. We note that this property holds, e.g., for trace distance and quantum relative entropy.
Definition II.2 (Generalized channel divergence). Given quantum channels N A→B and M A→B , we define the generalized channel divergence as where the supremum is over all mixed states ρ RA , and the reference system R is allowed to be arbitrarily large. However, as a consequence of purification, data processing, and the Schmidt decomposition, it follows that such that the supremum can be restricted to be with respect to pure states and the reference system R is isomorphic to the channel input system A.
Particular cases of the generalized channel divergence are the diamond norm of the difference of N A→B and M A→B as well as the Rényi channel divergence from [33].
In the following development, the notion of joint covariance plays a central role. We say that channels N A→B and M A→B are jointly covariant with respect to {(U A (g), V B (g))} g∈G if each of them is covariant with respect to {(U A (g), V B (g))} g . We also use the abbreviations We begin with the following lemma, which will be helpful in establishing several follow-up results: Lemma II.3. Let N A→B and M A→B be quantum channels, and let {(U A (g), V B (g))} g∈G denote unitary representations of a group G. Let ρ A be a density operator, and let φ ρ RA be a purification of ρ A . Letρ A denote the group average of ρ A according to a probability distribution p G , i.e.,ρ and let φρ RA be a purification ofρ A . Moreover, for g ∈ G we use the notation N g A→B ≡ V g † B • N A→B • U g A , and similarly for M g A→B . Then the following inequality holds: If the generalized divergence has the direct-sum property with respect to classical-quantum states, then the following inequality holds: Proof. Our proof is related to an approach from [34, Proposition 2] as well as that given in [35]. Given the purification φ ρ RA , consider the following state Observe that |ψ P RA is a purification ofρ A with purifying systems P and R. By the fact that all purifications are related by an isometry, there exists an isometric channel W R→P R such that W R→P R (φρ RA ) = ψ P RA . Then the following chain of inequalities holds: The first equality follows from isometric invariance of the channel divergence. The second equality follows because the isometric channel W R→P R commutes with N A→B and M A→B . The third equality follows because W R→P R (φρ RA ) = ψ P RA . The first inequality follows from monotonicity of the generalized divergence D under a dephasing of the P register (where the dephasing operation is given by g |g g| · |g g|). The last equality follows from invariance of the generalized divergence under unitaries, with the unitary chosen to be Note that one could also implement this operation as a classically controlled LOCC operation, i.e., a von Neumann measurement {|g g|} of the register P followed by a rotation V † B (g) of the B register, as discussed in [34,Proposition 2]. One can do so here because both arguments to D in (3) are classical on P .
We then have the following proposition, which allows us to restrict the form of the input states needed to optimize the generalized channel divergence of two jointly covariant channels: Proposition II.4. Let N A→B and M A→B be quantum channels that are jointly covariant with respect to {(U A (g), V B (g))} g∈G for a group G as above. Then, where the supremum is over all pure states ψ RA such that That is, it suffices to restrict the optimization to be over pure input states ψ RA such that the reduced state ψ A is invariant with respect to the symmetrizing channel 1 Proof. This is an immediate consequence of Lemma II.3, which follows from the assumption of joint covariance.
Applying it and taking p G (g) = 1/ |G|, we find that The first equality follows from the assumption of joint covariance, which implies that The last inequality follows because the generalized divergence D is invariant with respect to tensoring another quantum state.
Applying Proposition II.4 to the case in which {U A (g)} g∈G is a one-design leads to the following corollary: Corollary II.5. Let N A→B and M A→B be quantum channels that are jointly covariant with respect to {(U A (g), V B (g))} g∈G for a group G and where {U A (g)} g∈G is a one-design. Then, where |Φ RA := |A| −1/2 |γ RA denotes the (normalized) maximally entangled state.

D. Holevo information and classical capacity of quantum channels
We define the Holevo information χ(N ) of a quantum channel N : A → B as where and the maximum in (4) is over all quantum state en- . Note that this maximum is achieved by pure state ensembles of cardinality at most |A| 2 , i.e., ρ x A = |ψ x ψ x | A for all x = 1, . . . , |A| 2 . Defining the classical-quantum (cq) states the Holevo information can be expressed as where the maximum is over all cq states ρ XA of the form in (5), the state σ XB is defined as in (6), and I(A; B) θ = S(A) θ + S(B) θ − S(AB) θ is the mutual information of a bipartite state θ AB . The classical capacity C(N ) of N is given by the regularized Holevo information [2,3]: We say that a quantum channel N has weakly additive Holevo information if holds for all n ∈ N. For such a channel, the limit in the classical capacity formula (7) becomes trivial, and the classical capacity is equal to the Holevo information, C(N ) = χ(N ). Furthermore, we say that a quantum channel N has strongly additive Holevo information if for any other channel M. It is easy to see that every channel with strongly additive Holevo information also has weakly additive Holevo information. Subsequently, for channels with strongly additive Holevo information we also have C(N ) = χ(N ). In Section III we discuss examples of channels with weakly or strongly additive Holevo information. Leung and Smith [36] proved a number of continuity results for quantum channel capacities with respect to the diamond distance, including a continuity bound for the classical capacity. Shirokov [25] recently refined their result on the classical capacity using techniques developed by Winter [37], as well as giving an improved continuity bound for the Holevo information of two quantum channels. To state Shirokov's results, we introduce the function g : [0, 1] → R, defined as We then have: where g(ε) is defined as in (8).
From Theorem II.6 we can easily deduce the following result, which serves as the main mathematical tool in our discussion: Corollary II.7. Let N : A → B be an arbitrary quantum channel, and let M : A → B be a quantum channel with weakly additive Holevo information, χ(M ⊗n ) = nχ(M) for all n ∈ N. If 1 2 N − M ≤ ε for some ε ∈ [0, 1], the classical capacity of N can be bounded as with g(ε) as defined in (8).

A. Approximately covariant channels
In this subsection we define a notion of approximate covariance of a quantum channel, and we show how the assumptions of Corollary II.7 can be met using this concept. First, we discuss channels that are covariant with respect to certain groups called unitary designs, and show how the Holevo information of these channels becomes (weakly or strongly) additive. A where dµ(U ) denotes the Haar measure on U(H A ). Equivalently [38], for all For covariant channels with a one-design as the input space representation, the formula for the Holevo information simplifies in the following way: For covariant qubit-qubit channels with a one-design as the output space representation, the Holevo information is weakly additive: Then the Holevo information of N is weakly additive, Consequently, C(N ) = χ(N ) for such covariant channels.
Proof. First, let A and B be arbitrary systems with |A| = |B| (i.e., not necessarily qubits), and let N : For qubits A and B (i.e., |A| = |B| = 2), the result now follows from King's result about unital qubit channels [5].
For covariant quantum channels N : A → B, where A and B are isomorphic, d-dimensional systems, the Holevo information is additive if the group representations are unitary two-designs. This result is a direct consequence of [6,38,40], and we give a proof in Appendix A for the sake of completeness.
Lemma III.3. Let A and B be isomorphic ddimensional quantum systems, A ∼ = B, let G be a group, and let N : A → B be a quantum channel that is covariant with respect to a unitary representation Then N is an |A|-dimensional depolarizing channel, and hence its Holevo information is strongly additive, for an arbitrary quantum channel M : A → B . Consequently, C(N ) = χ(N ) for such covariant channels.
We now introduce a notion of approximate covariance. For a group G with unitary representations U A (g) ∈ U(H A ) on H A and V B (g) ∈ U(H B ) on H B , respectively, and an arbitrary quantum channel N : A → B, the twirled channel N G of N is defined as This twirled channel N G is covariant with respect to {(U A (g), V B (g))} g∈G by construction. Our notion of approximate covariance of a quantum channel is based on how close the channel is in diamond norm to its twirled channel: We define the covariance parameter cov G (N ) as the smallest ε ≥ 0 such that N is ε-covariant with respect to the given representations of G.
For given representations of a group G, the covariance parameter cov G (N ) can be efficiently computed using the SDP in (2) for the diamond norm. The Choi operator N G AB of the twirled channel N G can be obtained from the Choi operator N AB via the relation By Lemma III.2, the Holevo information of qubit-qubit channels that are covariant with respect to one-designs is weakly additive. More generally, quantum channels acting on a d-dimensional system which are covariant with respect to a two-design have strongly additive Holevo information, since these channels are d-dimensional depolarizing channels (Lemma III.3). In view of Definition III.4, we can therefore apply Corollary II.7 to any quantum channel once we consider suitable groups (or rather representations thereof) and the corresponding twirled channel.
It is well known that the "projective" Pauli group 1 P = {1, X, Y, Z} forms a one-design, for all ρ ∈ B(C 2 ), where X, Y, Z are the usual Pauli matrices. For an n-qubit system A (i.e., |A| = 2 n ), the Pauli group P n consists of all n-fold tensor products of elements in P, i.e., P n := P ⊗n . The "projective" Clifford group C n is defined as the normalizer of P n in U(H A ), that is, The Clifford group C n forms a unitary two-design [41] (see also [38]). More generally, the Clifford group C HW d of the Heisenberg-Weyl group acting on a d-dimensional system is also a unitary two-design [42].
Combining the above observations with Lemma III.2, Lemma III.3, and Corollary II.7, we obtain the following: Corollary III.5. Let A and B be quantum systems with |A| = |B|, and let N : A → B be an arbitrary quantum channel.
(ii) For |A| = |B| = 2 n , the choices G = C n and ε = cov Cn (N ) yield Note that in all three cases of Corollary III.5, the Holevo information χ(N G ) of the twirled channel N G for G ∈ {P, C n , C HW d } can be computed via Lemma III.1.

B. Approximately entanglement-breaking channels
is separable for all auxiliary quantum systems R and input states ρ RA . Equivalently, N is entanglement-breaking if and only if its Choi operator N AB is separable. Entanglement-breaking channels are an important class of quantum channels with strongly additive Holevo information [4]: for any arbitrary quantum channel M : A → B . In particular, we have χ(N ⊗n ) = nχ(N ) for entanglementbreaking channels, and thus C(N ) = χ(N ) by (7). Hence, an appropriate notion of an approximately entanglement-breaking channel, together with (9), provides another way of bounding the classical capacity of an arbitrary quantum channel via Corollary II.7. Fix quantum systems A and B, and let E ≡ E(A → B) = {N : A → B | N AB is separable} denote the set of all entanglement-breaking channels.
With this definition, we have the following application of Corollary II.7: Corollary III.7. Let N : A → B be a quantum channel, and set ε := EB(N ). Then, where the function g(ε) is defined through (8), and M : A → B is the entanglement-breaking channel achieving the minimum in Definition III.6.
If |A||B| ≤ 6, a state ρ AB is separable if and only if it has positive partial transpose (PPT) [44], i.e., ρ T B AB ≥ 0, where T B denotes the transpose on the B system. Hence, in low dimensions we can efficiently compute EB(N ): Lemma III.8. Let N : A → B be a quantum channel. If |A||B| ≤ 6, then the entanglement-breaking parameter EB(N ) is the solution to the following SDP: Proof. The constraint M T B AB ≥ 0 forces the operator M AB to be PPT, which by the assumption |A||B| ≤ 6 is equivalent to M AB being separable. Hence, M AB corresponds to the Choi operator of an entanglement-breaking channel M : A → B, and the SDP in (10) computes EB(N ).

C. Approximately Hadamard channels
A quantum channel N : A → B is called Hadamard if its complementary channel N c : A → E is entanglementbreaking. Since a channel is entanglement-breaking if and only if its Kraus operators are rank-one operators [43], we can parametrize a Hadamard channel as follows (cf. [32]): Let K be the Kraus rank of N , i.e., the minimal number of Kraus operators, which is equal to the smallest dimension of the environment |E| [45]. Let {|ϕ k E } K k=1 be a collection of normalized vectors on H E , ϕ k |ϕ k = 1 for all k = 1, . . . , K, let S = {|ψ k A } K k=1 be an overcomplete set of vectors on H A (such that K k=1 |ψ k ψ k | A = 1 A ), and let {|i B } |B| i=1 be an orthonormal basis for H B . 2 These sets of vectors give rise to a Hadamard channel N : A → B, whose action on an input state ρ A is given by Define [ρ A ] S as the matrix representation of ρ A with respect to S = {|ψ k A } K k=1 , i.e., ([ρ A ] ψ ) ij = ψ i |ρ A |ψ j . Furthermore, define the matrix (Γ) ij = ϕ i |ϕ j E . Then (11) can be rewritten as where * denotes the Hadamard product (viz. elementwise product) of matrices: (A * B) ij := (A) ij (B) ij . Equation (12) is the reason such channels are called Hadamard channels.
Hadamard channels are another class of quantum channels with strongly additive Holevo information [7,8]: If N is a Hadamard channel, then for any other channel M we have Hence, an appropriate notion of approximately Hadamard channels leads to another application of Corollary II.7 for bounding the classical capacity of arbitrary quantum channels.
In what follows, we define two notions of approximately Hadamard channels, one called ε-close Hadamard channels and the other called ε-Hadamard channels. To define ε-close Hadamard channels, fix quantum systems A and B and let H be the set of Hadamard channels from A to B.
For reasons that will become clear shortly, it is useful to define the following upper bound on Had(N ). Let S = {|ψ k A } i be an overcomplete set of vectors on H A , i.e., i |ψ i ψ i | A = 1 A , and define the set 2 For simplicity, we assume |B| = K = |E| here, though this is not necessary.
where Γ ≥ 0 satisfies Γ kk = 1 for all k. We then consider the parameter which clearly satisfies Had(N ) ≤ Had S (N ). In addition, Had S (N ) is the solution to an SDP and thus efficiently computable: Lemma III. 10. For fixed S, the parameter Had S (N ) is the solution to the following SDP: where O Γ AB := i, j, k, l (Γ * [|i j|] S ) kl |i j| A ⊗ |k l| B . Proof. A matrix Γ is positive semidefinite if and only if it is the Gram matrix of a collection of vectors, i.e., (Γ) ij = ϕ i |ϕ j for some set of vectors {|ϕ i } i . Hence, we can optimize over positive semidefinite Γ, and the constraints k|Γ|k = 1 for all k enforce that ϕ k |ϕ k = 1. Moreover, since the Hadamard product * is distributive over addition, (A+B) * C = A * C +B * C, the Choi operator i, j, k, l (Γ * [|i j|] S ) kl |i j| A ⊗|k l| B of a Hadamard channel M is linear in Γ for a fixed overcomplete set of vectors S = {|ψ k A } i . Thus, the SDP in (15) optimizes the diamond distance 1 2 N − M over all M ∈ H S . We can combine Definition III.9, Corollary II.7, and (13) to obtain an upper bound on C(N ) similar to Corollary III.5. Since the function 2ε log |B|+g(ε) is monotonically increasing for ε ∈ [0, 1], we can use the parameter Had S (N ) for a fixed S instead of Had(N ). The former has the advantage of being efficiently computable via its SDP representation given in Lemma III. 10. In summary, we have the following: Corollary III.11. Let N : A → B be a quantum channel, and set ε = Had(N ) and ε S := Had S (N ) for a fixed collection S = {|ψ k A } k of vectors. Then, where the function g(ε) is defined through (8), and M : A → B is the Hadamard channel achieving the minimum in Definition III.9. Note that we also have where M S : A → B is the Hadamard channel defined in terms of S achieving the minimum in (14).
We now define ε-Hadamard channels, an alternative way of defining a Hadamard parameter of an arbitrary quantum channel. To this end, we recall that Hadamard channels N : A → B belong to the class of degradable channels mentioned in Section I: For every Hadamard channel N : A → B with environment E there exists a quantum channel D : B → E, called the degrading channel, such that N c = D • N . In other words, there exists a quantum channel that Bob can apply locally to simulate the leakage of N to the environment, modeled by the complementary channel N . Moreover, the degrading channel of Hadamard channels is entanglement-breaking; that is, the Choi operator D BE of D is separable [46]. This observation gives rise to the following definition: Definition III.12. For a given ε ∈ [0, 1], a quantum channel N : where E(B → E) denotes the set of all entanglementbreaking channels from B to E. The Hadamard parameter Had deg (N ) is defined to be the smallest ε ∈ [0, 1] such that N is ε-Hadamard.
If |B||E| ≤ 6, the parameter Had deg (N ) of a quantum channel N : A → B with environment E can be expressed as the solution to an SDP. This SDP is obtained from the SDP that computes the approximate degradability parameter defined in [23] by adding a constraint enforcing the 'approximate degrading' map D to be entanglementbreaking. In summary, we have: Lemma III.13. Let N : A → B be a quantum channel with environment E. If |B||E| ≤ 6, then the Hadamard parameter Had deg (N ) is the solution to the following SDP: where J (·) denotes the Choi-Jamio lkowski isomorphism that maps a channel to its Choi operator.
Note that in (16) the operator D BE corresponds to the Choi operator of D : B → E, and the constraint D T E BE ≥ 0 enforces D BE to be PPT, which for |B||E| ≤ 6 is equivalent to D being entanglement-breaking. The map S → J (S • T ) is linear in S for a fixed channel T [23], and hence, the corresponding constraint in (16) is indeed semidefinite.
Using the Hadamard parameter Had deg (·) from Definition III.12, we can again deduce an upper bound on the classical capacity of a quantum channel by adapting the arguments in the proof of Corollary II.7. In particular, we have the following theorem, whose proof we give in Appendix B.
Theorem III.14. For a channel N : A → B, set ε = Had deg (N ), and let D : B → E be the entanglementbreaking channel achieving the minimum in Definition III.12. Then where the cq state ξ XF E is defined as A } x is a set of pure states.

D. Bounds on triple trade-off capacities for ε-close
Hadamard channels In addition to the various single-resource capacities that we have discussed so far, one can also consider the ability of a quantum channel to generate or consume multiple resources [21,[46][47][48][49][50][51]. One of the most general such tasks is the triple trade-off problem [49,50]: What is the net rate at which classical bits, quantum bits, and entangled bits can be consumed, in addition to many independent uses of a quantum channel, in order to generate the same resources? Let C denote the rate of classical communication, Q the rate of quantum communication, and E the rate of entanglement generation (if the rate is negative, it means that the resource is being consumed). The set of all achievable rates in this setting is called the "dynamic capacity region." This question has been addressed in [49][50][51] (see also [32]), via the following dynamic quantum capacity theorem: Theorem III.15 ( [49,51]). The quantum dynamic capacity region C CQE (N ) of a quantum channel N is given by the following expression: where the overbar indicates the closure of a set. The region C   where the coherent information I(F G) ω of a bipartite state ω F G is defined as I(F G) ω := H(G) ω − H(F G) ω . The above entropic quantities are with respect to a classical-quantum state σ XAB , where and the states φ x AA are pure, with system A isomorphic to system A . It is implicit that one should consider states on A k instead of A when taking the regularization in (17).
If the channel N is a Hadamard channel, then the regularization is not needed and the dynamic capacity region is equal to C (1) CQE (N ) [46,51]. Thus, we are motivated to consider the notion of approximate Hadamard channels in this context, leading to Theorem III.14 below. Note that Gao et al. [52] derived an outer bound on the dynamic capacity region of a special class of channels using operator space methods.
Theorem III. 16. Let N be an ε-close-Hadamard channel; i.e., there exists a Hadamard channel M such that Then the dynamic capacity region C CQE (N ) is contained in the region C  The state-dependent region C (1) CQE (M, τ, ε) is the set of all rates C, Q, and E, such that f 2 (ε) := 2ε log |B| + g(ε) + 2 √ 2ε log |E| + g( √ 2ε), (19) and g(ε) is defined in (8). The above entropic quantities are with respect to a classical-quantum state τ XAB , where and the states φ x AA are pure.
Proof. To prove this result, we consider an approach related to that for a statement given in [25], recalled here as Theorem II.6. It is convenient to distinguish between the output system B of the channel N and the output systemB of M, whereB ∼ = B. For n ∈ N, let be an arbitrary cq state, where each φ x AA n is a pure state. By assumption, we have that and so by the continuity of Stinespring's representation theorem [53], it follows that there exist isometric channels U N A →BE and U M A →BE extending N A →B and M A →B , respectively, such that the corresponding complementary channels N c and M c satisfy We thus define the following cq states for 1 ≤ t ≤ n − 1: where we use the shorthand Q ≤i ≡ Q 1 Q 2 . . . Q i for 1 ≤ i and quantum systems Q 1 , . . . , Q i , and use analogous definitions for Q <i , Q ≥i , and Q >i . For a Hadamard channel M and for all integers n > 1, there exist states ω i AiXiBiẼi for 1 ≤ i ≤ n, each having the form such that the following entropy inequalities hold [32,51] where the state ω ZÃXBẼ is defined as and the registersÃ andX are taken to be large enough to contain the contents of the largest A i and X i , respectively. Applying (20) and (21), we find that for 1 ≤ t ≤ n by the definition of the diamond norm. Moreover, σ t−1 XAB ≤t−1 B>t−1 and σ t XAB ≤t B>t have the same marginals on the systems XAB <t B >t , and σ t−1 XAẼ ≤t−1 E>t−1 and σ t XAẼ ≤t E>t have the same marginals on the systems XAẼ <t E >t . Hence, using the continuity bound from [25, Corollary 1] we obtain (25) for 1 ≤ t ≤ n, whereB <1 and B >n represent empty systems, respectively, and where f 1 (ε) is defined in (18). We also get that by applying (23), (24), and [37, Lemma 2]. We can now bound I(AX; B n ) σ 0 from above as follows: where (26) follows from writing out the telescope sum and observing that all terms except the first and last one cancel out.
Step (27) uses (25) in each term of the sum. The next inequality and the equality after that follow by invoking (22). The final inequality is a consequence of the chain rule and non-negativity of mutual information. For the second bound involving the coherent information term I(A B n X) σ 0 , consider that We handle each term separately. First, by reasoning similar to that in the proof of [23,Theorem 3.4], consider that = nH(B|XZ) ω + n (2ε log |B| + g(ε)) .
By similar reasoning, we find that Thus, we conclude that where f 2 (ε) is defined in (19). For the final term I(X; B n ) σ 0 + I(A B n X) σ 0 , consider that Since we already have a bound for −H(E n |X) σ 0 , we just need to bound H(B n ) σ 0 . By applying similar reasoning as above, we find that = nH(B|Z) ω + n (2ε log |B| + g(ε)) .
Combining with the above, we then get that We end this section by mentioning that this kind of approach could be applied in the context of Hadamard broadcast channels, which constitute the main class of quantum broadcast channels for which we have singleletter capacity regions [54,55].

IV. APPLICATION TO PARTICULAR QUBIT CHANNELS
The MATLAB code used to obtain the numerical results of this section is available in the ancillary files section on the arXiv page of this paper. The code makes heavy use of the quantinf package [56], as well as the YALMIP package to solve SDPs [57].

A. On the amplitude damping channel
The amplitude damping channel A p is defined for p ∈ [0, 1] as where An exact expression for the Holevo information of the amplitude damping channel was derived by Giovannetti and Fazio [58]. They showed that χ(A p ) is equal to denotes the binary entropy. However, its classical capacity C(A p ) is yet to be determined, which remains a major open problem in quantum information theory.
For low values of p, the amplitude damping channel belongs to the class of so-called low-noise channels [59]. This is the content of Proposition IV.1 below, whose proof we defer to Appendix C.
We have A 0 = id, the identity channel, which is trivially covariant under the full unitary group, and furthermore Hadamard, since the complementary channel of the identity channel is completely depolarizing and hence entanglement-breaking. It is also easy to see that A 1 is entanglement-breaking. Therefore, one might expect to get useful upper bounds on the classical capacity of A p using notions of approximate covariance or Hadamardness for p 0, or approximate entanglement-breaking for p 1.
The results of [59] can be applied to show that a (super)linear behavior in the underlying noise parameter of an approximation parameter leads to a useless bound on the classical capacity, as the appearing error term involves the function ε log ε, which has infinite slope at ε = 0 if ε = O(p). Unfortunately, all parameters that we introduced in Section III have such behavior in the amplitude damping parameter p: the covariance parameter cov P (A p ), the entanglement-breaking parameter EB(A p ), and the Hadamard parameters Had(A p ) and Had deg (A p ). First, the developments in Section II C lead to the following analytical formula for cov P (A p ), which we prove in Appendix C: Proposition IV.2. The covariance parameter cov P (A p ) of an amplitude damping channel A p with damping parameter p ∈ [0, 1] with respect to the Pauli group P is given by We can also derive an analytical lower bound on the entanglement-breaking parameter EB(A p ), showing that the latter has at least linear behavior in p. The proof of the following result is again deferred to Appendix C: Proposition IV.3. The entanglement-breaking parameter EB(A p ) of an amplitude damping channel A p with damping parameter p ∈ [0, 1] satisfies Moreover, as shown in Figure 1, numerics demonstrate that both Hadamard parameters Had S (A p ) (with S = {|0 , |1 }) and Had deg (A p ) are at least linear in p.
Recently, Wang et al. [26] derived the following strong converse upper bound on the classical capacity of a quantum channel N : A → B: where the quantity β(N ) is the solution to the following SDP, with N AB denoting the Choi operator of N : The quantity C β (N ) is a strong converse bound in the sense that for any sequence of classical codes with rate  (14), is plotted in blue/dashed, and the Hadamard parameter Had deg (Ap), as given in Definition III.12, is plotted in red/dash-dotted.
above the classical capacity C(N ), the success probability of that code sequence converges to 0 exponentially fast.
For the amplitude damping channel A p , the quantity C β (A p ) constitutes the best known upper bound on C(A p ) for p ∈ [0, 1/2] [26], and it can be expressed in a closed form, We plot this bound in Figure 2, together with the Holevo information χ(A p ), which is a lower bound on the classical capacity C(A p ). Evidently, C β (A p ) is not tangent to the Holevo information χ(A p ). This indicates that a suitable notion of approximate additivity of the Holevo information of A p would necessarily improve upon C β (A p ) for low values of p due to continuity. Here, suitable means that the resulting upper bound is tangent to χ(A p ). However, our arguments made above, together with the results from [59], show that the approximation parameters defined in the present paper are not suitable in this sense. It therefore remains an interesting open question to find suitable approximation parameters for A p with the correct sublinear behavior in the damping parameter p.
As mentioned above, the quantity C β (N ) provides a strong bound on the classical capacity C(N ) of a quantum channel, as exhibited with the example of the amplitude damping channel. Moreover, it can be easily computed for any channel N via its SDP representation given in (31). For these reasons, we use C β (N ) as a benchmark for upper bounds on the classical capacity of certain examples of channels in the following sections. These bounds are obtained from Corollaries III.5, III.7, and III.11, respectively. We first consider a channel that is a convex mixture of an amplitude damping channel and a depolarizing channel. More precisely, for p ∈ [0, 1] we define the channel where the amplitude damping channel A p is defined in (28), and D p denotes the qubit depolarizing channel The depolarizing channel D p is covariant under the full unitary group for all p, and hence also covariant with respect to the Pauli group P. We therefore expect the channel N p to be almost covariant with respect to the Pauli group for small values of p, so that Corollary III.5 applies. Indeed, we have the following immediate consequence of Proposition IV.2: Corollary IV.4. The covariance parameter of the channel N p defined in (32) with respect to the Pauli group P is given by The resulting upper bound on C(N p ) obtained via Corollary III.5(i) is plotted in Figure 3 together with the Holevo information χ(N p ), and the strong converse upper bound C β (N p ) defined in (30). Numerical investigations (that were verified using the results from [60]) showed that χ(N p ) is equal to the Holevo information χ(N p, P ) of the twirled channel N p, P computed via Lemma III.1, which enables us to use the stronger upper bound χ(N p ) + 2ε p + g(ε p ) in Figure 3.

C. Composition of amplitude damping and dephasing noise
We now consider the channel where Z p denotes the Z-dephasing channel This channel was, e.g., considered by Aliferis et al. [61] in the context of fault-tolerant quantum computation. Let us explicitly calculate the Choi operator M 1/2 of M 1/2 . It is easy to see that (id A ⊗Z 1/2 )(γ) = |00 00| + |11 11|, where |00 ≡ |0 ⊗ |0 and |11 ≡ |1 ⊗ |1 . The action of the Kraus operators {K 1 , K 2 } of A 1/2 (given in (28)) on the computational basis is from which we obtain M 1/2 = |00 00|+|1 1|⊗π 2 . Since M 1/2 is manifestly separable, M 1/2 is entanglementbreaking, and in a neighborhood of p = 1 2 we expect M p to be approximately entanglement-breaking according to Definition III.6. In Figure 4, the entanglementbreaking parameter EB(M p ) is plotted as a function of p for the whole interval p ∈ [0, 1] and zoomed in on the interval p ∈ [0.35, 0.75]. Evidently, the numerics suggest a quadratic dependence of EB(M p ) on p, i.e., EB(M p ) = O(p 2 ). The resulting upper bound from Corollary III.7 on the classical capacity C(M p ) is plotted in Figure 5, both in terms of the original channel M p and the entanglement-breaking channel M EB p found by the SDP in (10) that is closest to M p in diamond distance. The plot also includes the Holevo information χ(M p ) and the strong converse upper bound C β (M p ). The computation of χ(M p ) and χ(M EB p ) was verified using the methods from [60].

V. CONCLUDING REMARKS AND OPEN PROBLEMS
A quantum channel can be used in different contexts, and depending on the information-processing task there are different capacities characterizing the channel. Most of these capacities -including the classical, quantum, and private capacity -are given in terms of regularized formulae that are intractable to evaluate for most channels. 3 This is both good and bad news: Good, because entanglement between different uses of a quantum channel clearly enhances some its communication capabilities, giving rise to interesting effects such as superadditivity of coherent [17] and private information [20], and superactivation of quantum capacity [63]; bad, because the regularization severely limits our understanding of these capacities. Hence, we need to resort to deriving useful lower and upper bounds on these capacities, as well as single out classes of channels for which the respective capacity formulae reduce to single-letter ones due to additivity of the underlying quantities (Holevo, coherent, and private information).
In the case of the quantum capacity, the largest class of channels with additive coherent information is the class of so-called informationally degradable channels [64], which include degradable and conjugate degradable channels. 4 To obtain upper bounds on the quantum capacity, Sutter et al. [23] defined an approximate version of degradability, and showed that the desirable additivity properties of exactly degradable quantum channels are approximately preserved. Their approach yields efficiently computable upper bounds on the quantum capacity, and works particularly well for so-called low-noise channels [59], which are close in diamond norm to the ideal channel and hence 'almost' degradable.
In this paper, we applied the approach of [23] to the classical capacity. In contrast to the quantum capacity, there are various distinct classes of channels with (weakly or strongly) additive Holevo information, including entanglement-breaking channels, unital qubit channels, depolarizing channels, and Hadamard channels. This presented us with the option of defining multiple 'approximation parameters': a covariance parameter (Definition III.4), an entanglement-breaking parameter (Definition III.6), and two Hadamard parameters (Definition III.9 and Definition III.12). For the first two parameters, we found interesting examples of channels (the channels N p and M p defined in (32) and (33) of Section IV, respectively) that exhibited the usefulness of our approach. More generally, we note here that one can obtain single-letter upper bounds on the triple trade-off capacities [32,[49][50][51] of approximately Hadamard channels, given that Hadamard channels are quite special, as their triple-trade-off capacity regions are single-letter [32,46,51] in addition to their classical capacities.
We were not able to find an interesting channel for which the notion of approximate Hadamard-ness leads to good upper bounds on its classical capacity. More precisely, we were looking for a channel L p defined in terms of a noise parameter p ∈ [0, 1], satisfying or for some a > 1, where Had(·) and Had deg (·) are the Hadamard parameters defined in Definition III.9 and Definition III.12, respectively. The results of [59] show that a > 1 is necessary for the upper bound on C(L p ) from Corollary II.7 to be non-trivial. It remains an interesting open problem to find a channel satisfying (34).
On a more general note, we once again mention that our approach was not helpful for gaining a better understanding of the classical capacity of the amplitude damping channel A p . This is because for this channel all four approximation parameters introduced in this paper have at least linear behavior in the amplitude damping parameter p (cf. Section IV), rendering the resulting upper bounds on C(A p ) trivial. We are curious as to whether a variation of the approximation methods of [23] and the present paper might yield new insights in this matter, or whether a different approach, e.g., in the spirit of [65,66], is needed.
Taking the partial transpose on H in (A1) and using the above identities, we obtain where f = Tr S T2 Φ = f /d and s = Tr S = Tr S T2 . Choosing S = T T2 and noting that s = t for this choice proves the claim.
We are now ready to prove Lemma III.3: Proof of Lemma III.3. The covariance of N with respect to {U A (g)} g∈G can be written as Let B denote the basis for H A with respect to which the unnormalized maximally entangled vector γ AA in (1) is defined. Then, due to (A2), the Choi operator N AB := (id A ⊗N )(γ AA ) of N is equal to whereX denotes the complex conjugate of an operator X with respect to the basis B. The formula (A3) follows from the 'transpose trick' identity (A ⊗ 1)|γ = (1 ⊗ A T )|γ . Since U A (g) ∈ U(H A ) is a unitary two-design, we further have where |Φ AB := 1 √ |A| |γ AB , the last equality follows from Lemma A.1 in Appendix A, and with f = Φ|N AB |Φ AB . Hence, setting q = |A|x and noting that y |A| = 1 − q, we can rewrite (A4) as where D q (·) := (1 − q) id +q Tr(·)π is an |A|-dimensional depolarizing channel, which has strongly additive Holevo information as proved by King [6].
with U D i ≡ U D Bi→FiẼi and N i ≡ N Ai→Bi , such that the following entropy inequalities hold [32,Theorem 20.4.1]: where the state ω ZXFẼ is defined as and the registerX is taken to be large enough to contain the contents of the largest X i . Applying (B2), we find that for 1 ≤ t ≤ n by the definition of the diamond norm. Moreover, σ t−1 XẼ ≤t−1 E>t−1 and σ t XẼ ≤t E>t have the same marginals on the systems XẼ <t E >t . We get that by applying (B5) and [37,Lemma 2]. By reasoning similar to that in the proof of [23,Theorem 3.4], consider that ≤ −nH(Ẽ|XZ) ω + n (2ε log |E| + g(ε)) . (B6) The final inequality is a consequence of (B4). We can now bound the quantity H(F nẼn ) σ n − H(E n |X) σ 0 of interest from above as follows: ). The first inequality follows from (B3) and (B6). The second inequality follows from the chain rule. The final inequality follows because the state ω ZXFẼ is a particular one to consider for optimizing the entropy difference. Furthermore, it suffices to optimize over pure states due to another application of the data processing inequality. Since we have shown the above chain of inequalities for an arbitrary positive integer n and an arbitrary initial ensemble at the channel input, we can conclude the statement of the theorem.
Appendix C: Properties of the amplitude damping channel We first prove Proposition IV.2, which states that cov P (A p ) = p 2 . Proof of Proposition IV.2. We set G = P and argue by employing Lemma II.3, proving the equality in (29) by first showing that the maximally entangled qubit state achieves the diamond norm and then that the resulting trace distance is equal to p 2 , i.e., First, consider a general channel N and its twirled version N G with respect to some covariance group {(U g , V g )} g , where {U g } g is a one-design. We again use the notation N g := V g † • N • U g . Taking the generalized divergence to be the trace distance, ψ RA an arbitrary pure state, and applying Lemma II.3, we find that where π G denotes the maximally mixed state (note that for the second channel, we get the maximally mixed state here because the channel is already symmetrized with respect to the covariance group). The second equality follows from how the trace norm decomposes when acting on block-diagonal operators.
Applying the above inequality to the amplitude damping channel A p and the symmetrized channel A p,G with covariance group given by the Pauli group on the input and output, and noting that A p is covariant with respect to σ Z , we find that For an amplitude damping channel, consider that A p,G (·) = 1 2 A p (·) + 1 2 σ X A p (σ X (·) σ X )σ X . This implies that Combining with the above, this implies that the following inequality holds for any state ψ RA : This establishes that the diamond norm is achieved by the maximally entangled state. We can then use the above again to see that To compute the value of the right-hand side, recall that the Kraus operators of the amplitude damping channel A p are given by which implies that the Kraus operators of σ X A p (σ X (·) σ X )σ X are given by Applying these Kraus operators to the maximally entangled state |Φ = 1 √ 2 (|00 + |11 ) leads to (1 − p) |00 00| + 1 − p|00 11| Then we find that implying that and in turn that This concludes the proof.
Next, we prove Proposition IV.3, which states that Note that numerics suggest that f (p) is in fact optimal, i.e., EB(A p ) = f (p).
Proof of Proposition IV.3. We prove the lower bound on EB(A p ) by judiciously choosing a feasible point of the primal SDP for EB(A p ). The primal SDP can be obtained from the dual formulation in (10) by standard techniques (we use the notation X A , Y A := Tr(X † A Y A ) for the Hilbert-Schmidt inner product): where A p is the Choi operator of the amplitude damping channel A p , We now make the following ansatz for the variables appearing in the primal SDP in (C1) (with a dot representing a zero for improved readability): 5 where q 1 , q 2 , r ≥ 0 are real parameters satisfying r 2 = q 1 q 2 and r = 1 − 1 2 (q 1 + q 2 ).
It is easy to check that, imposing the conditions (C4) on q 1 , q 2 , r, the choices of N AB , P AB , H A , M A in (C3) satisfy all constraints in (C1). Moreover, for these choices the objective function reduces to With the constraints (C4), the objective function (C5) can be determined as a function f (p) using the method of Lagrange multipliers, which we carried out in the attached Mathematica notebook amp_damp_EB_parameter.nb. This yields It is furthermore easy to see that f (p) ≥ 1 2 (1 − p), which proves the claim.
To conclude, we prove the fact that the amplitude damping channel A p is a low-noise channel in the sense of [59], i.e., id −A p = 2p.
Proof of Proposition IV.1. By sending in the state |1 1| (with trivial purification |11 11|) to both channels, we first obtain the following lower bound: id −A p ≥ 2p.

Indeed, consider that
A p (|1 1|) = (1 − p)|1 1| + p|0 0|, 5 The ansatz in (C3) and (C4), which seems rather ad-hoc at first, was determined by carefully analyzing the optimal numerical solutions to the SDP in (C1). We thus need to prove that the value of 2p is indeed optimal. One way to show this is by SDP duality as follows. Consider the bipartite operator where q := 1 − √ 1 − p. It is easy to check (see amp_damp_feasible_Z.nb in the ancillary files) that where γ ≡ |γ γ| is the Choi operator of id, and where A p is the Choi operator of A p as given in (C2). The two conditions (C6) show that Z AB is a feasible point for the dual SDP of 1 2 id −A p in (2). Furthermore, Tr B Z AB = p1 A , which shows that 1 2 id −A p ≤ p, concluding the proof.
In the following, we also give an analytical proof of the fact that id −A p ≤ 2p. We consider only the interval p ∈ (0, 1] because otherwise the diamond norm is trivially equal to zero, given that the amplitude damping channel A p becomes the identity channel for p = 0. The identity channel and the amplitude damping channel are jointly covariant with respect to the group {I, σ Z }. Applying Proposition II.4, we find that the optimal state for the diamond norm of the difference id −A p takes the form: for some q ∈ [0, 1]. By following steps similar to those in the proof of Proposition IV.2, we find that One can compute that the eigenvalues of the above matrix are given by 0, p(q − 1), 1 2 p (1 − q) ± (1 − q) r(p, q) , where r(p, q) := p 2 (1 − q) + 8q 1 − 1 − p − 4pq.


extfieldsofstudy:
Biology
Computer Science

s2fieldsofstudy:
Computer Science
Biology

text:
Snaptron: querying and visualizing splicing across tens of thousands of RNA-seq samples

As more and larger genomics studies appear, there is a growing need for comprehensive and queryable cross-study summaries. Snaptron is a search engine for summarized RNA sequencing data with a query planner that leverages R-tree, B-tree and inverted indexing strategies to rapidly execute queries over 146 million exon-exon splice junctions from over 70,000 human RNA-seq samples. Queries can be tailored by constraining which junctions and samples to consider. Snaptron can also rank and score junctions according to tissue specificity or other criteria. Further, Snaptron can rank and score samples according to the relative frequency of different splicing patterns. We outline biological questions that can be explored with Snaptron queries, including a study of novel exons in annotated genes, of exonization of repetitive element loci, and of a recently discovered alternative transcription start site for the ALK gene. Web app and documentation are at http://snaptron.cs.jhu.edu. Source code is at https://github.com/ChristopherWilks/snaptron under the MIT license.

Introduction
The Sequence Read Archive (SRA) is a huge and valuable repository of public and controlledaccess sequencing data, spanning over 9 petabases and doubling in size every 18-20 months.
Such archives allow researchers to reproduce past studies, combine data in new ways, and access unique datasets that would otherwise be too expensive or difficult to obtain. But researchers struggle to take full advantage of archived data. There is no convenient way to pose scientific questions against the archives without first downloading and re-analyzing data. The situation is analogous to the early days of the World Wide Web, when content was accessed at well known addresses via transport protocols (FTP, HTTP). The web became vastly easier to use with the advent of search engines: crawlers, indexes, and ranking algorithms made it possible for users to filter the web for content relevant to their queries.
Snaptron is a search engine that enables study of splicing patterns in large, pre-analyzed collections of human RNA sequencing (RNA-seq) samples. Snaptron answers queries via a Representational State Transfer (RESTful) web service interface. Driving Snaptron is a query planner that combines the strengths of different indexing strategies (R-trees, B-trees and term-document inverted indices) to rapidly address user queries. The data used to service a given query can be a mix of genomic interval data, numeric values associated with genomic intervals, and free-or controlled-text from associated metadata. The REST interface can be queried via HTTP with no software installation necessary. Alternately, Snaptron can be queried via a client script that provides a richer set of queries. Users may also download the (large) files used to populate Snaptron's database as well as the Snaptron server software to create a fully local Snaptron installation.
While past efforts address the problem of enabling efficient cross-study queries, most have focused on genotype rather than expression or splicing data. GEMINI [1] and Genome Query Tools (GQT) [2] are complementary tools for indexing and querying genotypes from many individuals, facilitating computation of genomewide summaries over subsets of individuals. BGT [3] builds on the positional Burrows-Wheeler Transform (PBWT) [4] to provide similar functionality, including region-specific queries. The ExAC [5] browser and REST allow querying of frequencies of genetic variants, as summarized over 90,000 re-analyzed exomes.
Other past efforts sought to enable querying of expression data in particular. Solomon and Kingsford propose Sequence Bloom Trees (SBTs) [6] for indexing the raw reads from many sequencing samples. They indexed 2,652 human RNA-seq experiments and queried the index using known transcript sequences. The index reports which samples contain the query string, but it is up to the user to build the index and to reduce a biological question into such a presence/absence query. The Expression Atlas [7] summarizes a curated subset of the data in ArrayExpress [8] and enables querying of baseline gene expression and differential gene expression across groups in certain studies. But it enables only gene-level queries, and only performs differential gene expression comparisons over manually-selected subsets of the samples in the archive.
Another focus of past work has been on computational problems that arise when working with many genomic intervals. BEDTools [9] and GenomicRanges [10] are widely used tools for working with intervals. The Genome Query Language (GQL) [11] is a SQL-like language for searching and joining aligned reads with other genome-mapped data. GORPipe [12] provides an interface to genomic interval based data, where queries are accelerated via file seeks on tabular genomic data files sorted by start-positions.
Our goal is to create a full suite of search-engine software for summarizing expression and splicing data. The project began with a "crawling" effort, described previously [13,14], where we used the Rail-RNA software tool to analyze tens of thousands of RNA-seq samples in a uniform fashion. Here we present the Snaptron tool, which can rapidly answer sophisticated queries with respect to splicing and expression data as well as sample metadata. Snaptron makes it easier to leverage large amounts of public data in data-to-day research, without needing users to be overly concerned with lower-level computational ideas (indexing schemes, data structures) used in the system itself. Snaptron is particularly useful for lending additional context and support to hypotheses related to splicing.
In Methods we describe the design of Snaptron and results from the performance profiling that inform the current design. In Results, we describe analyses leveraging both the REST interface and the command-line client for Snaptron. These are examples of analyses that users can perform using Snaptron queries. The Snaptron REST service and documentation are available   Table 1. sample. This is the source material for Snaptron as well as for the intropolis resource [14].
Intropolis makes junction data available for bulk download but without an indexing facility and without an interface for querying the data. Further details on alignment of GTEx samples are contained in [15], while details on alignment of other SRA samples as well as TCGA samples are contained in [16].
Snaptron further adds auxiliary information to each junction: • Gene annotation status (discussed below) • Count of samples with one or more reads covering the junction We used a composite of several gene annotation sources (Supplementary Table 1) to determine annotation status of each junction, and of each junction's donor and acceptor splice sites. If the junction as a whole appears in an annotation, we mark the junction and its splice sites as annotated. If the junction does not appear as a whole, each splice site is marked according to whether it participates in an annotated splice junction. We used UCSC's liftOver tool to convert annotation sources between genomic coordinate systems.
Data types. Snaptron uses a hybrid indexing approach that enables efficient querying and retrieval. Queries can be concerned with these distinct but related data types: • Genomic intervals, each consisting of a chromosome and beginning and ending offsets. An interval might represent an exon-exon splice junction or an exon as it appears in a gene annotation. A collection of intervals might represent all exon-exon splice junctions in a sample.
Intervals within a collection might overlap, i.e. cover some of the same genomic positions.
• Integer and floating-point numbers. For example, Snaptron uses non-negative integers to encode the number of reads spanning an exon-exon junction in a sample. Snaptron also stores pre-calculated summaries such as the average coverage of a junction across all samples it appears in, or the number of samples in which a junction has non-zero coverage.
• Variable length strings of text, for sample metadata. Metadata is stored in a combination of semi-and un-structured fields where semi-structured fields here are controlled vocabulary and ID/accession fields. Unstructured data are free-text fields ranging from fragments to full paragraphs. A semi-structured text field might contain metadata of a category that is particularly clearly annotated: i.e. sex and tissue type of a sample from the GTEx project.
An un-structured field might contain a study's abstract or a description of how the sample was prepared for sequencing.
The particular query determines which index or combination of indices Snaptron uses to compose the response.
Region query. A Region (R) query (Table 1) retrieves junction data situated in a given genomic interval. It is handled using Tabix [17] and its associated R-tree index. Such a query might ask for a list of exon-exon junctions that occur in any sample and that overlap a specified genomic interval. An R-tree index is a tree of nested multi-dimensional bounding rectangles. An R-tree node corresponds to the minimum bounding rectangle for the points below in the tree. Since we are working with one-dimensional intervals, the bounding rectangles are simply line segments, and the R-tree is essentially an interval tree [17] [18]. A junction and all associated data is stored in stored the lowest R-tree node fully containing the spliced interval. Data associated with a junction includes its strand, splice motif, annotation status, and its depth of coverage in each sample.
Querying a human-scale Tabix index on the current Snaptron server takes a few seconds, including overhead added by Python and Snaptron ( Figure 3). However, the performance of the Tabix R-tree depends on whether the indexed dataset is compressed. We compared the relative performance of the SQLite B-tree and the Tabix R-tree, using Tabix in both compressed and uncompressed modes, and found that uncompressed Tabix outperforms SQLite but SQLite outperforms compressed Tabix ( Figure 3). Thus, Snaptron uses the Tabix R-tree in uncompressed mode.
Further discussion of these experiments is in Supplementary Note 1.2.
When querying to find junctions that "match" a specified interval, Snaptron allows the user to specify precisely what it means to "match": • contains: match any junction that falls entirely within the specified interval • exact: match any junction with exactly the specified chromosome, start and end coordinates • either: match when either the start or end coordinate falls inside the interval Filtering attributes. A Region + Filter (R+F) query additionally constrains junction attributes.
These attributes describe, for example, annotation status, strand, or prevalence. Examples of attribute constraints are given in Table 1. Snaptron uses SQLite and its B-tree index for these queries [19]. Probes into the B-tree index are efficient -logarithmic in the size of the tree -and the tree data is organized in a blocked fashion that enables efficient transfers to and from disk.
In a Snaptron B-tree, a key represents a junction, including its chromosome, start coordinate and end coordinate. The full record, including the junction and all associated data (strand, annotation status, coverage in each sample, etc) is stored in a related tree structure.
Some junctions in Snaptron's compilations are false positives, due to alignment error and other factors [13]. Consequently, we expect a popular query type will be R+F queries requiring the returned junctions to meet a minimum level of prevalence. For instance, a user might ask for "only junctions with coverage ≥ 50" or "only junctions with non-zero coverage in ≥ 1,000 samples." While Snaptron could re-use the Tabix R-tree for both R and R+F queries, we found SQLite's B-tree was faster for the R+F case ( Figure 3). This is because the junction attribute filter is not handled by Tabix; rather, the F constraint must be handled separately by Snaptron, which parses Tabix output and suppresses records not satisfying the constraint. This adds overhead compared to SQLite, which can naturally combine the interval and attribute constraints in a single action.
Constraining metadata. Metadata constraints narrow Snaptron's focus to only those samples with metadata matching or containing key phrases. If we think of the junction evidence as forming a matrix with rows corresponding to junctions and columns to samples, metadata constraints narrow the query's focus to a subset of the columns. A metadata constraint can be used on its own in a Metadata (M) query, or combined with a Region (R) query or Region + Filter (R+F) query. We call the latter two combinations R+M and R+F+M queries (Table 1).
Snaptron uses the popular Lucene [20] inverted indexing system to handle metadata con- fields and field contents depend on the data source. Some fields contain unstructured ("free") text and describe, for example, how the sample was prepared and sequenced or what was being studied. Other fields are semi-structured, using text labels to describe categorical variables, such as whether the reads are paired-end or the sample's tissue type. For example, the GTEx compilation includes a controlled-vocabulary field describing the tissue of origin, but the SRA compilations do not; that information can often be gleaned from other free text-fields, though sometimes with difficulty [21]. The Lucene index allows searching for key phrases in any metadata field. The problem of handling this query can be decomposed into a few tasks. A "column projection" task determines which samples satisfy the metadata constraint. If C denotes the full set of columns (samples), let C ⊂ C be the subset satisfying the constraint. A "row projection" task determines which junctions (rows) satisfy the region constraint. If R denotes the full set of rows (junctions), let R ⊂ R be the satisfying subset. Once C and R are known, the final task ("submatrix filtration") is to determine the subset of R satisfying the "at least 10" constraint. Submatrix filtration is concerned only with the R × C submatrix, so summaries calculated over entire rows or columns from the original matrix cannot be reused here.
The column projection is handled by querying the Lucene index and the row projection is handled by querying the Tabix index. The set of sample IDs returned by Lucene is then converted into an Aho-Corasick automaton. The automaton performs setwise pattern matching on Snap-tron's internal string representation of the matrix rows. Specifically, Snaptron stores a row as a comma-delimited string, with each field containing the concatenation of the sample ID and the read coverage of the junction in that sample. To save space, samples with 0 coverage are not included as fields. The automaton analyzes a single row by consuming the row string's characters one-by-one and signaling when it has encountered one of the selected columns by entering a special "match" state. Each such match contributes a non-zero entry to the R × C submatrix. Once the submatrix is formed, Snaptron re-calculates row-wise summaries (e.g. sum, average, median).
Finally, if an attribute filter (F) was specified, it is evaluated with respect to the recalculated summaries to further narrow the list of returned junctions, completing submatrix filtration.
Higher-level functions. Snaptron supports three higher-level queries showcased in the Results section (Table 1). They are called higher-level because each involves particular sets of junctions defined using "basic" sub-queries.
The shared sample count (SSC) high-level query returns the number of distinct samples in a compilation that have evidence supporting the co-occurrence of two junctions. Later we show how to use SSC to study the prevalence of putative novel exons. The output of the query can easily be loaded into an R or Python session and analyzed or visualized to better understand the prevalence of a splicing pattern.
The tissue specificity (TS) high-level query uses the GTEx v6 compilation. The user specifies one or more groups of junctions using one or more region sub-queries, one sub-query per group. The TS query returns an N × 2 table, where the N rows correspond to all 9.6K samples from the GTEx project and the two columns correspond to (a) whether a junction from every group occurred in that sample, and (b) which of the 32 GTEx v6 tissue types the sample was derived from. This list can then be loaded into Python or R to assess tissue specificity.
The junction-inclusion ratio (JIR) high-level query scores each sample according to a particular overrepresented splicing pattern relative to another. The user specifies two groups of junctions using two region sub-queries. Call these groups A and B. The query calculates the normalized difference between coverage counts of the two groups across all samples containing the junctions. This is the "junction inclusion ratio" (JIR) suggested previously by Nellore et al [14], but with one added to the denominator: A and B represent the total coverage for the two groups of junctions in the sample. Ranking samples according to JIR reveals the degree to which a splicing pattern is specific to a particular kind of sample.
Interfaces. Snaptron provides the following interfaces: • RESTful web service interface (WSI): handles query requests made by a user or by other Snaptron interfaces via HTTP 1.1. Results come in the form of lists of junctions and associated junction data, or lists of samples and associated sample metadata. Queries usually return within seconds.
• Client command-line interface (CCLI): handles both basic queries and high-level queries.
High-level queries are decomposed and handled via one or more WSI queries.
• Web-based graphical user interface (GUI): allows a user to visualize splicing patterns across many samples for a given window of the genome. Supports basic queries for populating the window. Queries are decomposed and ultimately handled by the WSI.
• Complete server installation (Local): users can download the underlying Snaptron data and software, build local indices and compilations, and run a local Snaptron service for handling WSI queries. This is for advanced users who require rapid processing of high query volumes.
Users experienced with command-line tools may prefer the direct WSI interface, which has minimal software requirements and responds within seconds in most cases. Users willing to install the lightweight Python CCLI additionally gain access to high-level queries. The CCLI is easily called from wrapper scripts to compose more complex analyses, as shown in our example scripts.
The GUI is ideal for users concerned with a particular gene or genomic region. The GUI will display junctions in that region, distinguishing clearly between annotated and unannotated junctions and using colors to differentiate junctions that occur more or less widely in the dataset. After exploring in the GUI, users can switch to the CCLI or WSI to answer specific questions.

Results
We describe three analyses that use Snaptron. Each leverages public data to provide context or support for a hypothesis about splicing. Scripts for performing these analyses are available as described in Supplementary Note 1.1. Figure 5 shows screen captures from the Snaptron GUI for each analysis.

Novel Exon Discovery and Evaluation
Snaptron can measure the prevalence of candidate junctions and exons in public RNA-seq data.
Candidate junctions need not be annotated; since Snaptron's junction calls were made without the influence of a gene annotation, it can give support for both annotated and unannotated splicing patterns. We demonstrate this by following the work of Goldstein et al [22],

Exonization of Repetitive Elements
Snaptron can also use public data to measure the tissue specificity of a splicing pattern. A repetitive element locus (REL) exonizaton is an instance where a stretch of repetitive sequence (e.g. a SINE or LINE) is spliced into a surrounding gene as an exon. A study by Darby et al [25] reported numerous REL exonization events in human protein-coding genes, including events specific to brain or blood. We used Snaptron to study these events and to measure tissue specificity with respect to the much larger SRAv2 and GTEx compilations.
We began by obtaining coordinates for 5 PCR-validated REL exonization events in three genes (KCNIP4, KMT2E and GLRB) and using the shared sample count (SSC) high-level query to measure the prevalence of the events in the SRAv2 and GTEx collections. We noted that the samples studied by Darby et al, derived from the Stanley brain collection, were not present in these compilations. For both the SRAv2 and GTEx compilations, we found that all five events had a shared sample count of 39 or greater. We also found that none of the junctions flanking the events were fully annotated, in agreement with Darby et al.
We also analyzed the tissue specificity of the 5 REL exons using Snaptron's high-level Tissue Specificity (TS) query (Table 1). We then performed a Kruskal-Wallis rank sum test on the output from the TS query, using the presence/absence results as the data vector and the tissue-annotation results as the group vector. All rank sum tests yielded P < 1 · 10 −9 , indicating strong tissue specificity. For example, the REL exon we refer to as GLRB 1 is present in 33% of the 1,409 samples labeled "Brain" but only 3% of other samples. Similarly, the REL exon KMT2E 1 is present in 56% of the 102 samples labeled "Bone Marrow" but only 12% of other samples.

ALK and Junction Inclusion Ratio
Snaptron can also be used to study splicing patterns involving many junctions. To demonstrate this, we performed an experiment modeled on Nellore et al's analysis of the anaplastic lymphoma kinase (ALK) gene's ALK ATI variant isoform [14]. ALK is mutated or abberrently expressed in some cancers, with its ALK ATI variant, characterized by an alternative transcription initiation (ATI) site, found to be expressed in 11% of melanomas [26].
Following Nellore et al, we used Snaptron to demonstrate the ALK ATI variant and related EML4-ALK gene fusion can also be found in non-cancer samples. Note that whereas Nellore et al distinguish between the ALK ATI variant and the EML4-ALK fusion by integrating other assays, we do not make the distinction here. We started by using Snaptron's high-level JIR query to rank samples in order according to the difference between the total coverage of ALK junctions downstream of the ATI versus the junctions upstream. The sets of upstream and downstream junctions are defined using R+F queries. We constrained the strand to be the same as that of the ALK gene and required that junctions lie within ALK's annotated boundaries. Also following Nellore et al, we postprocessed the JIR results to exclude samples with fewer than 50 total reads covering the ALK junctions. We found that the top 10 samples in our JIR-ranked list exactly match those they reported, including the unexpected melanocyte and macrophage samples.

Discussion
Recent efforts have addressed the important and related problems of (a) analyzing many archived datasets in a uniform [13,27] and privacy-sensitive [15] fashion (b) compiling, augmenting and correcting associated metadata [28], and (c) making concise summaries available to the community [16,27]. Curated summaries are now available for collections of over 70,000 human RNAseq samples [16]. This motivates the computational question: how do we build systems that make it easy for typical biological researchers to ask and answer questions using these resources?
Snaptron is a search engine that combines summarized output from splice-aware RNA-seq alignment tools like Rail-RNA [13] with a range of indexing strategies and a sophisticated query planner. Through its array of interfaces, Snaptron allows researchers to query and visualize the vast amount of splicing data now available in summaries like intropolis [14]. At no point are users required to download or process raw sequencing data, or any other large files.
Snaptron's design addresses the question of how to combine the best qualities of multiple indexing and database systems in a way that allows rapid queries, even when queries are concerned with a combination of both structured interval and numeric data, and much less structured textual metadata. The design mixes genomics-oriented software like Tabix [17] with more generic  Figure 5: Three Snaptron GUI screen captures corresponding to the three analyses. Green horizontal lines indicate the genome. Arcs indicate exon-exon splice junctions. Colors indicate the number of samples having evidence for the junction, ranging from black (least support) to red (most). Annotated junctions are represented by arcs above the green line, and unannotated junctions by arcs below the line. Light blue rectangles are annotated exons. A) Splice junctions matching the Goldstein et al prediction of a novel alternative exon in the ABCD3 gene. A1 is the 5' junction, A2 is the novel exon, and A3 is the 3' junction; B) KMT2E gene and unannotated junctions supporting a REL exonization event. B1 is the 5' junction, B2 is the REL exon, and B3 is the 3' junction; C) ALK spliceforms. C1 indicates the full length ALK transcript, C2 is the truncated ALK ATI transcript incorporating only the last 10 exons (ALK is on the reverse strand, and so is laid out right-to-left), C3 is the alternative transcription initiation exon, and C4 is the upstream full transcription initiation site.
database and indexing systems like SQLite [19] and Lucene [20]. Generic systems like SQLite performed surprisingly well, sometimes better than genomics-oriented tools when queries conjoined interval constraints with other constraints.
To demonstrate its utility, we used Snaptron to assess: (a) prevalence of putative novel junctions and exons, (b) tissue specificity of novel splicing events, and (c) which public samples exhibit the most divergent splicing patterns for a particular gene. With the growing popularity of RNAseq analysis tools that quantify with respect to a given gene annotation [29,30], thereby trusting the completeness and accuracy of the annotation, questions about which annotated and unannotated splicing patterns are well supported by public data are increasingly crucial. Snaptron makes it easy to visualize and measure support for putative splicing patterns.
In the future it will be important to further optimize Snaptron queries that impose complex constraints on both sample metadata and junction data. While we proposed and implemented an Aho-Corasick-based method that is efficient for some expected queries -with response times measured in seconds or tens of seconds -it is not hard to construct more complex queries that push response times to minutes. The main example of this kind of search type is where thousands of samples are used to further filter a larger R+M or R+F+M query where 100's of thousands of junctions are returned. A specific example would be querying for all junctions on chromosome 1 while also requiring that all junctions appear in samples that have the keyword "tissue" in their description metadata field in the GTEx compilation. The problem is fundamentally difficult since it requires scanning, compiling and summarizing a large fraction of the overall data compilation.
It will be important to investigate more sophisticated algorithms, caching schemes, and other methods for reducing response time.
Another future goal is to generalize Snaptron's current support for coverage summaries like mean and SSC to additionally support user-defined functions. There are many possible summaries users could define or that have been proposed in previous studies, "percent spliced in" (PSI) [31] being a well known example. Allowing user-defined functions would require major changes, but would also obviate the need for Snaptron to individually support a large number of potential summaries.
Sample metadata quality is another important issue to be addressed in future work. The quality of metadata in public sequencing archives is generally poor, but recent efforts such as MetaSRA [32] provide both new methods as well as improved compilations of metadata. In the future, it will be important to integrate such efforts into Snaptron.