The Quantum Strong Exponential-Time Hypothesis

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

• Harry Buhrman
• Tuesday 26 November 2019, 16:00-17:00
• MR13, Centre for Mathematical Sciences, Wilberforce Road, Cambridge.

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.

This talk is included in these lists:

• All CMS events
• CMS Events
• CQIF Seminar
• DAMTP info aggregator
• Hanchen DaDaDash
• Interested Talks
• MR13, Centre for Mathematical Sciences, Wilberforce Road, Cambridge
• bld31

Note that ex-directory lists are not shown.