Communication tasks in operational theories

We investigate the question which communication tasks can be accomplished within a given operational theory. The concrete task is to find out which communication matrices have a prepare-and-measure implementation with multiple states and a single measurement from a given theory, without using shared randomness. To set a general framework for this question we develop the ultraweak matrix majorization in the set of communication matrices. This preorder gives us means to determine when one communication task is more difficult than another. Furthermore, we introduce several monotones which can be used to compare and characterize the communication matrices. We observe that not only do the monotones allow us to compare communication matrices, but also their maximal values in a given theory are seen to relate to some physical properties of the theory. The maximal values can then be thought as 'dimensions', allowing us to compare different theories to each other. We analyse the introduced monotones one by one and demonstrate how the set of implementable communication matrices is different in several theories with the focus being mainly on the difference between classical and quantum theories of a given dimension. (paper)