The Information Content of Systems in General Physical Theories

Abstract

What kind of object is a quantum state? Is it an object that encodes an exponentially growing amount of information (in the size of the system) or more akin to a probability distribution? It turns out that these questions are sensitive to what we do with the information. For example, Holevo's bound tells us that n qubits only encode n bits of classical information but for certain communication complexity tasks there is an exponential separation between quantum and classical resources. Instead of just contrasting quantum and classical physics, we can place both within a broad landscape of physical theories and ask how non-quantum (and non-classical) theories are different from, or more powerful than quantum theory. For example, in communication complexity, certain (non-quantum) theories can trivialise all communication complexity tasks. In recent work [C. M. Lee and M. J. Hoban, Proc. Royal Soc. A 472 (2190), 2016], we showed that the immense power of the information content of states in general (non-quantum) physical theories is not limited to communication complexity. We showed that, in general physical theories, states can be taken as "advice" for computers in these theories and this advice allows the computers to easily solve any decision problem. Aaronson has highlighted the close connection between quantum communication complexity and quantum computations that take quantum advice, and our work gives further indications that this is a very general connection. In this work, we review the results in our previous work and discuss the intricate relationship between communication complexity and computers taking advice for general theories.

arXiv commentIn Proceedings PC 2016, arXiv:1606.06513

References in corpus (14)

• On the reality of the quantum state
• Informational derivation of Quantum Theory
• Non-locality and Communication Complexity
• Probabilistic theories with purification
• A limit on nonlocality in any world in which communication complexity is not trivial
• Almost quantum correlations
• All reversible dynamics in maximally non-local theories are trivial
• The structure of reversible computation determines the self-duality of quantum theory
• Strong nonlocality: A trade-off between states and measurements
• Computation in generalised probabilistic theories
• Determinism without causality
• Information and communication in polygon theories
• Bounds on the power of proofs and advice in general physical theories
• Generalised probabilistic theories and conic extensions of polytopes

Cited by in corpus (7)

• The computational landscape of general physical theories
• Ruling out higher-order interference from purity principles
• Oracles and query lower bounds in generalised probabilistic theories
• Compositional resource theories of coherence
• Device-independent certification of non-classical joint measurements via causal models
• A no-go theorem for theories that decohere to quantum mechanics
• Computation in a general physical setting