Evolutionary Discovery of Bivariate Bicycle Codes with LLM-Guided Search

本論文は、Pythonプログラムを突然変異させ、多段階のパイプラインを通じて候補を厳密に検証することで、非分解型や高距離型のバリアントを含む465種類の異なるコードを生成し、高性能な二変量バイシクル量子LDPC符号の発見に成功した、LLM誘導型の進化ワークフローを提示するものである。

要約

あなたは、完璧なデジタル金庫の「鍵」を作ろうとしていると想像してください。量子コンピューティングの世界では、この「鍵」は量子誤り訂正符号と呼ばれます。その役割は、ノイズやエラーから脆弱な量子情報を守ることです。鍵が優れていれば優れているほど、より多くのデータを保存でき（高い「レート」）、破壊される前の耐性が高くなります（高い「距離」）。

長い間、科学者たちはこれらの鍵の最適な設計、具体的には二変量バイシクル（Bivariate Bicycle, BB）符号と呼ばれるタイプの設計を見つけようとしてきました。これらは複雑な数学的設計図のようなものです。問題は、可能な設計図の数が膨大すぎて、それは地球上のあらゆるビーチにある特定の砂粒を探すようなものであり、さらに、ある設計図が機能するかどうかを確認する作業は非常に遅く、困難であるということです。

この論文は、**人工知能（具体的には大規模言語モデル、LLM）**を「進化のガイド」として用いて、これらの設計図を見つける新しい方法について記述しています。

以下に、彼らの発見の物語をシンプルな概念に分解して説明します。

1. 「進化型」検索エンジン

人間が完璧な設計図を推測する代わりに、研究者たちは自然界の進化を模倣したシステムを構築しました。

• 「生物」: 単一の符号を進化させるのではなく、符号を生成するPythonコンピュータプログラム（レシピ）を進化させました。
• 「突然変異」: AI（LLLLM）が現行の最良のレシピを観察し、「この数字を変える」や「新しいステップを追加する」といった小さな変更を提案します。
• 「適者生存」: システムは数千の新しいレシピを生成します。それらが有効な符号を生成するかどうかを迅速にテストします。優れたレシピは再び突然変異するために生き残り、劣ったものは破棄されます。

5つの「キャンペーン」（探索ラウンド）にわたって、このAI駆動型システムは約1,650世代を実行し、約20万個の候補となる符号をスクリーニングしました。プロセス全体にかかった費用は約400ドルで、時間は約140時間でした。

2. 「罠」と「審判」

探索の初期段階で、AIはある巧妙な罠に陥りました。AIは、データ保存量（レート）が非常に多いレシピを見つけ出し、それは素晴らしく見えました。しかし、これらの符号は実際には全く役に立たないものでした。なぜなら、エラーを訂正する能力がゼロ（距離 = 2）だったからです。それは、まるでペーパークリップで開けられる金庫の扉を見つけたようなものです。多くの物を収納できますが、安全性はありません。

研究者たちは、初期の「距離チェッカー」（BP-OSDと呼ばれる標準的なツール）が嘘をついていることに気づきました。それは、これらの符号の強さを、時には12倍も過大評価していました。

これを修正するために、彼らはプロセスに厳格な**審判（MILP）**を追加しました。

• 審判の仕事: これは、符号の距離を100%の確実さでチェックする強力な数学的ソルバーです。
• 結果: 審判は「罠」を即座に捉えました。また、AIが強力だと考えていた多くの符号が、実は脆弱であることを明らかにしました。これにより、AIは「偽の」高性能な符号への探索を止め、真に強力なものを見つけ出すことを余儀なくされました。

3. 発見

プロセスを洗練させた後、システムは465個の明確で高品質な符号を発見しました。ハイライトは以下の通りです。

• 「ゴールドスタンダード」との一致: 彼らは、現在の最高水準の符号（「グロス符号」）の性能に匹つする、新しいタイプの符号（「摂動を加えた二変量バイシクル符号」）を発見しました。これは、より複雑な構造を用いています。それは、市場で最高の車と同じ燃費を実現する、新しい種類のエンジン設計を見つけるようなものです。
• より多くのデータ、同じ保護: 彼らは、適切なレベルの保護を維持しながら、従来の記録よりも多くのデータ（最大54論理量子ビット）を保存できる符号を発見しました。
• 「分解可能」な発見: システムはある種の超高度な鍵に見える符号を発見しました。しかし、審判によるグラフ解析の結果、それは実際には2つの普通の鍵を接着しただけのものであることが判明しました。それは新しい発明ではなく、既存のものが2つ並んでいるだけでした。これは、システムが「偽の」複雑性を見抜く能力を持っていることを示しました。

4. 「レート vs 距離」のトレードオフ

研究者たちは、これらすべての符号の景観をマッピングし、これらの鍵に関する物理法則のような一貫したルールを見出しました。

• 「エンベロープ（包絡線）」: 一般的に、膨大な量のデータを保存しつつ、同時に極めてタフな鍵を持つことはできません。
• 「曲線」: もしより多くのデータを保存したい（高いレート）のであれば、鍵は壊れやすくなります（低い距離）。もし超強力な鍵が欲しいのであれば、保存できるデータ量は少なくなります。
• 例外: 彼らはこの曲線の限界を押し広げる符号（例えば、50のデータユニットと距離8を持つ符号）を見つけましたが、それでもこのトレードオフの根本的な「エンベロープ」を打破することはできませんでした。

5. ななぜこれが重要なのか

本論文は、AIを使用してコンピュータプログラムを進化させることが、新しい量子符号を発見するための実用的で低コストなツールであることを結論づけています。

• それは、人間や従来の数学的探索が見逃していた符号を発見しました。
• 標準的なテストツールが高性能な符号に対して危険なほど不正確であり、厳格な「審判（MILP）」が必要であることを証明しました。
• AIが「罠」を回避し、異なるサイズの量子コンピュータ全般に適用できる複雑な代数的パターンを発見できることを示しました。

要約すると、研究者たちはAIを用いて「符号生成器」を進化させ、偽の結果を無視するように教え、以前のどのものよりも強く、効率的、あるいは単に異なる新しいタイプの量子的な鍵を発見することに成功したのです。

技術概要

技術要約：LLM誘導型探索による二変量バイシクル符号の進化的発見

問題定義

量子低密度パリティ検査（qLDPC）符号、特に二変量バイシクル（BB）符号の発見には、良好なレート–距離–閾値のトレードオフを持つ符号を見つけるために、膨大な組合せデザイン空間をナビゲートする必要がある。BB符号は、近未来のハードウェアに適した重み6のスタビライザーと定数深さのシンドローム抽出を提供するが、実用的なブロック長（$n \lesssim 1000$）における高性能な符号の景観は、依然として大部分が未探索である。既存の系統的な列挙は、特定の多項式形式や小さなブロック長に制限されていることが多く、探索空間には連続的な最適化に適した勾配構造が欠けている。さらに、候補となる符号のパラメータ（特に最小距離 $d$）を確実に検証することは計算量的に困難である。標準的なヒューリスティック手法であるBelief Propagation（BP）とOrdered Statistics Decoding（OSD）の組み合わせ（BP-OSD）は、高レートの符号において距離を系統的に過大評価することが示されており、進化的な探索において信頼性の低いフィットネス信号をもたらす。

手法

著者らは、量子符号を生成および検証するために設計された、LLM誘導型の進化的ワークフローを導入する。個々の符号パラメータを進化させるのではなく、システムは任意の格子次元に対して候補となる多項式ペア（非CSS符号の場合は4つ組）を生成するジェネレータ・アンサンブル（生成器の雛形）、すなわちPythonプログラムを進化させる。

進化的フレームワーク

• アルゴリズム: システムは、MAP-Elitesアルゴリズムの実装であるOpenEvolveを利用し、LLMにコードジェネレータの変異を誘導させる。
• 変異戦略: LLMは、現在の最高フィットネスを持つアンサンブル、ドメイン知識、および評価フィードバックを受け取り、完全な書き換えではなく、ターゲットを絞ったコードの差分（例：指数の調整、制御フローの再構成）を提案する。
• 集団: 探索は複数の「アイランド（島）」に分散され、多様性を維持するために定期的なマイグレーション（移動）が行われる。アーカイブは、有効な符号を生み出す格子の数や、高品質な符号の総数といった行動次元に基づいてアンサンブルをインデックス化する。

多段階検証パイプライン

ヒューリスティックな距離推定の不確実性を軽減するため、著者らは多段階のカスケードを採用している：

1. ステージ1（スクリーニング）: 小さな格子上での迅速な評価を行い、$\text{GF}(2)$ のランクを通じて符号化次元 $k$ を計算する。有効な符号を生成できないアンサンブルは破棄される。
2. ステージ2（ヒューリスティック推定）: 生き残ったアンサンブルは、より大きな格子上で複数のデコーダ構成（OSD0, OSD-CS10）を用いたBP-OSDによって評価され、距離 $d$ を推定される。
3. ステージ3（厳密な検証）: トップの候補（および後半のキャンペーンにおけるインループでの検証）に対して、**混合整数線形計画法（MILP）**を用いて、正確な距離または厳密な上限値を計算する。このステージは、BP-OSDで観察された系統的な過大評価を修正するために極めて重要である。
4. ポストキャンペーン分析: パミュテーション等価な符号を特定するためのBLISSベースのタンナーグラフ重複排除、分解可能性の分析（直和の検出）、および非CSS符号に対するローカル・クリフォード（LC）等価性チェックが含まれる。

コードファミリー

• CSS BB符号: $\mathbb{F}_2[x,y]/(x^\ell-1, y^m-1)$ 上の2つの三項式 $A, B$ によって定義される。
• 摂動を加えたBB（PBB）符号: 非CSS構造を可能にする混合スタビライザーを作成するために、摂動多項式 $C, D$ を導入した非CSSアンサンブル。

主な貢献

1. 465個の異なる符号の発見

5回の進化的キャンペーンを通じて、システムはブロック長 $n \le 360$ において465個の異なる符号を発見した：

• 97個のCSS符号: 97個の異なる代表元（再発見を含む99個の等価類）を含む。注目すべき発見は以下の通り：
  • [[288, 16, 12]] 符号：$d=12$（厳密）かつ全てのシフトが $\le 3$ である、非分解のCSS符号。
  • 高次重みの符号：新しい $(k, d)$ 組み合わせを実現する重み8の符号、例えば [[288, 50, 8]] ($k=50, d=8$) など。
  • 既知の高パフォーマンス符号（例：「gross code」[[144, 12, 12]]）の回収、および新しい有限長代表元の特定。
• 368個の非CSS PBB符号: 混合スタビライザーを使用する符号。探索により、gross codeのFigure of Merit (FOM) と一致する [[144, 12, 12]] PBB符号、および信頼できるFOM上限が19.2である [[360, 12, $\le$24]] 符号が見つかった。

2. 検証における手法的進展

• BP-OSDによる過大評価: 本研究は、BP-OSDが高レートの符号（$k/n > 0.1$）において距離を系統的に過大評価し、その誤差が最大 12倍 に達することを定量化している。例えば、[[360, 40, 2]] 符号はBP-OSDによって $d \le 24$ と推定されたが、MILPは $d=2$ であることを確認した。
• 達成可能シンドローム・サンプリング: 非CSS符号の場合、達成可能な論理余剰（logical coset）は厳密な部分空間を形成するため、標準的なランダム・シンドローム・サンプリングは失敗する。著者らは、達成可能な部分空間のみからサンプリングする方法を導入し、BP-OSDの機能を回復させた。
• MILPによるグラウンドトゥルース: MILPを用いた検証基準は、多くの高$k$候補が実際には低距離であったり、分解可能であったりすること（例：[[288, 24, 12]] 符号は2つのgross codeの直和であることが特定された）を明らかにした。

3. BB景観の構造的特性

著者らは、異なるレート–距離プロファイルを持つ4つの代数的ファミリーを特定している：

• 単変量/HGP: 巡回符号のハイパーグラフ積に相当する符号。これらは最高の符号化次元（$k \propto \ell$）を達成するが、距離の天井（$d \le 4$）に苦しむ。
• x/y-swap: 多項式に混合変数を持つ符号。$d \ge 12$ を達成するが、非分解なものについては $k \le 16$ に制限される。
• 混合単項式/高次重み: 4〜6項の多項式を持つ符号であり、新しい $(k, d)$ 点（例：$d=8$ で $k=50$）にアクセスできるが、全体的なレート–距離の包絡線（envelope）を突破することはない。
• 非CSS PBB: $n=144$ における最良のCSS符号のFOMに一致するが、それを超えることはない。

4. 実証的なレート–距離・トレードオフ

探索は一貫した実証的トレードオフを示している：高い符号化レートは一般に低い距離を伴う。

• $d=12$ を持つ非分解の重み6の符号は、$k \le 16$ に制限される。
• $k > 24$ を持つ重み6の符号は、一様に $d \le 4$ となる。
• 高次重みの符号（重み8）は、中程度の $d$ においてより高い $k$（例：$d=8$ で $k=50$）にアクセスできるが、観察された包絡線を打破することはない。

結果と意義

主要な知見

• LLMの有効性: LLM誘導型の進化は、格子次元を超えて汎用化可能な代数的パターン（例：単変量構造、x/y-swap）の発見に成功し、ランダム探索や標準的な遺伝的アルゴリズムよりも、 $d \ge 6$ を持つ高FOM符号の発見において優れていた。
• 検証の必要性: 本研究は、ヒューリスティックな距離推定が高レートの符号発見において不十分であることを証明している。「$A = B$ の距離トラップ」（$A=B$ のとき $d=2$ となる現象）は、$1.5 \times 10^6$ 回の試行を行ってもBP-OSDでは検出できなかったが、MILPパイプラインでは即座に特定された。
• ハードウェアへの関連性: 発見された符号（例：[[288, 16, 12]]）は、gross codeと同等の擬似閾値を維持しつつ、より多くの論理量子ビット（最大1.7倍）を提供できる。非CSS PBB符号は、特定のノイズモデル（Xのみのノイズ）の下でエラー抑制を改善する可能性を示しているが、標準的なデコーダを用いたデポラリゼーションノイズ下ではその利点は減少する。

意義

本論文は、厳密な多段階独立検証（特にMILP）と組み合わせたLLM誘導型プログラム進化が、構造化された量子符号発見のための実用的かつ費用対効果の高いツールとして機能することを主張している。総計算コストが約 400ドル かつ140時間であることは、このアプローチの実現可能性を示している。

本研究は、高レートのBB符号の主張に対する新しい検証基準を確立し、ヒューリスティックな推定と厳密な距離との間の決定的なギャップを浮き彫りにした。これは、量子符号の組合せ空間を探索するための再利用可能なフレームワークを提供しており、レート–距離の包絡線は堅牢であるものの、構造化された探索によってその中の新しい高性能な代表元を見つけ出せることを明らかにしている。著者らは、この包絡線を脱出するには、二変量バイシクル・ファミリーを超えた、より複雑な代数的構造への移行が必要であると述べている。