{
  "id": "0906.1811",
  "version": "v4",
  "published": "2009-06-09T20:00:46.000Z",
  "updated": "2009-07-29T16:42:49.000Z",
  "title": "Quantum algorithms know in advance 50% of the solution they will find in the future",
  "authors": [
    "Giuseppe Castagnoli"
  ],
  "comment": "The example of new quantum speed up that was just outlined in the previous version (finding the character of a permutation) is fully deployed in the present version. There are minor distributed changes to the writing",
  "categories": [
    "quant-ph"
  ],
  "abstract": "Quantum algorithms require less operations than classical algorithms. The exact reason of this has not been pinpointed until now. Our explanation is that quantum algorithms know in advance 50% of the solution of the problem they will find in the future. In fact they can be represented as the sum of all the possible histories of a respective \"advanced information classical algorithm\". This algorithm, given the advanced information (50% of the bits encoding the problem solution), performs the operations (oracle's queries) still required to identify the solution. Each history corresponds to a possible way of getting the advanced information and a possible result of computing the missing information. This explanation of the quantum speed up has an immediate practical consequence: the speed up comes from comparing two classical algorithms, with and without advanced information, with no physics involved. This simplification could open the way to a systematic exploration of the possibilities of speed up.",
  "revisions": [
    {
      "version": "v4",
      "updated": "2009-07-29T16:42:49.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "quantum algorithms",
      "advanced information classical algorithm",
      "operations",
      "exact reason",
      "explanation"
    ],
    "tags": [
      "journal article"
    ],
    "publication": {
      "doi": "10.1007/s10773-009-0143-6",
      "journal": "International Journal of Theoretical Physics",
      "year": 2009,
      "month": "Dec",
      "volume": 48,
      "number": 12,
      "pages": 3383
    },
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2009IJTP...48.3383C"
    }
  }
}