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.