[{"user_id":"71541","editor":[{"first_name":"Ran","last_name":"Raz","full_name":"Raz, Ran"}],"volume":50,"page":"27:1-17:21","publisher":"Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik","_id":"8159","status":"public","conference":{"location":"Tokyo, Japan","name":"31st Conference on Computational Complexity (CCC 2016)"},"oa":"1","external_id":{"arxiv":["1508.07338"]},"place":"Dagstuhl, Germany","citation":{"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>.","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>","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)} }","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>.","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>","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>."},"doi":"10.4230/LIPIcs.CCC.2016.27","main_file_link":[{"open_access":"1","url":"http://drops.dagstuhl.de/opus/volltexte/2016/5836/"}],"language":[{"iso":"eng"}],"series_title":"Leibniz International Proceedings in Informatics (LIPIcs)","date_updated":"2023-02-28T11:01:53Z","publication_status":"published","intvolume":"        50","year":"2016","title":"A Linear Time Algorithm for Quantum 2-SAT","author":[{"full_name":"de Beaudrap, Niel","last_name":"de Beaudrap","first_name":"Niel"},{"id":"71541","first_name":"Sevag","orcid":"0000-0002-9992-3379","last_name":"Gharibian","full_name":"Gharibian, Sevag"}],"publication_identifier":{"isbn":["978-3-95977-008-8"]},"keyword":["quantum 2-SAT","transfer matrix","strongly connected components","limited backtracking","local Hamiltonian"],"type":"conference","department":[{"_id":"623"},{"_id":"7"}],"date_created":"2019-03-01T11:19:54Z","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]."}],"extern":"1","publication":"Proceedings of the 31st Conference on Computational Complexity (CCC 2016)"},{"language":[{"iso":"eng"}],"doi":"10.3938/jkps.57.929","title":"Modeling of Piezoelectric Langevin Transducers by Using Mixed Transfer Matrix Methods","year":"2010","author":[{"first_name":"Bo","last_name":"Fu","full_name":"Fu, Bo"},{"full_name":"Li, Chao","last_name":"Li","first_name":"Chao"},{"first_name":"Jianming","last_name":"Zhang","full_name":"Zhang, Jianming"},{"first_name":"Zhenwei","last_name":"Huang","full_name":"Huang, Zhenwei"},{"last_name":"Hemsel","first_name":"Tobias","full_name":"Hemsel, Tobias","id":"210"}],"publication_identifier":{"issn":["1948-5719"]},"date_updated":"2022-01-06T07:04:19Z","intvolume":"        57","date_created":"2019-05-13T09:40:42Z","type":"journal_article","keyword":["Piezoelectric langevin transducer","Transfer matrix method","Four (six)-pole element description","Pre-stressed bolt"],"department":[{"_id":"151"}],"publication":"Journal of Korean Physical Society","issue":"4","abstract":[{"lang":"eng","text":"In the modeling of piezoelectric Langevin transducers using usual transfer matrix methods, some simplifications have been adopted. This leads to reduction of the model quality. A mixed transfer matrix method is employed in the modeling of Langevin transducers, where the pre-stressed bolt is modeled as a separate four-pole element, which is connected to other elements in parallel. Based on the mixed transfer matrix method, the four (six)-pole element description of the piezoelectric Langevin transducer is built up and the total transfer matrix relation is derived. The resonance frequencies of the transducer are calculated and then measured using the impedance analyzer (HP4192). Experimental result shows that the mixed transfer matrix method has better modeling quality than the usual transfer matrix method for the vibration analysis of piezoelectric Langevin transducers."}],"page":"929","_id":"9745","user_id":"55222","volume":57,"status":"public","citation":{"bibtex":"@article{Fu_Li_Zhang_Huang_Hemsel_2010, title={Modeling of Piezoelectric Langevin Transducers by Using Mixed Transfer Matrix Methods}, volume={57}, DOI={<a href=\"https://doi.org/10.3938/jkps.57.929\">10.3938/jkps.57.929</a>}, number={4}, journal={Journal of Korean Physical Society}, author={Fu, Bo and Li, Chao and Zhang, Jianming and Huang, Zhenwei and Hemsel, Tobias}, year={2010}, pages={929} }","short":"B. Fu, C. Li, J. Zhang, Z. Huang, T. Hemsel, Journal of Korean Physical Society 57 (2010) 929.","ama":"Fu B, Li C, Zhang J, Huang Z, Hemsel T. Modeling of Piezoelectric Langevin Transducers by Using Mixed Transfer Matrix Methods. <i>Journal of Korean Physical Society</i>. 2010;57(4):929. doi:<a href=\"https://doi.org/10.3938/jkps.57.929\">10.3938/jkps.57.929</a>","chicago":"Fu, Bo, Chao Li, Jianming Zhang, Zhenwei Huang, and Tobias Hemsel. “Modeling of Piezoelectric Langevin Transducers by Using Mixed Transfer Matrix Methods.” <i>Journal of Korean Physical Society</i> 57, no. 4 (2010): 929. <a href=\"https://doi.org/10.3938/jkps.57.929\">https://doi.org/10.3938/jkps.57.929</a>.","ieee":"B. Fu, C. Li, J. Zhang, Z. Huang, and T. Hemsel, “Modeling of Piezoelectric Langevin Transducers by Using Mixed Transfer Matrix Methods,” <i>Journal of Korean Physical Society</i>, vol. 57, no. 4, p. 929, 2010.","apa":"Fu, B., Li, C., Zhang, J., Huang, Z., &#38; Hemsel, T. (2010). Modeling of Piezoelectric Langevin Transducers by Using Mixed Transfer Matrix Methods. <i>Journal of Korean Physical Society</i>, <i>57</i>(4), 929. <a href=\"https://doi.org/10.3938/jkps.57.929\">https://doi.org/10.3938/jkps.57.929</a>","mla":"Fu, Bo, et al. “Modeling of Piezoelectric Langevin Transducers by Using Mixed Transfer Matrix Methods.” <i>Journal of Korean Physical Society</i>, vol. 57, no. 4, 2010, p. 929, doi:<a href=\"https://doi.org/10.3938/jkps.57.929\">10.3938/jkps.57.929</a>."},"quality_controlled":"1"}]