  The problem 2-quantum-satisfiability (2-QSAT) is the generalisation of the
2-CNF-SAT problem to quantum bits, and is equivalent to determining whether or
not a spin-1/2 Hamiltonian with two-body terms is frustration-free. Similarly
to the classical problem 2-SAT, the counting problem #2-QSAT of determining the
size (i.e. the dimension) of the set of satisfying states is #P-complete.
However, if we consider random instances of #2-QSAT in which constraints are
sampled from the Haar measure, intractible instances have measure zero. An
apparent reason for this is that almost all two-qubit constraints are
entangled, which more readily give rise to long-range constraints.
  We investigate under which conditions product constraints also give rise to
efficiently solvable families of #2-QSAT instances. We consider #2-QSAT
involving only discrete distributions over tensor product operators, which
interpolates between classical #2-SAT and #2-QSAT involving arbitrary product
constraints. We find that such instances of #2-QSAT, defined on Erdos--Renyi
graphs or bond-percolated lattices, are asymptotically almost surely
efficiently solvable except to the extent that they are biased to resemble
monotone instances of #2-SAT.
