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$ を受け取る。受信者（ボブ）は、集合 $[n]$ 上の完全マッチング $M$（またはブール版の場合は部分 $1/4$-マッチング）を受け取る。
• 目標: ボブは、マッチングからエッジ $(i_\ell, j_\ell)$ を出力すると同時に、全送信者にわたる対応するビットのグローバルなパリティ $\bigoplus_{r=1}^m (x_{r, i_\ell} \oplus x_{r, j_\ell})$ を出力しなければならない。
• 比較されるモデル: 本研究では、以下のリソースモデルの下での通信複雑性を比較している：
  1. 真のマルチパーティ・エンタングルメント（GHZ状態）を事前共有した古典通信。
  2. 事前共有されたエンタングルメントを持たない、無制限の量子通信。
  3. 共有乱数を用いた古典通信。
• 解析ツール:
  • 上界の構成: $(m+1)$-パーティGHZ状態を利用したプロトコル。送信者は局所的なユニタリ・フェーズ符号化を自身の入力に基づいて適用し、フーリエ基底で測定した後、古典的な結果をボブに送る。
  • 下界の証明: 著者らは、二部グラフのヒドゥン・マッチングの下界の手法を適応・拡張している。エンタングルメントのない量子ケースについては、出力分布と一様分布の識別可能性を分析するために、行列値関数に対するハイパーコントラクティブ不等式（Kahn-Kalai-Linial不等式の一般化）を用いている。

主な貢献と結果

1. 通信複雑性における指数関数的な分離:

   • マルチパーティ・エンタングルメントがある場合: 著者らは、送信者と受信者がGHZ状態を共有している場合、各送信者から $O(\log n)$ ビット の古典通信によってタスクが解決できることを示している。このプロトコルは、局所的な入力を符号化し、受信者でグローバルなパリティを復元するために、マルチパーティのフェーズ相関を利用する。
   • 事前共有されたエンタングルメントがない場合: 対照的に、事前共有されたエンタングルメントなしで高い成功確率を達成するいかなるプロトコルも、たとえ無制限の量子通信が許容されるとしても、少なくとも一つの送信者から $\Omega(\sqrt{n})$ 量子ビットの通信を必要とする。
   • 結果: これにより、マルチパーティ・エンタングルメントによって補助された古典通信と、補助なしの量子通信との間の指数関数的な分離が確立される。特筆すべきは、送信者が受信者と二部グラフ・エンタングルメントを共有していても、送信者間で「真の」マルチパーティ・エンタングルメントを共有していない限り、この下界が保持される点である。

2. 有界ストレージ暗号への応用:

   • 著者らは、マルチパーティ・ヒドゥン・マッチング問題に基づいた**シード付き二源乱数抽出器（seeded two-source randomness extractor）**を構築している。この抽出器は、2つの独立した弱い乱源と公開シード（マッチング）を取り込み、準一様な出力を生成する。
   • 非エンタングル型アドバーサリに対する安全性: この抽出器は、エンタングルメントのない量子サイド情報を持つアドバーサリに対して安全であり、そのメモリサイズは $\sqrt{n}$ の多項式である。
   • エンタングル型アドバーサリに対する脆弱性: もしアドバーサリが少量の事前共有エンタングルメント（具体的には、ソースあたり $O(\log n)$ 量子ビットのエンタングルド・メモリ）を保有している場合、抽出器は侵害される可能性がある。
   • 結果: これは、エンタングルメントのない量子サイド情報と、エンタングルメントのあるサイド情報の間の、指数関数的な力の差を明らかにしている。抽出器を破るには、多項式サイズの非エンタングル型メモリが必要であるが、エンタングル型メモリであれば指数関数的に小さいメモリで済む。

意義と主張
本論文は、マルチパーティ・エンタングルメントを、量子通信単体よりも厳密に強力な情報処理リソースとして位置づけている。

• 通信領域: 本研究は、事前共有されたGHZエンタングルメントが、単なる量子通信の代替物ではなく、そのようなリソースなしでは達成できない指数関数的な節約を可能にすることを実証している。
• 暗号領域: 著者らの知見は、有界ストレージ暗号における質的な区別を浮き彫りにしている。すなわち、非エンタングル型の量子アドバーサリに対する安全性は、たとえ少量の事前共有エンタングルメントを持つアドバーサリに対しても必ずしも拡張されないということである。
• 範囲: 著者らは、自らの暗号学的構成を最適化された抽出器としてではなく、主にエンタングル型と非エンタングル型のサイド情報の根本的な分離を示すための「原理証明（proof-of-principle）」として位置づけている。

結論として、本論文は、マルチパーティ・エンタングルメントが非局所的な相関の生成を超えた力を持つ、独自の計算リソースとして扱われるべきであることを主張しており、分散型計算タスクや安全な量子ネットワークの研究に新たな方向性を提示している。