Computation in a general physical setting
arXiv:2108.11454 · doi:10.1088/1751-8121/ac2007
Abstract
The computational abilities of theories within the generalised probabilistic theory framework has been the subject of much recent study. Such investigations aim to gain an understanding of the possible connections between physical principles and computation. Moreover, comparing and contrasting the computational properties of quantum theory with other operationally-sensible theories could shed light on the strengths and limitations of quantum computation. This paper reviews and extends some of these results, deriving new bounds on the computational ability of theories satisfying n-local tomography, and theories in which states are represented as generalised superpositions. It moreover provides a refined version of the conjecture that a quantum computer can simulate the computation in any theory within a certain sub-class of generalised probabilistic theories with at most polynomial overhead. The paper ends by describing an important relation between this conjecture and delegated computation, similar to the relation between quantum non-locality and device-independent cryptography.
Accepted to the J. Phys. A: Math. Theor. Special Issue "Foundational Structures in Quantum Theory," edited by Giulio Chiribella, Bob Coecke, Teiko Heinosaari, Ana Belen Sainz, and Robert Spekkens. 21 pages, no figures
References in corpus (5)
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
- Higher-order interference and single-system postulates characterizing quantum theory
- Terminality implies non-signalling
- The Information Content of Systems in General Physical Theories
- On computation with 'probabilities' modulo k