{
  "annotation_id": "6820cd0b-1725-4541-9f74-813f8b7639f2",
  "date_created": "2026-03-02T18:01:59.065000Z",
  "date_modified": "2026-03-02T18:01:59.065000Z",
  "file_hash": "34379a5c09296ad6762890247a5dd4f9dc978b9dfe077f89c97ab35e92437ace",
  "private": false,
  "record": {
    "abstract": "It is generally believed that entanglement is essential for quantum\ncomputing. We present here a few simple examples in which quantum computing\nwithout entanglement is better than anything classically achievable, in terms\nof the reliability of the outcome after a xed number of oracle calls. Using a\nseparable (that is, unentangled) n-qubit state, we show that the Deutsch-Jozsa\nproblem and the Simon problem can be solved more reliably by a quantum computer\nthan by the best possible classical algorithm, even probabilistic. We conclude\nthat: (a) entanglement is not essential for quantum computing; and (b) some\nadvantage of quantum algorithms over classical algorithms persists even when\nthe quantum state contains an arbitrarily small amount of information|that is,\neven when the state is arbitrarily close to being totally mixed.",
    "arxiv_id": "quant-ph/0306182",
    "authors": [
      "Eli Biham",
      "Gilles Brassard",
      "Dan Kenigsberg",
      "Tal Mor"
    ],
    "categories": [
      "quant-ph",
      "cs.CC"
    ],
    "doi": "10.1016/j.tcs.2004.03.041",
    "journal_ref": "Theoretical Computer Science, Volume 320, Issue 1, Pages 15 - 33,\n  June 2004.",
    "title": "Quantum Computing Without Entanglement",
    "url": "https://arxiv.org/abs/quant-ph/0306182"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "095ff470-139c-442a-8bd0-804ebc9ae17b",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}