The computational landscape of general physical theories

Abstract

There is good evidence that quantum computers are more powerful than classical computers, and that various simple modifications of quantum theory yield computational power that is dramatically greater still. However, these modifications also violate fundamental physical principles. This raises the question of whether there exists a physical theory, allowing computation more powerful than quantum, but which still respects those fundamental physical principles. Prior work by two of us introduced this question within a suitable framework for theories that make good operational sense, and showed that in any theory satisfying tomographic locality, the class of problems that can be solved efficiently is contained in the complexity class AWPP. Here, we show that this bound is tight, in the sense that there exists a theory, satisfying tomographic locality, as well as a basic principle of causality, which can efficiently decide everything in AWPP. Hence this theory can efficiently simulate any computation in this framework, including quantum computation.

15 pages, 5 figures. Close to published version. Comments welcome

References in corpus (16)

• Quantum Computing
• Quantum discord and the power of one qubit
• A derivation of quantum theory from physical requirements
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• A generalized no-broadcasting theorem
• Almost quantum correlations
• Universal quantum computation with little entanglement
• Higher-order interference and single-system postulates characterizing quantum theory
• Towards device-independent information processing on general quantum networks
• Implausible Consequences of Superstrong Nonlocality
• Bounding quantum contextuality with lack of third-order intereference
• Exploring non-signalling polytopes with negative probability
• The Information Content of Systems in General Physical Theories
• Quantum Computing and Hidden Variables II: The Complexity of Sampling Histories
• On computation with 'probabilities' modulo k
• Device-independent certification of non-classical joint measurements via causal models

Cited by in corpus (26)

• General probabilistic theories: An introduction
• A no-go theorem on the nature of the gravitational field beyond quantum theory
• Ruling out higher-order interference from purity principles
• Accessible fragments of generalized probabilistic theories, cone equivalence, and applications to witnessing nonclassicality
• Oracles and query lower bounds in generalised probabilistic theories
• Post-quantum steering is a stronger-than-quantum resource for information processing
• An effect-theoretic reconstruction of quantum theory
• Quantum Theory is a Quasi-stochastic Process Theory
• On the impossibility of coin-flipping in generalized probabilistic theories via discretizations of semi-infinite programs
• Nonlinear Schrödinger equations and generalized Heisenberg uncertainty principle violating the principle of estimation independence
• Universal structure of objective states in all fundamental causal theories
• Correlations constrained by composite measurements
• Compositional resource theories of coherence
• Generalized dynamical theories in phase space and the hydrogen atom
• On characterising assemblages in Einstein-Podolsky-Rosen scenarios
• A no-go theorem for theories that decohere to quantum mechanics
• Every non-signalling channel is common-cause realizable
• Simulating all multipartite non-signalling channels via quasiprobabilistic mixtures of local channels in generalised probabilistic theories
• Computation in a general physical setting
• Reality, Causality, and Quantum Theory
• Minimal operational theories: classical theories with quantum features
• Quantum interpretations, causality and quantum computation
• Efficient classical simulation of cluster state quantum circuits with alternative inputs
• Spacetime symmetries and the qubit Bloch ball: a physical derivation of finite dimensional quantum theory and the number of spatial dimensions
• Periodic Fourier representation of Boolean functions
• Does Quantum Mechanics Breed Larger, More Intricate Quantum Theories? The Case for Experience-Centric Quantum Theory and the Interactome of Quantum Theories