{
  "annotation_id": "1f5b4317-cbae-4e07-a5f7-44ed6a58cee9",
  "date_created": "2026-03-02T18:01:58.870000Z",
  "date_modified": "2026-03-02T18:01:58.870000Z",
  "file_hash": "013861ed021682a5caa95ad048801c64d641fc5d58591380c569b6edbdc6dbaf",
  "private": false,
  "record": {
    "abstract": "We introduce the quantum complexity class FQMA. This class describes the\ncomplexity of generating a quantum state that serves as a witness for a given\nQMA problem. In a certain sense, FQMA is the quantum analogue of FNP (function\nproblems associated with NP). The latter describes the complexity of finding a\nsuccinct proof for a NP decision problem. Whereas all FNP problems can be\nreduced to NP, there is no obvious reduction of FQMA to QMA since the solution\nof FQMA is a quantum state and the solution of QMA the answer yes or no.\n  We consider quantum state generators that get classical descriptions of\n3-local Hamiltonians on n qubits as input and prepare low energy states for\nthese systems as output. We show that such state generators can be used to\nprepare witnesses for QMA problems. Hence low energy state preparation is\nFQMA-complete. Our proofs are extensions of the proofs by Kitaev et al. and\nKempe and Regev for the QMA-completeness of k-local Hamiltonian problems. We\nshow that FQMA can be solved by preparing thermal equilibrium states with an\nappropriate temperature decreasing as the reciprocal of a polynomial in n.",
    "arxiv_id": "quant-ph/0303186",
    "authors": [
      "Dominik Janzing",
      "Pawel Wocjan",
      "Thomas Beth"
    ],
    "categories": [
      "quant-ph"
    ],
    "title": "Cooling and Low Energy State Preparation for 3-local Hamiltonians are   FQMA-complete",
    "url": "https://arxiv.org/abs/quant-ph/0303186"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "a211f54c-4516-4f3e-9877-74fd1a3df9db",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}