A Linear Time Algorithm for Quantum 2-SAT
de Beaudrap, Niel
Gharibian, Sevag
Raz, Ran
quantum 2-SAT
transfer matrix
strongly connected components
limited backtracking
local Hamiltonian
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].
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
2016
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
https://ris.uni-paderborn.de/record/8159
de Beaudrap N, Gharibian S. A Linear Time Algorithm for Quantum 2-SAT. In: Raz R, ed. <i>Proceedings of the 31st Conference on Computational Complexity (CCC 2016)</i>. Vol 50. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik; 2016:27:1-17:21. doi:<a href="https://doi.org/10.4230/LIPIcs.CCC.2016.27">10.4230/LIPIcs.CCC.2016.27</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.4230/LIPIcs.CCC.2016.27
info:eu-repo/semantics/altIdentifier/isbn/978-3-95977-008-8
info:eu-repo/semantics/altIdentifier/arxiv/1508.07338
info:eu-repo/semantics/openAccess