Finding diagonal logical gates in CSS codes and circuits

技術要約：CSS符号および回路における対角論理ゲートの探索

問題提起
大規模でフォールトトレラントなユニバーサル量子コンピュータの実現には、非クリフォード論理ゲートの効率的な実装が必要である。クリフォード演算はスタビライザー形式において比較的容易であるが、非クリフォードゲートは大きな課題を突きつけている。現在のアプローチは、魔法状態蒸留（magic state distillation）、横断的（transversal）な非クリフォードゲート（時にコードスイッチングと組み合わせたもの）、あるいはシンドローム抽出回路内に挿入される「時空」論理ゲートに依存していることが多い。中心となる課題は、規定された物理アンザッツゲートの集合から構成される、効率的で局所性を保存する対角非クリフォード論理ゲート（$T$, $CS$, または$CCZ$ など）を、どのCSS（Calderbank-Shor-Steane）符号または回路が許容するかを特定することである。三直交性（triorthogonality）条件などの既存の手法は、特定のゲートタイプに限定されていたり、任意の局所性保存回路に対する汎用性に欠けたりすることが多い。

手法
本論文は、与えられたCSS符号（または回路）において、規定された対角アンザッツゲートから構成されるすべての論理ゲートを見つけるための効率的なアルゴリズムを提案する。その中核となる理論的洞察は、「対角論理ゲートが符号空間を保存するための必要十分条件は、与えられたコホモロジー類内のすべての$Z$基底構成に対して同じ位相を割り当てることである」という点にある。

1. 数学的定式化:

   • 対角ゲート $V_c$ の計算基底状態 $|a\rangle$ への作用は、位相関数 $S_c(a)$ によって定義される。クリフォード階層の第3レベルのゲートの場合、$S_c(a)$ は $a_i a_j a_k$（$CCZ$の場合）、$a_i a_j$（$CS$の場合）、$a_i$（$T$の場合）のような項を含む「3次」の関数となる。
   • 符号空間保存の条件は、$S_c(a)$ が同じコホモロジー類内のすべての $a$ に対して定数であることである。これは、$S_c(a + A e_j) = S_c(a)$ がすべての $X$ スタビライザー生成元 $A e_j$ に対して成り立つこと（ここで $A$ は $X$ チェック行列である）という要求に帰着する。
   • この条件は、位相関数による $X$ チェックの「プルバック（pullback）」、$S_c \circ A$ が自明な位相関数を与えることと等価である。

2. プルバック準同型 ($A^*$):

   • 著者らは、物理アンザッツゲートの係数（$c \in G_{phys}$）を、誘導される $X$ チェック上の位相関数の係数へと写像する群準同型 $A^*$ を定義する。
   • $G_{phys}$ は、クリフォード階層の異なるレベルに対応する有限アーベル2群（例：$\mathbb{Z}_2, \mathbb{Z}_4, \mathbb{Z}_8$）の直積である。
   • 有効な論理ゲートの集合は、この準同型 $A^*$ の**核（kernel）**に正確に一致する：$A^* c = 0$。

3. アルゴリズムの実装（フィルタリング）:

   • $A^*$ の核を効率的に計算するために、著者らは「フィルタリング」手法を導入する。スミス標準形（Smith normal form）を用いる代わりに（これは大きな整数演算を伴う）、問題をバイナリ体（$\mathbb{Z}_2$）上の連続的な核計算へと分解する。
   • アルゴリズムは、$X \pmod 2$、$X \pmod 4$ などの核を逐次的に計算し、低次の群から高次の群へと解をリフトアップしていく。これは、$\ker(X) \subset \ker(X \pmod 4) \subset \ker(X \pmod 2)$ という性質を利用している。
   • これらのサブルーチンは、ビットパッキングによって加速可能な標準的なバイナリ線形代数（ガウス消去法/簡約段階段形 RREF）に依拠している。

4. 一般化:

   • 時空ゲート: 本手法は、シンドローム抽出回路内に対角ゲートが挿入される「時空局所論理ゲート」へと拡張される。これは、回路をテンソルネットワーク（または経路積分）として扱い、同様のプルバック論理を $Z$ デコーディンググラフに適用することでモデル化される。
   • 高次レベルおよび任意のゲート: 本フレームワークは、位相関数の定義および係数群を調整することで、クリフォード階層のより高いレベルや、任意の対角ゲート（非階層的ゲート）へと一般化される。
   • Qudit（高次元量子ビット）: $\mathbb{Z}_{d_i}$ 上の高次関数を定義することにより、素数および合成数次元のクディットへと一般化されている。

主要な貢献

• 統一されたフレームワーク: 本論文は、横断的ゲート、局所性を保存する論理回路、および時空論理ゲートの探索を、特定の群準同型 $A^*$ の核を見つけるという単一の代数的条件の下に統一する一般的な形式を提供している。
• 効率的なアルゴリズム: $O(n)$ 個の量子ビット（またはゲート）を持つシステムに対して、ナイーブな計算量が $O(n^3)$ である効率的なアルゴリズムを提示しており、フィルタリング技術を用いて問題をバイナリ行列演算へと還元している。
• 柔軟性: ユーザーは任意のアンザッツゲートの集合（非局所的または折り畳まれたゲートを含む）を指定でき、並進不変性を課すことなく、結果として得られるすべての論理ゲートを見つけることができる。
• 実装: 特殊なパッケージ（twogroup-linalg）を含むPython実装が提供されており、これはアーベル2群上の線形代数に特化したものである。

結果と例

• アルゴリズムは、2Dおよび3Dトーリック符号、カラー符号、フラクトン符号、およびバイバリエイト・バイシクル（bivariate bicycle）符号における既知の論理ゲートを正常に回収した。
• 「デュアル3Dカラー符号」において、論理 $T$ ゲートと同等な第3次の対角ゲートを新たに発見した。
• 本手法は、システムサイズに対して $O(1)$ の時間（単位セルのパラメータにのみ依存）で、並進不変な論理ゲートを見つけられることを示した。
• 800量子ビットを持つ2Dカラー符号の実行時間は、標準的なノートPC上で約30秒であった（非並進不変の場合）。

意義と主張
本論文は、その手法がCSS符号および回路におけるフォールトトレラントな論理ゲートを探索するための、系統的かつ効率的な方法を提供すると主張している。問題を核の計算へと再定式化することで、三直交性条件を、クリフォード階層の任意の積および局所性を保存する回路へと一般化している。

著者らは、本手法は任意の対角ゲートを見つけることができるものの、フォールトトレラントな設定における物理的な実現可能性は、おそらくこれらのゲートをクリフォード階層内に制限する（Bravyi-Koenig型の議論と一致する）旨を述べている。本研究は、このアプローチが望ましい論理ゲート特性を持つ新しいqLDPC符号の発見や、論理ゲートのコード境界やドメインウォールへの拡張の最適化に使用できる可能性を示唆している。著者らは、将来的な高速化に関するトーンについては控えめな姿勢を維持しており、qLDPC符号の疎性がさらなる最適化（Wiedemannのアルゴリズムや局所的な核分解などによる）の可能性を提供していることを認めつつも、現在の $O(n^3)$ の密な実装が、符号の論理基底を見つけること自体と比較しても十分に競争力があることを示している。