Computation in generalised probabilistic theories
arXiv:1412.8671 · doi:10.1088/1367-2630/17/8/083001
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.
arXiv comment14+9 pages. Comments welcome
References in corpus (14)
- No Signalling and Quantum Key Distribution
- Informational derivation of Quantum Theory
- Quantum computations without definite causal structure
- Probabilistic theories with purification
- A generalized no-broadcasting theorem
- Computational advantage from quantum-controlled ordering of gates
- Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems
- Theory-independent limits on correlations from generalised Bayesian networks
- On the hardness of classically simulating the one clean qubit model
- All reversible dynamics in maximally non-local theories are trivial
- The structure of reversible computation determines the self-duality of quantum theory
- Quantum Computational Complexity in the Presence of Closed Timelike Curves
- Treating Time Travel Quantum Mechanically
- A general framework for phase and interference
Cited by in corpus (38)
- General Resource Theories in Quantum Mechanics and Beyond: Operational Characterization via Discrimination Tasks
- Quantum from principles
- The completeness of quantum theory for predicting measurement outcomes
- Introduction to the book "Quantum Theory: Informational Foundations and Foils"
- Quasi-quantization: classical statistical theories with an epistemic restriction
- 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
- Bounds on the power of proofs and advice in general physical theories
- Post-quantum steering is a stronger-than-quantum resource for information processing
- Interferometric computation beyond quantum theory
- Dense Coding with Locality Restriction for Decoder: Quantum Encoders vs. Super-Quantum Encoders
- On defining the Hamiltonian beyond quantum theory
- 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
- Universal structure of objective states in all fundamental causal theories
- On the impossibility of coin-flipping in generalized probabilistic theories via discretizations of semi-infinite programs
- Infinite-Dimensionality in Quantum Foundations: W*-algebras as Presheaves over Matrix Algebras
- Correlations constrained by composite measurements
- Compositional resource theories of coherence
- How dynamics constrains probabilities in general probabilistic theories
- Device-independent certification of non-classical joint measurements via causal models
- Quantum Darwinism and the spreading of classical information in non-classical theories
- 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
- 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