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 Category: research Comments: 0 Disputed: false Division: physics Mentions: 0 Discussed: 0 Published: 2026-11-05 Page: https://delphi.science/r/arxiv/2611.07413 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…