  Quantum k-SAT (the problem of determining whether a k-local Hamiltonian is
frustration-free) is known to be QMA_1-complete for k >= 3, and hence likely
hard for quantum computers to solve. Building on a classical result of Alon and
Shapira, we show that quantum k-SAT can be solved in randomised polynomial time
given the `property testing' promise that the instance is either satisfiable
(by any state) or far from satisfiable by a product state; by `far from
satisfiable by a product state' we mean that \epsilon n^k constraints must be
removed before a product state solution exists, for some fixed \epsilon > 0.
The proof has two steps: we first show that for a satisfiable instance of
quantum k-SAT, most subproblems on a constant number of qubits are satisfiable
by a product state. We then show that for an instance of quantum k-SAT which is
far from satisfiable by a product state, most subproblems are unsatisfiable by
a product state. Given the promise, quantum k-SAT may therefore be solved by
checking satisfiability by a product state on randomly chosen subsystems of
constant size.
