技術要約：量子ペシランド (Quantum Pessiland)

1. 問題提起と動機

本論文は、Impagliazzo [Imp95] によって定義された古典的な「ペシランド (Pessiland)」に類似した理論的世界、すなわち「量子ペシランド」の存在について論じている。古典的なペシランドでは、NP に属する問題は平均的に困難であるが、一方向関数 (One-Way Functions; OWFs) は存在しない。ほとんどの古典的な暗号プリミティブは OWF を含意するため [IL89]、ペシランドは、平均的なケースでの困難な問題が存在するにもかかわらず、本質的に古典的な暗号が不可能な世界を表している。

量子領域における景観は異なる。近年の研究 [Kre21, MY22, AQY22] は、OWF が存在しない場合でも、より弱いプリミティブである 擬似乱数状態生成器 (Pseudorandom State Generators; PRSGs)、一方向状態生成器 (One-Way State Generators; OWSGs)、一方向パズル (One-Way Puzzles; OWPuzzs)、および EFI ペア (Extremely Far but Indistinguishable pairs) に依存することで、量子暗号（例：プライベートキー量子マネー、秘密鍵暗号、デジタル署名）が存在し得ることを示してきた。

提示されている中心的な問いは、「NP（または関連する部分集合）が平均的に困難であるが、これらより弱い量子暗号プリミティブさえも存在しない世界は存在するのか？」 ということである。もしそのような世界が存在するならば、それは量子暗号が単なる古典的暗号の緩和版ではなく、根本的に異なる困難性の仮定を必要としていること、あるいは量子暗号がある種の平均的なケースの困難な設定においては不可能であることを意味する。

2. 手法と技術的概要

著者らは、量子ペシランドの存在を証明するために、相対化された世界（オラクル分離）を構築している。彼らの手法は、ランダムな置換オラクルと PSPACE 完全なオラクルを用いた Wee [Wee06] による古典的なペシランドの構成を適応・拡張したものである。

2.1 オラクル構成

著者らは、結果が成立する相対的なオラクルを以下のように定義する：

• 古典的オラクル ($O$): 一様ランダムな置換族 $\pi = (\pi_1, \pi_2, \dots)$ に対する検証オラクル $V^\pi$ と、固定された PSPACE 完全なオラクル ($QBF$) で構成される。
  • $V^\pi(\ell, u, v) = 1$ （ただし $|u|=|v|=\ell$ かつ $\pi_\ell(u)=v$ の場合）、それ以外は $0$。
• 量子オラクル ($U$): EFI ペアの結果については、回路によって生成された量子状態を区別するための最適測定を行う ヘルストロム・オラクル (Helstrom oracle)（ユニタリ・オラクル）を、古典的オラクル $V$ と共に導入する。

2.2 中核となる課題：補助入力 (Auxiliary Inputs)

大きな技術的障壁は、補助入力を持つプリミティブを排除することである。古典的な設定において、Wee [Wee06] は、少数の「重い」クエリに対するオラクル値がハードワイヤリング（直接書き込み）されている場合、任意の多項式サイズの回路がオラクルフリーの回路によって近似できることを示すことで、補助入力を持つ OWF を排除した。しかし、この手法は量子設定においては以下の 2 点から失敗する：

1. 重ね合わせクエリ: 量子アルゴリズムは重ね合わせ状態でオラクルにクエリを投げるため、古典的な「重いクエリ」（古典的な入力の割合に基づくもの）という概念が定義不能になる。
2. 一様性と非一様性: 補助入力を持つ量子プリミティブは、無限の集合の困難な補助入力を受け取る 一様 な敵対者に対して定義される。非一様的な「ハードワイヤリング」戦略（アドバイス）だけでは不十分であり、必要な情報を学習する 一様 なアルゴリズムによって敵対者が打破されなければならない。

2.3 パッチング・レマ (Patching Lemma)（主要な技術的革新）

これらの障害を克服するために、著者らは パッチング・レマ (Patching Lemma)（定理 5.2）を導入する。このレマは、補助入力 $x$ が与えられたときに、「パッチ」$\Gamma$（トリプル $(\ell, u, v)$ の有限集合、ここで $V^\pi(\ell, u, v)=1$）を学習する一様な量子多項式時間 (QPT) 抽出器 $E$ を提供する。

• メカニズム: 抽出器は、ランダムなクエリまで敵対者アルゴリズム $A$ を実行し、クエリレジスタを測定し、古典的にオラクル $V^\pi$ をチェックする。もしクエリが「正（positive）」である場合（すなわち $V^\pi=1$）、それをパッチに追加する。
• 指数的モーメント境界: 単純な $2^n$ 個の全補助入力に対する和の境界（union bound）を用いる手法は失敗するが、「発見（パッチへの要素追加）」の数は、多くの発見を行う確率が指数関数的に小さい分布に従う。指数的モーメント (exponential moment) を境界付けることで、著者らは、最悪の入力に対しても、発見の期待値が入力長に対して線形 ($O(n)$) であることを示す。これにより、ランダムな置換 $\pi$ の選択に関する確率 1 において、すべての入力に対して同時に識別不能性を維持しながら、パッチを多項式サイズに保つことが可能となる。

2.4 困難性の証明

• 平均的なケースの困難性: 量子アドバイスを持つ量子置換反転に関する最新のタイトな境界 [ABC+26] と Goldreich-Levin 定理 [KT24, AC02] を組み合わせ、置換を反転させること（または関連する探索問題を解くこと）が、量子アドバイスを持つ QPT アルゴリズムに対しても依然として困難であることを示す。
• プリミティブの非存在: パッチング・レマを用いて、任意の補助入力を持つ OWPuzz または EFI ペアは、オラクルフリーのバージョン（または PSPACE/ヘルストロム・オラクルのみを使用するバージョン）へと「パッチ」できることを示す。PSPACE/ヘルストロム・オラクルは効率的な反転や区別を可能にするため、元のプリミティブは打破される。

3. 主要な結果

本論文は、量子ペシランドの存在に関して 2 つの主要な定理を確立している。

定理 1.1 (古典的オラクル)

以下の性質を満たす古典的オラクル $O$ が存在する：

1. 困難性: $UP^O \cap coUP^O$ に属する言語 $L_O$ が、多項式サイズのオラクル依存量子アドバイスを持つ QPT アルゴリズムに対して、平均的に強く困難である。（したがって、$NP \cap coNP$ もまた困難である。）
2. 探索の困難性: $TFUP^O$ に属する全単射な一意の探索関係 $R_O$ が、同様のクラスのアルゴリズムに対して平均的に困難である。
3. 量子的優位性の欠如: $SampBQP^O = SampBPP^O$ である。したがって、サンプリングに基づく量子的優位性は存在しない。
4. 暗号の不在: 古典的に安全な補助入力型の一方向パズル (OWPuzzs) は存在しない。

定理 1.2 (量子オラクル)

量子ユニタリ・オラクル $U$ および古典的オラクル $V$ が存在し、これらに関して以下が成立する：

1. 困難性: $L_V \in UP^V \cap coUP^V$ および関係 $R_V \in TFUP^V$ は、量子アドバイスを持つ QPT アルゴリズムに対して平均的に困難である。
2. 暗号の不在: 補助入力を持つ EFI ペアは存在しない。

系

• 系 1.3: 古典的オラクルに関して、$PP$ は量子アドバイスを持つ QPT に対して平均的に強く困難である。これは $P^{\#P} \not\subseteq_{i.o.} BQP/qpoly$ である。
• 系 1.4: 古典的オラクルに関して、$UP \cap coUP$ の平均的なケースの困難性にもかかわらず、非効率な検証者による量子性の証明 (Inefficient-Verifier Proofs of Quantumness; IV-PoQ) は存在しない。

4. 意義と影響

本論文は、以下の意義を主張している：

1. 量子ペシランドの存在: 平均的なケースの困難性（具体的には $UP \cap coNP$ に関して）が存在する一方で、量子暗号（OWPuzzs および EFI ペアの古典的安全および量子的安全の両方のバリエーション）が一切不可能である世界が存在することを証明している。これは、OWF の非存在がすべての古典的暗号の非存在を意味する古典的なケースとは対照的である。ここでは、$UP \cap coUP$ が困難であるにもかかわらず、量子プリミティブの非存在が示されている。
2. 量子的優位性の限界: この世界における $SampBQP = SampBPP$という結果は、$UP \cap coUP$ の平均的なケースの困難性だけでは、サンプリングに基づく量子的優位性を保証するには不十分であることを示している。
3. 手法の分離: 本論文は、$P^{\#P} \not\subseteq_{i.o.} BQP/qpoly$ から OWPuzz を構築するという未解決問題に取り組んでいる。OWPuzzs がこの複雑性理論的仮定が成立しているにもかかわらず、彼らのオラクル世界では存在しないことから、著者らは、OWPuzzs を構築するためには 非相対化された証明手法 が必要であると結論付けている。これは、Khurana および Tomer [KT25] によって提起された未解決問題に対する部分的な否定的な回答を与えている。
4. 技術的進展: パッチング・レマは、重ね合わせクエリが存在する状況下で、補助入力を伴う一様（uniform）な敵対者を扱うために特別に設計された、Wee の近似レマの一様な量子版として提示されている。

著者らは、自らの結果はオラクルに関するものであり、現実（非相対化された世界）においてそのような世界が存在するかどうかという問いを解決するものではないと述べ、謙虚な姿勢を維持している。彼らは、本研究が、相対化された設定における平均的なケースの困難性と量子暗号プリミティブの存在との間の分離を明確にすることを目的としていると強調している。