Title :
Quantum 3-SAT Is QMA1-Complete
Author :
Gosset, David ; Nagaj, Daniel
Abstract :
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 QMA1-complete [4]. Quantum 3-SAT was known to be contained in QMA1 [4], but its computational hardness was unknown until now. We prove that quantum 3-SAT is QMA1-hard, and therefore complete for this complexity class.
Keywords :
Boolean functions; computability; computational complexity; constraint satisfaction problems; QMA1-complete; classical Boolean satisfiability; complexity class; computational hardness; constraint satisfaction problem; quantum 3-SAT problem; quantum k-SAT problem; quantum satisfiability; Clocks; Complexity theory; Hilbert space; Logic gates; Quantum computing; Registers; Stationary state; Computational complexity; Quantum computing;
Conference_Titel :
Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on
Conference_Location :
Berkeley, CA
DOI :
10.1109/FOCS.2013.86