  For a classical channel, neither the Shannon capacity, nor the sum of
conditional probabilities corresponding to the cases of successful transmission
can be increased by the use of a non-signaling resource. Yet, perhaps somewhat
counterintuitively, entanglement assistance can help and actually elevate the
chances of success even in a one-way communicational task that is to be
completed by a single-shot use of a noiseless classical channel.
  To quantify the help that a non-signaling resource provides to a noiseless
classical channel, one might ask how many extra letters should be added to the
alphabet of the channel in order to perform equally well without the specified
non-signaling resource. As was observed by Cubitt, Leung, Matthews, and Winter,
there is no upper bound on the number of extra letters required for
substituting the assistance of a general non-signaling resource to a noiseless
one-bit classical channel. In contrast, here we prove that if this resource is
a bipartite quantum system in a maximally entangled state, then an extra
classical bit always suffices as a replacement.
