技術的要約：ノイズのあるもつれを用いた非局所ゲームと通信複雑性

問題設定

本研究は、量子情報理論の二つの基本柱である「非局所ゲーム」と「もつれ補助通信複雑性」に対するノイズの影響を調査するものである。標準的なモデルでは、完全でノイズのないもつれ（具体的には、無制限のEPRペアの供給）へのアクセスを想定しているが、実用的な近未来のアプリケーションでは、ノイズを含む共有リソースが関わることになる。著者らは、完全なEPRペアの片半分をノイズのあるチャネルに通すことで生成される、固定されたノいのあるもつれ状態 $\Psi_{E_A E_B}$ の独立したコピーを任意個数共有するというモデルを研究している。

本論文は、主に以下の二つの問いに取り組んでいる：

1. ノイズのあるEPRペアを共有する場合、非局所ゲーム（特にCHSHゲーム）の勝率（値）にノイズはどのように影響するか？
2. ノイズのあるもつれは、通信複雑性のタスクにおいて、ノイズのないもつれと同じ計算能力を提供するのか（特にEquality関数や関係的問題に関して）？

本研究では、デポラライジング・ノイズ（脱分極ノイズ）、ユニタール・ノイズ（デポラライジングやデフェージングを含む一般クラス）、バイアス付きリセット・ノイズ、および消去（エレイジャー）ノイズの4つの特定のノイズモデルを検討している。

手法

著者らは、演算子代数、ハイパーコントラクティビティ（超収縮性）不等式、および幾何学的議論を組み合わせて結果を導出している。

1. 最大相関とハイパーコントラクティビティ

中心的なツールは、Beigiによって導入された古典的な概念の量子版である、共有状態の最大相関（$MC$）である。著者らは、4つのノイズモデルにおけるEPRペアの最大相関を計算している。

• 彼らは、ノイズチャネルに関するハイパーコントラクティビティ定理を確立している。デポラライジング・ノイズについては既知の結果を利用し、一般的なユニタール・ノイズについてはKingの乗法性結果を用いて新しいハイパーコントラクティビティ定理を証明し、消去ノイズについては既存の結果を適応させている。
• これらの定理により、著者らは結合出力確率分布 $P_{AB|xy}(a,b)$ を、周辺分布 $P_{A|x}(a)P_{B|y}(b)$ をノイズパラメータ（具体的には $1/(1+\rho)$、ここで $\rho$ は最大相関）のべき乗で高めたものとして抑えることができる。

2. 非局所ゲームの解析

• 上界（Upper Bounds）: 著者らは、ノイズのあるもつれ下でのCHSHゲームの値に対する上界を導出している。ユニタール・ノイズの場合、最大相関から導かれる追加の制約を用いた**NPAローカルレベル1半正定値計画法（SDP）**緩和を用いている。一般的なノイズについては、CHSHバイアスの特定の構造を利用して、最大相関から直接的に境界を導いている。
• 並列反復（Parallel Repetition）: 著者らはノイズのある並列反復定理を証明している。ベースとなる指数的減衰の底が単一コピーの量子値に依存する標準的な並列反復定理とは異なり、これらの定理は、減衰率を古典的な値と最大相関を用いて表現する。
  • 一般的なゲームについては、点別境界（pointwise bound）とレニー・ダイバージェンスを用いて、ノイズのある量子値を古典的な並列反復値に関連付けている。
  • ユニークゲーム（CHSHを含む）については、衝突演算子の誘導ノルムを通じて定義される衝突値（$col_p(G)$）を導入している。出力空間を周辺確率に基づく「バケット」に分割し、「ハードリスト境界」（古典的な値に基づく）と「衝突リスト境界」（衝突値に基づく）の間を補間することで、勝率を抑えている。

3. 通信複雑性の解析

• 分離結果: 著者らは、通信モデルを分離するための関係的問題（具体的にはCHSHゲームの閾値版）を構築している。彼らは、完全なもつれを用いるとゼロ通信で解ける問題が、ノイズのあるもつれを用いる場合には線形な通信を必要とすることを示す。
• もつれのシミュレーション: 完全な共有ランダムネスをノイズのある共有ランダムネスでシミュレートする手法（[CGMS15]より）を、もつれ補助の設定へと一般化している。彼らは、二方向もつれ補助プロトコルをベクトルの内積推定問題へと還元している。ジョンソン＝リンデンストラウスの次元削減と相関変数による多項式展開を用いて、ノイズのある共有ランダムネスを用いた同時メッセージパッシング（SMP）プロトコルを構築している。
• Equalityに対する下界: Equality関数（$EQ_n$）の下界を証明するために、標準的なパッキング引数と最大相関写像の特異値分解を組み合わせている。彼らは、定数通信量において、必要なノイズのあるEPRペアの数は$n$に対して多項式的に増大しなければならないことを示している。

主要な貢献と結果

1. CHSHゲームの値の境界

本論文は、4つのノイズモデルすべてにおいて、CHSHゲームに対する新しい上界および下界を提供している。

• 上界: 値は $\rho$ の関数によって上界が抑えられる。ユニタール・ノイズの場合、境界は $\min\left(\frac{1}{2} + \frac{1}{4}\sqrt{1-\rho^2}, \frac{1}{2} + \frac{\sqrt{1+\rho}}{4}\right)$ である。一般的なノイズの場合、それは $\min\left(\frac{1}{2} + \frac{1}{4\sqrt{1-\rho^2}}, \frac{1}{2} + \frac{1}{2\sqrt{2}}\right)$ である。
• 意義: これらの境界は、観測量に関する仮定なしに成立する（無偏差の観測量を必要とした[FQXY26]とは異なる）。著者らは、デポラライジング・ノイズの場合、境界は低ノイズレベル（状態がまだもつれている段階）ではタイトではない（境界が古典的な値を超えている）と指摘している。

2. ノイズのある並列反復定理

• 一般的なゲーム: ゲーム $G$ の $n$ 個の並列コピーのノイズのある量子値は、$(2\rho \log(|A||B|) \cdot w_G)^{\frac{n}{1+\rho}}$ によって上界が抑えられる（ここで $w_G$ は古典的な値）。
• ユニークゲーム: より鋭い境界が導かれる：$O(n^2) \cdot \left( (col_{1+\rho}(G))^{4\rho} w_G^{1-\rho} \right)^{\frac{n}{1+3\rho}}$。
• CHSHの特性: デポラライジング、ユニタール、および消去ノイズ下のCHSHゲームについて、著者らは、並列反復率がノイズのない量子率（$\cos^2(\pi/8)$）よりも厳密に小さいことを証明している（具体的には、最大相関 $\rho \le 0.36$ の範囲において）。これは、共有状態が分離可能になる前であっても、ノイズがもつれの優位性を損なうことを示しており、非常に重要である。

3. 通信複雑性における分離

• ノイズのあるもつれ vs ノイズのないもつれ: 著者らは、完全なEPRペアを用いた通信ともつれのあるEPRペアを用いた通信との間の分離を示している。完全なもつれを用いればゼロ通信で解けるが、ノイズのあるもつれを用いる場合は（十分にノイズが多い状態において）$\Theta(n)$ の二方向古典通信を必要とする関係的問題（$t$-out-of-$n$ CHSHに基づく）が存在する。
• 含意: これは、これらの状態から $n$ 個のほぼ完全なEPRペアを蒸留するために必要な二方向通信コストに対して、$\Omega(n)$ の下限が存在することを意味しており、既知の蒸留プロトコルがこれらの状態に対して最適であることを示している。
• ノイズのあるもつれ vs 完全なランダムネス: 十分に低いノイズレベルにおいて、ノイズのあるもつれは特定のタスクにおいて完全な共有ランダムネスよりも厳密に弱い。なぜなら、ノイズのあるもつれは、完全なランダムネスができるのと同様の方法で、通信オーバーヘッドなしに完全なランダムネスをシミュレートできないためである。

4. Equalityのためのノイズのあるもつれのコスト

• 多項式の下限: 本論文は、定数通信量でEquality関数（$EQ_n$）を計算する場合、4つのノイズモデルすべてにおいて、必要なノイズのあるEPRペアの数が多項式的（具体的には $n^{\Omega(1)}$）であることを証明している。
• 未解決問題の解決: これは、[CGMS15]における疑問に対し、否定的な回答を与えるものである。すなわち、対数個のノイズのある共有ビット（またはノイズのあるEPRペア）は、Equalityのための定数通信プロトコルには不十分である。完全な相関がある場合（$O(\log n)$ で十分）と比較して、必要なリソースコストは指数関数的に高い。

5. プロトコルのシミュレーション

著者らは、任意の相互作用的なもつれ補助通信プロトコルが、通信量の指数的な増大を伴って、ノイズのある共有ランダムネスを用いたSMPプロトコルによってシミュレートできることを示している。これは、ノイズのない共有ランダムネスのシミュレーションに関する先行研究を一般化したものである。

意義と主張

本論文は、通信複雑性をノイズのあるもつれの存在下で体系的に研究した最初の研究であり、このモデルがいくつかのタスクにおいてノイズのないモデルよりも厳密に弱いことを確立している。

• 非自明なノイズ領域: 主要な貢献は、量子的な優位性の劣化が、「非自明な」ノイズ領域（例えば、デポラライジング・ノイズにおいて $\rho > 1/3$ の場合など、共有状態が依然としてもつれている領域）で発生することを示した点にある。並列反復率は、状態がもつれている間でも、ノイズのない量子率を下回る。
• 蒸留の最適性: この分離結果は、既存の蒸馏プロトコルが、特定のノイズのある状態に対して二方向通信コストの観点で最適であることを示唆しており、これは $n$ 個のペアを蒸留するという文脈でこれまで確立されていなかった結果である。
• リソースのスケーリング: 本研究は、ノイズのあるもつれのリソーススケーリングを明確にし、Equalityに対して、完全なリソースを用いた場合の対数的スケーリングとは対照的に、多項式個のコピーが必要であることを示している。

著者らは限界についても認めており、現在の手法は振幅減衰（amplitude damping）ノイズ（最大相関が1となるもの）には適用できず、またバイアス付きリセット・ノイズに関する並列反復定理は、適切なハイパーコントラクティビティの結果が欠けているため未解決のままであるとしている。また、並列反復率の境界はさらに改善できる可能性があるとも示唆している。