  One of the primary goals of information theory is to provide limits on the
amount of information it is possible to send through various types of
communication channels, and to understand the encoding methods that will allow
one to achieve such limits. An early surprise in the study of \textit{quantum}
information theory was the discovery of dense coding, which demonstrated that
it is possible to achieve higher rates for communicating classical information
by transmitting quantum systems, rather than classical ones. To achieve the
highest possible rate, the transmitted quantum system must initially be
maximally entangled with another that is held by the receiver, and the sender
can achieve this rate by encoding her messages with unitary operations. The
situation where these two systems are not maximally entangled has been
intensively studied in recent years, and to date it has appeared as though
unitary encoding might well be optimal in all cases. Indeed, this optimality of
unitary operations for quantum communication protocols has been found to hold
under far more general conditions, extending well beyond the special case of
dense coding. Nonetheless, we here present strong numerical evidence supported
by analytical arguments that indicate there exist circumstances under which one
can encode strictly more classical information using dense coding with
non-unitary, as opposed to unitary, operations.
