  The computational abilities of theories within the generalised probabilistic
theory framework has been the subject of much recent study. Such investigations
aim to gain an understanding of the possible connections between physical
principles and computation. Moreover, comparing and contrasting the
computational properties of quantum theory with other operationally-sensible
theories could shed light on the strengths and limitations of quantum
computation. This paper reviews and extends some of these results, deriving new
bounds on the computational ability of theories satisfying n-local tomography,
and theories in which states are represented as generalised superpositions. It
moreover provides a refined version of the conjecture that a quantum computer
can simulate the computation in any theory within a certain sub-class of
generalised probabilistic theories with at most polynomial overhead. The paper
ends by describing an important relation between this conjecture and delegated
computation, similar to the relation between quantum non-locality and
device-independent cryptography.
