21 suffices to consider a classical-quantum state with diag- onal conditional density operators, in the sense that the following inequality holds: Lemma 11 λ parametrizes all points on the CQ and CE trade-off curves with the possible exception of those lying on segments of constant slope. where Proof. We prove the lemma for the case of the CQ trade- off curve. The proof for the CE trade-off curve is similar. Let ( C ( t ) , Q ( t )) for 0 ≤ t ≤ 1 be a parametrization of the trade-off curve with C (0) equal to the classical capacity and Q (1) equal to the quantum capacity. The function C ( t ) is monotonically decreasing and the function Q ( t ) is monotonically increasing. The graph of the trade-off curve is convex and, therefore, has one-sided directional derivatives at all points [70]. It is also monotonically decreasing. Consider the function f$_{λ}$ ( N ) where U A $^{′}$→ BE N is an isometric extension of N , ϕ A ′ x = Δ( ϕ A ′ x ) = Δ( φ A ′ x ) , and Δ is the completely dephasing channel. Appendix C: On the parametrization of the trade-off curve I ( X ; B )$_{ρ}$ + λI ( A 〉 BX )$_{ρ}$ ≤ I ( X ; B )$_{θ}$ + λI ( A 〉 BX )$_{θ}$ , ρ XABE ≡ ∑ x p$_{X}$ ( x ) | x 〉 〈 x | X ⊗ U A $^{′}$→ BE N ( φ AA ′ x ) , θ XABE ≡ ∑ x p$_{X}$ ( x ) | x 〉 〈 x | X ⊗ U A $^{′}$→ BE N ( ϕ AA ′ x ) , f$_{λ}$ ( N ) ≡ max$_{ρ}$ XBE I ( X ; B ) + λI ( A 〉 BX ) . C ( t ) + λQ ( t ) ≥ C ( s ) + λQ ( s ) . (C1) σ XAY E ≡ ∑ x p$_{X}$ ( x ) | x 〉 〈 x | $^{X}$⊗ (Δ B → Y ◦ U A $^{′}$→ BE N )( φ AA ′ x ) . C ( s ) − C ( t ) Q ( s ) − Q ( t ) ≥ − λ I ( X ; B )$_{ρ}$ + λI ( A 〉 BX )$_{ρ}$ = H ( B )$_{ρ}$ + ( λ − 1) H ( B | X )$_{ρ}$ − λH ( E | X )$_{ρ}$ ≤ H ( Y )$_{σ}$ + ( λ − 1) H ( Y | X )$_{σ}$ − λH ( E | X )$_{σ}$ = H ( B )$_{θ}$ + ( λ − 1) H ( B | X )$_{θ}$ − λH ( E | X )$_{θ}$ = I ( X ; B )$_{θ}$ + λI ( A 〉 BX )$_{θ}$ . C ( s ) − C ( t ) Q ( s ) − Q ( t ) ≤ − λ. Proof. The proof of this lemma is similar to the proof of Lemma 9 in Ref. [71]. Consider another classical- quantum state σ in addition to the two presented in the statement of the theorem: For any 0 ≤ t ≤ 1, we have f$_{λ}$ ( N ) = C ( t ) + λQ ( t ) if and only if Then the following chain of inequalities holds for all λ ≥ 1: for all 0 ≤ s ≤ 1. Perhaps more instructively, if s < t and Q ( s ) = Q ( t ), this inequality can be written as because of the monotonicity of the functions C and Q . Likewise, when s > t , it has the form The first equality follows from entropic manipulations. The inequality follows because the entropies H ( B )$_{ρ}$ and H ( B | X )$_{ρ}$ can only increase under a complete dephasing [61]. The second equality follows because N ◦ Δ = Δ ◦ N and N c ◦ Δ = N c for a generalized dephasing channel N , and the final equality follows from entropic manipu- lations. If ( C ( t ) , Q ( t )) is a point on the graph at which the deriva- tive is not constant, then setting − λ to be the slope of the graph will lead to Eq. (C1) being satisfied. If the graph is not differentiable at ( C ( t ) , Q ( t )), then the slope must drop discontinuously at that point. Setting − λ to any value in the gap will again lead to the condition being satisfied. Lemma 13 An ensemble of the following form parametrizes all points on the CQ trade-off curve for a qubit dephasing channel: At points where the graph is differentiable but the slope is constant, λ might not be a good parameter. These points, however, are in the convex hull of the points that λ does parametrize. where ψ AA ′ 0 and ψ AA ′ 1 are pure states, defined as follows for µ ∈ [0 , 1 / 2] : We first prove two important lemmas and then prove a theorem that gives the exact form of the CQ trade-off curve. Lemma 12 Let N be a generalized dephasing channel. In the optimization task for the CQ trade-off curve, it Proof. We assume without loss of generality that the dephasing basis is the computational basis. Consider a Appendix D: Form of the CQ Trade-off Curve for Qubit Dephasing Channels 1 2 | 0 〉 〈 0 | X ⊗ ψ AA ′ 0 + 1 2 | 1 〉 〈 1 | X ⊗ ψ AA ′ 1 , (D1) Tr$_{A}$ $^{{}$ψ AA ′ 0 } = µ | 0 〉 〈 0 | A ′ + (1 − µ ) | 1 〉 〈 1 | A ′ , (D2) Tr$_{A}$ $^{{}$ψ AA ′ 1 } = (1 − µ ) | 0 〉 〈 0 | A ′ + µ | 1 〉 〈 1 | A ′ . (D3)