論文の概要: Structured Quantum Hardness from Unstructured Assumptions

• arxiv url: http://arxiv.org/abs/2611.07413v1
• Date: Thu, 05 Nov 2026 04:08:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-06 21:50:50.543251
• Title: Structured Quantum Hardness from Unstructured Assumptions
• Title（参考訳）: 非構造的仮定からの構造化量子硬度
• Abstract要約: 長年続いたベネット=ギルの質問は、$mathsfNPcapmathsfcoNP$がランダムなオラクルに対して難しいままであるかどうかを問うものである。 量子アナログを確立する:$mathsfUPnotsubseteqmathsfBQP$, then $mathsfNPOcapmathsfNPOnotsubseteqmathsfBQPO$。
• 参考スコア（独自算出の注目度）: 8.670798659615388
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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.
• Abstract（参考訳）: 構造化されていない仮定から有用な構造化硬度が生じるかどうかは、複雑さと暗号の基本的な問題である。 長年続いたベネット=ギルの質問は、$\mathsf{NP}\cap\mathsf{coNP}$がランダムなオラクルに対して難しいままであるかどうかを問うものである。 量子アナログが成立する: if $\mathsf{UP}\not\subseteq\mathsf{BQP}$, then $\mathsf{NP}^{O}\cap\mathsf{coNP}^{O}\not\subseteq\mathsf{BQP}^{O}$。 ショアのアルゴリズムは正準数理論的硬さ候補を破り、格子仮定やその他の主要な量子後暗号仮定は、全ての入力に対して2面の古典的認証を持つハード言語を直接供給しない。 我々の条件付きオラクル分離は、そのような構造化された量子硬さは、それでも非構造的な源から生じうるという証拠を提供する。 この結果の補足として、$\mathsf{NP}\cap\mathsf{coNP}$における最悪の量子硬さの完全なブラックボックス量子還元を、量子後射出片方向関数と区別不能な難読化のために除外する。 この障壁は、構造化された量子硬度を一般的な暗号プリミティブから導き出すための幅広い種類のブラックボックスアプローチを除外し、最初の結果における非ブラックボックス手法が不可欠であることを示す部分的な証拠を提供する。

関連論文リスト

• Verifiable quantum advantage in extremely low depth [52.51019642214249]
  浅量子回路では解けない問題を格子ベースの仮定で解くのが困難である。 浅量子回路は、解を効率よく検証できる古典的な難題を解くのに十分な構造を持っていることを証明している。
  論文  参考訳（メタデータ） (2026-09-01T15:54:34Z)
• On the Cryptographic Futility of Non-Collapsing Measurements [13.234610219099102]
  衝突抵抗の量子アナログを調査し, 衝突抵抗のプリミティブと量子ワンウェイの分離を求める。
  論文  参考訳（メタデータ） (2025-10-06T17:36:22Z)
• Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy [0.7321157455672144]
  証明に特有の量子古典的PCPの制限は、そのパワーを低下させるものではないことを示す。 また、カルプ・リプトンの定理の非一様量子類似性も証明する。 これらの結果は、量子証明システムの構造に関する新たな洞察を与える。
  論文  参考訳（メタデータ） (2025-06-24T16:59:50Z)
• Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from $\mathsf{\#P}$-Hardness [10.438299411521099]
  近年の分離により、階層構造が崩壊しても持続する硬さの源から量子暗号を構築する可能性が高まっている。 量子暗号は、$mathsfP#P notsubseteq mathsf(io)BQP/qpoly$という非常に穏やかな仮定に基づいている。
  論文  参考訳（メタデータ） (2024-09-23T17:45:33Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。 特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
  論文  参考訳（メタデータ） (2024-02-29T01:35:46Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  浅量子回路の計算能力と古典計算の組合せを包括的に評価する。 いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
  論文  参考訳（メタデータ） (2022-10-12T17:54:02Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。 本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
  論文  参考訳（メタデータ） (2021-07-05T17:45:41Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。