The Complexity of the Separable Hamiltonian Problem

Details The Complexity of the Separable Hamiltonian Problem The Complexity of the Separable Hamiltonian Problem

2011-11-22

arxiv.org/abs/1111.5247v1

Physics

Quantum Physics

Scientific paper

In this paper, we study variants of the canonical Local-Hamiltonian problem where, in addition, the witness is promised to be separable. We define two variants of the Local-Hamiltonian problem. The input for the Separable-Local-Hamiltonian problem is the same as the Local-Hamiltonian problem, i.e. a local Hamiltonian and two energies a and b, but the question is somewhat different: the answer is YES if there is a separable quantum state with energy at most a, and the answer is NO if all separable quantum states have energy at least b. The Separable-Sparse-Hamiltonian problem is defined similarly, but the Hamiltonian is not necessarily local, but rather sparse. We show that the Separable-Sparse-Hamiltonian problem is QMA(2)-Complete, while Separable-Local-Hamiltonian is in QMA. This should be compared to the Local-Hamiltonian problem, and the Sparse-Hamiltonian problem which are both QMA-Complete. To the best of our knowledge, Separable-SPARSE-Hamiltonian is the first non-trivial problem shown to be QMA(2)-Complete.

Affiliated with

Also associated with

No associations

Rating

The Complexity of the Separable Hamiltonian Problem 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 The Complexity of the Separable Hamiltonian Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Complexity of the Separable Hamiltonian Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-553746