[{"language":[{"iso":"eng"}],"keyword":["search complexity","local Hamiltonian","Quantum SAT","algebraic geometry"],"external_id":{"arxiv":["1712.09617"]},"abstract":[{"text":"The constraint satisfaction problems k-SAT and Quantum k-SAT (k-QSAT) are canonical NP-complete and QMA_1-complete problems (for k >= 3), respectively, where QMA_1 is a quantum generalization of NP with one-sided error. Whereas k-SAT has been well-studied for special tractable cases, as well as from a parameterized complexity perspective, much less is known in similar settings for k-QSAT. Here, we study the open problem of computing satisfying assignments to k-QSAT instances which have a \"matching\" or \"dimer covering\"; this is an NP problem whose decision variant is trivial, but whose search complexity remains open. Our results fall into three directions, all of which relate to the \"matching\" setting: (1) We give a polynomial-time classical algorithm for k-QSAT when all qubits occur in at most two clauses. (2) We give a parameterized algorithm for k-QSAT instances from a certain non-trivial class, which allows us to obtain exponential speedups over brute force methods in some cases by reducing the problem to solving for a single root of a single univariate polynomial. (3) We conduct a structural graph theoretic study of 3-QSAT interaction graphs which have a \"matching\". We remark that the results of (2), in particular, introduce a number of new tools to the study of Quantum SAT, including graph theoretic concepts such as transfer filtrations and blow-ups from algebraic geometry; we hope these prove useful elsewhere.","lang":"eng"}],"publication":"43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)","title":"On Efficiently Solvable Cases of Quantum k-SAT","date_created":"2019-03-01T11:34:41Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik","year":"2018","department":[{"_id":"623"},{"_id":"7"}],"user_id":"71541","series_title":"Leibniz International Proceedings in Informatics (LIPIcs)","_id":"8162","status":"public","editor":[{"full_name":"Potapov, Igor","last_name":"Potapov","first_name":"Igor"},{"last_name":"Spirakis","full_name":"Spirakis, Paul","first_name":"Paul"},{"first_name":"James","last_name":"Worrell","full_name":"Worrell, James"}],"type":"conference","conference":{"location":"Liverpool, UK","name":"43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)"},"doi":"10.4230/LIPIcs.MFCS.2018.38","main_file_link":[{"url":"http://drops.dagstuhl.de/opus/volltexte/2018/9620/","open_access":"1"}],"volume":117,"author":[{"first_name":"Marco","last_name":"Aldi","full_name":"Aldi, Marco"},{"first_name":"Niel","last_name":"de Beaudrap","full_name":"de Beaudrap, Niel"},{"orcid":"0000-0002-9992-3379","last_name":"Gharibian","full_name":"Gharibian, Sevag","id":"71541","first_name":"Sevag"},{"first_name":"Seyran","full_name":"Saeedi, Seyran","last_name":"Saeedi"}],"oa":"1","date_updated":"2023-02-28T11:01:16Z","intvolume":"       117","page":"38:1-38:16","citation":{"apa":"Aldi, M., de Beaudrap, N., Gharibian, S., &#38; Saeedi, S. (2018). On Efficiently Solvable Cases of Quantum k-SAT. In I. Potapov, P. Spirakis, &#38; J. Worrell (Eds.), <i>43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)</i> (Vol. 117, p. 38:1-38:16). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2018.38\">https://doi.org/10.4230/LIPIcs.MFCS.2018.38</a>","bibtex":"@inproceedings{Aldi_de Beaudrap_Gharibian_Saeedi_2018, place={Dagstuhl, Germany}, series={Leibniz International Proceedings in Informatics (LIPIcs)}, title={On Efficiently Solvable Cases of Quantum k-SAT}, volume={117}, DOI={<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2018.38\">10.4230/LIPIcs.MFCS.2018.38</a>}, booktitle={43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)}, publisher={Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, author={Aldi, Marco and de Beaudrap, Niel and Gharibian, Sevag and Saeedi, Seyran}, editor={Potapov, Igor and Spirakis, Paul and Worrell, James}, year={2018}, pages={38:1-38:16}, collection={Leibniz International Proceedings in Informatics (LIPIcs)} }","short":"M. Aldi, N. de Beaudrap, S. Gharibian, S. Saeedi, in: I. Potapov, P. Spirakis, J. Worrell (Eds.), 43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2018, p. 38:1-38:16.","mla":"Aldi, Marco, et al. “On Efficiently Solvable Cases of Quantum K-SAT.” <i>43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)</i>, edited by Igor Potapov et al., vol. 117, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018, p. 38:1-38:16, doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2018.38\">10.4230/LIPIcs.MFCS.2018.38</a>.","ama":"Aldi M, de Beaudrap N, Gharibian S, Saeedi S. On Efficiently Solvable Cases of Quantum k-SAT. In: Potapov I, Spirakis P, Worrell J, eds. <i>43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)</i>. Vol 117. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik; 2018:38:1-38:16. doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2018.38\">10.4230/LIPIcs.MFCS.2018.38</a>","ieee":"M. Aldi, N. de Beaudrap, S. Gharibian, and S. Saeedi, “On Efficiently Solvable Cases of Quantum k-SAT,” in <i>43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)</i>, Liverpool, UK, 2018, vol. 117, p. 38:1-38:16, doi: <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2018.38\">10.4230/LIPIcs.MFCS.2018.38</a>.","chicago":"Aldi, Marco, Niel de Beaudrap, Sevag Gharibian, and Seyran Saeedi. “On Efficiently Solvable Cases of Quantum K-SAT.” In <i>43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)</i>, edited by Igor Potapov, Paul Spirakis, and James Worrell, 117:38:1-38:16. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2018.38\">https://doi.org/10.4230/LIPIcs.MFCS.2018.38</a>."},"place":"Dagstuhl, Germany","publication_identifier":{"unknown":["978-3-95977-086-6"]},"publication_status":"published"}]