  Quantum theory presents us with the tools for computational and communication
advantages over classical theory. One approach to uncovering the source of
these advantages is to determine how computation and communication power vary
as quantum theory is replaced by other operationally-defined theories from a
broad framework of such theories. Such investigations may reveal some of the
key physical features required for powerful computation and communication. In
this paper we investigate how simple physical principles bound the power of two
different computational paradigms which combine computation and communication
in a non-trivial fashion: computation with advice and interactive proof
systems. We show that the existence of non-trivial dynamics in a theory implies
a bound on the power of computation with advice. Moreover, we provide an
explicit example of a theory with no non-trivial dynamics in which the power of
computation with advice is unbounded. Finally we show that the power of simple
interactive proof systems in theories where local measurements suffice for
tomography is non-trivially bounded. This result provides a proof that QMA is
contained in PP which does not make use of any uniquely quantum structure -
such as the fact that observables correspond to self-adjoint operators - and
thus may be of independent interest.
