2026-07-23T05:51:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13664 2024-03-06T10:52:36Z ddc:004 open_access

A Framework of Quantum Strong Exponential-Time Hypotheses Buhrman, Harry Patro, Subhasree Speelman, Florian complexity theory fine-grained complexity longest common subsequence edit distance quantum query complexity strong exponential-time hypothesis 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 Ω(n^1.5) for the Longest Common Subsequence and Edit Distance problems. We also show that the n² 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Harry Buhrman and Subhasree Patro and Florian Speelman 2021 Is Part Of LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2021.19 urn:nbn:de:0030-drops-136642 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.19 eng https://creativecommons.org/licenses/by/4.0/legalcode