19 The following additivity lemma aids in proving the ad- ditivity of the plane in (17). Lemma 7 The following additivity relation holds for any two quantum channels N$_{1}$ and N$_{2}$ : where U A$_{j}$ → B$_{j}$E$_{j}$ j is the isometric extension of N$_{j}$ . Suppose further that ρ is the state that maximizes h ( N$_{1}$ ⊗ N$_{2}$ ). Proof. The inequality h ( N$_{1}$ ⊗N$_{2}$ ) ≥ h ( N$_{1}$ )+ h ( N$_{2}$ ) triv- ially holds for all quantum channels, because the maxi- mization on the RHS is a restriction of the maximization in the LHS to a tensor product of states of the form in (15). Therefore, we prove the non-trivial inequality h ( N$_{1}$ ⊗ N$_{2}$ ) ≤ h ( N$_{1}$ ) + h ( N$_{2}$ ). Let Appendix A: Single-letterization of the Plane in (17) ψ XAA$_{1}$A$_{2}$ ≡ ∑ x p$_{X}$ ( x ) | x 〉〈 x | X ⊗ | ϕ$_{x}$ 〉〈 ϕ$_{x}$ | AA$_{1}$$^{A$_{2}$}$, θ XAB$_{1}$E$_{1}$A$_{2}$ ≡ U$_{1}$ψU † $_{1}$, ω XAA$_{1}$B$_{2}$E$_{2}$ ≡ U$_{2}$ψU † $_{2}$, ρ XAB$_{1}$E$_{1}$B$_{2}$E$_{2}$ ≡ ( U$_{1}$ ⊗ U$_{2}$ ) ψ ( U$_{1}$ ⊗ U$_{2}$ ) $^{†}$, h ( N$_{1}$ ⊗ N$_{2}$ ) = h ( N$_{1}$ ) + h ( N$_{2}$ ) . h ( N$_{1}$ ⊗ N$_{2}$ ) = I ( AX ; B$_{1}$B$_{2}$ )$_{ρ}$ = H ( B$_{1}$B$_{2}$ | E$_{1}$E$_{2}$X )$_{ρ}$ + H ( B$_{1}$B$_{2}$ )$_{ρ}$ ≤ H ( B$_{1}$ | E$_{1}$X )$_{ρ}$ + H ( B$_{1}$ )$_{ρ}$ + H ( B$_{2}$ | E$_{2}$X )$_{ρ}$ + H ( B$_{2}$ )$_{ρ}$ , = H ( B$_{1}$E$_{1}$ | X )$_{ρ}$ − H ( E$_{1}$ | X )$_{ρ}$ + H ( B$_{1}$ )$_{ρ}$ + H ( B$_{2}$E$_{2}$ | X )$_{ρ}$ − H ( E$_{2}$ | X )$_{ρ}$ + H ( B$_{2}$ )$_{ρ}$ = H ( AA$_{2}$ | X )$_{θ}$ − H ( AA$_{2}$B$_{1}$ | X )$_{θ}$ + H ( B$_{1}$ )$_{θ}$ + H ( AA$_{1}$ | X )$_{ω}$ − H ( AA$_{1}$B$_{1}$ | X )$_{ω}$ + H ( B$_{2}$ )$_{ω}$ = I ( AA$_{2}$X ; B$_{1}$ )$_{θ}$ + I ( AA$_{1}$X ; B$_{2}$ )$_{ω}$ ≤ h ( N$_{1}$ ) + h ( N$_{2}$ ) . The following chain of inequalities holds for any two channels N$_{1}$ and N$_{2}$ : to a point on the CE trade-off curve. That is, given the constraint C = I ( AX ; B )$_{ρ}$, there exists some other state σ XAB of the form in (15) such that I ( AX ; B )$_{σ}$ = I ( AX ; B )$_{ρ}$ = C , but E = H ( A | X )$_{σ}$ < H ( A | X )$_{ρ}$. That is, the state σ allows for communication of as much clas- sical information as the state ρ does, but consumes less entanglement. But then the following inequality holds for all λ ≥ 0: The first equality holds because ρ is the state that max- imizes h ( N$_{1}$ ⊗ N$_{2}$ ). The second equality follows from straightforward entropic manipulations by noting that the state ρ on systems A , B$_{1}$ , B$_{2}$ , E$_{1}$ , and E$_{2}$ is pure when conditioned on X . The first inequality follows from an application of strong subadditivity [61] and subaddi- tivity. The next three equalities follow by straightforward entropic manipulations. The last inequality follows from the definition of h in (20) and the fact that both θ and ω are states of the form in (15). Proof of Lemma 1. The proof follows from Lemma 7 in the same way as Corollary 1 does from Lemma 4. We remark that the above lemma follows from the single-letterization of the entanglement-assisted classical capacity [37], but we have included the result for com- pleteness. contradicting the fact that the state ρ XAB maximizes (23). I ( AX ; B )$_{σ}$ − λH ( A | X )$_{σ}$ > I ( AX ; B )$_{ρ}$ − λH ( A | X )$_{ρ}$ , Lemma 9 We get all points on the CE trade-off curve by considering 0 ≤ λ ≤ 1 in the maximization in (23) because the maximization optimizes only the classical ca- pacity when λ > 1 . Proof. Consider a state ρ XABE of the form in (15). Suppose that we perform a von Neumann measurement of the system A , resulting in a classical variable Y , and let σ XY BE denote the resulting state. The following chain Proof. We argue by contradiction. Suppose that ρ XAB maximizes (23). Suppose further that it does not lead Lemma 8 For any fixed λ ≥ 0 , the function in (23) leads to a point ( I ( AX ; B )$_{ρ}$ ,H ( A | X )$_{ρ}$) on the one-shot CE trade-off curve in the sense of Theorem 3. Appendix B: Proof of the Single-letterization of the CE Trade-off Curve for Hadamard channels