Membership in the cone of quantum states over time is NP-hard

技術要約：量子状態の時系列における円錐への所属問題はNP困難である

問題設定
本論文は、「時系列における状態（stotes）」の凸円錐 $\mathcal{Q}$ の特性評価に関する計算複雑性を扱っている。stoteは、初期状態 $\rho$ と量子チャネル $E$ を用い、ジョルダン積の形式に従って構成される、二部系 $H_A \otimes H_B$ 上のエルミートかつ一般に非正の演算子として定義される：
$$Q = (\rho \otimes \mathbb{1}) \star J_E = \frac{1}{2}((\rho \otimes \mathbb{1})J_E + J_E(\rho \otimes \mathbb{1}))$$
ここで、$J_E$ はチャネル $E$ のジャミオルコフ演算子である。円錐 $\mathcal{Q}$ は、このような演算子によって生成される凸円錐である。中心となる未解決問題は、[HCW26] で提起されたものであり、この円錐およびその双対円錐 $\mathcal{Q}^*$ の所属特性を特徴付けることである。具体的には、与えられた演算子が $\mathcal{Q}$ に属するかどうか（厳密な所属）や、$\mathcal{Q}$ に近いかどうか（弱所属）を多項式時間で判定できるかどうかを調査している。

手法
著者は、NP困難であることが知られている量子分離可能性問題からの帰着を用いている。核心となる技術的戦略は、分離可能状態の円錐を「状態の時系列」の円錐へと**面的埋め込み（facial embedding）**を行うことである。

1. 面的埋め込みの構成:
   著者は、特定の出力系 $H_B = H_{A'} \otimes H_R$ を定義する。ここで、$H_{A'}$ は入力空間 $H_A$ のコピーであり、$H_R$ は補助レジスタである。彼らは、証拠演算子 $W_0 = (d\mathbb{1}_{AA'} - S_{AA'}) \otimes \mathbb{1}_R$（ここで $S_{AA'}$ はスワップ演算子）を構成する。
   彼らは、$W_0$ が双対円錐 $\mathcal{Q}^*$ に属すること、および $W_0$ に直交する超平面によって定義される $\mathcal{Q}$ の露出面（exposed face）（すなわち $\{Q \in \mathcal{Q} : \text{Tr}[W_0 Q] = 0\}$）が、分離可能状態の円錐 $\text{SEP}^+(A:R)$ と同型であることを証明している。

2. 埋め込み写像:
   $A \otimes R$ 上の任意のエルミート演算子 $\sigma$ に対して、以下の関係を満たす具体的な有理線形写像 $L$ が定義される：
   $$\sigma \in \text{SEP}^+(A:R) \iff L(\sigma) \in \mathcal{Q}(A:A'R)$$
   写像 $L$ は、対称化写像 $\Gamma(X) = \frac{1}{2}\{X \otimes \mathbb{1}, S\}$ を $R$ 上の恒等写像とテンソル積をとることで構成されている。

3. 安定性と頑健性:
   厳密な所属から弱所属（凸集合における標準的な複雑性の概念）へと困難性の結果を拡張するために、著者は定量的な安定性境界（命題3.6）を導出している。この境界は、露出面からの演算子 $Y \in \mathcal{Q}$ のトレースノル距離と、$\text{Tr}[W_0 Y]$ の値との関係を記述している。これにより、演算子が分離可能円錐から遠い場合、その像 $L(\sigma)$ もまた、プロミス問題における「NO」のインスタンスを考慮した後でも、stote円錐から遠い状態に留まることが保証される。

4. 混合ステップ:
   弱所属の帰着に必要な境界ケースを処理するために、著者は混合ステップ $T_\theta(X) = (1-\theta)X + \theta \mathbb{1}/N$ を導入している。これは、分離可能円錐の像を $\mathcal{Q}$ のトレース1の基底の相対内部へと移動させると同時に、非分離入力に対する分離性を保持する。

主要な貢献と結果

• 厳密な所属のNP困難性:
  定理4.1は、有理エルミート演算子が $\mathcal{Q}$ に属するかどうかを判定することがNP困難であることを確立している。これは、分離可能性と $\mathcal{Q}$ の露出面との間の厳密な等価性によって証明される。

• 弱所属および最適化のNP困難性:
  定理4.2は、弱所属（演算子が $\mathcal{Q}$ から多項式的に小さい距離内にあるか、あるいは遠いかを判定すること）が強NP困難であることを証明している。したがって、$\mathcal{Q}$ およびその双対上での弱最適化もまたNP困難である。これは、P = NP でない限り、$\mathcal{Q}$ に対する多項式時間の所属テストは存在しないことを意味する。

• 有限SDP表現の不在:
  定理4.5は、次元 $d, r \ge 2$ かつ $d+r > 5$ のとき、円錐 $\mathcal{Q}(A:A'R)$ は有限半定値表現（SDR）を持たないことを示している。この証明は、露出面およびスペクトラヘドラの線形像がスペクトラヘドラの影（spectrahedral shadow）であるという性質に基づいている。分離可能円錐は有限のSDRを持たないことが既知であるため（Fawziによる定理 [Faw21]）、$\mathcal{Q}$ もまた、その面として分離可能円錐の線形なコピーを含んでいることから、有限のSDRを持つことはできない。

• 幾何学的特性:
  本論文は、$\mathcal{Q}$ が閉じており、尖っており（pointed）、かつ全空間を張る（spanning）円錐であることを確立している。また、露出面への距離が証拠のペアリング値の平方根（$\sqrt{\eta}$）に比例するという定量的な安定性境界を提供しており、これが最適であることを示している。

意義と主張

本論文は、量子ベイズ推論、レトロディクション（逆推論）、および量子最適輸送の中心的な構造である「時系列における状態」の所属問題の複雑性のステータスを解決したと主張している。

• 計算の障壁: 主な意義は、一般的なケースにおいて、時系列における状態の円錐を特徴付けることが計算量的に困難であることを示した点にある。これは、P $\neq$ NP と仮定した場合、この円錐に対する所属テストや最適化のための効率的な（多項式時間）アルゴリズムの存在を否定するものである。
• SDP階層への制限: 非表現性の結果は、この円錐を有限個の半定値制約によって正確に記述できないことを示唆している。これは、分離可能性のためのDoherty-Parrilo-Spredali階層のようなSDP階層は収束する可能性があるものの、$\mathcal{Q}$ の正確かつ有限レベルでの特徴付けを提供することはできないことを意味している。
• 先行研究との区別: 著者は、自身の困難性の結果が、多時刻の状態適合性に関する既存の半定値テスト（例：[GBB26]）と矛盾しないことを明確にしている。これらのテストは、ここでの定義とは異なる、初期系と環境の相関やメモリを許容する集合を扱っているためである。

結論として、本論文は、特定の出力次元（$B = A' \otimes R$）については困難性が確立されたものの、任意の固定次元や一定のギャップが存在する場合の複雑性は依然として未解決の課題であることを述べている。また、導出された安定性指数は最適であり、潜在的な近似アルゴリズムの精度を制限するものであることも強調している。