Bounding Two-Way Average Communication Cost of Simulating Quantum Correlations

技術要約：量子相関のシミュレーションにおける二方向平均通信コストの境界設定

問題提起
もつれに由来するベル非局所相関は、古典的な通信なしでは局所隠れた変数モデルによって再現することはできない。固定された有限のベル・シナリオにおいて、任意の相関をシミュレートするには有限の通信で十分であることは確立されているが、その「最小」の通信量を決定することは依然として困難な問題である。これは特に、コストが入力を介して平均化され（入力平均通信コスト）、プロトコルが可変長かつ**完全な相互作用（二方向）**を許容する場合において顕著である。本論文は、以下の問いに取り組んでいる：与えられた任意の有限の通信予算に対し、緩和された二方向・可変長条件の下でも、その予算を必ず超えてしまうような有限の量子相関を提示できるか？

手法
著者らは、通信コストの下限を導出するために、2つの補完的な手法を用いている。

1. 非局所ゲームに基づく境界：

   • 勝利矩形（完全勝利）： 相関が確実に勝利するゲーム（擬似テレパシー）において、著者らは標準的な「矩形法」を適応させている。彼らは「勝利矩形」を、局所決定論的戦略が勝利できる入力ペア $S \times T$ の部分集合として定義する。彼らは、最大の勝利矩形確率 $\alpha$ が並列反復の下で乗法的（$\alpha_n = \alpha^n$）であることを証明している。通信コストを通信ツリーのリーフ分布のエントロピーに関連付けることで、コピーあたりの下限 $\log_2(1/\alpha)$ を導出する。
   • 勝利確率（不完全勝利）： 確実に勝利しない相関については、達成された勝利確率と古典的限界との間の相対エントロピーに基づく情報理論的な議論を利用する。彼らは、バイナリ相対エントロピー $D_{bin}(w \| \omega_c)$ に基づく関数 $\Phi_{\omega_c}(w)$ を定義する。並列ゲームにおいて、積入力分布を持つ場合、総通信コストはこれら各コピーにおける関数の総和によって抑えられることを示す。

2. 線形計画法（LP）階層：

   • 正確なシミュレーション・コストは、決定論的相関への凸分解の最適化として定式化できることを認識し、著者らは計算可能な階層を導入している。
   • 決定論的相関を、その最小入力平均通信コスト（$\kappa_k$）によってグループ化する。
   • 下限： 階層のレベル $L$ において、コスト $\le \kappa_L$ である決定論的相関のみを含めることでコストを最小化し、残りの確率重みを次のレベル（$\kappa_{L+1}$）のコストとして計上する。
   • 上限： コスト $\le \kappa_k$ である決定論的相関への正確な分解を制限することで、補完的な上限を得る。
   • この階層は、最終レベルにおいて正確な入力平均コストに収束する。もし下限と上限が低いレベルで一致すれば、すべての戦略を列挙することなく正確なコストが決定される。

主な貢献と結果

• マジック・スクエア（MS）ゲーム：

  • 著者らは、一様入力の下での $n$ 個の並列コピーのMSゲームの正確なシミュレーションに対して、$n \log_2(3/2)$ ビットの低限を証明した。これは、最大の勝利矩形が入力空間の最大 $2/3$ しかカバーしないという事実から導かれる。
  • 彼らは、漸近的なシミュレーション率が $\log_2(3/2)$ ビット／コピーとなる一方向通信プロトコルを構築した。これは、二方向の相互作用を許容しても、MSの漸近的なシミュレーション率は減少しないことを示している。
  • したがって、任意の所定の有限予算 $B$ に対して、正確なシミュレーションが $B$ ビットを超えるような有限のコピー数 $n \approx B / \log_2(1.5)$ が存在する。

• 並列CHSHゲーム：

  • 量子相関が確率 $w_T = (2+\sqrt{2})/4$ で勝利する（古典的な $3/4$ を超える）$n$ コピーのCHSHゲームについて、著者らは$n \times D_{bin}(w_T \| 3/4) \approx 0.04627n$ ビットの下限を導出した。
  • この結果は、相関が完璧に勝利しない場合であっても、正確なシミュレーション・コストが $n$ に対して線形に増大し、十分に大きな $n$ に対してはあらゆる有限の予算を超えることを確立している。
  • 著者らは、彼らの係数が従来の最悪ケースの一方向境界よりも小さいものの、彼らの結果がより一般的な、可変長かつ完全な相互作用を伴う二方向プロトコルの入力平均コストの設定に適用されることを指摘している。

• 境界の階層：

  • 提案されたLP階層は、境界が一致する場合に正確なコストを回収する。
  • 小さなベル・シナリオ（例：$2 \times 2$ 入力／出力）に対する数値結果は、既知の正確なコスト（例：CHSHに対する $\sqrt{2}-1 \approx 0.4142$）を回収している。
  • より大きなシナリオでは、階層の第1レベルが非自明な下限を提供し、しばしばEPR2の非局所的内容と一致する。

意義
本論文は、可変長かつ完全な相互作用を伴う二方向プロトコルが許容される場合でも、有限の量子相関の中に、いかなる所定の有限予算をも超える通信を必要とするものが存在するか、という問いに対し肯定的に答えている。

• 明示的な有限の分離： 大きな $n$ においてコストが増大することを保証する従来のアスンプトティック（漸近的）な結果とは異なり、本研究は、正確なシミュレーション・コストが与えられた予算を厳密に超える、具体的な有限コピーの相関（具体的にはMSおよびCHSH）を提示している。
• 境界のタイトさ： マジック・スクエア・ゲームについては、導出された下限が構成的な一方向プロトコルによって一致することから、漸近的にタイトであることが示されている。これにより、コピーあたりの正確な漸近的シミュレーション率が $\log_2(3/2)$ ビットであることが決定される。
• 方法論的枠組み： LP階層の導入は、すべての可能な通信戦略の無限の空間を考慮する必要なく、特定の相関の正確な入力平均コストを計算するための体系的な方法を提供する（境界が計算可能なレベルで収束する場合）。
• 堅牢性： これらの境界は、最悪ケースのコストよりも一般に低い入力平均コストに対して成立しており、かつ完全な相互作用を伴うプロトコルにも適用されるため、プロトコルの最適化に対して堅牢である。

著者らは、これらの結果が、有限のベル・シナリオにおいて観測される量子相関をシミュレートするために必要な古典的通信を定量化する枠組みを提供し、非局所性の強さや限定的なクロストークを持つ古典モデルの限界を理解することへの示唆を与える、と結論付けている。