Unitary complexity in polynomial space

技術要約：多項式空間におけるユニタリ複雑性

問題提起
本論文は、量子暗号プリミティブ、特に量子コミットメント・スキームの基礎的な複雑性と、古典的な計算複雑性理論との関係について論じている。古典的な暗号理論は $P \neq NP$ という困難性の仮定に依存しているが、近年のオラクル分離の研究は、たとえ $P = NP$ であっても量子暗号が存在し得る可能性を示唆している。これは、量子コミットメントを量子暗号の最小プリミティブと見なす「マイクロクリプト（Microcrypt）」パラダイムへとつながっている。しかし、これらのコミットメントの背後にある計算量理論的な困難性は依然として不明である。

中心的な未解決問題は、ユニタリ合成問題（Aharonov and Knill, 2007によって提起）である。すなわち、古典的なオラクルへのアクセスが与えられたとき、任意の $n$ 量子ビット・ユニタリ変換 $U$ を実装できる多項式時間の量子アルゴリズムは存在するか？ 正の解決が得られれば、ユニタリ実装に関する超多項式の下界が、古典的関数の超多項式的な困難性を意味することになる。逆に、負の解決が得られたとしても、それが特定の暗号スキームの困難性に直接的な情報をもたらすわけではない。

著者らは、古典的な複雑性理論の手法を用いて、unitaryPSPACE（多項式空間で実装可能なユニタリ）の計算量的な困難さを調査することを目的としている。具体的には、ユニタリ複雑性クラス、ユニタリ合成問題、および古典的な下界の関係を調査する。

手法と定義
本論文では、まず既存のユニタリ複雑性クラスの定義（特に Bostanci et al. [BEMPQY26] および Zhandry [Zha25] によるもの）における重大な概念的欠陥を特定している。主な問題点は以下の通りである：

1. 誤差のスケーリング： 従来の定義は、誤差に対して $1/\epsilon$（誤差の逆多項式）でスケールしており、これが合成における病理的な挙動（例：自己低複雑性（self-lowness）の失敗）を引き起こし、位相エンコーディングを通じて困難な問題を低複雑性クラスへ「密輸」することを許してしまう。
2. ゴミ（Garbage）の処理： 定義によって、実装がアンシラ量子ビットを $|0\rangle$ 状態に戻さなければならない（ゴミなし）とするか、あるいは任意のゴミ状態を許容するか（プロジェクト的）が異なっている。

これらを解決するため、著者らは第一原理に基づき、unitaryP および unitaryPSPACE のための新しい厳密な定義を提案する：

• 誤差のスケーリング： 複雑性は $1/\epsilon$ ではなく $\log(1/\epsilon)$ に対して多項式的にスケールしなければならない。これにより、合成に対する堅牢性とソロヴェイ・キタエフ（Solovay-Kitaev）定理との整合性が確保される。
• ゴミなし vs プロジェクティブ（投影的）： 著者らは2つのクラスを定義する：
  • unitaryP/unitaryPSPACE： 実装は「クリーン」である必要があり（アンシラが $|0\rangle$ にリセットされる）、グローバル位相を保存しなければならない。
  • projUnitaryP/projUnitaryPSPACE： 実装はゴミ（アンシラが $|g\rangle$ 状態）を生成してもよく、実質的にグローバル位相を無視する（射影的ユニタリ群）。
• オラクルアクセス： オラクルは、あるユニタリ $U$ とそのホモモルフィズム（$U^\dagger, U^*, U^T$, および制御版）へのアクセスを提供し、これにより合成可能性を保証する。

主要な貢献と結果

1. 定義の等価性（時間および空間）：

   • 著者らは、「クリーン」な定義と「ゴミ」の定義が深く関連していることを証明する。具体的には、$U \in \text{projUnitaryP}$ であることの必要十分条件は $U \otimes U^\dagger \in \text{unitaryP}$ であることである。
   • 極めて重要な点として、多項式空間に関して、彼らはより強力な結果を証明している：unitaryPSPACEは汎用的にゴミを除去できる。すなわち、すべての $U \in \text{projUnitaryPSPACE}$ に対して、$U = \phi V$（ここで $\phi$ はグローバル位相）を満たす $V \in \text{unitaryPSPACE}$ が存在することを示す。これは、ユニタリPSPACEを行列成分の計算可能性によって特徴付けることで達成される。つまり、あるユニタリが $\text{unitaryPSPACE}$ に属するための必要十分条件は、その成分を任意の精度で多項式空間内で近似できることである。
   • 対照： このゴミ除去の性質は、ユニタリ・オラクルに対しては成立しない。そこでは、トポロジカルな障害により、グローバル位相の連続的な割り当てが妨げられるためである。

2. 主要な二分法（Lemma 1.2 / Lemma 7.4）：
   本論文は、任意の $U \in \text{unitaryPSPACE}$ に対して以下の根本的な二分法を確立している：

   • $U$ がユニタリ合成困難である（すなわち、$U \notin \text{unitaryP}^{\text{ALL}}$、つまりいかなる古典的オラクルに対しても効率的に合成できない）。
   • あるいは、$U$ がNEXP探索問題に効率的に還元される（すなわち、$U \in \text{unitaryP}^{\text{FNEXP}}$、ここで $\text{FNEXP}$ はNEXP問題の証拠へのアクセスを表す）。

3. 暗号学および複雑性理論への含意：

   • 定理 1.1： もし量子コミットメント（EFIペアと同等）が存在するならば、ユニタリ合成問題に多項式時間の解が存在しないか、あるいは $\text{BPP} \neq \text{NEXP}$ である。
   • これは、量子コミットメントの存在に関する無条件の証明には、少なくとも以下の2つの長年の未解決問題のいずれかを解決する必要があることを意味する：ユニタリ合成問題（20年以上の未解決問題）、または $\text{BPP}$ と $\text{NEXP}$ の分離（40年以上の未解決問題）。
   • 系 7.10： もし $\text{unitaryP}^L_{\text{PSPACE}} \neq \text{unitaryPSPACE}^L$ となるような古典的オラクル $L$ が存在するならば、ユニタリ合成問題が偽である（$\text{unitaryP}^{\text{ALL}} \neq \text{unitaryALL}$）か、あるいは $\text{NC} \neq \text{NP}$ である。これは、そのようなオラクルの構築がなぜ困難であったかを説明している。

意義
本論文は、自らの定義が誤差のスケーリングとゴミに関する一貫性を解決し、ユニタリ複雑性理論の「堅牢」かつ「エレガント」な基礎を提供するものであると主張している。行列成分による $\text{unitaryPSPACE}$ の特徴付けを確立することで、著者らは、空間制限のあるユニタリ計算が古典的な複雑性クラスと密接に結びついていることを示している。

主要な意義は、量子暗号、ユニタリ合成、および古典的な下界の間の架け橋となる点にある。著者らは、量子コミットメントの存在は古典的な複雑性理論から孤立した問題ではないと論じている。むしろ、その存在を無条件に証明することは、古典的な複雑性理論における深いブレイクスルー（特に $\text{BPP}$ と $\text{NEXP}$ の分離、またはユニタリ合成問題の解決）を必要とする。この研究は、「マイクロクリプト」を完全に理解するには、これらの深い複雑性理論的な問いに対処しなければならないことを示唆している。

最後に、論文は、多項式空間においてはゴミの除去が可能であるが、多項式時間においても可能か（すなわち、$\text{unitaryP} = \text{projUnitaryP}$ か？）という問いは、ユニタリ・オラクルに対しては負の回答を示しているものの、依然として未解決であることを述べて締めくくっている。