# Structured Quantum Hardness from Unstructured Assumptions

DevFeed: [Structured Quantum Hardness from Unstructured Assumptions](<https://devfeed.tech/articles/structured-quantum-hardness-from-unstructured-assumptions-119913.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.07413>)

Author: Xiao Liang, Takashi Yamakawa, Chak Fai Yung

Published: 2026-11-06T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Cryptography and Security](<https://devfeed.tech/sources/arxiv-cryptography-and-security.md>)

Topics: [Quantum Computing](<https://devfeed.tech/topics/quantum-computing.md>), [Post-quantum cryptography](<https://devfeed.tech/topics/post-quantum-cryptography.md>), [Cryptography](<https://devfeed.tech/topics/cryptography.md>)

Tags: [2023](<https://devfeed.tech/tags/2023.md>), [abstract](<https://devfeed.tech/tags/abstract.md>), [algorithms](<https://devfeed.tech/tags/algorithms.md>), [analogue](<https://devfeed.tech/tags/analogue.md>), [arxiv](<https://devfeed.tech/tags/arxiv.md>), [black](<https://devfeed.tech/tags/black.md>), [box](<https://devfeed.tech/tags/box.md>), [can](<https://devfeed.tech/tags/can.md>), [canonical](<https://devfeed.tech/tags/canonical.md>), [certification](<https://devfeed.tech/tags/certification.md>), [class](<https://devfeed.tech/tags/class.md>), [complexity](<https://devfeed.tech/tags/complexity.md>), [conditional](<https://devfeed.tech/tags/conditional.md>), [cryptographic](<https://devfeed.tech/tags/cryptographic.md>), [cryptography](<https://devfeed.tech/tags/cryptography.md>), [cs-cc](<https://devfeed.tech/tags/cs-cc.md>), [cs-cr](<https://devfeed.tech/tags/cs-cr.md>), [essential](<https://devfeed.tech/tags/essential.md>), [first](<https://devfeed.tech/tags/first.md>), [functions](<https://devfeed.tech/tags/functions.md>), [quant-ph](<https://devfeed.tech/tags/quant-ph.md>), [quantum](<https://devfeed.tech/tags/quantum.md>), [structured](<https://devfeed.tech/tags/structured.md>)

## AI overview

Assuming \(\mathsf{UP}\not\subseteq\mathsf{BQP}\), the authors show that with probability 1 over a random oracle \(O\), \(\mathsf{NP}^{O}\cap\mathsf{coNP}^{O}\not\subseteq\mathsf{BQP}^{O}\). This is a quantum analogue of a classical conditional result and offers evidence that structured quantum hardness can arise from unstructured assumptions, despite the limitations of familiar number-theoretic and post-quantum assumptions for producing languages with two-sided classical certification on every input. The authors also rule out fully black-box quantum reductions from worst-case quantum hardness in \(\mathsf{NP}\cap\mathsf{coNP}\) to post-quantum injective one-way functions or indistinguishability obfuscation, ruling out a broad class of approaches and suggesting non-black-box techniques may be essential.

## Source excerpt

arXiv:2611.07413v1 Announce Type: cross 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.