On efficiently solvable cases of Quantum k-SAT
Sevag Gharibian
Department of Computer Science
University of Paderborn, Germany
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 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. This is, to our knowledge, the first known such parameterized algorithm. 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).
Sevag obtained his Ph.D. in 2012 from the University of Waterloo in Canada under the supervision of Dr. Richard Cleve. He taught as a Visiting Lecturer at the University of Illinois at Chicago in Fall 2012, and from 2013-2014 was a Postdoctoral Fellow in the group of Dr. Umesh Vazirani at the University of California, Berkeley. He was awarded Canada's top postdoctoral fellowship in 2013, the NSERC Banting Postdoctoral Fellowship, and was also a Simons Research Fellow at the Simons Institute for the Theory of Computing at UC Berkeley. From 2014 to 2018, he was an Assistant Professor in Computer Science at Virginia Commonwealth University in the USA, and since 2018 is a Junior Professor in Computer Science at Universität Paderborn, Germany. He served from 2016 to 2018 as Secretary on the Board of Trustees of the Computational Complexity Conference (CCC) (currently acts as Past Secretary from 2018 to 2019), and is a Founding Editor of the open-access journal Quantum.