Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond

技術要約：多様体の線形切片の計算

問題定義
本論文は、任意の円錐多様体 $X \subseteq \mathbb{F}^n$（ここで $\mathbb{F}$ は $\mathbb{R}$ または $\mathbb{C}$）と、与えられた線形部分空間 $U \subseteq \mathbb{F}^n$ の共通部分に含まれる要素を見つけるというアルゴリズム的問題を扱っている。多様体 $X$ は、次数 $d$ の一連の同次多項式の共通零点として定義され、部分空間 $U$ は基底 $\{u_1, \dots, u_R\}$ によって指定される。

核心となる問題（問題1）は、次のように問いかける：$U$ と $X$ の定義多項式が与えられたとき、$U \cap X = \{0\}$ であることを証明するか、あるいは非ゼロの点 $v \in U \cap X$ を見つけることができるか？

この問題は、特に $X$ がランク1の行列（行列式多様体）である特定のケースにおいてさえ、最悪の場合にはNP困難であることが知られている。著者らは、この困難性が量子情報理論における中心的な問題（例：部分空間がもつれ状態にあるかどうかの判定）や、テンソル分解に適用されることを指摘している。

手法
著者らは、「典型的」または「生成的（generic）」なインスタンスに対してこの問題を解くための多項式時間アルゴリズムである Algorithm 1 を提案している。このアルゴリズムは、以下の2つの主要な数学的柱に基づいている：

1. ヒルベルトの零点定理（Hilbert's Nullstellensatz）: 交わりが自明であることを確認するための、射影的零点定理から導かれる次数 $d$ の証明書（certificate）。
2. 同時対角化（Simultaneous Diagonalization）: 次数 $d$ の多項式の空間に適用された、「持ち上げられた（lifted）」バージョンの同時対角化アルゴリズム（しばしばJennrichのアルゴリズムやHarshmanのアルゴリズムに関連付けられる）。

アルゴリズムのステップ:

1. 入力: 部分空間 $U$ の基底と、$X$ を定義する一連の同次次数 $d$ の多項式 $\{f_1, \dots, f_p\}$。
2. 構成: アルゴリズムは、$\{P_1, \dots, P_s\}$ という基底を計算する。これは $S_d(U) \cap I_d^\perp$ の基底である。ここで $S_d(U)$ は $U$ の $d$ 次対称冪であり、$I_d^\perp$ は定義多項式によって生成されるイデアルの次数 $d$ の空間における直交補空間である。
3. 自明な交差のチェック: もし $S_d(U) \cap I_d^\perp = \{0\}$ であれば、アルゴリズムは $U \cap X = \{0\}$ であることを証明する。
4. 復元: もし交わりが非自明であれば、アルゴリズムは基底要素をテンソルとして扱い、同時対角化アルゴリズムを実行する。
   • 対角化が $\{z_i \otimes v_i^{\otimes d}\}$ という分解（ここで $v_i$ は線形独立）をもたらす場合、アルゴリズムは $\{v_1, \dots, v_s\}$ を $U \cap X$ の一意な要素（スカラー倍を除いて）として出力する。
   • 対角化がこのような構造を生成できなかった場合、アルゴリズムは「Fail（失敗）」を出力する。

主要な貢献と理論的保証
主要な貢献は、最悪の場合のNP困難性にもかかわらず、特定の次元を持つ「生成的」なインスタンスに対して Algorithm 1 が高い確率で成功することを証明する 生成性の保証（定理2）である。

• 主要定理 (Theorem 2): $X$ を $p = \delta \binom{n+d-1}{d}$ 個の線形独立な次数 $d$ の同次多項式によって切り出された既約多様体とし、$X$ が次数 $d-1$ において非退化であると仮定する。もし $U$ が、$s$ 個の $X$ の生成的要素と $R-s$ 個の周囲空間の生成的要素によって生成される、次元 $R \leq \frac{\delta}{d!}(n+d-1)$ の生成的（generic）な部分空間であるならば、以下が成り立つ：

  1. $U \cap X$ は（スカラー倍を除いて）ちょうど $s$ 個の要素を含む。
  2. Algorithm 1 は、これら $s$ 個の要素を $n^{O(d)}$ 時間で復元し、その一意性を証明する。
  3. $s=0$ の場合、アルゴリズムは $n^{O(d)}$ 時間で $U \cap X = \{0\}$ であることを証明する。

• 先行研究の修正: 著者らは、De Lathauwer, Cardoso, および Castaing [DL06] による記念碑的な研究における、FOOBIアルゴリズムに関する極めて重要な補題（Lemma 2.3）の決定的な誤りを特定している。彼らは反例を提示し、ランク1の行列だけでなく、より広範なクラスの多様体に対して生成性の保証を確立する修正された証明手法を提供している。

結果と応用
本論文は、主定理を特定の領域に適用したいくつかの系（corollaries）を導いている：

1. 量子もつれ（Quantum Entanglement）:

   • もつれた部分空間: アルゴリズムは、生成的な部分空間 $U$ が $r$-もつれ状態（ランク $r$ の行列を含まない）であるかどうかを判定するか、あるいは植え付けられた（planted）可分状態を見つけ出す。これは、$r$-もつれ、完全なもつれ（積状態を持たない）、および純粋なもつれ（分離可能状態を持たない）に適用される。
   • 効率性: 最悪の場合の判定はNP困難であるが、アルゴリズムは全次元の定数割合までの次元を持つ部分空間に対して、これらの問題を多項式時間で解く。

2. 低ランク分解:

   • 一意性と復元: 本論文は、$T = \sum_{i=1}^R v_i \otimes w_i$（ここで $v_i \in X$）という形式の $(X, W)$-分解の一意性と効率的な復元を確立している。
   • テンソル分解: 標準的なテンソル分解（$X$ がランク1の行列の多様体である場合）において、アルゴリズムは3次テンソルの場合、ランク $R \approx \frac{1}{4}(n_1-1)(n_2-1)$ までのユニークな分解を復元する。これは、従来の生成性の境界（通常 $n \times n \times n$ テンソルに対して $R \leq n$ に制限されていた）を改善している。
   • 高次テンソル: 結果は、任意の次数 $m$ の非対称テンソルへの拡張が可能であり、ランク $O(n^{\lfloor m/2 \rfloor})$ までの生成性を保証する。これは、偶数次の非対称テンソルにおいて、これまで保証が未知であった重要な改善である。
   • ブロック分解: フレームワークは $r$-aided 分解（ブロック分解）にも適用され、これらの構造を復元するための多項式時間の保証を提供する。

意義
本論文は、代数幾何学とアルゴリズム計算量の複雑さを橋渡しすることで、最悪の場合には手に負えないと考えられていたクラスの問題を解決することによって、その意義を主張している。生成的（generic）なインスタンスに焦点を移すことで、著者らは以下を実証している：

• 効率性: 最悪の場合にNP困難である分解や交わりを復元するための多項式時間アルゴリズムが存在する。
• 汎用性: この手法はテンソルや行列に限定されず、緩やかな非退化条件を満たすあらゆる既約円錐多様体に適用できる。
• 正確性: 本研究は、FOOBIアルゴリズムおよび関連するテンソル分解法の理論的基礎を修正し、従来の証明に欠陥があった箇所に対して厳密な生成性の保証を提供している。
• 一意性: アルゴリズムは単に解を見つけるだけでなく、見つけられた分解が（自明なスケーリングと置換を除いて）一意であるという証明書を提供する。この性質は、潜在変数モデルの推定や信号処理のアプリケーションにおいて極めて重要である。