Testing Quantum Satisfiability

Quantum <i>k</i>-SAT (the problem of determining whether a <i>k</i>-local Hamiltonian is frustration-free) is known to be QMA <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mmultiscripts><mml:mrow></mml:mrow> <mml:mn>1</mml:mn> <mml:mrow></mml:mrow></mml:mmultiscripts> </mml:math> -complete for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>k</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>3</mml:mn></mml:mrow> </mml:math> , and hence likely hard for quantum computers to solve. Building on a classical result of Alon and Shapira, we show that quantum <i>k</i>-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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>ϵ</mml:mi> <mml:msup><mml:mi>n</mml:mi> <mml:mi>k</mml:mi></mml:msup> </mml:mrow> </mml:math> constraints must be removed before a product state solution exists, for some fixed <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>ϵ</mml:mi> <mml:mo>></mml:mo> <mml:mn>0</mml:mn></mml:mrow> </mml:math> . The proof has two steps: we first show that for a satisfiable instance of quantum <i>k</i>-SAT, most subproblems on a constant number of qubits are satisfiable by a product state. We then show that for an instance of quantum <i>k</i>-SAT which is far from satisfiable by a product state, most subproblems are unsatisfiable by a product state. Given the promise, quantum <i>k</i>-SAT may therefore be solved by checking satisfiability by a product state on randomly chosen subsystems of constant size.