dorsal/arxiv
View SchemaTwo QCMA-complete problems
| Authors | Pawel Wocjan, Dominik Janzing, Thomas Beth |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0305090 |
| URL | https://arxiv.org/abs/quant-ph/0305090 |
Abstract
QMA and QCMA are possible quantum analogues of the complexity class NP. In QCMA the verifier is a quantum program and the proof is classical. In contrast, in QMA the proof is also a quantum state. We show that two known QMA-complete problems can be modified to QCMA-complete problems in a natural way: (1) Deciding whether a 3-local Hamiltonian has low energy states (with energy smaller than a given value) that can be prepared with at most k elementary gates is QCMA-complete, whereas it is QMA-complete when the restriction on the complexity of preparation is dropped. (2) Deciding whether a (classically described) quantum circuit acts almost as the identity on all basis states is QCMA-complete. It is QMA-complete to decide whether it acts on all states almost as the identity.
{
"annotation_id": "5a65a947-1366-4b22-b67c-01ba10aa9ccd",
"date_created": "2026-03-02T18:01:59.820000Z",
"date_modified": "2026-03-02T18:01:59.820000Z",
"file_hash": "1e33ada6fac7099e372dbe44a7aa1c0fdb7ac917b110dbec153ed9ea6ad14fc0",
"private": false,
"record": {
"abstract": "QMA and QCMA are possible quantum analogues of the complexity class NP. In\nQCMA the verifier is a quantum program and the proof is classical. In contrast,\nin QMA the proof is also a quantum state.\n We show that two known QMA-complete problems can be modified to QCMA-complete\nproblems in a natural way:\n (1) Deciding whether a 3-local Hamiltonian has low energy states (with energy\nsmaller than a given value) that can be prepared with at most k elementary\ngates is QCMA-complete, whereas it is QMA-complete when the restriction on the\ncomplexity of preparation is dropped.\n (2) Deciding whether a (classically described) quantum circuit acts almost as\nthe identity on all basis states is QCMA-complete. It is QMA-complete to decide\nwhether it acts on all states almost as the identity.",
"arxiv_id": "quant-ph/0305090",
"authors": [
"Pawel Wocjan",
"Dominik Janzing",
"Thomas Beth"
],
"categories": [
"quant-ph"
],
"title": "Two QCMA-complete problems",
"url": "https://arxiv.org/abs/quant-ph/0305090"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "a6693ff2-dcbc-4b8b-9fdc-ab0ceb2f296b",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}