Abstract

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.