Paper 2026/2780

Structured Quantum Hardness from Unstructured Assumptions

Abstract

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 separation has a distinctly quantum significance: Shor’s algorithms defeat canonical number-theoretic hardness candidates, while lattice assumptions and other leading post-quantum cryptographic assumptions do not directly supply hard languages with two-sided classical certification on every input. Our conditional oracle separation provides evidence that such structured quantum hardness can nevertheless arise from unstructured sources. Complementing this result, we rule out fully black-box quantum reductions of worst-case quantum hardness in $\mathsf{NP}\cap\mathsf{coNP}$ to post-quantum injective one-way functions and indistinguishability obfuscation. This barrier excludes a broad class of black-box approaches to deriving structured quantum hardness from generic cryptographic primitives, providing partial evidence that the non-black-box techniques in our first result are essential.