  Complexity of a quantum analogue of the satisfiability problem is studied.
Quantum k-SAT is a problem of verifying whether there exists n-qubit pure state
such that its k-qubit reduced density matrices have support on prescribed
subspaces. We present a classical algorithm solving quantum 2-SAT in a
polynomial time. It generalizes the well-known algorithm for the classical
2-SAT. Besides, we show that for any k>=4 quantum k-SAT is complete in the
complexity class QMA with one-sided error.
