Oracles and query lower bounds in generalised probabilistic theories

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.

17+7 pages. Comments Welcome. Published in special issue "Foundational Aspects of Quantum Information" in Foundations of Physics

References in corpus (8)

• A generalized no-broadcasting theorem
• Higher-order interference and single-system postulates characterizing quantum theory
• Testing Born's Rule in Quantum Mechanics with a Triple Slit Experiment
• Three path interference using nuclear magnetic resonance: a test of the consistency of Born's rule
• The computational landscape of general physical theories
• 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