• What English QuSoft
  • When 29-03-2019 from 11:00 to 12:00 (Europe/Amsterdam / UTC100)
  • Where Room L0.16 at CWI Science Park 123, Amsterdam
  • Contact Name
  • Contact Phone 020 592 4032
  • Web Visit external website
  • Add event to calendar iCal

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).



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.