Two QCMA-complete problems
Loading...
Date
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
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.
9 pages
9 pages