{
  "annotation_id": "b7e53251-9682-466c-9565-24604f6cd330",
  "date_created": "2026-03-02T18:02:23.900000Z",
  "date_modified": "2026-03-02T18:02:23.900000Z",
  "file_hash": "ba68619a5d171a80b6cbbbf3a0d52ddbeb55e19ef0be5335d82054e2728f4a07",
  "private": false,
  "record": {
    "abstract": "We study the advantage of pure-state quantum computation without entanglement\nover classical computation. For the Deutsch-Jozsa algorithm we present the\nmaximal subproblem that can be solved without entanglement, and show that the\nalgorithm still has an advantage over the classical ones. We further show that\nthis subproblem is of greater significance, by proving that it contains all the\nBoolean functions whose quantum phase-oracle is non-entangling. For Simon\u0027s and\nGrover\u0027s algorithms we provide simple proofs that no non-trivial subproblems\ncan be solved by these algorithms without entanglement.",
    "arxiv_id": "quant-ph/0511272",
    "authors": [
      "Dan Kenigsberg",
      "Tal Mor",
      "Gil Ratsaby"
    ],
    "categories": [
      "quant-ph",
      "cs.CC"
    ],
    "doi": "10.1117/12.617175",
    "journal_ref": "Quantum Information and Computation 6(7), 606--615 (2006)",
    "title": "Quantum Advantage without Entanglement",
    "url": "https://arxiv.org/abs/quant-ph/0511272"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "e87b5150-07ea-42cc-b6f2-215350058d82",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}