技術要約：可分集合の半正定値拡張複雑性

1. 問題設定

本論文は、可分状態の集合 $\text{Sep}(d:d)$ に対する2結果測定演算子 $Q$ の最大受容確率を近似することの計算複雑性を扱っている。この最適化問題 $h_{\text{Sep}}(Q) = \max_{\sigma \in \text{Sep}(d:d)} \text{Tr}(Q\sigma)$ は、$\text{QMA}(2)$（2つの非もつれ証明を持つ量子メリン・アーサー）の複雑性クラスの中心的な概念である。

具体的な焦点は、Harrow, Natarajan, および Wu (HNW) によって確立された枠組みにおける、可分集合の**半正定値拡張複雑性（semidefinite extension complexity）**である。著者らは、以下の制約下で $h_{\text{Sep}}$ を近似するために必要な半正定値計画法（SDP）の最小サイズ $r$ を調査している：

• 共通実行可能領域： すべての測定演算子 $Q$ は、単一のSDP実行可能領域 $\mathcal{P}$（$r \times r$ の正定値行列のスペクトラヘドロン）を共有する。
• 目的関数に依存しない埋め込み： 純粋な積状態を $\mathcal{P}$ に埋め込む固定された写像 $\iota$ が存在し、あらゆる積状態 $\tau$ に対して、SDPの目的関数 $\Phi_Q$ が受容確率 $\text{Tr}(Q\tau)$ を再現する（これは $Q$ によらず成立する）。
• 近似： SDPは、指定された加法的誤差 $a$ または相対ギャップ $\varrho$ の範囲内で $h_{\text{Sep}}$ を近似しなければならない。

また、本論文は**近似ディスエンタングラー（approximate disentanglers）**へのこれらの下界の適用についても述べている。これは、任意の入力を可分状態に近い状態へと写す量子チャネル $\Lambda: \mathcal{L}(\mathbb{C}^D) \to \mathcal{L}(\mathbb{C}^d \otimes \mathbb{C}^d)$ であり、すべての可分状態をカバーするものである。目標は、そのようなチャネルに必要な最小入力次元 $D$ を決定することである。

2. 手法

著者らは、パターン行列下界、擬密度（pseudo-density）技術、およびスペクトラヘドロン幾何学を組み合わせて用いている。

2.1 HNW 枠組みと PSD ランク

核となる手法は、特定の非負行列（「スラック行列」）のPSD ランクと、SDP 定式のサイズを関連付ける Lee–Raghavendra–Steurer (LRS) の定理に基づいている。

• スラック行列の構成： 著者らは、行が「証拠（witnesses）」（ブロック正値演算子 $W_T$）に対応し、列が「状態」（積状態 $\sigma_S$）に対応する行列 $M$ を構成する。そのエントリーは $M(T, S) = \text{Tr}(W_T \sigma_S)$ である。
• 分解： サイズ $r$ の共通実行可能領域を持つSDPは、この行列のサイズ $r+1$ のPSD分解を意味する。したがって、$M$ のPSDランクに対する下界は、SDPサイズの下界を与える。

2.2 ナップサック・パターン行列

グラフの3彩色問題に基づくQMA(2)プロトコルを利用した先行研究（HNW）とは異なり、本論文では中心的なナップサック多項式に基づく行列を構成している：
$$f_m(x) = \frac{1}{m^2} \left[ \left( \sum_{i=1}^m x_i - \frac{m}{2} \right)^2 - \frac{1}{4} \right]$$
ここで $m$ は奇数である。ブール超立方体 $\{0,1\}^m$ 上で $f_m(x) \geq 0$ である。しかし、Grigoriev の擬期待値汎関数 $\mathcal{G}_m$ は、存在しないハミング重み層 $m/2$ を有効なものとして扱うことにより、$f_m$ に対して負の値（具体的には $-1/4m^2$）を割り当てる。

2.3 チェビシェフ多項式による増幅

HNWの指数関数的に小さい誤差のレジームと比較して、より大きな近似誤差（定数または逆多項式）を扱うために、著者らはチェビシェフ・アダマール増幅を適用している：

• 著者らは、行列のエントリーに対して多項式変換 $P_\ell(u) = (1 + T_\ell(2u-1))/2$ を適用する。
• この変換は、範囲 $[0,1]$ におけるエントリーの非負性を保持しつつ、「形式的な」負の点における擬期待値の負の値を $\ell^2$ 倍に増幅する。
• 決定的なことに、著者らは恒等式 $P_\ell(u) = u Q_\ell(u)^2$ を用いて、PSDランクの増加を制御している。これにより、ランクのコストが多項式の次数に対して線形にしか増大しないことを示し、誤差パラメータが大きくなっても議論がスケール可能であることを示している。

2.4 証拠と状態の構成

命題 4.1 は以下を明示的に構成している：

• 積状態： 特定の基底ベクトルの重ね合わせを用いて、部分集合 $S \subseteq [N]$ を符号化する $\sigma_S$。
• ブロック正値証拠： 対角射影演算子とスワップ演算子 $F$ を含むペナルティ項からなる $W_T$。これらの証拠は、積状態に対しては非負であるが、もつれ状態に対しては負になり得るように設計されており、周囲の次元に依存しないノルム境界 $O(m)$ を持つ。

3. 主な貢献と結果

3.1 SDP 定式化の低界

本論文は、$h_{\text{Sep}}$ を近似するSDP定式のサイズ $r$ に関する新しい下界を確立している。

• 定理 5.4： 固定された $0 < \theta < 2/7$ に対して、十分大きな $d$ と近似誤差 $a \leq a_\theta$ に対し、定数 $c_\theta, a_\theta > 0$ が存在して、 $h_{\text{Sep}}$ を加法的誤差 $a$ で近似する任意のSDPは、以下のサイズを持つ：
  $$r \geq d^{c_\theta \min\{a^{-1/3}, d^\theta\}}$$
• HNW との比較： HNW は、誤差 $O(1/d^2)$ に対して $d^{\log d / \text{polylog} \log d}$ の下界を示した。新しい下界は、定数誤差に対して適用可能であり、誤差が十分に小さい場合（$a \leq d^{-3\theta}$）、HNW の下界を $d$ のべき乗に対する指数関数（具体的には $d^{\Omega(d^\theta)}$）へと改善する。
• 幾何学的解釈： 系数 5.6 はこれをスペクトラヘドロンの影（spectrahedral shadows）に拡張し、$\text{Sep}(d:d)$ を含み、かつそれとのトレース距離 $a$ 以内に位置する任意の凸集合は、少なくとも $d^{c_\theta \min\{(2a)^{-1/3}, d^\theta\}}$ のサイズのスペクトラヘドロン・リフトを必要することを証明している。これは、可分集合には厳密な半正定値表現が存在しないという Fawzi の定理に対する定量的な対応物を提供している。

3.2 近似ディスエンタングラーの低界

著者らは、SDPの下界を近似ディスエンタングラーの入力次元 $D$ に適用している。

• 定理 1.1： 全誤差 $a = \varepsilon + \delta$ を持つ $(\varepsilon, \delta)$-近似ディスエンタングラーについて、入力次元 $D$ は以下を満たす：
  $$\log D \geq c M_a \log(2 + R_a)$$
  ここで $M_a$ と $R_a$ は、SDPの下界から導かれる $d$ と $a$ の関数である。
• 系 1.2 (定量的成長)：
  • もし $a \leq n^{-c}$ （量子ビット数 $n = \log d$ の逆多項式）であれば、$\log D = \Omega(n^{1+c/3})$ である。これは超線形な入力量子ビット数を強制する。
  • もし $a$ が $(\log d)^{18/7} / d^{6/7}$ のオーダーであれば、$\log D = \Omega(d^{2/7} / (\log d)^{6/7})$ である。
• QMA(2) への示唆： これらの結果は、約束ギャップが超多項式的に小さい（$n^{-\omega(1)}$）場合、ディスエンタングラー戦略を用いて $\text{QMA} = \text{QMA}(2)$ を証明することは不可能であることを示している。なぜなら、そのような戦略には超多項式数の入力量子ビットが必要になるからである。

3.3 ボゾン可分性

系 5.7 は、これらの下界を2粒子ボゾン可分体（状態 $|\psi\rangle\langle\psi|^{\otimes 2}$ の形式）に拡張し、同様の複雑性下界が適用されることを示している。

4. 意義と主張

著者らは、以下の意義を主張している：

1. SDP 特有の下界： 本研究は、可分集合を定数または逆多項式トレース距離内で近似する $h_{\text{Sep}}$ の一般的なSDP拡張定式化に対する、最初の一致的な情報理論的下界を提供している。並行研究である Bostanci et al. [BGH+26] は、量子オラクル分離を用いて近似ディスエンタングラーに対するより強い下界（$\log D = \Omega(\sqrt{d})$）を確立しているが、彼らの簡約は一般的なSDP定式化には適用されない。したがって、SDP特有の下界（定理 5.4 および 系 5.5）が、半正定値複雑性の文脈における本研究の主要な貢献である。
2. 定量的改善： 本研究の境界は、定数または逆多項式誤差に対して、HNW の結果を準多項式から $d$ に対する指数関数的な下界へと大幅に改善している。
3. ディスエンタングラー戦略の反駁： これらの結果は、約束ギャップが十分に小さい（SDPの下界が適用される領域において）場合、多項式個の入力量子ビットを持つチャネルを用いて $\text{QMA}(2)$ をシミュレートするディスエンタングラーアプローチが不可能であることを示している。
4. 方法論的進展： 本研究は、ナップサック多項式とチェビシェフ増幅を用いた LRS 定理の洗練された適用を導入しており、従来のプロトコルベースの構成と比較して、誤差パラメータと PSD ランクのコストをより精密に制御することを可能にしている。

著者らは、量子オラクル分離を用いて近似ディスエンタングラーに対するより強い下界を証明している並行研究 [BGH+26] を認めているが、彼らの簡約は一般的なSDP定式化には適用できないため、SDP特有の下界（定理 5.4 および 系 5.5）が本研究の主要な貢献として残るとしている。これらの結果は、形式的な Lean 証明によって支持されている。