On Efficiently Solvable Cases of Quantum k-SAT

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, pp. 38:1-38:16.

Conference Paper | Published | English
Author
; ; ;
Editor
; ;
Department
Abstract
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.
Publishing Year
Proceedings Title
43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Volume
117
Page
38:1-38:16
Conference
43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Conference Location
Liverpool, UK
LibreCat-ID

Cite this

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. 43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018). Vol 117. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik; 2018:38:1-38:16. doi:10.4230/LIPIcs.MFCS.2018.38
Aldi, M., de Beaudrap, N., Gharibian, S., & Saeedi, S. (2018). On Efficiently Solvable Cases of Quantum k-SAT. In I. Potapov, P. Spirakis, & J. Worrell (Eds.), 43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018) (Vol. 117, pp. 38:1-38:16). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2018.38
@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={10.4230/LIPIcs.MFCS.2018.38}, 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, JamesEditors}, year={2018}, pages={38:1-38:16}, collection={Leibniz International Proceedings in Informatics (LIPIcs)} }
Aldi, Marco, Niel de Beaudrap, Sevag Gharibian, and Seyran Saeedi. “On Efficiently Solvable Cases of Quantum K-SAT.” In 43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018), 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. https://doi.org/10.4230/LIPIcs.MFCS.2018.38.
M. Aldi, N. de Beaudrap, S. Gharibian, and S. Saeedi, “On Efficiently Solvable Cases of Quantum k-SAT,” in 43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018), Liverpool, UK, 2018, vol. 117, pp. 38:1-38:16.
Aldi, Marco, et al. “On Efficiently Solvable Cases of Quantum K-SAT.” 43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018), edited by Igor Potapov et al., vol. 117, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018, pp. 38:1-38:16, doi:10.4230/LIPIcs.MFCS.2018.38.

Link(s) to Main File(s)
Access Level
Restricted Closed Access

Export

Marked Publications

Open Data LibreCat

Sources

arXiv 1712.09617

Search this title in

Google Scholar