技術要約：トレースノルム縮小係数の計算論的側面

問題設定

本論文は、ノイズのある量子チャネルにおける情報の符号化における最適成功確率を決定することの計算複雑性を調査している。具体的には、量子チャネル $\Phi$ に対するトレースノルム縮小係数（$\eta_{tr}(\Phi)$ と表記）に焦点を当てている。この係数は、チャネルが任意の入力状態間で保持する最大識別可能性を定量化するものである。

中心となる問題は次のように定義される。明示的な量子チャネル $\Phi$ の古典的な記述と、整数 $k$（メッセージ数）が与えられたとき、一様に分布されたメッセージを伝送するための最大平均成功確率 $P_{succ}(\Phi, k)$ はいくらか。$k=2$（1ビットの符号化）の特定の場合、この確率はHolevo–Helstromの定理を介して縮小係数と直接関連している：
$$P_{succ}(\Phi, 2) = \frac{1}{2} + \frac{1}{2}\eta_{tr}(\Phi)$$
著者らは、$\eta_{tr}(\Phi)$ を計算または近似すること、および $\eta_{tr}(\Phi) = 1$ であるか（すなわち、ビットに対する完全なゼロエラー符号化が存在することを示す）を判定することのアルゴリズム的な困難さを特徴付けようとしている。

手法

著者らは、計算複雑性理論の技術、特に既知のNP困難問題からの帰着、および凸最適化階層を用いている。

1. 複雑性の帰着:

   • 近似の困難性: 著者らは、リトル・グレンドック問題（特にエルミート非可換および実可換のバリアント）を $\eta_{tr}(\Phi)$ の計算へと帰着させている。彼らは、線形写像 $F$ に関連する量子チャネル $\Phi$ を、グレンドック問題に関連する $F$ の演算子ノルムに比例するように構成している。
   • 決定の困難性: $\eta_{tr}(\Phi) = 1$ であることを判定する困難さを証明するために、著者らはGraph 2-CSP（制約充足問題）およびクラス QAM$_{\log}$ を利用している。彼らは、チャネルの混同グラフ（非可換グラフ）がCSPインスタンスの充足可能性に関連するような量子チャネルを構築している。$\eta_{tr}(\Phi) = 1$ という条件は、チャネルの混同グラフの直交補空間におけるランク1の行列の存在（あるいは、グラフの独立数が $\ge 2$ であること）と等価であると示されている。

2. チャネルの表現:
   チューリングマシンモデル内で問題が適切に定義されるように、著者らは代数数を用いた量子チャネルの厳密な表現を導入している。クラウス演算子は、絶対表現および相対表現を用いた代数数のリストとして表現され、これにより入力サイズが有限かつ計算可能であることを保証している。

3. 半正定値計画法（SDP）階層:
   上界の側面については、制約付き双線形問題のメソッド（先行研究[4]より）を適応して、収束するSDP階層を構築している。この階層は、任意の $k$ に対して $P_{succ}(\Phi, k)$ の上界を与えるものであり、$k=2$ のとき $\eta_{tr}(\Phi)$ の上界へと変換される。この階層は、出力系の複数のコピーを導入し、対称性と正値性の制約を課すプロセスを含む。

主要な貢献と結果

1. 近似のNP困難性

本論文は、トレースノルム縮小係数の近似が計算的に困難であることを確立している：

• 定理 2: $\eta_{tr}(\Phi)$ を $1/\sqrt{2} + \epsilon$ の因子（任意の $\epsilon > 0$ に対して）で近似することは、チャネルがユニタールであることが約束されている場合でもNP困難である。
• 量子・古典チャネル: 限定された量子・古典（ユニタール）チャネルのクラスにおいてさえ、$\eta_{tr}(\Phi)$ を $\sqrt{2/\pi} + \epsilon$ の因子で近似することはNP困難である。
• 意義: これは、この問題が効率的に解ける古典的な類似物とは対照的である。これは、ノイズのある量子チャネルにおける単一ビットの最適な符号化を見つけることがNP困難であることを意味している。

2. 「完全な」ケースのNP困難性

著者らは、決定問題に対して困難性の結果を強化している：

• 定理 3: $\eta_{tr}(\Phi) = 1$ の場合と、$\eta_{tr}(\Phi) \le 1 - 1/\text{poly}(n)$ の場合（ここで $n$ は入力ヒルベルト空間の次元）を区別することはNP困難である。
• 非可換グラフへの含意: $\eta_{tr}(\Phi) = 1$ がチャネルの非可換混同グラフの独立数が2以上であることと等価であるため、非可換グラフの独立数が $\ge 2$ であるかどうかを決定することはNP困難である。

3. 既存の境界の限界

本論文は、既知の効率的に計算可能な境界が必ずしもタイトではないことを示している：

• 定理 28: 著者らは、量子ドブリン係数（および誘導されたドブリン係数）がゼロであるにもかかわらず、縮小係数が厳密に1未満であるチャネルの具体的な例を提示している。これは、$P \neq NP$ と仮定した場合、これらの係数が完全なゼロエラー符号の不在を常に検出できるわけではないことを証明している。

4. 収束するSDP階層

係数の上界を得るための実践的な方法を提供するために、著者らは以下を提案している：

• 定理 30 & 32: $P_{succ}(\Phi, k)$ の非増加な上界の列を与える、半正定値計画法の階層。
• 収束性: この階層は、階層のレベル $m$ が無限大に近づくにつれて、$P_{succ}(\Phi, k)$ の真の値へと収束する。その収束率は $O(\text{poly}(kd)/\sqrt{m})$ である。
• 数値結果: 著者らは、特定のチャネル（一般化振幅減衰チャネルおよびデポラリジングチャネル）に対してこの階層を適用している。これらの例では、階層の第1レベルは量子ドブリン係数よりもタイトな上界を与え、第2レベル（PPT制約を含む）はさらに境界をタイトにしている。

意義と主張

本論文は、チャネル容量や誤り訂正に関連する量子情報理論の基本量である、トレースノルム縮小係数を計算することの複雑性のステータスを解決することを主張している。

• 古典理論との対比: 主な意義は、古典的および量子的情報処理の間の根本的な乖離を浮き彫りにしている点にある。最適な符号化は古典的チャネルでは効率的に近似可能であるが、その量子的な対応物は、最も単純な1ビットの符号化の場合であってもNP困難である。
• 理論的限界: これらの結果は、$P = NP$ でない限り、量子チャネルがビットを完全に保持できるかどうか（すなわち、単一ビットのゼロエラー容量を持つかどうか）を常に判断できる効率的なアルゴリズムは存在しないことを確立している。
• アルゴリズム的ツール: 収束するSDP階層を提供することで、本論文は、成功確率の上界を計算するための体系的な（ただし、潜在的に高コストな）手法を提示しており、それらは特定のケースにおいてドブリン係数のような解析的な境界よりもタイトであることが示されている。

著者らは、階層の有用性について、変数の数が階層のレベルとともに指数関数的に増大するため、正確な計算に関する確立されたNP困難性の結果と矛盾するものではないと述べ、控えめな立場をとっている。本研究は、効率的に計算可能なものと、計算不可能なものの境界を明確にする役割を果たしている。