  The strong exponential-time hypothesis (SETH) is a commonly used conjecture
in the field of 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 field of research,
fine-grained complexity, obtaining (mostly tight) lower bounds for many
problems in P whose unconditional lower bounds are hard to find. In this work,
we introduce a framework of Quantum Strong Exponential-Time Hypotheses, as
quantum analogues to SETH.
  Using the QSETH framework, we are able to translate quantum query lower
bounds on black-box problems to conditional quantum time lower bounds for many
problems in BQP. As an example, we illustrate the use of the QSETH by providing
a conditional quantum time lower bound of $\Omega(n^{1.5})$ for the Edit
Distance problem. We also show that the $n^2$ SETH-based lower bound for a
recent scheme for Proofs of Useful Work, based on the Orthogonal Vectors
problem holds for quantum computation assuming QSETH, maintaining a quadratic
gap between verifier and prover.
