Quantum 3-SAT Is QMA1-Complete

Quantum satisfiability is a constraint satisfaction problem that generalizes classical boolean satisfiability. In the quantum k-SAT problem, each constraint is specified by a k-local projector and is satisfied by any state in its nullspace. Bravyi showed that quantum 2-SAT can be solved efficiently on a classical computer and that quantum k-SAT with k ≥ 4 is QMA₁-complete [4]. Quantum 3-SAT was known to be contained in QMA₁ [4], but its computational hardness was unknown until now. We prove that quantum 3-SAT is QMA₁-hard, and therefore complete for this complexity class.