22 Proof of CQ trade-off in Theorem 4. We simply need to compute the Holevo information I ( X ; B ) and the coherent information I ( A 〉 BX ) for an ensemble of the form in the statement of Lemma 13, due to the results of Lemmas 12 and 13. First consider respective purifications of the states in (D2-D3): classical-quantum state with a finite number N of diag- onal conditional density operators ρ A ′ x : We can form a new classical-quantum state with dou- ble the number of conditional density operators by “bit- flipping” the original conditional density operators: The above states lead to a classical-quantum state of the form in (D1). An isometric extension U$_{N}$ = $^{√}$1 − p $_{2}$I ⊗ | 0 〉 E + √ p $_{2}$Z ⊗ | 1 〉 E of the qubit dephasing channel acts as follows on the above states: where X is the σ$_{X}$ “bit-flip” Pauli operator. Consider the following chain of inequalities that holds for all λ ≥ 1: | ψ$_{0}$ 〉 AA ′ = √ µ | 0 〉 $^{A}$| 0 〉 A ′ + $^{√}$1 − µ | 1 〉 $^{A}$| 1 〉 A ′ , (D4) | ψ$_{1}$ 〉 AA ′ = $^{√}$1 − µ | 0 〉 $^{A}$| 0 〉 A ′ + √ µ | 1 〉 $^{A}$| 1 〉 A ′ . (D5) ρ XA ′ ≡ N − 1 ∑ x =0 p$_{X}$ ( x ) | x 〉〈 x | X ⊗ ρ A ′ x . σ XA ′ ≡ 1 2 N − 1 ∑ x =0 p$_{X}$ ( x ) | x 〉〈 x | X ⊗ ρ A ′ x + 1 2 N − 1 ∑ x =0 p$_{X}$ ( x ) | x + N 〉〈 x + N | X ⊗ Xρ A ′ x X, | ψ$_{0}$ 〉 ABE ≡ U$_{N}$ | ψ$_{0}$ 〉 AA ′ = √ µ | 0 〉 $^{A}$| 0 〉 B ( √ 1 − p 2 | 0 〉 E +$^{√}$ p 2 | 1 〉 E ) + $^{√}$1 − µ | 1 〉 $^{A}$| 1 〉 B ( √ 1 − p 2 | 0 〉 E −$^{√}$ p 2 | 1 〉 E ) , | ψ$_{1}$ 〉 ABE ≡ U$_{N}$ | ψ$_{1}$ 〉 AA ′ = $^{√}$1 − µ | 0 〉 $^{A}$| 0 〉 B ( √ 1 − p 2 | 0 〉 E +$^{√}$ p 2 | 1 〉 E ) + √ µ | 1 〉 $^{A}$| 1 〉 B ( √ 1 − p 2 | 0 〉 E −$^{√}$ p 2 | 1 〉 E ) . I ( X ; B )$_{ρ}$ + λI ( A 〉 BX )$_{ρ}$ = H ( B )$_{ρ}$ + ( λ − 1) H ( B | X )$_{ρ}$ − λH ( E | X )$_{ρ}$ = H ( B )$_{ρ}$ + ( λ − 1) H ( B | X )$_{σ}$ − λH ( E | X )$_{σ}$ ≤ H ( B )$_{σ}$ + ( λ − 1) H ( B | X )$_{σ}$ − λH ( E | X )$_{σ}$ = 1 + ( λ − 1) H ( B | X )$_{σ}$ − λH ( E | X )$_{σ}$ = 1 + ∑ x p$_{X}$ ( x ) $^{[}$( λ − 1) H ( B )$_{ρ}$$_{x}$ − λH ( E )$_{ρ}$$_{x}$ ] ≤ 1 + max$_{x}$ $^{[}$( λ − 1) H ( B )$_{ρ}$$_{x}$ − λH ( E )$_{ρ}$$_{x}$ ] = 1 + ( λ − 1) H ( B )$_{ρ}$$_{∗}$ x − λH ( E )$_{ρ}$$_{∗}$ x . ρ XABE ≡ 1 2$^{[}$ | 0 〉〈 0 | $^{X}$⊗ | ψ$_{0}$ 〉〈 ψ$_{0}$ | $^{ABE}$+ | 1 〉〈 1 | $^{X}$⊗ | ψ$_{1}$ 〉〈 ψ$_{1}$ | ABE ] . (D6) ρ XB = 1 2$^{[}$ | 0 〉〈 0 | X ⊗ ψ B 0 + | 1 〉〈 1 | X ⊗ ψ B 1 ] , ψ B 0 = µ | 0 〉〈 0 | B + (1 − µ ) | 1 〉〈 1 | $^{B}$, ψ B 1 = (1 − µ ) | 0 〉〈 0 | B + ( µ ) | 1 〉〈 1 | $^{B}$, ρ B = 1 2$^{[}$ | 0 〉〈 0 | B + | 1 〉〈 1 | B ] . The first equality follows by standard entropic manipu- lations. The second equality follows because the condi- tional entropy H ( B | X ) is invariant under a bit-flipping unitary on the input state that commutes with the chan- nel: H ( B )$_{Xρ}$ B $_{x}$X = H ( B )$_{ρ}$ B x . Furthermore, a bit flip on the input state does not change the eigenvalues for the output of the dephasing channel’s complementary chan- nel (as observed in Section II C 3): H ( E )$_{N}$ $^{c}$( Xρ A ′ x X ) = H ( E )$_{N}$ $^{c}$( ρ A ′ x $_{)}$. The first inequality follows because en- tropy is concave, i.e., the local state σ B is a mixed ver- sion of ρ $^{B}$. The third equality follows because H ( B )$_{σ}$ B = H ( ∑ x 1 $_{2}$p$_{X}$ ( x ) ( ρ B x + Xρ B $_{x}$X ) = H ( 1 2 $^{∑}$$_{x}$p$_{X}$ ( x ) I ) = 1. The fourth equality follows because the system X is classical. The second inequality follows because the maximum value of a realization of a random variable is not less than its expectation. The final equality simply follows by defining ρ ∗ x to be the conditional density op- erator on systems B and E that arises from sending a diagonal state of the form µ | 0 〉 〈 0 | A ′ + (1 − µ ) | 1 〉 〈 1 | A ′ through the channel. Thus, an ensemble of the kind in (D1) is sufficient to attain a point on the CQ trade-off curve. The classical-quantum state at the output of the channel is as follows: The following states are useful for computing the en- tropies H ( B ) and H ( B | X ): The Holevo information is then as follows: In the last step above, we observe that there is a direct correspondence between µ that parametrizes the ensem- ble and λ that parametrizes a point on the CQ trade-off curve. We now compute the coherent information I ( A 〉 BX ) = H ( B | X ) − H ( E | X ). The following states are important I ( X ; B ) = H ( B ) − H ( B | X ) = 1 − H$_{2}$ ( µ ) .