  There is good evidence that quantum computers are more powerful than
classical computers, and that various simple modifications of quantum theory
yield computational power that is dramatically greater still. However, these
modifications also violate fundamental physical principles. This raises the
question of whether there exists a physical theory, allowing computation more
powerful than quantum, but which still respects those fundamental physical
principles. Prior work by two of us introduced this question within a suitable
framework for theories that make good operational sense, and showed that in any
theory satisfying tomographic locality, the class of problems that can be
solved efficiently is contained in the complexity class AWPP. Here, we show
that this bound is tight, in the sense that there exists a theory, satisfying
tomographic locality, as well as a basic principle of causality, which can
efficiently decide everything in AWPP. Hence this theory can efficiently
simulate any computation in this framework, including quantum computation.
