{
  "id": "1902.03513",
  "version": "v1",
  "published": "2019-02-09T23:44:18.000Z",
  "updated": "2019-02-09T23:44:18.000Z",
  "title": "Computational Complexity and the Nature of Quantum Mechanics (Extended version)",
  "authors": [
    "Alessio Benavoli",
    "Alessandro Facchini",
    "Marco Zaffalon"
  ],
  "categories": [
    "quant-ph",
    "cs.CC",
    "math.OC"
  ],
  "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-02-09T23:44:18.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "quantum mechanics",
      "computational complexity",
      "extended version",
      "quantum world appears",
      "computation postulate defines"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}