技術要約：ランク分解動的計画法による、木幅を超えた厳密な最大尤度復号

問題設定

最大尤度復号（MLD）は、確率的なパウリノイズ下における量子誤り訂正の最適戦略であり、誤った論理クラスを選択する確率を最小化します。しかし、量子符号の縮退（degeneracy）のため、MLDの実装は計算量的に困難です。すなわち、同一の論理クラス内のエラーは、シンドロームが共通であり、かつスタビライザーによって互いに区別されます。論理クラスの全確率を計算するには、指数関数的に巨大なエラー構成の空間を総和する必要があり、これは#P困難な問題として知られています。

現在の最先端のアプローチでは、これらの分配関数を評価するためにテンソルネットワーク（TN）縮約を利用しています。効果的ではあるものの、標準的なTN縮約の計算量は、基礎となるグラフの**木幅（treewidth）*に対して指数関数的になります。多くの重要な符号ファミリー（距離が増大する場合や特定の代数的構造を持つものなど）において、木幅は大きいため、厳密なMLDは超多項式時間の計算量を要します。本論文は、以下の問いに取り組んでいます：「グラフの連結性だけでなく、代数的構造を利用することで、テンソルネットワーク縮約を超えた厳密な最大尤度復号を行うことは可能か？」*

手法

著者らは、**ランク分解動的計画法（Rank-Decomposition Dynamic Programming: Rank DP）**に基づく新しい復号アルゴリズムを提案しています。その主要な手法は、以下の3つのステップで構成されます。

1. 分配関数の定式化：
   符号容量モデルおよび回路レベルノイズモデルの両方に対する復号尤度は、バイナリ線形制約を持つ分配関数 $Z_M(t; w)$ として定式化されます。これらの関数は、シンドロレおよび論理制約を満たす構成にわたって、局所的なフォルトブロックの重みを総和したものです。

2. 冪の二次和（SOP）への還元：
   バイナリフーリエ恒等式を用いることで、分配関数は冪の二次和（Sum of Powers: SOP）へと変換されます。この表現により、尤度は、制約行列のタナーグラフによって定義される局所的な重みとエッジ間の相互作用を含む、バイナリ変数に関する和として表されます。

3. ランク分解動的計画法：
   グラフの木幅に基づいてテンソルを縮約する代わりに、著者らはタナーグラフの**ランク幅（rank-width）**によってパラメータ化された動的計画法を適用します。

   • アルゴリズムは、グラフのランク分解木を利用します。
   • 「境界シグネチャ」（カットの線形汎関数）によってインデックス付けされた部分和のテーブルを保持します。
   • 計算量は、グラフの木幅（$tw$）ではなく、ランク幅（$rw$）に対して指数関数的になります。
   • ガウス消去法： 重要なステップとして、分解幅を増やすことなく、ガウス消去法を用いてタナーグラフをより小さなグラフ（バイナリ・マトロイドの基本グラフ）へと簡約化します。この簡約化は、特定の符号ファミリーに対して多項式時間の結果を得るために極めて重要です。
   • 非負実現（Nonnegative Realization）： 符号付き算術に特有のキャンセル誤差や数値的不安定性を回避するため、著者らは非負実現を用いたDPを提示しています。このバージョンは、テーブルのサイズと算術計算量を維持しつつ、非負の和と積のみを使用し、厳密な相対浮動小数点誤差境界を提供します。

主な貢献

• 理論的枠組み： 本論文は、厳密なMLDが、テンソルネットワークのグラフの木幅ではなく、タナーグラフのランク幅（フォルトブロックの分割に関する）に対して、入力サイズに対して多項式時間で行えることを確立しました。
• 複雑性の分離： 著者らは、Rank DPと標準的な高密度ペアワイズTN縮約との間の指数関数的な分離を証明しました。具体的には、Rank DPが多項式時間で動作する一方で、TN縮約が超多項式時間を要する符号ファミリーを特定しています。
• 具体的な符号ファミリー： 著者らは、パンクチャリングされた量子リード・マラー符号およびステイン連結（Steane-concatenated）ファミリーが、独立した単一量子ビット・パウリノイズ下において、ガウス消去法適用後に多項式時間のMLDを許容することを実証しました。これらのファミリーについて、簡約化されたタナーグラフのランク幅は $O(m)$ （ここで $n \approx 2^m$ ）ですが、元のテンソルネットワークグラフの木幅は超多項式的にスケールします。
• 数値的堅牢性： 非負実現は、明示的な算術仮定の下で、認証された相対誤差境界を提供し、稀なイベントに対しても信頼性の高い推論を可能にします。
• 実証的検証： 広範な数値実験により、Rank DPが、選択された符号容量および回路レベルのインスタンスにおいて、テストされたTN実装（代数的プリプロセッシングを含む）よりも優れた性能を示すことが確認されました。これには、最大1,023量子ビットまでのリード・マラー符号の完全な尤度評価が含まれます。

結果

• 実行性能： リード・マラー符号（$n=1023$）において、Rank DPは、最も高性能なプリプロセスの施されたTN実装よりも約2.83倍高速でした。3D表面符号およびカラー符号において、Rank DPは回路パラメータに応じて1.5倍から7.7倍の高速化を示しました。
• 構造的境界： パンクチャリングされたリード・マラー符号について、簡約されたタナーグラフのランク幅は $O(m)$ （すなわち $O(\log n)$ ）ですが、元のテンソルネットワークグラフの木幅は $\Omega(n / (\log n)^{3/2})$ の下限を持ちます。
• 応用： 著者らは、得られた厳密な尤度を以下の用途に成功的に使用しました。
  • 勾配ベースの最適化を介した、シンドロームデータからの回路ノイズパラメータの学習。
  • 認証された精度を用いた、稀なポストセレクション確率（例：$10^{-26}$ まで下がる条件付き論理失敗確率）の評価。
  • 実用的なデコーダ（例：BP+OSD）の、厳密なMLDベンチマークに対する最適性ギャップの定量化。

意義と主張

本論文は、量子復号およびノイズ特性評価において、代数的構造を活用するための新たな道を切り開くものであると主張しています。複雑性のパラメータを木幅からランク幅へとシフトさせることで、著者らは、厳密な手法では扱いにくいと考えられていた符号ファミリーに対して、厳密なMLDが可能であることを示しました。

著者らは、その範囲について謙虚であり、多項式時間の保証は特定の構造的条件（ガウス消去法後の小さなランク幅）に依存していること、および現在の手法は独立した局所的なフォルト因子に限定されていることを述べています。彼らはすべての量子符号に対してMLDを解決すると主張しているのではなく、特定のクラスの符号に対する効率的な厳密評価器、および精密なノイズ特性評価のためのツールを提供しています。本研究は、「代数的構造」（ランク幅によって捉えられる）が、テンソルネットワークの「連結性」（木幅によって捉えられる）よりも簡潔になり得ることを強調しており、標準的なテンソルネットワーク縮約の限界を超えた、効率的な厳密評価への道筋を示しています。