On efficiently solvable cases of quantum \(k\)-SAT (Q2223725)

The authors address the question of special cases of k-QSAT which can be solved efficiently on a classical computer. Here, k-QSAT is the question of whether a given local Hamiltonian is frustration free. There are three main results obtained by the authors. First, they show how to efficiently solve k-QSAT with sufficiently bounded occurrence of variables. Second, they provide a general framework for parameterized algorithms for k-QSAT. Finally, the authors conduct a graph theoretic study of 3-QSAT interaction graphs which have a dimer covering. New tools to study QSAT are obtained throughout the article, including graph theoretic concepts.