---
res:
  bibo_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.@eng'
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Marco
      foaf_name: Aldi, Marco
      foaf_surname: Aldi
  - foaf_Person:
      foaf_givenName: Niel
      foaf_name: de Beaudrap, Niel
      foaf_surname: de Beaudrap
  - foaf_Person:
      foaf_givenName: Sevag
      foaf_name: Gharibian, Sevag
      foaf_surname: Gharibian
      foaf_workInfoHomepage: http://www.librecat.org/personId=71541
    orcid: 0000-0002-9992-3379
  - foaf_Person:
      foaf_givenName: Seyran
      foaf_name: Saeedi, Seyran
      foaf_surname: Saeedi
  bibo_doi: 10.4230/LIPIcs.MFCS.2018.38
  bibo_volume: 117
  dct_date: 2018^xs_gYear
  dct_language: eng
  dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik@
  dct_subject:
  - search complexity
  - local Hamiltonian
  - Quantum SAT
  - algebraic geometry
  dct_title: On Efficiently Solvable Cases of Quantum k-SAT@
...