The computational landscape of general physical theories
arXiv:1702.08483 · doi:10.1038/s41534-019-0156-9
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.
arXiv comment15 pages, 5 figures. Close to published version. Comments welcome
References in corpus (50)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum Computing
- Efficient classical simulation of slightly entangled quantum computations
- Strengths and Weaknesses of Quantum Computing
- Quantum discord and the power of one qubit
- 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
- Contextuality supplies the magic for quantum computation
- Quantum Theory From Five Reasonable Axioms
- Probabilistic theories with purification
- A derivation of quantum theory from physical requirements
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
- Average-case complexity versus approximate simulation of commuting quantum computations
- A generalized no-broadcasting theorem
- Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems
- Local orthogonality as a multipartite principle for quantum correlations
- Almost quantum correlations
- Estimating outcome probabilities of quantum circuits using quasiprobabilities
- Complexity limitations on quantum computation
- Universal quantum computation with little entanglement
- 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
- The elusive source of quantum effectiveness
- Towards device-independent information processing on general quantum networks
- Implausible Consequences of Superstrong Nonlocality
- Three Slit Experiments and the Structure of Quantum Theory
- Quantum interference as a resource for quantum speedup
- Generalised phase kick-back: the structure of computational algorithms from physical principles
- Deriving quantum theory from its local structure and reversibility
- Higher-order interference in extensions of quantum theory
- Strong nonlocality: A trade-off between states and measurements
- Deriving Grover's lower bound from simple physical principles
- Discord and quantum computational resources
- Computation in generalised probabilistic theories
- Simulating all non-signalling correlations via classical or quantum theory with negative probabilities
- Bounding quantum contextuality with lack of third-order intereference
- Determinism without causality
- Generalized Bell Inequality Experiments and Computation
- Conditional probability, three-slit experiments, and the Jordan algebra structure of quantum mechanics
- Bounds on the power of proofs and advice in general physical theories
- Exploring non-signalling polytopes with negative probability
- 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
- Quantum Computing and Hidden Variables II: The Complexity of Sampling Histories
- Device-independent certification of non-classical joint measurements via causal models
Cited by in corpus (28)
- General probabilistic theories: An introduction
- A no-go theorem on the nature of the gravitational field beyond quantum theory
- Generalised phase kick-back: the structure of computational algorithms from physical principles
- Deriving Grover's lower bound from simple physical principles
- 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
- Nonlinear Schrödinger equations and generalized Heisenberg uncertainty principle violating the principle of estimation independence
- On the impossibility of coin-flipping in generalized probabilistic theories via discretizations of semi-infinite programs
- Universal structure of objective states in all fundamental causal theories
- Compositional resource theories of coherence
- Correlations constrained by composite measurements
- 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
- Periodic Fourier representation of Boolean functions
- Quantum interpretations, causality and quantum computation
- Does Quantum Mechanics Breed Larger, More Intricate Quantum Theories? The Case for Experience-Centric Quantum Theory and the Interactome of Quantum Theories
- Spacetime symmetries and the qubit Bloch ball: a physical derivation of finite dimensional quantum theory and the number of spatial dimensions
- Efficient classical simulation of cluster state quantum circuits with alternative inputs