Unbounded degree overhead for Alice-conditioned quantum Bell certificates

技術要約：アリス条件付き量子ベル証明書における次数オーバーヘッドの非有界性

問題設定
本論文は、証明書の構造が制約されている場合の、ナバスク・ピロニオ・アシン（NPA）階層内における量子ベル境界の計算コストを調査している。具体的には、各平方和（SOS）項がアリスの測定質問のうち一つのみを含む必要がある「アリス条件付き」階層を検討する。この構造は、コンパイルされた非局所ゲームや、特定の暗号学的健全性証明（例：「nice-SOS」ルート）に関連している。中心となる問いは、証明書をこの「単一質問」構造に制限することで、標準的な（制約のない）証明書と比較して、SOS分解の次数に有界なオーバーヘッドが生じるかどうかである。著者は、標準的な証明書が次数2で厳密であることが知られている、傾斜型CHSH（tilted-CHSH）ファミリーのベル汎関数に焦点を当てている。

手法
著者は、半正定値プログラミング（SDP）および作用素環の枠組みの中で、解析的な構成、代数的な検証、および数値最適化を組み合わせて用いている。

1. 階層と錐体（Cones）: 本研究では、実数ベル・ギャップ空間における2つのSOS証明書の錐体を比較する：

   • $D_k$: 標準的な次数-$k$の証明書（総減少長 $\le k$ のワード）。
   • $O_k$: アリスの質問/回答によってインデックス付けされたブロック内のボブのワード（長さ $\le k$）を用いた、アリス条件付き次数-$k$の証明書。
     変換次数 $d_{std}$ および $d_{os}$ は、特定の境界 $\beta$ を証明するために必要な最小レベルとして定義される。

2. 解析的な反例（非有界なオーバーヘッド）: 有限の条件付きレベルがすべての標準レベル2の証明書を含むことはないことを証明するために、著者は無限二面体群（$\mathbb{Z}_2 * \mathbb{Z}_2$）上の正の汎関数を用いた、実現可能なウィットネス（witness）を構成する。

   • **フェイエール重み付きトレース（Fejér-weighted trace）**を利用して、特定のボブのワードに質量を集中させる正の汎関数を構成する。
   • $r_k \sim k^{-2}$ でスケールする決定論的なボブの応答に対応するランク1の項を減算することで、特定の傾斜 $\alpha_k$（$\alpha \to 2$ へ接近する）において、特定の条件付きレベル $k$ の正定値制約を違反するウィットネスを作成する。
   • この構成は、移動平均のグラム行列に依存しており、ランク1の減算が正定値性を維持するためには、条件付きレベルが十分に高くなければならない。

3. 区間における厳密な証明書: 逆に、オーバーヘッドが有界となる領域を特定するために、傾斜パラメータ $\alpha$ の特定の区間に対する厳密な証明書を構成する。

   • 最適面への還元（Optimal-Face Reduction）: 傾斜型CHSHゲームの最適戦略を利用して、モーメント行列の核（kernel）を特定する。これにより、デュアル証明書の探索を、核の直交補空間上の正定値（PSD）行列の探索へと還元する。
   • 有理関数ファミリー: 区間 $\alpha \in [13/10, 3/2]$ に対して、量子境界と戦略の核を有理関数を用いてパラメータ化する。グラム行列が次数20の行列多項式となる、連続的な証明書ファミリーを構築する。
   • バーンスタイン正定値性（Bernstein Positivity）: これらの多項式の正定値性を、バーンスタイン基底への展開と、すべての係数行列が厳密にPSDであることの確認によって検証する。

4. ランダムネスの認証: 本論文は、これらのベル境界の分離を、デバイス非依存のランダムネス認証へと翻訳する。推測確率の凹性に係わるコンタクト基準を用いることで、ベル境界の分離が、認証された最小エントロピーの分離に直結することを示す。

主要な貢献と結果

• 非有界な次数オーバーヘッド: 主要な結果（定理1）は、傾斜型CHSHファミリーにおいて、有限のレベルのアリス条件付き階層は、すべての標準レベル2の証明書を含まないことを証明している。具体的には、傾斜 $\alpha$ が局所的な終点（$\alpha \to 2$）に近づくにつれ、必要な条件付きレベル $d_{os}$ は少なくとも $\Omega((2-\alpha)^{-1/2})$ のオーダーで増大する。

  • 任意の整数 $k$ に対して、標準的な証明書はレベル2で厳密であるが（$d_{std}=2$）、条件付き証明書はレベル $k$ よりも厳密に高いレベルを必要とする（$d_{os} > k$）ような傾斜 $\alpha_k$ が存在する。
  • これにより、「単一質問」の制限が、低次の標準的な証明書が存在する場合であっても、代数的なリソースの無界な増加を強制し得ることが示された。

• 区間における厳密な有限変換: 終点付近での非有界なオーバーヘッドにもかかわらず、著者は（定理2）、区間 $\alpha \in [13/10, 3/2]$ においてオーバーヘッドが正確に1レベルであることを証明する。

  • すべての $\alpha$ について、この範囲では $d_{std} = 2$ かつ $d_{os} = 3$ である。
  • これは、バーンスタイン正定値性を用いて検証された、明示的な有理関数による証明書ファミリーを通じて示され、条件付き階層がこのサブファミリーに対してレベル3で正確に閉じることを証明している。

• レベル1の値の分離: 本論文は、レベル1の等価性に関する以前の主張を修正している。傾斜型CHSHにおいて $\alpha > 0$ の場合、標準的なレベル1の値はアリス条件付きレベル1の値よりも厳密に大きい（$\omega_{std}^1 > \omega_{os}^1$）ことを証明している（定理3.7）。これは、レベル1の条件付きブロックが、標準的なレベル1の切り捨てには存在しない総次数3のモーメントを（ブロックラベルを介して）暗黙的に含んでいるためである。

• デバイス非依存のランダムネス: 著者は、次数オーバーヘッドの非有界性が運用上の影響を持つことを示す（定理3）。有限の条件付きレベルは、量子サイド情報に対する完全なCHSHランダムネス・トレードオフ全体を認証することはできないが、標準的なレベル2は可能である。具体的には、量子最適値に向かう数列 $s_k \to 2$ に対して、条件付きレベル $k$ を用いて認証された最小エントロピーは、量子最適値よりも厳密に低くなり、特定の点において $10^{-3}$ ビットを超える欠損が生じる。

• コンパイルされた健全性への示唆: これらの結果は、「nice-SOS」入力に対する定量的障害を提供している。任意の傾斜に対して、厳密なnice-SOS証明書におけるボブのワード因子の次数は $\Omega(\epsilon^{-1/2})$ として増大しなければならず、これは任意の傾斜に対するこのような証明の効率を制限するものである。

意義と主張
本論文は、「通常のSOS次数」と「単一質問の証明書構造によって課されるリソース」を分離することを主張している。コンパイルされたゲームの安全性などの暗号学的用途から動機付けられることが多い、証明書の構造的制約が、NPA階層の収束特性を根本的に変え得ることを示している。

• 主張の謙抑性: 著者は、コンパイルされたプロトコルの安全性や有限キーレートの失敗を主張しているのではないことを明記している。結果は、単一ラウンドの認証手法の精度と、厳密な証明書に必要な代数的次数に関するものである。
• 未解決問題: 漸近的な下界 $\Omega(\epsilon^{-1/2})$ は証明されているものの、すべての固定された劣臨界的な傾斜に対する正確な上界や、有限の厳密な閉鎖の証明は依然として未解決である。数値的な飽和は平方根の成長を示唆しているが、この指数に一致する厳密な上界は確立されていない。
• 文献の修正: 本研究は、標準階層と条件付き階層の関係についての理解を洗練させ、特に傾斜型CHSHのレベル1の値の等価性に関する以前の主張を修正し、POVM/ローカライザー・フィルトレーションと、ここで使用されている生のPVM商との区別を明確にしている。

要約すると、本論文は、アリス条件付き階層は特定のパラメータ領域では低レベルで厳密になり得るものの、量子集合の境界付近では次数オーバーヘッドが非有界となり、厳密な認証タスクにおいて標準的な階層を普遍的に代替することを妨げることを確立している。