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-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 εn^k 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.

31 pages. Rev 3: Final version. Rewrote the proof of Theorem 1.8 to make it more reader-friendly. To appear in Comm. Math. Phys

References in corpus (12)

• Monogamy of entanglement and other correlations
• "Squashed Entanglement" - An Additive Entanglement Measure
• Faithful Squashed Entanglement
• Shadows and intersections: stability and new proofs
• NLTS Hamiltonians from good quantum codes
• A note on the optimality of decomposable entanglement witnesses and completely entangled subspaces
• On product, generic and random generic quantum satisfiability
• No-go Theorem for One-way Quantum Computing on Naturally Occurring Two-level Systems
• A Quantum Lovasz Local Lemma
• Approximating random quantum optimization problems
• On efficiently solvable cases of Quantum k-SAT
• A construction of Combinatorial NLTS