Optimality of Meta-Converse for Channel Simulation

We study the effect of shared non-signaling correlations for the problem of simulating a channel using noiseless communication in the one-shot setting.For classical channels, we show how to round any non-signaling-assisted simulation strategy -which corresponds to the natural linear programming meta-converse for channel simulation -to a strategy that only uses shared randomness.For quantum channels, we round any non-signaling-assisted simulation strategy to a strategy that only uses shared entanglement.Our main result is for classical and classical-quantum channels, for which we employ ideas from approximation algorithms to give a guarantee on the ratio of success probabilities of at least (1 -e -1 ).We further show this ratio to be optimal for the purely classical case.It can be improved to (1 -t -1 ) using O(ln ln(t)) additional bits of communication.