2023/01/25 by Ashley Montanaro, Changpeng Shao, Montanaro, Ashley +3
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Distributed systems and fault tolerance #FOS: Physical sciences #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.2301.10699
openalex publication_date 2023/01/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Quantum k-SAT (the problem of determining whether a k-local Hamiltonian is frustration-free) is known to be QMA1-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 εnk constraints must be removed before a product state solution exists, for some fixed ε> 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.