Lee, CM;
Selby, JH;
(2016)
Generalised phase kick-back: the structure of computational algorithms from physical principles.
New Journal of Physics
, 18
(2016)
, Article 033023. 10.1088/1367-2630/18/3/033023.
Text
Lee_Generalised phase kick-back the structure of computationalVoR.pdf Download (1MB) |
Abstract
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.
Type: | Article |
---|---|
Title: | Generalised phase kick-back: the structure of computational algorithms from physical principles |
Open access status: | An open access version is available from UCL Discovery |
DOI: | 10.1088/1367-2630/18/3/033023 |
Publisher version: | http://dx.doi.org/10.1088/1367-2630/18/3/033023 |
Language: | English |
Additional information: | © 2016 IOP Publishing Ltd and Deutsche Physikalische Gesellschaft. Original content from this work may be used under the terms of the Creative Commons Attribution 3.0 licence. Any further distribution of this work must maintain attribution to the author(s) and the title of the work, journal citation and DOI. date_received: 2015-12-02 date_accepted: 2016-02-22 date_epub: 2016-03-11 |
UCL classification: | UCL UCL > Provost and Vice Provost Offices UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Physics and Astronomy |
URI: | https://discovery.ucl.ac.uk/id/eprint/1521117 |
Archive Staff Only
View Item |