Communication of information in the absence of a shared frame of reference

In a communication protocol the sender, Alice, encodes classical messages by preparing a quantum system in a particular state and sending it to the receiver, Bob, who decodes the message by an appropriate quantum measurement. Implicit in the protocol is the assumption that whatever the physical encoding employed by Alice, whether it is the spin of particle, or the energy levels of an atom, is known to Bob. This assumption amounts to Alice and Bob sharing a common reference frame relative to which the states of physical systems are described. The lack of a shared frame of reference imposes severe restrictions on many communication and computational tasks. We obtain the optimal protocols for two cases: where invariant subspaces are available and where they are not.