Sequences of Bivariate Bicycle Codes from Covering Graphs

技術要約：被覆グラフからの二変量バイシクル符号の列

問題提起
量子低密度パリティ検査（qLDPC）符号は、表面符号に代わる有望な選択肢であり、定数レートと改善された距離のスケーリングを提供し、フォールトトレラント量子計算に必要な空間オーバーヘッドを削減できる可能性がある。しかし、高パフォーマンスなqLDPC符号の新たな特定は、可能なパリティ検査多項式の膨大な探索空間のため、依然として課題となっている。具体的には、二変量バイシクル（BB）符号（$\mathbb{F}_2[Z_l \times Z_m]$上の群環符号）は、高レート・高距離のインスタンス（例：[[144, 12, 12]] "gross" 符号）を示しているが、予測可能なパラメータを持つ無限の符号族を生成するための一般的な手法は限られている。さらに、異なる符号インスタンス間での論理演算子と自己同型の関係を理解することは、論理操作の実装において極めて重要であるが、大規模な符号に対しては分析が困難であることが多い。

手法
著者らは、被覆グラフ（またはグラフのリフト）という数学的概念を用いて、BB符号の無限列を生成するためのフレームワークを提案している。核心となる手法は以下の通りである：

1. 被覆のための代数的条件： 本論文は、BB符号 $\tilde{Q}$ のタナーグラフが、ベースとなるBB符号 $Q$ の被覆グラフであるための特定の代数的条件が満たされる場合、その条件を確立している。具体的には、$Q$ がパラメータ $(l, m)$ と多項式 $A, B$ を持ち、被覆符号 $\tilde{Q}$ がパラメータ $(\tilde{l}, \tilde{m})$ と多項式 $\tilde{A}, \tilde{B}$ を持つとき、$\tilde{Q}$ が有効な $h$-被覆（ここで $h = \tilde{l}\tilde{m}/lm$）であるための条件は以下の通りである：

   • $\tilde{l} = ul$ かつ $\tilde{m} = tm$ （$u, t$ は整数）。
   • $\tilde{A}$ および $\tilde{B}$ における単項式の指数が、それぞれ $l$ および $m$ を法として $A$ および $B$ の指数と合同であること。
   • 派生グラフを生成するために使用される電圧割り当て（voltage assignment）が、格子パラメータの「商」に対応していること。

2. 探索空間の縮小： これらの合同条件を満たす多項式に探索を限定することで、著者らは新しい符号の探索空間を劇的に削減している。長さ $n$ の全多項式の空間を探索する代わりに、ベースとなる符号の多項式のバリエーションに制限されるため、複雑性は $O(n^6)$ から $h$-被覆に対しておよそ $O(h^4)$ へと減少する。

3. 鎖写像（Chain Maps）とホモロジー： グラフ被覆写像は、ベースとなる符号と被覆符号の鎖複体（chain complexes）間の鎖写像へと拡張される。これは（余）ホモロジーへの写像を誘導する：

   • 射影写像 ($p$): 被覆符号からベースとなる符号へ論理演算子を写す。
   • 持ち上げ写像 ($\tau$): ベースとなる符号から被覆符号へ論理演算子を写す。
   • 重さ保存持ち上げ ($\sigma$): 各頂点の単一の前像を選択する特定の種類の持ち上げであり、被覆符号の距離の上限を定めるために用いられる。

4. 自己同型の持ち上げ： 本フレームワークは、グラフの自己同型（およびそれに伴うCSS符号の自己同型）が、ベースから被覆へと持ち上げられることを示すように拡張されている。特定の条件（奇数の $h$ および等しい論理量子数）の下では、これらの自己同型の論理的な作用が保持される。

主要な貢献と結果

• 符号列の生成： 著者らは、既知の高パフォーマンスなBB符号（例：[[144, 12, 12]] gross 符号）が、より小さな符号（例：[[72, 12, 6]]）の二重被覆として見ることができることを示している。彼らは、固定された論理量子数 ($k$) と増加するブロックサイズ ($n$) を持つ、新しいBB符号の無限列を生成している。
• 新しい符号族：
  • 重み6の符号： この手法は、バランス・プロダクト符号や一般化されたトーリック符号を含む既知のファミリーを再現し、さらに $k=6, 8, 10, 12$ の新しい列を生成する。
  • 重み8の符号： 著者らは、重み8のチェック（定義多項式における4つの項）を持つBB符号を探索するためにこの手法を適用した。その結果、$k=8, 10, 12, 14$ のシーケンスを発見し、それらは重み6の対応物よりも有意に高い $kd^2/n$ 比を示している。注目すべき例として、[[64, 14, 8]] および [[144, 14, 14]] 符号がある。
  • クディット符号： 本手法は $\mathbb{F}_q$ 上のクディット符号へと一般化され、ベースとなるクディットBB符号の被覆符号の生成に成功している。
• 理論的境界：
  • 論理量子数 ($k$): 著者らは、$h$ が奇数である $h$-被覆符号について、論理量子数が $k_h \ge k$ を満たすことを証明している。彼らはこれがすべての $h$ に対して成立すると予想している。
  • 距離 ($d$): $h$ が奇数の場合、$d_h \le hd$ であることを証明している。また、$k_h = k$ かつ $h$ が奇数である場合、$d_h \ge d$ であることを証明している。彼らは、$d \le d_h \le hd$ という一般的な境界がすべての $h$ に対して成立するという予想を立てている。
  • 重さ保存持ち上げ： 重さ保存持ち上げが存在する場合、$d_h \le d$ であることが示される。これは、距離が増加しない被覆符号を排除するための数値的なツールとなる。
• 論理演算子と自己同型の分析： 本論文は、論理演算子と自己同型を持ち上げるための明示的な構成を提供している。$h$ が奇数で $k_h = k$ であるとき、持ち上げ写像がホモロジーにおける同型写像となり、ベースとなる符号の論理基底が被覆符号の完全な論理基底へと持ち上げられ、自己同型（例：論理CNOTおよびアダマールゲート）の論理的作用が保持されることを証明している。

意義

著者らは、本研究の意義は以下の3つの領域にあると主張している：

1. 効率的な符号発見： 被覆グラフ理論に基づく縮小された探索空間を特定することで、著者らは、全多項式空間に対するブルートフォース探索を回避し、有望なパラメータを持つ新しいBB符号を発見するための系統的かつ効率的な手法を提供している。
2. 理論的統一： 本研究は、既知の様々なBB符号の構成（gross 符号、バランス・プロダクト符号、一般化されたトーリック符号を含む）を、被覆グラフという単一のフレームワークの下に統合し、それらの構造的関係を明らかにしている。
3. 論理演算子の管理： 射影および持ち上げ写像の開発は、大規模な符号を分析するための実用的なツールを提供する。ベースとなる、より小規模でよく理解された符号から論理演算子と自己同型を導出することで、大規模なqLDPC符号における論理操作の管理の複雑さが軽減される。

著者らは、焦点はBB符号に置かれているものの、手法は他の群環符号や、ハイパーグラフまたはリフト積を含む構成にも一般化できると述べている。また、探索空間は縮小されているものの、大きな被覆符号の正確な距離を計算することは依然としてボトルネックであり、彼らの理論的境界は完全な解決策ではなく、あくまでガイドとして機能するものであることも強調している。