|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'506'133
Articles rated: 2609
27 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
The Quantum Strong Exponential-Time Hypothesis | | Harry Buhrman
; Subhasree Patro
; Florian Speelman
; | | Date: |
13 Nov 2019 | | Abstract: | 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. | | Source: | arXiv, 1911.5686 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER