Paper Info
Title
A Framework Of Quantum Strong Exponential-Time Hypotheses
Abstract
The strong exponential-time hypothesis (SETH) is a commonly used conjecture in the field of complexity theory. It essentially states that determining whether a CNF formula is satisfiable can not be done faster than exhaustive search over all possible assignments. 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 very likely beyond current techniques. In this work, we introduce an extensive framework of Quantum Strong Exponential-Time Hypotheses, as quantum analogues to what SETH is for classical computation.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 P. As an example, we provide a conditional quantum time lower bound of Omega(n(1.5)) for the Longest Common Subsequence and Edit Distance problems. We also show that the n(2) SETH-based lower bound for a recent scheme for Proofs of Useful Work carries over to the quantum setting using our framework, maintaining a quadratic gap between verifier and prover.Lastly, we show that the assumptions in our framework can not be simplified further with relativizing proof techniques, as they are false in relativized worlds.
Year
DOI
Venue
2021
10.4230/LIPIcs.STACS.2021.19
38TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2021)
Keywords
DocType
Volume
complexity theory, fine-grained complexity, longest common subsequence, edit distance, quantum query complexity, strong exponential-time hypothesis
Conference
187
ISSN
Citations 
PageRank 
1868-8969
0
0.34
References 
Authors
0
3
Name
Order
Citations
PageRank
Harry Buhrman11607117.99
Subhasree Patro200.34
Florian Speelman3445.61