  We investigate the correlations that can arise between Alice and Bob in
prepare-and-measure communication scenarios where the source (Alice) and the
measurement device (Bob) can share prior entanglement. The paradigmatic example
of such a scenario is the quantum dense coding protocol, where the
communication capacity of a qudit can be doubled if a two-qudit entangled state
is shared between Alice and Bob. We provide examples of correlations that
actually require more general protocols based on higher-dimensional entangled
states. This motivates us to investigate the set of correlations that can be
obtained from communicating either a classical or a quantum $d$-dimensional
system in the presence of an unlimited amount of entanglement. We show how such
correlations can be characterized by a hierarchy of semidefinite programming
relaxations by reducing the problem to a non-commutative polynomial
optimization problem. We also introduce an alternative relaxation hierarchy
based on the notion of informationally-restricted quantum correlations, which,
though it represents a strict (non-converging) relaxation scheme, is less
computationally demanding. As an application, we introduce device-independent
tests of the dimension of classical and quantum systems that, in contrast to
previous results, do not make the implicit assumption that Alice and Bob share
no entanglement. We also establish several relations between communication with
and without entanglement as resources for creating correlations.
