University of Cambridge > Talks.cam > CQIF Seminar > The Quantum Strong Exponential-Time Hypothesis

The Quantum Strong Exponential-Time Hypothesis

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Johannes Bausch.

The strong exponential-time hypothesis (SETH) is a widely believed conjecture in the field of(classical) complexity theory. It states that CNF formulas cannot be analyzed for satisfiability with a speedup over exhaustive search. This hypothesis and its variants gave rise to a fruitful fieldof research, fine-grained complexity, obtaining (mostly tight) lower bounds for many problems in P whose unconditional lower bounds we are unable to prove. In this work, we introduce a framework of Quantum Strong Exponential-Time Hypotheses, as quantum analogues to SETH . We provide a series of hypotheses that allow for obtaining conditional quantum-time lower bounds for many problems in BQP : the QSETH framework. As an example, we illustrate the use of the QSETH by providing a conditional quantum time lower bound of (almost) Ω(n^1.5) for the Edit-Distance problem.

This is joint work with Florian Speelman en Subhasree Patro.

This talk is part of the CQIF Seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2019 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity