  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.
