Bounds on computation from physical principles
<p>The advent of quantum computing has challenged classical conceptions of which problems are efficiently solvable in our physical world. This raises the general question of what broad relationships exist between physical principles and computation. The current thesis explores this question wi...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | English |
| Published: |
2017
|
| Subjects: |
| _version_ | 1817932778052780032 |
|---|---|
| author | Lee, C |
| author2 | Coecke, B |
| author_facet | Coecke, B Lee, C |
| author_sort | Lee, C |
| collection | OXFORD |
| description | <p>The advent of quantum computing has challenged classical conceptions of which problems are efficiently solvable in our physical world. This raises the general question of what broad relationships exist between physical principles and computation. The current thesis explores this question within the operationally-defined framework of generalised probabilistic theories. In particular, we investigate the limits on computational power imposed by simple physical principles. At present, the best known upper bound on the power of quantum computers is that <b>BQP</b> is contained in <b>AWPP</b>, where <b>AWPP</b> is a classical complexity class contained in PP. We define a circuit-based model of computation in the above mentioned operational framework and show that in theories where local measurements suffice for tomography, efficient computations are also contained in <b>AWPP</b>. Moreover, we explicitly construct a theory in which the class of efficiently solvable problems exactly equals <b>AWPP</b>, showing this containment to be tight. We also investigate how simple physical principles bound the power of computational paradigms which combine computation and communication in a non-trivial fashion, such as interactive proof systems. Additionally, we show how some of the essential components of computational algorithms arise from certain natural physical principles. We use these results to investigate the relationship between interference behaviour and computational power, demonstrating that non-trivial interference behaviour is a general resource for post-classical computation. We then investigate whether post-quantum interference is a resource for post-quantum computation. Sorkin has defined a hierarchy of possible post-quantum interference behaviours where, informally, the order in the hierarchy corresponds to the number of paths that have an irreducible interaction in a multi-slit experiment. In quantum theory, at most pairs of paths can ever interact in a fundamental way. We consider how Grover's speed-up depends on the order of interference in a theory, and show that, surprisingly, the quadratic lower bound holds regardless of the order of interference. </p> |
| first_indexed | 2024-03-06T20:55:59Z |
| format | Thesis |
| id | oxford-uuid:39451e29-3719-4cf4-a030-57c07e603380 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-12-09T03:43:19Z |
| publishDate | 2017 |
| record_format | dspace |
| spelling | oxford-uuid:39451e29-3719-4cf4-a030-57c07e6033802024-12-07T14:24:13ZBounds on computation from physical principlesThesishttp://purl.org/coar/resource_type/c_db06uuid:39451e29-3719-4cf4-a030-57c07e603380Foundations of quantum theoryQuantum computingEnglishORA Deposit2017Lee, CCoecke, BBarrett, J<p>The advent of quantum computing has challenged classical conceptions of which problems are efficiently solvable in our physical world. This raises the general question of what broad relationships exist between physical principles and computation. The current thesis explores this question within the operationally-defined framework of generalised probabilistic theories. In particular, we investigate the limits on computational power imposed by simple physical principles. At present, the best known upper bound on the power of quantum computers is that <b>BQP</b> is contained in <b>AWPP</b>, where <b>AWPP</b> is a classical complexity class contained in PP. We define a circuit-based model of computation in the above mentioned operational framework and show that in theories where local measurements suffice for tomography, efficient computations are also contained in <b>AWPP</b>. Moreover, we explicitly construct a theory in which the class of efficiently solvable problems exactly equals <b>AWPP</b>, showing this containment to be tight. We also investigate how simple physical principles bound the power of computational paradigms which combine computation and communication in a non-trivial fashion, such as interactive proof systems. Additionally, we show how some of the essential components of computational algorithms arise from certain natural physical principles. We use these results to investigate the relationship between interference behaviour and computational power, demonstrating that non-trivial interference behaviour is a general resource for post-classical computation. We then investigate whether post-quantum interference is a resource for post-quantum computation. Sorkin has defined a hierarchy of possible post-quantum interference behaviours where, informally, the order in the hierarchy corresponds to the number of paths that have an irreducible interaction in a multi-slit experiment. In quantum theory, at most pairs of paths can ever interact in a fundamental way. We consider how Grover's speed-up depends on the order of interference in a theory, and show that, surprisingly, the quadratic lower bound holds regardless of the order of interference. </p> |
| spellingShingle | Foundations of quantum theory Quantum computing Lee, C Bounds on computation from physical principles |
| title | Bounds on computation from physical principles |
| title_full | Bounds on computation from physical principles |
| title_fullStr | Bounds on computation from physical principles |
| title_full_unstemmed | Bounds on computation from physical principles |
| title_short | Bounds on computation from physical principles |
| title_sort | bounds on computation from physical principles |
| topic | Foundations of quantum theory Quantum computing |
| work_keys_str_mv | AT leec boundsoncomputationfromphysicalprinciples |