{
  "annotation_id": "6ba7393a-e032-4b53-a6f4-3d9e8dc51d42",
  "date_created": "2026-03-02T18:01:49.555000Z",
  "date_modified": "2026-03-02T18:01:49.555000Z",
  "file_hash": "c6fa992de6087e56a516bfb75ebf13d214fbc4d13e6d5abbce828c202cab8f52",
  "private": false,
  "record": {
    "abstract": "Krentel [J. Comput. System. Sci., 36, pp.490--509] presented a framework for\nan NP optimization problem that searches an optimal value among\nexponentially-many outcomes of polynomial-time computations. This paper expands\nhis framework to a quantum optimization problem using polynomial-time quantum\ncomputations and introduces the notion of an ``universal\u0027\u0027 quantum optimization\nproblem similar to a classical ``complete\u0027\u0027 optimization problem. We exhibit a\ncanonical quantum optimization problem that is universal for the class of\npolynomial-time quantum optimization problems. We show in a certain relativized\nworld that all quantum optimization problems cannot be approximated closely by\nquantum polynomial-time computations. We also study the complexity of quantum\noptimization problems in connection to well-known complexity classes.",
    "arxiv_id": "quant-ph/0204010",
    "authors": [
      "Tomoyuki Yamakami"
    ],
    "categories": [
      "quant-ph",
      "cs.CC"
    ],
    "title": "Quantum Optimization Problems",
    "url": "https://arxiv.org/abs/quant-ph/0204010"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "5356bd50-a0e6-4103-8afb-a486eae06ae8",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}