  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
O(n^4), assuming unit-cost arithmetic over a field extension of the rational
numbers, where n is number of variables. In this paper, we present an algorithm
for quantum 2-SAT which runs in linear time, i.e. deterministic time O(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].
