Linear time algorithm for quantum 2SAT

A canonical result about satisfiability theory is that the 2-SAT problem can be solved in linear time, despite the NP-hardness of the 3-SAT problem. In the quantum 2-SAT problem, we are given a family of 2-qubit projectors Π_ij on a system of n qubits, and the task is to decide whether the Hamiltonian H=sum Π_ij has a 0-eigenvalue, or it is larger than 1/n^α for some α=O(1). The problem is not only a natural extension of the classical 2-SAT problem to the quantum case, but is also equivalent to the problem of finding the ground state of 2-local frustration-free Hamiltonians of spin frac{1}{2}, a well-studied model believed to capture certain key properties in modern condensed matter physics. While Bravyi has shown that the quantum 2-SAT problem has a classical polynomial-time algorithm, the running time of his algorithm is O\(n⁴\). In this paper we give a classical algorithm with linear running time in the number of local projectors, therefore achieving the best possible complexity.