Two QCMA-complete problems
| dc.creator | Wocjan, Pawel | |
| dc.creator | Janzing, Dominik | |
| dc.creator | Beth, Thomas | |
| dc.date | 2003-05-16 | |
| dc.date.accessioned | 2026-07-07T06:06:46Z | |
| dc.date.available | 2026-07-07T06:06:46Z | |
| dc.description | 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. | |
| dc.description | 9 pages | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0305090 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0305090 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/91094 | |
| dc.subject | Quantum Physics | |
| dc.title | Two QCMA-complete problems | |
| dc.type | text |