Matched Instances of Quantum Satisfiability (QSat) – Product State Solutions of Restrictions

Matched instances of the quantum satisfiability problem have the following property: They have a product state solution. This is a mere existential statement and the problem is to find such a solution efficiently. Recent work by Gharibian and coauthors has made first progress on this question: They give an efficient algorithm which works for instances whose interaction hypergraph is restricted in a certain way.