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.
arXiv commentAccepted 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 (42)
- Quantum Mechanics helps in searching for a needle in a haystack
- Strengths and Weaknesses of Quantum Computing
- No Signalling and Quantum Key Distribution
- Information Causality as a Physical Principle
- In defense of the epistemic view of quantum states: a toy theory
- Informational derivation of Quantum Theory
- Probabilistic theories with purification
- Quantum Mechanics as Quantum Measure Theory
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
- Local orthogonality as a multipartite principle for quantum correlations
- Blind quantum computation protocol in which Alice only makes measurements
- Minimal Informationally Complete Measurements for Pure States
- Limited Holism and Real-Vector-Space Quantum Theory
- Higher-order interference and single-system postulates characterizing quantum theory
- Existence of an information unit as a postulate of quantum theory
- Reformulating and Reconstructing Quantum Theory
- All reversible dynamics in maximally non-local theories are trivial
- Limits on non-local correlations from the structure of the local state space
- Generalized Probabilistic Theories Without the No-Restriction Hypothesis
- Quantum Measure Theory and its Interpretation
- Density cubes and higher-order interference theories
- Generalised phase kick-back: the structure of computational algorithms from physical principles
- On the superposition principle in interference experiments
- The Feynman problem and Fermionic entanglement: Fermionic theory versus qubit theory
- Higher-order interference in extensions of quantum theory
- Fermionic computation is non-local tomographic and violates monogamy of entanglement
- Deriving Grover's lower bound from simple physical principles
- Computation in generalised probabilistic theories
- The computational landscape of general physical theories
- Ruling out higher-order interference from purity principles
- Terminality implies non-signalling
- Entropy, majorization and thermodynamics in general probabilistic theories
- Determinism without causality
- Oracles and query lower bounds in generalised probabilistic theories
- Quantum computation is the unique reversible circuit model for which bits are balls
- Bounds on the power of proofs and advice in general physical theories
- Hyperdense coding and superadditivity of classical capacities in hypersphere theories
- The Information Content of Systems in General Physical Theories
- On computation with 'probabilities' modulo k
- Compositional resource theories of coherence
- A no-go theorem for theories that decohere to quantum mechanics
- Density Hypercubes, Higher Order Interference and Hyper-Decoherence: a Categorical Approach