On the restrictiveness of quantum satisfiability

​Given a k-QSAT instance on a fixed interaction hypergraph H, in which each projector excludes a uniformly random state, what is the criterion for satisfiability? We show the following combinatorial sufficient condition: for every induced subgraph of H, the matching polynomial evaluated at −2^−k is strictly positive. We conjecture that this condition holds if and only if a tightly related instance (which uses qudits with large enough dimensions on the same interaction graph H) is satisfiable. We will describe the relationship between this condition and the roots of the partition function of a hard core lattice gas. We find when the above condition holds analytically for 1-D chains, trees (which coincide and provide an arguably simpler proofs to Movassagh et al. 2010 and Coudron and Movassagh 2012), cycles, and the ladder graph. We also show how this condition implies the quantum Lovász local lemma.​​