Testing Quantum Satisfiability

Abstract Quantum k -SAT (the problem of determining whether a k -local Hamiltonian is frustration-free) is known to be QMA $$_1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mmultiscripts> <mml:mrow/> <mml:mn>1</mml:mn> <mml:mrow/> </mml:mmultiscripts> </mml:math> -complete for $$k\ge 3$$ <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 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$$ <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 $$\epsilon &gt;0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ϵ</mml:mi> <mml:mo>&gt;</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 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.