DocumentCode :
655243
Title :
Quantum 3-SAT Is QMA1-Complete
Author :
Gosset, David ; Nagaj, Daniel
fYear :
2013
fDate :
26-29 Oct. 2013
Firstpage :
756
Lastpage :
765
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on
Conference_Location :
Berkeley, CA
ISSN :
0272-5428
Type :
conf
DOI :
10.1109/FOCS.2013.86
Filename :
6686212
Link To Document :
بازگشت