Generalised phase kick−back: a conputational advantage for higher−order interference?
Ciaran M. Lee · arXiv (Cornell University) · 2015
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. A major roadblock to such a study is that quantum computation is phrased in the language of Hilbert spaces, which lacks direct operational significance -- making connections to physical principles difficult to uncover. In contrast, the framework of general probabilistic theories provides a clear-cut operational language in which to address this question. In this paper we show that some of the common machinery of quantum computation -- namely reversible controlled transformations and the phase kick-back mechanism -- exist in any general theory with a well-defined notion of information. These results provide the tools for an exploration of the structure of computational algorithms and how they connect to physical principles. We show in such theories that non-trivial interference behaviour is a general resource for post-classical computation. Motivated by the intimate connection between interference and phase in quantum theory, we introduce a framework that relates higher-order (post-quantum) interference, originally defined by Sorkin, and phase transformations. This framework -- via the generalised phase kick-back -- is used to provide evidence that theories with higher-order interference can solve problems intractable on a quantum computer. Additionally, using the existence of reversible controlled transformations, higher-order interference is shown to imply the existence of post-quantum particle types.