dorsal/arxiv
View SchemaCooling and Low Energy State Preparation for 3-local Hamiltonians are FQMA-complete
| Authors | Dominik Janzing, Pawel Wocjan, Thomas Beth |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0303186 |
| URL | https://arxiv.org/abs/quant-ph/0303186 |
Abstract
We introduce the quantum complexity class FQMA. This class describes the complexity of generating a quantum state that serves as a witness for a given QMA problem. In a certain sense, FQMA is the quantum analogue of FNP (function problems associated with NP). The latter describes the complexity of finding a succinct proof for a NP decision problem. Whereas all FNP problems can be reduced to NP, there is no obvious reduction of FQMA to QMA since the solution of FQMA is a quantum state and the solution of QMA the answer yes or no. We consider quantum state generators that get classical descriptions of 3-local Hamiltonians on n qubits as input and prepare low energy states for these systems as output. We show that such state generators can be used to prepare witnesses for QMA problems. Hence low energy state preparation is FQMA-complete. Our proofs are extensions of the proofs by Kitaev et al. and Kempe and Regev for the QMA-completeness of k-local Hamiltonian problems. We show that FQMA can be solved by preparing thermal equilibrium states with an appropriate temperature decreasing as the reciprocal of a polynomial in n.
{
"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
}