[{"conference":{"name":"31st Conference on Computational Complexity (CCC 2016)","location":"Tokyo, Japan"},"doi":"10.4230/LIPIcs.CCC.2016.27","main_file_link":[{"open_access":"1","url":"http://drops.dagstuhl.de/opus/volltexte/2016/5836/"}],"volume":50,"author":[{"first_name":"Niel","last_name":"de Beaudrap","full_name":"de Beaudrap, Niel"},{"id":"71541","full_name":"Gharibian, Sevag","last_name":"Gharibian","orcid":"0000-0002-9992-3379","first_name":"Sevag"}],"date_updated":"2023-02-28T11:01:53Z","oa":"1","page":"27:1-17:21","intvolume":"        50","citation":{"apa":"de Beaudrap, N., &#38; Gharibian, S. (2016). A Linear Time Algorithm for Quantum 2-SAT. In R. Raz (Ed.), <i>Proceedings of the 31st Conference on Computational Complexity (CCC 2016)</i> (Vol. 50, p. 27:1-17:21). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.CCC.2016.27\">https://doi.org/10.4230/LIPIcs.CCC.2016.27</a>","mla":"de Beaudrap, Niel, and Sevag Gharibian. “A Linear Time Algorithm for Quantum 2-SAT.” <i>Proceedings of the 31st Conference on Computational Complexity (CCC 2016)</i>, edited by Ran Raz, vol. 50, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016, p. 27:1-17:21, doi:<a href=\"https://doi.org/10.4230/LIPIcs.CCC.2016.27\">10.4230/LIPIcs.CCC.2016.27</a>.","bibtex":"@inproceedings{de Beaudrap_Gharibian_2016, place={Dagstuhl, Germany}, series={Leibniz International Proceedings in Informatics (LIPIcs)}, title={A Linear Time Algorithm for Quantum 2-SAT}, volume={50}, DOI={<a href=\"https://doi.org/10.4230/LIPIcs.CCC.2016.27\">10.4230/LIPIcs.CCC.2016.27</a>}, booktitle={Proceedings of the 31st Conference on Computational Complexity (CCC 2016)}, publisher={Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, author={de Beaudrap, Niel and Gharibian, Sevag}, editor={Raz, Ran}, year={2016}, pages={27:1–17:21}, collection={Leibniz International Proceedings in Informatics (LIPIcs)} }","short":"N. de Beaudrap, S. Gharibian, in: R. Raz (Ed.), Proceedings of the 31st Conference on Computational Complexity (CCC 2016), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2016, p. 27:1–17:21.","ama":"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). 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>","chicago":"Beaudrap, Niel de, and Sevag Gharibian. “A Linear Time Algorithm for Quantum 2-SAT.” In <i>Proceedings of the 31st Conference on Computational Complexity (CCC 2016)</i>, edited by Ran Raz, 50:27:1-17:21. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. <a href=\"https://doi.org/10.4230/LIPIcs.CCC.2016.27\">https://doi.org/10.4230/LIPIcs.CCC.2016.27</a>.","ieee":"N. de Beaudrap and S. Gharibian, “A Linear Time Algorithm for Quantum 2-SAT,” in <i>Proceedings of the 31st Conference on Computational Complexity (CCC 2016)</i>, Tokyo, Japan, 2016, vol. 50, p. 27:1–17:21, doi: <a href=\"https://doi.org/10.4230/LIPIcs.CCC.2016.27\">10.4230/LIPIcs.CCC.2016.27</a>."},"place":"Dagstuhl, Germany","publication_identifier":{"isbn":["978-3-95977-008-8"]},"publication_status":"published","extern":"1","department":[{"_id":"623"},{"_id":"7"}],"user_id":"71541","series_title":"Leibniz International Proceedings in Informatics (LIPIcs)","_id":"8159","status":"public","editor":[{"full_name":"Raz, Ran","last_name":"Raz","first_name":"Ran"}],"type":"conference","title":"A Linear Time Algorithm for Quantum 2-SAT","date_created":"2019-03-01T11:19:54Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik","year":"2016","language":[{"iso":"eng"}],"keyword":["quantum 2-SAT","transfer matrix","strongly connected components","limited backtracking","local Hamiltonian"],"external_id":{"arxiv":["1508.07338"]},"abstract":[{"lang":"eng","text":"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]."}],"publication":"Proceedings of the 31st Conference on Computational Complexity (CCC 2016)"}]