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 & varepsilon;n(k) constraints must be removed before a product state solution exists, for some fixed & varepsilon;>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.

Publication:

COMMUNICATIONS IN MATHEMATICAL PHYSICS

http://dx.doi.org/10.1007/s00220-025-05377-4

Author:

Ashley Montanaro

School of Mathematics, University of Bristol, Bristol BS8 1UG, UK.

Phasecraft Ltd., Bristol BS1 4XE, UK.

E-mail: ashley.montanaro@bristol.ac.uk.

Changpeng Shao

Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China.

E-mail: changpeng.shao@amss.ac.cn.

Dominic Verdon

Department of Computer Science and Technology, University of Cambridge, Cambridge CB3 0FD, UK

E-mail: dtv20@cam.ac.uk.

School of Mathematics, University of Bristol, Bristol BS8 1UG, UK.

E-mail: dominic.verdon@bristol.ac.uk.