Two QCMA-complete problems

Details Two QCMA-complete problems Two QCMA-complete problems

2003-05-16

arxiv.org/abs/quant-ph/0305090v1

Physics

Quantum Physics

9 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Two QCMA-complete problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Two QCMA-complete problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Two QCMA-complete problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-545664