On efficiently solvable cases of Quantum k-SAT
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 generalization of NP with one-sided error. Whereas k-SAT has been well-studied for special tractable cases, as well...
| Main Authors: | , , , |
|---|---|
| Format: | Conference item |
| Published: |
Schloss Dagstuhl
2018
|