  What kind of object is a quantum state? Is it an object that encodes an
exponentially growing amount of information (in the size of the system) or more
akin to a probability distribution? It turns out that these questions are
sensitive to what we do with the information. For example, Holevo's bound tells
us that n qubits only encode n bits of classical information but for certain
communication complexity tasks there is an exponential separation between
quantum and classical resources. Instead of just contrasting quantum and
classical physics, we can place both within a broad landscape of physical
theories and ask how non-quantum (and non-classical) theories are different
from, or more powerful than quantum theory. For example, in communication
complexity, certain (non-quantum) theories can trivialise all communication
complexity tasks. In recent work [C. M. Lee and M. J. Hoban, Proc. Royal Soc. A
472 (2190), 2016], we showed that the immense power of the information content
of states in general (non-quantum) physical theories is not limited to
communication complexity. We showed that, in general physical theories, states
can be taken as "advice" for computers in these theories and this advice allows
the computers to easily solve any decision problem. Aaronson has highlighted
the close connection between quantum communication complexity and quantum
computations that take quantum advice, and our work gives further indications
that this is a very general connection. In this work, we review the results in
our previous work and discuss the intricate relationship between communication
complexity and computers taking advice for general theories.
