{
  "id": "quant-ph/0306182",
  "version": "v1",
  "published": "2003-06-26T15:55:58.000Z",
  "updated": "2003-06-26T15:55:58.000Z",
  "title": "Quantum Computing Without Entanglement",
  "authors": [
    "Eli Biham",
    "Gilles Brassard",
    "Dan Kenigsberg",
    "Tal Mor"
  ],
  "comment": "18 pages. Presented at FoCM'02 (Aug 2002, see http://www.cs.technion.ac.il/~danken/pub/QCnoEnt.pdf), QIP'03 (Dec 2002, see http://www.msri.org/publications/ln/msri/2002/qip/brassard/1/), Qubit'03 (Apr 2003, see http://www.cs.technion.ac.il/~talmo/Qubitconf/QUBIT-2003/program/)",
  "journal": "Theoretical Computer Science, Volume 320, Issue 1, Pages 15 - 33, June 2004.",
  "doi": "10.1016/j.tcs.2004.03.041",
  "categories": [
    "quant-ph",
    "cs.CC"
  ],
  "abstract": "It is generally believed that entanglement is essential for quantum computing. We present here a few simple examples in which quantum computing without entanglement is better than anything classically achievable, in terms of the reliability of the outcome after a xed number of oracle calls. Using a separable (that is, unentangled) n-qubit state, we show that the Deutsch-Jozsa problem and the Simon problem can be solved more reliably by a quantum computer than by the best possible classical algorithm, even probabilistic. We conclude that: (a) entanglement is not essential for quantum computing; and (b) some advantage of quantum algorithms over classical algorithms persists even when the quantum state contains an arbitrarily small amount of information|that is, even when the state is arbitrarily close to being totally mixed.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2003-06-26T15:55:58.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "quantum computing",
      "entanglement",
      "quantum state contains",
      "classical algorithms persists",
      "quantum algorithms"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 18,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2003quant.ph..6182B"
    }
  }
}