---
res:
bibo_abstract:
- 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].@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Niel
foaf_name: de Beaudrap, Niel
foaf_surname: de Beaudrap
- foaf_Person:
foaf_givenName: Sevag
foaf_name: Gharibian, Sevag
foaf_surname: Gharibian
foaf_workInfoHomepage: http://www.librecat.org/personId=71541
orcid: 0000-0002-9992-3379
bibo_doi: 10.4230/LIPIcs.CCC.2016.27
bibo_volume: 50
dct_date: 2016^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/978-3-95977-008-8
dct_language: eng
dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik@
dct_subject:
- quantum 2-SAT
- transfer matrix
- strongly connected components
- limited backtracking
- local Hamiltonian
dct_title: A Linear Time Algorithm for Quantum 2-SAT@
...