Bounds on the power of proofs and advice in general physical theories
arXiv:1510.04702 · doi:10.1098/rspa.2016.0076
Abstract
Quantum theory presents us with the tools for computational and communication advantages over classical theory. One approach to uncovering the source of these advantages is to determine how computation and communication power vary as quantum theory is replaced by other operationally-defined theories from a broad framework of such theories. Such investigations may reveal some of the key physical features required for powerful computation and communication. In this paper we investigate how simple physical principles bound the power of two different computational paradigms which combine computation and communication in a non-trivial fashion: computation with advice and interactive proof systems. We show that the existence of non-trivial dynamics in a theory implies a bound on the power of computation with advice. Moreover, we provide an explicit example of a theory with no non-trivial dynamics in which the power of computation with advice is unbounded. Finally we show that the power of simple interactive proof systems in theories where local measurements suffice for tomography is non-trivially bounded. This result provides a proof that QMA is contained in PP which does not make use of any uniquely quantum structure - such as the fact that observables correspond to self-adjoint operators - and thus may be of independent interest.
arXiv comment19 pages, no figures. Title and presentation changed in response to referees' suggestions
References in corpus (29)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Efficient classical simulation of slightly entangled quantum computations
- Quantum discord and the power of one qubit
- Informational derivation of Quantum Theory
- Contextuality supplies the magic for quantum computation
- Quantum computations without definite causal structure
- Coding Theorem and Strong Converse for Quantum Channels
- Probabilistic theories with purification
- Computational advantage from quantum-controlled ordering of gates
- Contextuality in Measurement-based Quantum Computation
- Popescu-Rohrlich correlations as a unit of nonlocality
- Quantum Entanglement and Communication Complexity
- Universal quantum computation with little entanglement
- Higher-order interference and single-system postulates characterizing quantum theory
- All reversible dynamics in maximally non-local theories are trivial
- The structure of reversible computation determines the self-duality of quantum theory
- Limitations of Quantum Advice and One-Way Communication
- Quantum communication complexity advantage implies violation of a Bell inequality
- Quantum interference as a resource for quantum speedup
- Strong nonlocality: A trade-off between states and measurements
- If no information gain implies no disturbance, then any discrete physical theory is classical
- Discord and quantum computational resources
- Computation in generalised probabilistic theories
- Three-dimensionality of space and the quantum bit: an information-theoretic approach
- Determinism without causality
- Generalized Bell Inequality Experiments and Computation
- Stronger Quantum Correlations with Loophole-free Post-selection
- Reversibility and the structure of the local state space
- Reversible Dynamics in Strongly Non-Local Boxworld Systems
Cited by in corpus (17)
- General probabilistic theories: An introduction
- Higher-order interference in extensions of quantum theory
- Deriving Grover's lower bound from simple physical principles
- The computational landscape of general physical theories
- Ruling out higher-order interference from purity principles
- Quantum computation is the unique reversible circuit model for which bits are balls
- Oracles and query lower bounds in generalised probabilistic theories
- Interferometric computation beyond quantum theory
- On defining the Hamiltonian beyond quantum theory
- The Information Content of Systems in General Physical Theories
- On the impossibility of coin-flipping in generalized probabilistic theories via discretizations of semi-infinite programs
- Compositional resource theories of coherence
- Correlations constrained by composite measurements
- Device-independent certification of non-classical joint measurements via causal models
- Computation in a general physical setting
- Proceedings of the 7th International Workshop on Physics and Computation
- Spacetime symmetries and the qubit Bloch ball: a physical derivation of finite dimensional quantum theory and the number of spatial dimensions