  The advent of quantum computing has challenged classical conceptions of which
problems are efficiently solvable in our physical world. This motivates the
general study of how physical principles bound computational power. In this
paper we show that some of the essential machinery of quantum computation --
namely reversible controlled transformations and the phase kick-back mechanism
-- exist in any operational-defined theory with a consistent notion of
information. These results provide the tools for an exploration of the physics
underpinning the structure of computational algorithms. We use these results to
investigate the relationship between interference behaviour and computational
power, demonstrating that non-trivial interference behaviour is a general
resource for post-classical computation. In proving the above, we connect
post-quantum interference -- the higher-order interference of Sorkin -- to the
existence of post-quantum particle types, potentially providing a novel
experimental test for higher-order interference. Finally, we conjecture that
theories with post-quantum interference can solve problems intractable even on
a quantum computer.
