{
  "annotation_id": "058c853d-986d-452b-828b-0c8648e493d7",
  "date_created": "2026-03-02T18:02:13.758000Z",
  "date_modified": "2026-03-02T18:02:13.758000Z",
  "file_hash": "90248a3797a95432cdf8a75e50a27be997112c7af754f2f1c286d2a2ce871696",
  "private": false,
  "record": {
    "abstract": "We perform a mathematical analysis of the classical computational complexity\nof two genuine quantum-mechanical problems, which are inspired in the\ncalculation of the expected magnetizations and the entanglement between\nsubsystems for a quantum spin system. These problems, which we respectively\ncall SES and SESSP, are specified in terms of pure slightly-entangled quantum\nstates of n qubits, and rigorous mathematical proofs that they belong to the\nNP-Complete complexity class are presented. Both SES and SESSP are, therefore,\ncomputationally equivalent to the relevant 3-SAT problem, for which an\nefficient algorithm is yet to be discovered.",
    "arxiv_id": "quant-ph/0502022",
    "authors": [
      "Roman Orus"
    ],
    "categories": [
      "quant-ph"
    ],
    "journal_ref": "Quantum Information and Computation, Vol. 5, No. 6 (2005), pp.\n  449-455",
    "title": "Two Slightly-Entangled NP-Complete Problems",
    "url": "https://arxiv.org/abs/quant-ph/0502022"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "78652065-04b8-41bf-9d9d-d1c2d7617cd1",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}