@inproceedings{8162,
  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.}},
  author       = {{Aldi, Marco and de Beaudrap, Niel and Gharibian, Sevag and Saeedi, Seyran}},
  booktitle    = {{43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)}},
  editor       = {{Potapov, Igor and Spirakis, Paul and Worrell, James}},
  keywords     = {{search complexity, local Hamiltonian, Quantum SAT, algebraic geometry}},
  location     = {{Liverpool, UK}},
  pages        = {{38:1--38:16}},
  publisher    = {{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}},
  title        = {{{On Efficiently Solvable Cases of Quantum k-SAT}}},
  doi          = {{10.4230/LIPIcs.MFCS.2018.38}},
  volume       = {{117}},
  year         = {{2018}},
}