Permutation Enhances Classical Communication Assisted by Entangled States

We study classical communication over a noisy quantum channel when bipartite states are preshared between the sender and the receiver, and one of the following encoding strategies are available: i) local operations; ii) local operations and one-way classical communication; iii) local operations and global permutations. Our main result is a capacity formula for strategy iii). This formula's two endpoints are the capacity formula in strategy i) and the entanglement-assisted classical capacity. Interestingly, these capacities satisfy the strong converse property, and thus the formula serves as a sharp dividing line between achievable and unachievable rates of communication. We prove that the difference between the capacities by strategy i) and strategy iii) is upper bounded by the discord of formation of the preshared state. What's more, we show that strategy ii) has no advantage over strategy i) in the weak converse regime. As examples, we derive these capacities analytically by the above strategies for some fundamental quantum channels. In some cases, the capacity of strategy iii) is strictly larger than those of strategies i) and ii) whenever entanglement assistance is available. Our results witness the power of random permutation in entanglement-assisted classical communication.