Quantum hardness separation extends Bennett-Gill question
Original title: Structured Quantum Hardness from Unstructured Assumptions
Conditional oracle separation shows structured quantum hardness can arise from unstructured assumptions.
The paper proves if UP is not contained in BQP then NP^O intersect coNP^O is not contained in BQP^O with probability 1 over random oracle. This extends classical results to quantum settings. It also rules out black-box reductions for worst-case quantum hardness.
Unconfirmed: Conditional on UP notsubseteq BQP
- Conditional separation under random oracle O
- Rules out black-box reductions to iO and OWF
- Evidence for non-black-box techniques needed
- Extends Bennett-Gill question to quantum
From the original article
1 min read at arxiv.orgWhether useful structured hardness can arise from unstructured assumptions is a fundamental question in complexity and cryptography. The longstanding Bennett-Gill question asks whether $\mathsf{NP}\cap\mathsf{coNP}$ remains hard relative to a random oracle; [GIKKLS, STOC 2023] recently gave a conditional affirmative answer in the classical setting.
By Xiao Liang · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.