Polynomial-Time Algorithms for Nuclear Tensor Norms and Multipartite Separability

技術要約：核テンソルノルムおよび多部構成の可分性に関する多項式時間アルゴリズム

問題設定
本論文は、高次元最適化および量子情報理論における2つの基本的な計算問題に取り組んでいる：

1. 核ノルムの弱メンバーシップ（Nuclear Norm Weak Membership）: テンソル $M \in (\mathbb{R}^d)^{\otimes k}$ が与えられたとき、その核ノルムが1以下であるか、あるいは単位核ノルム球への距離が $\epsilon$ 以上であるかを判定する。核ノルムは、ランク1分解における絶対係数の総和のインフィマム（下限）として定義される。
2. 多部構成量子可分性（Multipartite Quantum Separability）: $k$ 部構成の量子状態 $\rho$ （明示的な古典的記述、または未知の状態のコピーを介して与えられる）が与えられたとき、$\rho$ が可分であるか（すなわち、積状態の凸結合であるか）、あるいはフロベニウスノルムにおいて可分状態の集合 $\text{Sep}(d,k)$ との距離が $\epsilon$ 以上であるかを判定する。

これらの問題は、精度 $\epsilon$ が次元 $d$ に依存する場合や、特定の領域で $k$ が入力の一部となる場合、NP困難であることが知られている。先行研究では、準多項式時間アルゴリズムや、固定された $k$ または二部構成（$k=2$）の場合のみの多項式時間解法は提供されていたが、任意の $k$ および $d$ に対して定数加算精度を持つ一般的な多項式時間アルゴリズムは未解決のままであった。

手法
著者らは、2つの異なるアルゴリズムの枠組みを開発している：明示的に与えられたテンソルに対する古典的な決定論的手法と、コピーとして与えられた状態に対する量子的な手法である。

1. 古典的アルゴリズム（決定論的）
古典的アプローチの核心は、多重線形最適化問題を協調的なマルチプレイヤーゲームとして捉える再帰的な**スペクトル圧縮（spectral compression）**技術である。

• スペクトル圧縮: $k$ 個のプレイヤーそれぞれの戦略空間を独立に離散化する（これは指数関数的な爆発を招く）代わりに、著者らは最初の $j$ 部構成のプレイヤーと残りの $k-j$ 部構成のプレイヤーとの間の相互作用を、単一の低次元の「メッセージ」空間 $V_j$ に圧縮する。
• 再帰的プレフィックス圧縮: $V_{j-1} \otimes H_j$ と残りのシステム間のカットに対してスペクトル截断（閾値 $\eta$ 以上の特異値のみを保持すること）を適用することで、メッセージの次元を $O(\eta^{-2})$ に維持する。
• エネルギー引数（Energy Argument）: 累積誤差を抑えるための極めて重要な技術的革新は、「エネルギー引数」である。破棄された成分の二乗ノルムが、初期ノルムへとテレスコーピング（望遠鏡和）される有界な量に収束することを示すことで、総誤差が単純な $O(\eta k)$ ではなく $O(\eta\sqrt{k})$ に抑えられることを示す。これにより、閾値 $\eta$ を $\Theta(\epsilon/\sqrt{k})$ と設定することが可能となり、メッセージ空間の次元を $k$ に対して多項式に保つことができる。
• メタアルゴリズム: アルゴリズムは、到達可能なメッセージの $\delta$ 被覆を反復的に構築する。$k$ が小さい場合（$k \le d^2$）、局所的な集合上の凸最適化を用いる。$k$ が大きい場合（$k > d^2$）、サイトをブロックにグループ化し、局所次元が $k$ に対して相対的に小さいという事実を利用して、ブロック内での全探索を行う。
• 弱メンバーシップへの還元: フランク・ウルフ（Frank-Wolfe）アルゴリズムを用いて、双対最適化問題（$\langle M, \rho_1 \otimes \dots \otimes \rho_k \rangle$ の最大化）の解を、核ノルムおよび可分性の弱メンバーシップ・テストへと変換する。

2. 量子アルゴリズム（プロパティ・テスティング）
入力がコピーとして与えられた未知の状態 $\rho$ である設定に対して、著者らは、状態の明示的な基底を学習することを回避する次元削減プロトコルを提案している。

• 符号付き積状態最適化: 著者らは、Bakshiらによる積状態学習者を、クディット（qudits）および符号付き目的関数（$\text{Tr}((\rho - \sigma)\pi)$ の最大化）へと拡張する。これは、ターゲットとのオーバーラップが高い積状態を特定する局所探索手順を用いて、小さな「オーバーラップ積被覆（overlap product cover）」を構築する。これには部分空間トモグラフィーと多項式最適化が利用される。
• フィルタリングによる次元削減: アルゴリズムは、局所的な「フロベニウス質量」演算子 $A_j = \text{Tr}_{-j}(\rho^2)$ を定義する。閾値以下の固有値を持つ $A_j$ をフィルタリングアウトする量子チャネルを適用し、実質的に、次元 $q = O(k^2/\epsilon^4)$ の低次元部分空間へ状態を射影する。
• シュル・ワイルルの二重性（Schur-Weyl Duality）: 高次元部分空間の明示的な基底を学習することなく（それには $\text{poly}(d)$ 時間を要する）この射影を実現するために、著者らはシュル・ワイルルの二重性を利用する。$N$ 個の $\rho$ のコピーに対してシュル変換を適用することで、置換レジスタをユニタリ表現レジスタから分離する。未知の基底情報を含むユニタリレジスタを破棄し、標準的な低次元空間に置き換えることで、実質的に局所的なユニタリ群に関するハール平均（Haar-average）を実行する。これにより、可分状態集合への距離を保持したまま、局所次元を $q$ まで削減できる。
• 結果: 削減された状態は、その後、低次元テスターに入力され、実行時間とサンプル複雑度が $k$ および $\log d$ の多項式であり、$d$ に依存しないものとなる。

主要な貢献と結果

• 定理 1.1 (核ノルム): 本論文は、定数加算精度を持つ高次テンソルの核ノルム単位球における、初の決定論的多項式時間アルゴリズムを提示している。実行時間は $d^{O_\epsilon(k)}$ である。
• 定理 1.2 (量子可分性): 著者らは、一般的な $k$ および $d$ に対して、フロベニウスノルムにおける多部構成の弱メンバーシップ問題に対する初の決定論的多項式時間アルゴリズムを提供しており、これは最近の二部構成限定の結果を改善するものである。実行時間は $d^{O_\epsilon(k)}$ である。
• 定理 1.3 (コピーからの可分性): $k^{O_\epsilon(1)}$ 個のコピーと $k^{O_\epsilon(1)} \cdot \text{polylog}(d)$ の時間を用いて、フロベニウスノルムにおいて $\epsilon$ だけ離れた可分状態を識別する量子アルゴリズムが提供されている。これは、可分状態の弱メンバーシップに関する初の次元フリー（dimension-free）なテストである。
• 技術的新規性: 本研究は、累積誤差を $O(\eta k)$ ではなく $O(\eta\sqrt{k})$ に抑える再帰的なスペクトル圧縮メカニズムを導入しており、これが従来のアルゴリズムを準多項式時間から多項式時間へと進化させた。また、量子プロパティ・テスティングにおいて、高次元部分空間の明示的な古典的記述を必要とせずに、表現論（シュル・ワイルルの二重性）がいかに活用できるかを示している。

意義
本論文は、定数精度領域における多部構成の可分性と核ノルム評価に関する、多項式時間アルゴリズムを見出すという未解決問題の解決を主張している。協調的なゲーム理論の視点とスペクトル圧縮を組み合わせることで、著者らはこれらの問題における準多項式時間と多項式時間の間のギャップを埋めている。量子設定においては、局所次元 $d$（$\text{polylog}(d)$ を除く）に依存しないコピー数と時間で可分性をテストできることは、従来の境界および次元依存のアルゴリズムに対する重要な進歩である。本研究は、トレースノル可分性の既知の下限を回避するために、コピー間でのコヒーレントな測定が必要であることを強調しており、効率的な量子プロパティ・テスティングへの新たな経路を提示している。