Building codes with transversal CCZ using projective geometry and SAT solvers

技術要約：射影幾何学とSATソルバを用いた横断的CCZを持つ符号の構築

問題提起
フォールトトレラント量子計算には、非クリフォード論理ゲートの実装が必要である。標準的な手法である魔法状態蒸留（magic-state distillation）は、膨大な時空オーバーヘッドを伴う。横断的ゲート構成は、物理的な位相回転（具体的には $T$ および $T^\dagger$ ゲート）が所望の論理対角ゲートを直接実装するように量子誤り訂正符号を設計することで、これに代わる選択肢を提供する。本研究は、特定の $Z$ 距離（$d_Z \ge 3$）および、対角クリフォード補正が論理ゲートを実現するために必要十分であるキャンベル・ハワード（Campbell–Howard, CH）条件を満たす、3つの論理量子ビット（$k=3$）を持つCSS符号の構築に焦点を当てている。

手法
著者らは、古典的な符号理論、有限幾何学、およびブール充足可能性（SAT）ソルバを組み合わせたハイブリッドなアプローチを採用している。

1. 幾何学的構成によるスタビライザー:
   著者らは、射影幾何学を用いて $X$ スタビライザー符号 $C_2$ を構築する。具体的には、バイナリ射影幾何 $PG(s-1, 2)$ から導出された**部分空間補集合符号（subspace-complement codes）**を利用する。全射影空間から $p$ 次元の部分空間を取り除くことで、8-divisible な符号を形成する点の集合を生成する。この8-divisibilityは、スタビライザーの行がCH条件のスタビライザーのみの部分（条件S1–S3）を満たすことを保証し、コードが射影的であることを保証することで、$Z$ 距離が少なくとも3（$d_Z \ge 3$）であることを保証する。

2. 論理演算子のためのSATベースの探索:
   幾何学的構成によってスタビライザー行列 $S$ が固定された状態で、互換性のある論理 $X$ 生成元（$K$）を見つける問題は、ブール充足可能性（SAT）問題としてエンコードされる。CH条件は、生成行列 $G = [K; S]$ の行の重なりに対するパリティ制約を課す。

• 探索は、残りのCH条件（K1–K3 および KS1–KS3）を満たす3つの論理行（$k=3$）を対象とする。
• エンコーディングには、生成行列のサポートを表現するために**列インジケケータ多項式（column indicator polynomials）**を使用する。
• 固定されたサポート $S$ に対して、パリティ制約が満たされるように、論理ラベル写像 $\kappa$（各スタビライザー列に論理ラベルを割り当てるもの）を解く。

3. 横断的実装の検証:
   CH条件を満たすことは、ある対角クリフォード補正 $C$ が存在し、それが横断的 $T$ ゲートと組み合わさることで論理CCZを実現することを保証する。単一量子ビット横断的実装（$C$ が自明であるか、あるいは実質的に $T$ と $T^\dagger$ のパターンである $S^\dagger$ ゲートのみで構成されるもの）を実現するために、著者らは $\mathbb{Z}_4$ 上の線形系を解く。この系は、どの量子ビットが $T$ の代わりに $T^\dagger$ を受けるかを指定する「反転ベクトル（flip vector）」$\gamma$ を決定する。

主な貢献と結果

• $Q_{48}$ 符号の構築:
  著者らは、以下の特性を持つ新しいCSS符号 $Q_{48}$（または $[[48, 3, 3]]$）の構築に成功した。

  • スタビライザー: $PG(5, 2)$ における4次元部分空間の補集合からなる、一意な射影8-divisible $[48, 6]$ コード（$FG_{48}$）から導出。
  • 論理量子ビット: SATソルバにより発見された3つの論理量子ビット。
  • ゲート実装: 論理CCZは、26個の $T$ ゲートと22個の $T^\dagger$ ゲートの横断的パターンによって実装される。
  • 距離: $d_Z = 3$ および $d_X = 16$。

• 符号の族:
  パラメータ $(p, q)$（ここで $s=p+q \le 9$）を変化させた部分空間補集合構成を用いることで、横断的CCZ実装を持つCSS符号の族を特定した。これらには、ブロック長 $n = 48, 64, 96, 112, 128, 192, 224, 240, 256, 384, 448, 480, 496$ を持つコードが含まれる。論文の表3は、各パラメータセットに対して見出された不等価な符号の数をリストしている。

• 符号長の低界:
  著者らは、このような符号のブロック長に関する厳密な下界を証明している。

  • 定理: $k=3, d_Z \ge 3$ であり、かつ9つのCH条件を満たすCSS符号は、ブロック長 $n \le 38$ では存在しない。
  • 手法: Reed–Muller符号の重み列挙関数を用いて可能なスタビライザーサポートを制限し、$n \le 38$ において、それらのサポート上で論理ラベル写像がCH条件を満たすことができないことを示した。
  • ギャップ: $39 \le n \le 46$ の範囲における存在は未解決の問題である。既知の $J_{47, 3, 3}$ 符号（Jacintoらによる）はCH条件を満たしているが、単一量子ビット横断的テストに失敗している（補正のために絡み合いCZゲートを必要とする）。

意義
本論文は、非クリフォード論理ゲートを横断的に実装できる小さなCSS符号を構築するための体系的な手法を提供しており、これにより魔法状態蒸留に伴うオーバーヘッドを削減する。

• 最適性: $Q_{48}$ 符号は、3つの論理量子ビット、$d_Z \ge 3$、および単一量子ビット横断的CCZ実装を持つ既知の最小のCSS符号である。$39 \le n \le 46$ の範囲にそのような符号が存在するかどうかは依然として未解決の問題であり、$Q_{48}$ は最小の既知の例であるが、絶対的な最小長が48であることはまだ証明されていない。
• 理論的境界: $n < 39$ ではそのような符号が存在しないという証明は、このクラスの符号に対する基礎的な限界を確立し、将来の構成に向けた探索空間を狭めている。
• 手法的な進展: 本研究は、幾何学的符号構成（距離とスタビライザーの特性を固定する）と、SATソルバ（互換性のある論理演算子を効率的に探索する）を組み合わせることが、複雑な符号設計問題の解決にいかに有効であるかを示している。

著者らは、$J_{47, 3, 3}$ 符号が最小長の暫定的な上限となる一方で、39から46の間のギャップは未解決であり、$n \ge 48$ における部分空間補集合サポートの特性付けもまだ完了していないことを注記している。