Journal
NEW JOURNAL OF PHYSICS
Volume 18, Issue -, Pages -Publisher
IOP PUBLISHING LTD
DOI: 10.1088/1367-2630/18/3/033023
Keywords
quantum computation; generalised probabilistic theories; quantum algorithms; higher-order interference
Categories
Funding
- EPSRC through the Controlled Quantum Dynamics Centre for Doctoral Training
- Oxford Department of Computer Science
- University College, Oxford
- Engineering and Physical Sciences Research Council [1374839, 1376720] Funding Source: researchfish
Ask authors/readers for more resources
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 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 higher-order interference 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-the higher-order interference of Sorkin-can solve problems intractable even on a quantum computer.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available