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 null space. Bravyi showed that quantum 2-SAT can be solved efficiently on a classical computer and that quantum k-SAT with k &gre; or equal to 4 is QMA1-complete. Quantum 3-SAT was known to be contained in QMA1, but its computational hardness was unknown until now. We prove that quantum 3-SAT is QMA1-hard, and therefore complete for this complexity class. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1109/FOCS.2013.86 | Foundations of Computer Science |
Keywords | Field | DocType |
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,Computational complexity,Quantum computing | Quantum complexity theory,Discrete mathematics,Combinatorics,Quantum computer,Quantum sort,Quantum algorithm,Quantum information,Mathematics,Quantum capacity,Quantum error correction,Quantum operation | Conference |
Volume | Issue | ISSN |
45 | 3 | 0272-5428 |
Citations | PageRank | References |
6 | 0.49 | 7 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
David Gosset | 1 | 39 | 6.76 |
Daniel Nagaj | 2 | 57 | 5.84 |