On efficiently solvable cases of Quantum k-SAT.
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).
Bio:
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.
