8 transmits one classical message from a set of M messages and an arbitrary quantum state of dimension K using a large number n uses of the quantum channel and a maximally entangled state Φ T$_{A}$T$_{B}$ of dimension D . The classical rate of transmission is C ≡ log( M ) n bits per chan- nel use, the quantum rate of transmission is Q ≡ log( K ) n qubits per channel use, and the rate of entanglement con- sumption is E ≡ log( D ) n ebits per channel use. If there is a scheme that transmits classical data, transmits quantum data, and consumes entanglement at respective rates C , Q , and E with vanishing error probability and fidelity approaching unity in the limit of a large number of uses of the channel, we say that the rates C , Q , and E form an achievable rate triple ( C,Q,E ). using a large number n uses of the quantum channel and a maximally entangled state Φ T$_{A}$T$_{B}$ of the form in (6) where the sender possesses the system T$_{A}$ , the receiver possesses the system T$_{B}$ , and D is the Schmidt rank of the entanglement. The classical rate of transmission is C ≡ log( M ) n bits per channel use, and the rate of entan- glement consumption is E ≡ log( D ) n ebits per channel use. If there is a scheme that transmits classical data at rate C with vanishing error probability and consumes entan- glement at rate E in the limit of a large number of uses of the channel, we say that the rates C and E form an achievable rate pair ( C,E ). Shor’s main result in Ref. [39] is that all achievable rate pairs lie in the following entanglement-assisted classical capacity region of N : Hsieh and Wilde’s main result in Ref. [40] is that all achievable rate triples lie in the following CQE capacity region for the channel N : where the “one-shot” region C (1) $_{CE}$( N ) is a union of the “one-shot, one-state” regions C (1) CE, $_{ρ}$( N ). The one-shot, one-state region C (1) CE, $_{ρ}$( N ) is the set of all C,E ≥ 0 such that where the one-shot region C (1) $_{CQE}$( N ) is the union of the “one-shot, one-state” regions C (1) CQE, $_{ρ}$( N ). The “one-shot, one-state” region C (1) CQE, $_{ρ}$( N ) is the set of all C,Q,E ≥ 0 such that C$_{CQE}$ ( N ) = ∞ ⋃ k =1 1 k C (1) $_{CQE}$( N ⊗ $^{k}$) , C$_{CE}$ ( N ) = ∞ ⋃ k =1 1 k C (1) $_{CE}$( N ⊗ $^{k}$) , (16) C ≤ I ( AX ; B )$_{ρ}$ , E ≥ H ( A | X )$_{ρ}$ , C + 2 Q ≤ I ( AX ; B )$_{ρ}$ , (17) Q ≤ I ( A 〉 BX )$_{ρ}$ + E, (18) C + Q ≤ I ( X ; B )$_{ρ}$ + I ( A 〉 BX )$_{ρ}$ + E. (19) where ρ is again a state of the form in (15). Hsieh and Wilde later gave a more refined “trape- zoidal” characterization of the one-shot, one-state region C (1) CE, $_{ρ}$( N ) [40], but the one-shot regions C (1) $_{CE}$( N ) result- ing from both Shor’s “rectangular” characterization and Hsieh and Wilde’s pentagonal characterization are equiv- alent, and the characterization above suffices for our pur- poses here. One of the observations in Ref. [40] is that there is a way to single-letterize the CQE capacity region provided one can show that both the CQ and CE trade-off curves single-letterize. We review these arguments briefly. Sup- pose that we have shown that both the CQ and CE trade- off curves single-letterize. Then three surfaces specify the boundary of the CQE capacity region so that we can simplify the characterization in (17-19). The first surface to consider is that formed by combining the CE trade-off curve with the “inverse” of the super-dense coding proto- col. Recall that the super-dense coding protocol exploits a noiseless ebit and a noiseless qubit channel to transmit two classical bits [38]. Let ( C$_{CE}$ ( s$_{1}$ ) , 0 ,E$_{CE}$ ( s$_{1}$ )) denote a parametrization of all points on the CE trade-off curve with respect to some parameter s$_{1}$ ∈ [0 , 1 / 2], and recall that each point on the trade-off curve has corresponding entropic quantities of the form ( I ( AX ; B ) , 0 ,H ( A | X )). Then the surface formed by combining the CE trade-off curve with the inverse of super-dense coding is For general channels, the multi-letter characterization in (16) is necessary, but for certain channels, such as the erasure channels and generalized dephasing channels, the CE capacity region admits a single-letter characteriza- tion as Ref. [40] stated and as we show in full detail here for the generalized dephasing channels. In fact, in Sec- tion IV B, we show that the CE region for all Hadamard channels, of which a generalized dephasing channel is an example, admits a single-letter characterization. The natural generalization of the two scenarios we have just considered is entanglement-assisted classical and quantum (CQE) communication. The goal of such a protocol is to transmit as much classical information with vanishing error probability and quantum informa- tion with fidelity approaching unity while consuming as little entanglement as possible in the limit of a large num- ber of uses of the channel N . More precisely, the protocol This surface forms an outer bound for the capacity re- gion. Were it not so, then one could combine points outside it with super-dense coding to outperform points C. The Capacity Region for Entanglement-Assisted Transmission of Classical and Quantum Information { ( C$_{CE}$ ( s$_{1}$ ) − 2 Q,Q,E$_{CE}$ ( s$_{1}$ ) − Q ) : s$_{1}$ ∈ [0 , 1 / 2] , 0 ≤ Q ≤ min { 1 $_{2}$C$_{CE}$ ( s$_{1}$ ) ,E$_{CE}$ ( s$_{1}$ ) } } .