Quantum 3-SAT is QMA1-complete

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 greater than 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.

References in corpus (3)

• Criticality without frustration for quantum spin-1 chains
• A new construction for a QMA complete 3-local Hamiltonian
• Quantum 3-SAT is QMA1-complete

Cited by in corpus (10)

• Quantum information processing with superconducting circuits: a review
• Adiabatic Quantum Simulation of Quantum Chemistry
• Exploiting locality in quantum computation for quantum chemistry
• The Bose-Hubbard model is QMA-complete
• Analysis and limitations of modified circuit-to-Hamiltonian constructions
• Complexity of Supersymmetric Systems and the Cohomology Problem
• Quantum 3-SAT is QMA1-complete
• On efficiently solvable cases of Quantum k-SAT
• The 7 faces of quantum NP
• Complexity of Fermionic 2-SAT