Oracles and query lower bounds in generalised probabilistic theories

Understand

We investigate the connection between interference and computational power within the operationally defined framework of generalised probabilistic theories.

• To compare the computational abilities of different theories within this framework we show that any theory satisfying three natural physical principles possess a well-defined oracle model.
• Indeed, we prove a subroutine theorem for oracles in such theories which is a necessary condition for the oracle to be well-defined.
• The three principles are: causality (roughly, no signalling from the future), purification (each mixed state arises as the marginal of a pure state of a larger system), and strong symmetry existence of non-trivial reversible transformations).