The constraint satisfaction problems k-SAT and Quantum k-SAT (k-QSAT) are canonical NP-complete and QMA1-complete problems (for k>=3), respectively, where QMA1 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 system of distinct representatives; this is an NP problem whose decision variant is trivial, but whose search complexity remains open.

Among other results, our main contribution is the first known parameterized algorithm for k-QSAT (which currently applies only to a certain non-trivial class of instances), which allows us to obtain exponential speedups over brute force methods in some cases. The techniques behind our work stem from algebraic geometry, although no background in the topic is required for this presentation. Along the way, we will require the new concept of transfer filtrations on hypergraphs, for which we leave certain complexity theoretic questions open.

Joint work with Marco Aldi (Virginia Commonwealth University), Niel de Beaudrap (University of Oxford), and Seyran Saeedi (Virginia Commonwealth University).