Computation in generalised probabilistic theories

Abstract

From the existence of an efficient quantum algorithm for factoring, it is likely that quantum computation is intrinsically more powerful than classical computation. At present, the best upper bound known for the power of quantum computation is that BQP is in AWPP. This work investigates limits on computational power that are imposed by physical principles. To this end, we define a circuit-based model of computation in a class of operationally-defined theories more general than quantum theory, and ask: what is the minimal set of physical assumptions under which the above inclusion still holds? We show that given only an assumption of tomographic locality (roughly, that multipartite states can be characterised by local measurements), efficient computations are contained in AWPP. This inclusion still holds even without assuming a basic notion of causality (where the notion is, roughly, that probabilities for outcomes cannot depend on future measurement choices). Following Aaronson, we extend the computational model by allowing post-selection on measurement outcomes. Aaronson showed that the corresponding quantum complexity class is equal to PP. Given only the assumption of tomographic locality, the inclusion in PP still holds for post-selected computation in general theories. Thus in a world with post-selection, quantum theory is optimal for computation in the space of all general theories. We then consider if relativised complexity results can be obtained for general theories. It is not clear how to define a sensible notion of an oracle in the general framework that reduces to the standard notion in the quantum case. Nevertheless, it is possible to define computation relative to a `classical oracle'. Then, we show there exists a classical oracle relative to which efficient computation in any theory satisfying the causality assumption and tomographic locality does not include NP.

14+9 pages. Comments welcome

References in corpus (5)

• A generalized no-broadcasting theorem
• Computational advantage from quantum-controlled ordering of gates
• Theory-independent limits on correlations from generalised Bayesian networks
• On the hardness of classically simulating the one clean qubit model
• Treating Time Travel Quantum Mechanically

Cited by in corpus (37)

• General Resource Theories in Quantum Mechanics and Beyond: Operational Characterization via Discrimination Tasks
• Introduction to the book "Quantum Theory: Informational Foundations and Foils"
• Quasi-quantization: classical statistical theories with an epistemic restriction
• Quantum from principles
• Causal and causally separable processes
• 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
• Operational quantum theory without predefined time
• Higher-order interference in extensions of quantum theory
• The computational landscape of general physical theories
• Ruling out higher-order interference from purity principles
• 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
• Oracles and query lower bounds in generalised probabilistic theories
• Post-quantum steering is a stronger-than-quantum resource for information processing
• Bounds on the power of proofs and advice in general physical theories
• Interferometric computation beyond quantum theory
• On defining the Hamiltonian beyond quantum theory
• Dense Coding with Locality Restriction for Decoder: Quantum Encoders vs. Super-Quantum Encoders
• Quantum Theory is a Quasi-stochastic Process Theory
• Perfect Discrimination in Approximate Quantum Theory of General Probabilistic Theories
• 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
• Universal structure of objective states in all fundamental causal theories
• Infinite-Dimensionality in Quantum Foundations: W*-algebras as Presheaves over Matrix Algebras
• How dynamics constrains probabilities in general probabilistic theories
• Compositional resource theories of coherence
• Correlations constrained by composite measurements
• Device-independent certification of non-classical joint measurements via causal models
• Quantum Darwinism and the spreading of classical information in non-classical theories
• Simulating all multipartite non-signalling channels via quasiprobabilistic mixtures of local channels in generalised probabilistic theories
• A no-go theorem for theories that decohere to quantum mechanics
• Computation in a general physical setting
• Tsirelson's Inequality for the Precession Protocol is Maximally Violated by Quantum Theory
• 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