{"id":"arxiv/2611.07413","url":"https://arxiv.org/abs/2611.07413","tags":["quant-ph","cs.CC","cs.CR"],"score":0,"title":"Structured Quantum Hardness from Unstructured Assumptions","domain":"quant-ph","source":"arxiv","authors":["Xiao Liang","Takashi Yamakawa","Chak Fai Yung"],"reviews":0,"subject":"quant-ph","summary":"Whether 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. We establish the quantum analogue: if $\\mathsf{UP}\\not\\subseteq\\mathsf{BQP}$, then $\\mathsf{NP}^{O}\\cap\\mathsf{coNP}^{O}\\not\\subseteq\\mathsf{BQP}^{O}$ with probability $1$ over a random oracle $O$. Beyond extending the classical result, this…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-11-05","reactions":{}}