An Efficient Algorithm to Sample Quantum Low-Density Parity-Check Codes

技術要約：量子低密度パリティ検査符号をサンプリングするための効率的なアルゴリズム

問題提起
本論文は、ランダムな量子低密度パリティ検査（LDPC）符号を効率的に生成するという課題に取り組んでいる。古典的なLDPC符号は、単に疎な行列をサンプリングすることで生成できるが、量子LDPC符号には追加の制約が必要である。具体的には、対応するパウリ群の部分群がアーベル群であることを保証するために、パリティ検査行列がシンプレクティック積条件（特に、双対含有符号における $HH^\top = 0$）を満たさなければならない。既存の量子LDPC符号の構成法は、主に代数的な手法（例：準巡回符号、ハイパーグラフ積、または特定の幾何学的構造に基づくもの）に依存している。これらの代数的なアプローチは、符号のパラメータ（長さ、次元、疎性）に対して硬直した制約を課しており、その結果として得られる符号はランダムなものからは程遠い。本論文は、次のような問いを投げかける：特定の代数的構造に依存することなく、ランダムな量子LDPC符号を効率的に生成できるか？

手法
著者らは、行ごとに疎で自己直交なバイナリ行列をサンプリングするための、純粋に組合せ論的なアルゴリズムを提案している。核となる手法は、このサンプリング・タスクのために適応させた情報集合復号（Information Set Decoding: ISD）、具体的にはリー・ブリックル（Lee-Brickell: LB）アルゴリズムである。

アルゴリズムは、$r$ ステップを経て行列 $H \in \mathbb{F}_2^{r \times n}$ を構築する：

1. 反復サンプリング： ステップ $u$ において、アルゴリズムは既に $u-1$ 個の線形独立で、疎かつ互いに直交するベクトル $\{h_1, \dots, h_{u-1}\}$ が見出されていると仮定する。
2. 符号の定義： これらのベクトルは線形符号 $C_u$ のパリティ検査行列を形成する。アルゴリズムは、新しいベクトル $h_u$ を探索する。この $h_u$ は $C_u$ の符号語であり（これにより以前の行との直交性が保証される）、かつ特定のハミング重み $v$ を持つ（これにより疎性が保証される）。自己直交性（バイナリ体における要件）を強制するため、全一ベクトルが追加のパリティ検査方程式として加えられる。
3. ISDの活用： 重み $v$ の符号語を見つけるために、アルゴリズムはISDを用いる。これが極めて重要なコンポーネントであり、これを用いなければ、高次元空間においてこのような疎なベクトルを見つけることは計算量的に不可能となる。
4. 基底の更新： もし有効な $h_u$ が前のベクトルのスパンに含まれずに発見された場合、それは行列に追加され、プロセスは $r$ 個の行が生成されるまで繰り返される。

理論的解析およびパラメータ選択
論文では、中間符号 $C_u$ の**期待重み分布（Expected Weight Distribution: EWD）**に焦点を当て、アルゴリズムの実現可能性に関する理論的特性を提示している。

• 解の存在： 著者らは、高確率で重み $v$ の符号語が存在するための条件を導出している。彼らはパリティ検査行列 $H_u$ を、各行が一定の重み $v$ を持つ分布 $H_{n,u,v}$ からのサンプルとしてモデル化している。
• 重みの制約： 漸近解析を通じて、定数符号率 $R$ に対して、符号語が劣線形な重み $w = o(n)$ を持つのは、行の重み $v$ が以下を満たす場合に限って高確率で起こることを証明している：
  $$v < \frac{\ln(2)}{1-R} \log_2(n)$$
  これは、アルゴリズムが効率的に成功するためには、行の重みが符号長 $n$ に対して対数的である必要があることを意味している。
• 計算量： 論文では、標準的なISDのヒューリスティクスを用いて時間計算量を分析している。著者らは、疎な行列に対するISDの挙動（ランダムな行列とは異なる）に関する仮定が必要であり、厳密な多項式時間の証明には課題があることを認めているが、妥当なヒューリスティクスの下では、 $v = O(\log n)$ のときアルゴリズムは多項式時間で動作すると主張している。具体的には、重み $v$ の符号語の期待数が大きい場合、ISDの呼び出し回数は最小限となる（しばしば1に近い）。

結果と数値検証
著者らはアルゴリズムをSageMathで実装し、標準的なノートPCを用いたベンチマークを提供した。

• 実現可能性： アルゴリズムは、様々なパラメータ（例：$n=250, 500, 1000$）に対して双対含有符号を正常に生成した。
• 効率性： 表Iおよび表IIIは、理論的境界を満たすパラメータにおいて、符号生成の平均時間が合理的であること（$n$ と $v$ に応じて数秒から数分）を示している。
• ISDの呼び出し回数： 主要な知見は、ステップあたりの平均ISD呼び出し回数が極めて1に近く（しばしば正確に1である）、これは理論的条件 $m_v^{(r)} \gg 1$ がアルゴリズムが停滞することを稀にしていることを裏付けている。
• 列分布： 論文は、得られた行列が予測可能な列重み分布を持つことを検証しており、これにより、自己直交性を壊すことなく「不運な」列（例：零列や重み1の列）を除去するためのパンクチャリングが可能であることを示している。

一般化
論文では、以下の拡張についても述べている：

• 非バイナリ体： アルゴリズムは、ISDを修正し、自己直交条件（体の標数が2でない場合は棄却サンプリングが必要）を扱うことで、$\mathbb{F}_q$ へ適応させることができる。
• 一般的なスタビライザー符号： この手法は、シンプレクティック積条件 $a_i b_j^\top + b_i a_j^\top = 0$ を満たすベクトルのペア $(a_i, b_i)$ を反復的にサンプリングすることで、CSS符号に限らない一般的な量子スタビライザー符号をサンプリングできる。

意義および主張
本論文は、ランダムな量子LDPC符号を効率的に生成できるかという問いに対し、肯定的な回答を提供していると主張している。

• 組合せ論的 vs 代数的： 既存の手法とは異なり、このアプローチは代数的構造（準巡回性など）に依存しないため、疎性と直交性にのみ制約を受ける、可能な限りランダムに近い符号をサンプリングできる。
• 計算量に関する控えめな主張： 著者らは、多項式時間の厳密な証明を主張することについては慎重である。彼らは、計算量の解析が、標準的なランダムコードの仮定とは異なる、疎な行列に対するISDの性能に関するヒューリスティクスに基づいていることを明示している。数値シミュレーションは多項式時間の挙動を強く示唆しているものの、厳密な理論的証明は依然として未解決の課題であると認めている。
• 今後の展望： 著者らは、効率性をさらに向上させ、厳密な計算量境界に関する未解決の課題に対処するために、LDPC符号に特化したISDアルゴリズムの設計が有望な方向性であると特定している。

総括すると、本論文は、古典的なLDPC符号生成の容易さと量子符号の構造的制約との間の溝を埋める、新しい組合せ論的なサンプリング手法を提示しており、ランダムな量子LDPC符号がISDベースのサンプリングを通じて到達可能であることを示している。