On efficiently solvable cases of Quantum k-SAT

Marco Aldi, Niel de Beaudrap, Sevag Gharibian +1

The constraint satisfaction problems k-SAT and Quantum k-SAT (k-QSAT) are canonical NP-complete and QMA_1-complete problems (for k>=3), respectively, where QMA_1 is a quantum gener…