Oracles and Query Lower Bounds in Generalised Probabilistic Theories
Oracles and Query Lower Bounds in Generalised Probabilistic Theories
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 four natural physical principles possess a well-defined oracle model. Indeed, we prove a subroutine theorem …