Exponential Advantage of Multipartite Entanglement over Quantum Communication with Applications to Bounded-Storage Cryptography

技術要約：多部構成もつれによる指数関数的な優位性と量子通信

問題提起
二部構成（bipartite）の量子もつれによる通信上の優位性は確立されているが、分散情報処理における多部構成（multipartite）のもつれの計算能力については、まだ十分に理解されていない。中心的な未解決問題は、多部構成のもつれのみによって、事前共有の量子通信がない設定で見られるものと同等の、通信タスクにおける指数関数的な優位性を提供できるかどうかである。具体的には、本論文は、多部構成のもつれによって補助された古典通信が、事前共有のもつれを欠いた無制限の量子通信を上回ることができるかどうかを調査している。

手法
著者らは、新しい多部構成の一方向通信タスクである多部構成隠れマッチング（$mHM_n$）、およびそのブール決定変種である**多部構成ブール隠れマッチング（$mBHM_n$）**を導入する。

• 設定: タスクは、$m$ 個の空間的に分離された送信者（アリスたち）と、単一の受信者（ボブ）で構成される。各アリスは入力文字列 $x_r \in \{0, 1\}^n$ を受け取る。ボブはマッチング $M$（$\{1, \dots, n\}$ からの互いに素なペアの集合）を受け取る。
• 目標: ボブは、マッチングのエッジ $(i_\ell, j_\ell) \in M$ に対して、$(i_\ell, j_\lor, \bigoplus_{r=1}^m (x_r^{i_\ell} \oplus x_r^{j_\ell}))$ というトリプルを出力しなければならない。ブール変種では、入力のパリティに関する約束（promise）に基づき、特定のビット $b$ を決定しなければならない。
• 比較されるモデル: 著者らは、以下のモデルにおける通信複雑性を分析する。
  1. 共有グローバルランダムネス（GSR）を伴う古典通信（$C_{\parallel, GSR}$）。
  2. 真の多部構成もつれによって補助された古典通信（$C_{\parallel, GEnt}$）。
  3. 事前共有のもつれを欠いた量子通信（$Q_{\parallel, GSR}$）。
  4. 送信者と受信者の間の二部構成もつれを伴う量子通信。

主要な貢献と結果

1. 多部構成もつれによる指数関数的な優位性:
   すべての当事者がグリーンバーガー＝ホーン＝ツァイリンガー（GHZ）状態を共有している場合、$mHM_n$ および $mBHM_n$ タスクは、各送信者から $O(\log n)$ ビットの古典通信で解決できることを著者らは示している。

   • メカニズム: 送信者は、自身の入力に基づいて、自身が持つGHZ状態のシェアに対して局所的なユニタリ位相符号化を適用する。その後、フーリエ基底で測定を行い、対数サイズの測定結果をボブに送信する。ボブは特定のユニタリ補正と測定を行うことで、要求されたグローバルなパリティを決定論的に復元する。
   • 備考: このプロトコルは「忘却的（oblivious）」である。つまり、ボブはマッチングエッジにおける入力のグローバルなパリティのみを知ることができ、単一の送信者または $m-1$ 個の送信者のサブセットの個別の入力に関する情報は得られない。

2. 事前共有もつれがない場合の低次境界（Lower Bounds）:
   対照的に、事前共有のもつれがない場合、高い成功確率を達成するいかなるプロトコルも、少なくとも一つの送信者から $\Omega(\sqrt{n})$ の通信を必要とすることを著者らは証明している。

   • この下限は、送信者がボブに対して**無制限の量子メッセージ（量子ビット）**を送信できる場合であっても、事前にエンタングルメントを共有していない限り成立する。
   • この証明は、二部構成の隠れマッチング問題として知られている下限を利用し、それを多部構成の設定へと拡張したものである。

3. 分離（The Separation）:
   もつれを用いた場合の（上界）$O(\log n)$ と、もつれを用いない場合の（下限）$\Omega(\sqrt{n})$ を組み合わせることで、指数関数的な分離が確立される。これは、多部構成のもつれによって補助された古典通信が、事前共有のもつれを欠いた無制限の量子通信よりも指数関数的に強力であることを証明している。

4. 暗号学的応用：有界ストレージ暗号学:
   この通信プロトコルは、弱い乱数源に対する**シード付き二源乱数抽出器（$Ext_2$）**を構築するために適用される。

   • 非エンタングルなサイド情報: 抽出器を侵害する（すなわち、出力を一様分布から区別する）ために、非エンタングルな量子サイド情報を持つ攻撃者は、多項式サイズの量子メモリ（$O(\sqrt{n})$）を必要とする。
   • エンタングルなサイド情報: もし攻撃者が少量の事前共有もつれ（具体的には、各ソースに対して $O(\log n)$ 量子ビットの二つのエンタングル状態）を保有している場合、彼らは抽出器を侵害することができる。
   • 結果: これは、有界ストレージ暗号学の文脈において、エンタングルな量子サイド情報と非エンタングルな量子サイド情報の間の、力の指数関数的な分離を確立している。

意義と主張
本論文は、多部構成のもつれを、量子通信単体よりも厳密に強力な情報処理リソースとして特定していると主張している。

• 通信複雑性: 多部構成の設定において、もつれを伴う古典通信が、もつれを欠いた量子通信を上回る最初の指数関数的な分離を示した。これは、多部構成のもつれが単なる量子通信の代替物ではなく、それを厳密に強化できるリソースであることを示している。
• 暗号学: 本研究は、量子攻撃者に対するセキュリティの質的な違いを明らかにしている。非エンタングルな量子メモリを持つ攻撃者に対するセキュリティ保証は、たとえ少量の事前共有もつれを持つ攻撃者に対しては必ずしも成立しないことを示している。
• 範囲: 著者らは、自らの暗号学的構成を最適化された抽出器ではなく、主にこの根本的な分離を示すための「原理証明（proof-of-principle）」として位置づけている。彼らは、この構成が抽出パラメータに対して最適化されているわけではないものの、エンタングルなサイド情報に対する脆弱性を浮き彫りにすることには成功していると述べている。

結論として、著者らは、多部構成のもつれを、非局所的な相関の生成を超えた計算リソースとして捉えるべきであると示唆しており、インタラクティブなモデル、ノイズのある設定、およびプライバシー増幅のような他の暗号プリミティブへの研究の方向性を提示している。