Class Description

QMA₁: One Sided QMA

Same as QMA except that for a "yes" instance, there exists a state that is accepted with probability 1.

Defined in [Bra06]. It was shown there that Quantum k-SAT is QMA₁-complete for any ${\displaystyle k\geq 4}$. It was also shown there that Quantum 2-SAT is in P.

This result was later improved in [GN13] where it was shown that Quantum 3-SAT is QMA₁-complete.

Linked From

No class.