Generalised phase kick-back: the structure of computational algorithms from physical principles
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 computat...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IOP Publishing
2016-01-01
|
| Series: | New Journal of Physics |
| Subjects: | |
| Online Access: | https://doi.org/10.1088/1367-2630/18/3/033023 |
| _version_ | 1827873720518049792 |
|---|---|
| author | Ciarán M Lee John H Selby |
| author_facet | Ciarán M Lee John H Selby |
| author_sort | Ciarán M Lee |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-12T16:41:08Z |
| format | Article |
| id | doaj.art-0ff6a740c8d74ab78069ee2b9cb9d31a |
| institution | Directory Open Access Journal |
| issn | 1367-2630 |
| language | English |
| last_indexed | 2024-03-12T16:41:08Z |
| publishDate | 2016-01-01 |
| publisher | IOP Publishing |
| record_format | Article |
| series | New Journal of Physics |
| spelling | doaj.art-0ff6a740c8d74ab78069ee2b9cb9d31a2023-08-08T14:28:05ZengIOP PublishingNew Journal of Physics1367-26302016-01-0118303302310.1088/1367-2630/18/3/033023Generalised phase kick-back: the structure of computational algorithms from physical principlesCiarán M Lee0John H Selby1University of Oxford , Department of Computer Science, Wolfson Building, Parks Road, Oxford OX1 3QD, UKUniversity of Oxford , Department of Computer Science, Wolfson Building, Parks Road, Oxford OX1 3QD, UK; Imperial College London , London SW7 2AZ, UKThe 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.https://doi.org/10.1088/1367-2630/18/3/033023quantum computationgeneralised probabilistic theoriesquantum algorithmshigher-order interference |
| spellingShingle | Ciarán M Lee John H Selby Generalised phase kick-back: the structure of computational algorithms from physical principles New Journal of Physics quantum computation generalised probabilistic theories quantum algorithms higher-order interference |
| title | Generalised phase kick-back: the structure of computational algorithms from physical principles |
| title_full | Generalised phase kick-back: the structure of computational algorithms from physical principles |
| title_fullStr | Generalised phase kick-back: the structure of computational algorithms from physical principles |
| title_full_unstemmed | Generalised phase kick-back: the structure of computational algorithms from physical principles |
| title_short | Generalised phase kick-back: the structure of computational algorithms from physical principles |
| title_sort | generalised phase kick back the structure of computational algorithms from physical principles |
| topic | quantum computation generalised probabilistic theories quantum algorithms higher-order interference |
| url | https://doi.org/10.1088/1367-2630/18/3/033023 |
| work_keys_str_mv | AT ciaranmlee generalisedphasekickbackthestructureofcomputationalalgorithmsfromphysicalprinciples AT johnhselby generalisedphasekickbackthestructureofcomputationalalgorithmsfromphysicalprinciples |