2026-07-22T18:36:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9620 2024-03-06T10:44:33Z ddc:004 open_access

On Efficiently Solvable Cases of Quantum k-SAT Aldi, Marco de Beaudrap, Niel Gharibian, Sevag Saeedi, Seyran search complexity local Hamiltonian Quantum SAT algebraic geometry 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marco Aldi and Niel de Beaudrap and Sevag Gharibian and Seyran Saeedi 2018 Is Part Of LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2018.38 urn:nbn:de:0030-drops-96201 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.38 eng https://creativecommons.org/licenses/by/3.0/legalcode