論文の概要: Quantum Pessiland
- arxiv url: http://arxiv.org/abs/2608.29493v1
- Date: Sun, 30 Aug 2026 01:04:52 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-01 18:31:30.983104
- Title: Quantum Pessiland
- Title（参考訳）: 量子ペシランド
- Abstract要約: ペシランド(Pessiland)は、NPが平均的に困難であるが一方関数(OWF)が存在しない世界である。
このような悲惨な世界、Quantum Pessilandが存在することを示す。
- 参考スコア（独自算出の注目度）: 12.90382979353427
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Pessiland is a world where NP is hard on average but one-way functions (OWFs) do not exist [Impagliazzo 1995]. Because almost all classical cryptographic primitives imply OWFs [Impagliazzo and Luby 1989], there is almost no classical cryptography in Pessiland. On the other hand, quantum cryptography can exist even when OWFs do not [Kretschmer 2021; Morimae and Yamakawa 2022; Ananth, Qian and Yuen 2022]. Is there a quantum analogue of Pessiland where NP is hard on average but even quantum cryptography does not exist? In this paper, we show that such a miserable world, Quantum Pessiland, exists: there is a quantum oracle relative to which $UP\cap coUP$ is hard on average against quantum polynomial-time algorithms with quantum advice, yet auxiliary-input EFI pairs do not exist. We also show that there is a classical oracle relative to which $UP\cap coUP$ is hard on average against quantum polynomial-time algorithms with quantum advice, yet classically-secure auxiliary-input one-way puzzles (OWPuzzs) do not exist. Almost all quantum cryptographic primitives imply EFI pairs or OWPuzzs, and therefore these results mean that there is almost no quantum cryptography relative to these oracles. We further show that relative to the classical oracle, SampBQP = SampBPP, and therefore there is no sampling-based quantum advantage in Quantum Pessiland. Finally, because our average-case hardness of $UP\cap coUP$ implies $P^{\#P}\not\subseteq i.o.BQP/qpoly$, our result also implies that a non-relativizing proof technique is necessary to construct OWPuzzs solely from $P^{\#P}\not\subseteq i.o.BQP/qpoly$, which gives a partial negative answer to the open problem of [Khurana and Tomer 2025].
- Abstract（参考訳）: ペシランドはNPが平均的に難しいが一方的関数(OWF)が存在しない世界である[Impagliazzo 1995]。
古典暗号プリミティブのほとんど全てがOWF(Impagliazzo と Luby 1989)を暗示しているので、ペシランドには古典暗号はほとんど存在しない。
一方、OWFが存在しない場合でも量子暗号が存在する(Kretschmer 2021, Morimae and Yamakawa 2022, Ananth, Qian and Yuen 2022]。
NPが平均的に難しいが量子暗号でさえ存在しないペシランドの量子アナログが存在するだろうか。
本稿では、量子的アドバイスを伴う量子多項式時間アルゴリズムに対して$UP\cap coUP$が平均的に難しい量子オラクルが存在するが、補助入力EFIペアは存在しないことを示す。
また、量子アドバイスを持つ量子多項式時間アルゴリズムに対して、$UP\cap coUP$が平均的に難しい古典的なオラクルが存在するが、古典的に安全な補助入力ワンウェイパズル(OWPuzzs)は存在しないことを示す。
ほぼ全ての量子暗号プリミティブは、EFI対またはOWPuzzを暗示しているので、これらの結果は、これらのオラクルに対して量子暗号がほとんど存在しないことを意味する。
さらに、古典的なオラクルと比較して、SampBQP = SampBPP であるため、量子ペシランドにおいてサンプリングベースの量子優位性は存在しないことを示す。
最後に、UP\cap coUP$の平均ケース硬さは$P^{\#P}\not\subseteq i.o.BQP/qpoly$であるので、この結果は、[Khurana and Tomer 2025] の開問題に対して部分的な負の答えを与える$P^{\#P}\not\subseteq i.o.BQP/qpoly$からのみOWPuzzsを構築するために非相対化証明技術が必要であることを示唆している。
関連論文リスト
- Verifiable quantum advantage in extremely low depth [52.51019642214249]
浅量子回路では解けない問題を格子ベースの仮定で解くのが困難である。
浅量子回路は、解を効率よく検証できる古典的な難題を解くのに十分な構造を持っていることを証明している。
論文 参考訳（メタデータ） (2026-09-01T15:54:34Z) - Pseudoentanglement in constant depth: How trivial states can have non-trivial entanglement structure [52.51019642214249]
我々は,カットのエントロピーを量子時間で推定できない2次元局所定数深さ量子回路の族を構築する。
定深量子回路は特定の多くの量子サンプルから学習できるので、結果として得られる擬似絡み状態は暗黙的に公鍵であり、擬似ランダムではない。
論文 参考訳（メタデータ） (2026-05-29T15:43:00Z) - Quantum Cryptography and Hardness of Non-Collapsing Measurements [10.237675529033163]
ワンウェイパズル (OWPuzzs) はワンウェイ関数 (OWFs) の量子アナログである。
本稿では,非折り畳み測定の硬さに基づくOWPuzzsについて述べる。
我々は、新しい原始的、分布的衝突耐性パズル(dCRPuzzs)を導入する。
論文 参考訳（メタデータ） (2025-10-06T02:42:20Z) - From Worst-Case Hardness of $\mathsf{NP}$ to Quantum Cryptography via Quantum Indistinguishability Obfuscation [8.093227427119325]
Indistinguishability obfuscation (iO) は多くの意味を持つ強力な暗号プリミティブとして登場した。
本研究では、量子iOのパワーの研究を開始する。
論文 参考訳（メタデータ） (2025-06-24T11:50:33Z) - Quantum-Computable One-Way Functions without One-Way Functions [0.6349503549199401]
古典的なオラクルを構築し、$mathsfP = MathsfNP$, but quantum-computable quantum-secure trapdoor one-way function が存在する。
この結果から,複数コピーの擬似乱数状態と擬似乱数ユニタリー,古典通信の公開鍵暗号,シグネチャ,暗黙の転送方式が示唆された。
論文 参考訳（メタデータ） (2024-11-04T19:40:01Z) - Quantum Cryptography and Meta-Complexity [2.6089354079273512]
古典暗号では、ワンウェイ関数(OWF)は最小の仮定であるが、量子暗号ではそうではない。
片方向パズル(OWPuzzs)がGapKが弱量子平均ハードである場合にのみ存在することを示す。
また、量子PRGが存在する場合、GapKは量子平均ハードであることを示す。
論文 参考訳（メタデータ） (2024-10-02T09:30:06Z) - 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) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳（メタデータ） (2020-04-14T11:05:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。