[{"publication":"43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)","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"}],"external_id":{"arxiv":["1712.09617"]},"keyword":["search complexity","local Hamiltonian","Quantum SAT","algebraic geometry"],"language":[{"iso":"eng"}],"year":"2018","publisher":"Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik","date_created":"2019-03-01T11:34:41Z","title":"On Efficiently Solvable Cases of Quantum k-SAT","type":"conference","editor":[{"first_name":"Igor","full_name":"Potapov, Igor","last_name":"Potapov"},{"first_name":"Paul","last_name":"Spirakis","full_name":"Spirakis, Paul"},{"full_name":"Worrell, James","last_name":"Worrell","first_name":"James"}],"status":"public","_id":"8162","department":[{"_id":"623"},{"_id":"7"}],"series_title":"Leibniz International Proceedings in Informatics (LIPIcs)","user_id":"71541","publication_identifier":{"unknown":["978-3-95977-086-6"]},"publication_status":"published","place":"Dagstuhl, Germany","intvolume":"       117","page":"38:1-38:16","citation":{"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>.","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.","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)} }","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>","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>."},"oa":"1","date_updated":"2023-02-28T11:01:16Z","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"},{"id":"71541","full_name":"Gharibian, Sevag","orcid":"0000-0002-9992-3379","last_name":"Gharibian","first_name":"Sevag"},{"full_name":"Saeedi, Seyran","last_name":"Saeedi","first_name":"Seyran"}],"conference":{"name":"43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)","location":"Liverpool, UK"},"doi":"10.4230/LIPIcs.MFCS.2018.38","main_file_link":[{"open_access":"1","url":"http://drops.dagstuhl.de/opus/volltexte/2018/9620/"}]},{"author":[{"first_name":"Sevag","orcid":"0000-0002-9992-3379","last_name":"Gharibian","id":"71541","full_name":"Gharibian, Sevag"},{"full_name":"Yirka, Justin","last_name":"Yirka","first_name":"Justin"}],"volume":73,"date_updated":"2023-02-28T11:00:48Z","oa":"1","main_file_link":[{"url":"http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8577","open_access":"1"}],"conference":{"name":"12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)","location":"Paris, France"},"doi":"10.4230/LIPIcs.TQC.2017.2","publication_status":"published","publication_identifier":{"unknown":["978-3-95977-034-7"]},"citation":{"ieee":"S. Gharibian and J. Yirka, “The Complexity of Simulating Local Measurements on Quantum Systems,” in <i>12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)</i>, Paris, France, 2018, vol. 73, p. 2:1-2:17, doi: <a href=\"https://doi.org/10.4230/LIPIcs.TQC.2017.2\">10.4230/LIPIcs.TQC.2017.2</a>.","chicago":"Gharibian, Sevag, and Justin Yirka. “The Complexity of Simulating Local Measurements on Quantum Systems.” In <i>12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)</i>, edited by Mark Wilde, 73:2:1-2:17. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. <a href=\"https://doi.org/10.4230/LIPIcs.TQC.2017.2\">https://doi.org/10.4230/LIPIcs.TQC.2017.2</a>.","ama":"Gharibian S, Yirka J. The Complexity of Simulating Local Measurements on Quantum Systems. In: Wilde M, ed. <i>12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)</i>. Vol 73. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik; 2018:2:1-2:17. doi:<a href=\"https://doi.org/10.4230/LIPIcs.TQC.2017.2\">10.4230/LIPIcs.TQC.2017.2</a>","mla":"Gharibian, Sevag, and Justin Yirka. “The Complexity of Simulating Local Measurements on Quantum Systems.” <i>12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)</i>, edited by Mark Wilde, vol. 73, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018, p. 2:1-2:17, doi:<a href=\"https://doi.org/10.4230/LIPIcs.TQC.2017.2\">10.4230/LIPIcs.TQC.2017.2</a>.","bibtex":"@inproceedings{Gharibian_Yirka_2018, place={Dagstuhl, Germany}, series={Leibniz International Proceedings in Informatics (LIPIcs)}, title={The Complexity of Simulating Local Measurements on Quantum Systems}, volume={73}, DOI={<a href=\"https://doi.org/10.4230/LIPIcs.TQC.2017.2\">10.4230/LIPIcs.TQC.2017.2</a>}, booktitle={12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)}, publisher={Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, author={Gharibian, Sevag and Yirka, Justin}, editor={Wilde, Mark}, year={2018}, pages={2:1-2:17}, collection={Leibniz International Proceedings in Informatics (LIPIcs)} }","short":"S. Gharibian, J. Yirka, in: M. Wilde (Ed.), 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2018, p. 2:1-2:17.","apa":"Gharibian, S., &#38; Yirka, J. (2018). The Complexity of Simulating Local Measurements on Quantum Systems. In M. Wilde (Ed.), <i>12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)</i> (Vol. 73, p. 2:1-2:17). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.TQC.2017.2\">https://doi.org/10.4230/LIPIcs.TQC.2017.2</a>"},"page":"2:1-2:17","intvolume":"        73","place":"Dagstuhl, Germany","user_id":"71541","series_title":"Leibniz International Proceedings in Informatics (LIPIcs)","department":[{"_id":"623"},{"_id":"7"}],"_id":"8160","type":"conference","status":"public","editor":[{"last_name":"Wilde","full_name":"Wilde, Mark","first_name":"Mark"}],"date_created":"2019-03-01T11:25:27Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik","title":"The Complexity of Simulating Local Measurements on Quantum Systems","year":"2018","external_id":{"arxiv":["1606.05626"]},"language":[{"iso":"eng"}],"keyword":["Complexity theory","Quantum Merlin Arthur (QMA)","local Hamiltonian","local measurement","spectral gap"],"publication":"12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)","abstract":[{"text":"An important task in quantum physics is the estimation of local quantities for ground states of local Hamiltonians. Recently, Ambainis defined the complexity class P^QMA[log], and motivated its study by showing that the physical task of estimating the expectation value of a local observable against the ground state of a local Hamiltonian is P^QMA[log]-complete. In this paper, we continue the study of P^QMA[log], obtaining the following results. The P^QMA[log]-completeness result of Ambainis requires O(log n)-local observ- ables and Hamiltonians. We show that simulating even a single qubit measurement on ground states of 5-local Hamiltonians is P^QMA[log]-complete, resolving an open question of Ambainis. We formalize the complexity theoretic study of estimating two-point correlation functions against ground states, and show that this task is similarly P^QMA[log]-complete. P^QMA[log] is thought of as \"slightly harder\" than QMA. We justify this formally by exploiting the hierarchical voting technique of Beigel, Hemachandra, and Wechsung to show P^QMA[log] \\subseteq PP. This improves the containment QMA \\subseteq PP from Kitaev and Watrous. A central theme of this work is the subtlety involved in the study of oracle classes in which the oracle solves a promise problem. In this vein, we identify a flaw in Ambainis' prior work regarding a P^UQMA[log]-hardness proof for estimating spectral gaps of local Hamiltonians. By introducing a \"query validation\" technique, we build on his prior work to obtain P^UQMA[log]-hardness for estimating spectral gaps under polynomial-time Turing reductions.","lang":"eng"}]},{"keyword":["Local Hamiltonian","ground state connectivity","quantum Hamiltonian complexity","reconfiguration problem"],"language":[{"iso":"eng"}],"external_id":{"arxiv":["1409.3182"]},"publication":"ACM Transactions on Computation Theory (TOCT)","title":"Ground State Connectivity of Local Hamiltonians","publisher":"ACM","date_created":"2019-03-01T11:49:31Z","year":"2018","issue":"2","_id":"8167","department":[{"_id":"623"},{"_id":"7"}],"user_id":"71541","status":"public","type":"journal_article","doi":"10.1145/3186587","main_file_link":[{"url":"https://arxiv.org/abs/1409.3182","open_access":"1"}],"oa":"1","date_updated":"2023-02-28T11:01:36Z","volume":10,"author":[{"orcid":"0000-0002-9992-3379","last_name":"Gharibian","full_name":"Gharibian, Sevag","id":"71541","first_name":"Sevag"},{"last_name":"Sikora","full_name":"Sikora, Jamie","first_name":"Jamie"}],"page":"8:1-8:28","intvolume":"        10","citation":{"short":"S. Gharibian, J. Sikora, ACM Transactions on Computation Theory (TOCT) 10 (2018) 8:1-8:28.","bibtex":"@article{Gharibian_Sikora_2018, title={Ground State Connectivity of Local Hamiltonians}, volume={10}, DOI={<a href=\"https://doi.org/10.1145/3186587\">10.1145/3186587</a>}, number={2}, journal={ACM Transactions on Computation Theory (TOCT)}, publisher={ACM}, author={Gharibian, Sevag and Sikora, Jamie}, year={2018}, pages={8:1-8:28} }","mla":"Gharibian, Sevag, and Jamie Sikora. “Ground State Connectivity of Local Hamiltonians.” <i>ACM Transactions on Computation Theory (TOCT)</i>, vol. 10, no. 2, ACM, 2018, p. 8:1-8:28, doi:<a href=\"https://doi.org/10.1145/3186587\">10.1145/3186587</a>.","apa":"Gharibian, S., &#38; Sikora, J. (2018). Ground State Connectivity of Local Hamiltonians. <i>ACM Transactions on Computation Theory (TOCT)</i>, <i>10</i>(2), 8:1-8:28. <a href=\"https://doi.org/10.1145/3186587\">https://doi.org/10.1145/3186587</a>","ama":"Gharibian S, Sikora J. Ground State Connectivity of Local Hamiltonians. <i>ACM Transactions on Computation Theory (TOCT)</i>. 2018;10(2):8:1-8:28. doi:<a href=\"https://doi.org/10.1145/3186587\">10.1145/3186587</a>","chicago":"Gharibian, Sevag, and Jamie Sikora. “Ground State Connectivity of Local Hamiltonians.” <i>ACM Transactions on Computation Theory (TOCT)</i> 10, no. 2 (2018): 8:1-8:28. <a href=\"https://doi.org/10.1145/3186587\">https://doi.org/10.1145/3186587</a>.","ieee":"S. Gharibian and J. Sikora, “Ground State Connectivity of Local Hamiltonians,” <i>ACM Transactions on Computation Theory (TOCT)</i>, vol. 10, no. 2, p. 8:1-8:28, 2018, doi: <a href=\"https://doi.org/10.1145/3186587\">10.1145/3186587</a>."},"publication_identifier":{"issn":["1942-3454"]},"publication_status":"published"},{"conference":{"location":"Tokyo, Japan","name":"31st Conference on Computational Complexity (CCC 2016)"},"doi":"10.4230/LIPIcs.CCC.2016.27","main_file_link":[{"open_access":"1","url":"http://drops.dagstuhl.de/opus/volltexte/2016/5836/"}],"oa":"1","date_updated":"2023-02-28T11:01:53Z","volume":50,"author":[{"first_name":"Niel","full_name":"de Beaudrap, Niel","last_name":"de Beaudrap"},{"first_name":"Sevag","id":"71541","full_name":"Gharibian, Sevag","last_name":"Gharibian","orcid":"0000-0002-9992-3379"}],"place":"Dagstuhl, Germany","page":"27:1-17:21","intvolume":"        50","citation":{"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>","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>.","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>.","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.","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>"},"publication_identifier":{"isbn":["978-3-95977-008-8"]},"publication_status":"published","extern":"1","_id":"8159","department":[{"_id":"623"},{"_id":"7"}],"series_title":"Leibniz International Proceedings in Informatics (LIPIcs)","user_id":"71541","editor":[{"full_name":"Raz, Ran","last_name":"Raz","first_name":"Ran"}],"status":"public","type":"conference","title":"A Linear Time Algorithm for Quantum 2-SAT","publisher":"Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik","date_created":"2019-03-01T11:19:54Z","year":"2016","keyword":["quantum 2-SAT","transfer matrix","strongly connected components","limited backtracking","local Hamiltonian"],"language":[{"iso":"eng"}],"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)"}]