Computational Complexity and the Nature of Quantum Mechanics (Extended version)

Abstract

Quantum theory (QT) has been confirmed by numerous experiments, yet we still cannot fully grasp the meaning of the theory. As a consequence, the quantum world appears to us paradoxical. Here we shed new light on QT by having it follow from two main postulates (i) the theory should be logically consistent; (ii) inferences in the theory should be computable in polynomial time. The first postulate is what we require to each well-founded mathematical theory. The computation postulate defines the physical component of the theory. We show that the computation postulate is the only true divide between QT, seen as a generalised theory of probability, and classical probability. All quantum paradoxes, and entanglement in particular, arise from the clash of trying to reconcile a computationally intractable, somewhat idealised, theory (classical physics) with a computationally tractable theory (QT) or, in other words, from regarding physics as fundamental rather than computation.

References in corpus (15)

• A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations
• A complete family of separability criteria
• Distinguishing separable and entangled states
• Quantum-Bayesian Coherence: The No-Nonsense Version
• Tsirelson bounds for generalized Clauser-Horne-Shimony-Holt inequalities
• NP-complete Problems and Physical Reality
• Necessary and sufficient conditions for bipartite entanglement
• Quantum Computational Complexity in the Presence of Closed Timelike Curves
• Explicit product ensembles for separable quantum states
• Information-theoretic postulates for quantum theory
• Quantum mechanics: The Bayesian theory generalised to the space of Hermitian matrices
• Desirability and the birth of incomplete preferences
• A Gleason-type theorem for any dimension based on a gambling formulation of Quantum Mechanics
• A polarity theory for sets of desirable gambles
• SOS for bounded rationality