A Linear Time Algorithm for Quantum 2-SAT

The Boolean constraint satisfaction problem 3-SAT is arguably the canonical NP -complete problem. In contrast, 2 -SAT can not only be decided in polynomial time, but in fact in deterministic linear time. In 2006, Bravyi proposed a physically motivated generalization of k -SAT to the quantum setting, defining the problem "quantum k -SAT". He showed that quantum 2-SAT is also solvable in polynomial time on a classical computer, in particular in deterministic time 0(n4), assuming unit -cost arithmetic over a field extension of the rational numbers, where n is the number of variables. In this paper, we present an algorithm for quantum 2 -SAT which runs in linear time, i.e. deterministic time 0(n + m) for n and m the number of variables and clauses, respectively. Our approach exploits the transfer matrix techniques of Laumann et al. [QIC, 2010] used in the study of phase transitions for random quantum 2 -SAT, and bears similarities with both the linear time 2-SAT algorithms of Even, Itai, and Shamir (based on backtracking) [SICOMP, 1976] and Aspvall, Plass, and Tarjan (based on strongly connected components) [IPL, 1979].