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 NP∩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 UPnot⊆BQP, then NPO∩coNPOnot⊆BQPO 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 NP∩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.
Related
- Classical-to-Quantum Transition in Blackbody Radiation Thermodynamics: Planck's Law without Statistical Assumptions
- Certifying quantum states without independence assumptions
- The Quantum Overlap Gap Property and Algorithmic Hardness for the Quantum Hypergraph Max-Cut Problem
- On Certifying Source Sampling Hardness in Quantum Generative Modeling
- Hardness of Approximating Quantum Code Distance Beyond √N
BibTeX
@misc{liang2026structured,
title = {{Structured Quantum Hardness from Unstructured Assumptions}},
author = {Xiao Liang and Takashi Yamakawa and Chak Fai Yung},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.07413},
eprint = {2611.07413},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.07413},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Structured Quantum Hardness from Unstructured Assumptions
AU - Xiao Liang
AU - Takashi Yamakawa
AU - Chak Fai Yung
PY - 2026
DA - 2026/11/05
PB - arXiv
DO - 10.48550/arxiv.2611.07413
UR - https://arxiv.org/abs/2611.07413
AB - Whether useful structured hardness can arise from unstructured assumptions is a fundamental question in complexity and cryptography. The longstanding Bennett-Gill question asks whether NP∩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 UPnot⊆BQP, then NP^O∩coNP^Onot⊆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 NP∩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.
ER -