  We explore the possibility of performing super dense coding with
non-maximally entangled states as a resource. Using this we find that one can
send two classical bits in a probabilistic manner by sending a qubit. We
generalize our scheme to higher dimensions and show that one can communicate
2log_2 d classical bits by sending a d-dimensional quantum state with a certain
probability of success. The success probability in super dense coding is
related to the success probability of distinguishing non-orthogonal states. The
optimal average success probabilities are explicitly calculated. We consider
the possibility of sending 2 log_2 d classical bits with a shared resource of a
higher dimensional entangled state (D X D, D > d). It is found that more
entanglement does not necessarily lead to higher success probability. This also
answers the question as to why we need log_2 d ebits to send 2 log_2 d
classical bits in a deterministic fashion.
