Oracles and query lower bounds in generalised probabilistic theories
arXiv:1704.05043 · doi:10.1007/s10701-018-0198-4
Abstract
We investigate the connection between interference and computational power within the operationally defined framework of generalised probabilistic theories. To compare the computational abilities of different theories within this framework we show that any theory satisfying three natural physical principles possess a well-defined oracle model. Indeed, we prove a subroutine theorem for oracles in such theories which is a necessary condition for the oracle to be well-defined. The three principles are: causality (roughly, no signalling from the future), purification (each mixed state arises as the marginal of a pure state of a larger system), and strong symmetry existence of non-trivial reversible transformations). Sorkin has defined a hierarchy of conceivable interference behaviours, where the order in the hierarchy corresponds to the number of paths that have an irreducible interaction in a multi-slit experiment. Given our oracle model, we show that if a classical computer requires at least n queries to solve a learning problem, then the corresponding lower bound in theories lying at the kth level of Sorkin's hierarchy is n/k. Hence, lower bounds on the number of queries to a quantum oracle needed to solve certain problems are not optimal in the space of all generalised probabilistic theories, although it is not yet known whether the optimal bounds are achievable in general. Hence searches for higher-order interference are not only foundationally motivated, but constitute a search for a computational resource beyond that offered by quantum computation.
arXiv comment17+7 pages. Comments Welcome. Published in special issue "Foundational Aspects of Quantum Information" in Foundations of Physics
References in corpus (32)
- Quantum Mechanics helps in searching for a needle in a haystack
- Strengths and Weaknesses of Quantum Computing
- Quantum Algorithms Revisited
- In defense of the epistemic view of quantum states: a toy theory
- Probabilistic theories with purification
- Quantum Mechanics as Quantum Measure Theory
- A generalized no-broadcasting theorem
- Ruling Out Multi-Order Interference in Quantum Mechanics
- Quantum Picturalism
- Higher-order interference and single-system postulates characterizing quantum theory
- The structure of reversible computation determines the self-duality of quantum theory
- Quantum Measure Theory and its Interpretation
- 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
- The Feynman problem and Fermionic entanglement: Fermionic theory versus qubit theory
- On the superposition principle in interference experiments
- Testing Born's Rule in Quantum Mechanics with a Triple Slit Experiment
- Obtaining tight bounds on higher-order interferences with a 5-path interferometer
- Entanglement and thermodynamics in general probabilistic theories
- Three path interference using nuclear magnetic resonance: a test of the consistency of Born's rule
- 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
- Bounds on the power of proofs and advice in general physical theories
- Grover search and the no-signaling principle
- Quantum Protocols within Spekkens' Toy Model
- Entanglement as an axiomatic foundation for statistical mechanics
- The Information Content of Systems in General Physical Theories
- A no-go theorem for theories that decohere to quantum mechanics
Cited by in corpus (19)
- General probabilistic theories: An introduction
- A no-go theorem on the nature of the gravitational field beyond quantum theory
- Accessible fragments of generalized probabilistic theories, cone equivalence, and applications to witnessing nonclassicality
- Quantum computation is the unique reversible circuit model for which bits are balls
- Post-quantum steering is a stronger-than-quantum resource for information processing
- Strongly symmetric spectral convex bodies are Jordan algebra state spaces
- Fantastic Quantum Theories and Where to Find Them
- On the impossibility of coin-flipping in generalized probabilistic theories via discretizations of semi-infinite programs
- Correlations constrained by composite measurements
- 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
- Simulating all multipartite non-signalling channels via quasiprobabilistic mixtures of local channels in generalised probabilistic theories
- Density Hypercubes, Higher Order Interference and Hyper-Decoherence: a Categorical Approach
- Computation in a general physical setting
- Complete extension: the non-signaling analog of quantum purification
- Spacetime symmetries and the qubit Bloch ball: a physical derivation of finite dimensional quantum theory and the number of spatial dimensions
- Mathematical methods for resource-based type theories
- Morphisms in categories of nonlocal games